Direct sampling of discrete random structures with algebraic dependencies

具有代数依赖性的离散随机结构的直接采样

基本信息

批准号：
20K03742
负责人：
間野修平
金额：
$ 2万
依托单位：
The Institute of Statistical Mathematics
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2020
资助国家：
日本
起止时间：
2020-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

データ解析のあらゆる分野においてサンプリングのアルゴリズムは必須である。近似的なサンプリングが使われることが多いので、近似ではないサンプリングを敢えてダイレクトサンプリングと呼ぶ。代表者はGelfandらが定義したGKZ超幾何系(A超幾何系)が定める離散確率分布族について計算代数を用いたダイレクトサンプリングのアルゴリズムを考案した。本研究は、付随する計算の効率化を図り、より一般的な代数的従属性をもつ離散確率構造のサンプリングに展開することを目的としている。令和4年度の研究実績として、より一般的な代数的従属性をもつ離散確率構造への展開（交付申請書研究方法２）について、量子計算の周辺にいくつかの課題を見出した。量子超越（何らかのタスクについて何らかの基準の下で古典計算が量子計算を優越すること）の実証は、ランダムに生成した量子回路の出力を古典計算機で生成するタスクについて行われており、その理由は分布函数の計算が計算複雑性の意味で難しいことに依拠する。ベイズ的手法を用いることで従来考えられているものとは異なる効率の高い古典計算のアルゴリズムを得た。この成果は研究集会で発表し、論文を作成中である。また、派生的ではあるが、本研究の発端になったDirichlet過程に関連するサンプリングの周辺に成果を得た。Dirichlet過程を定常分布とする拡散過程を有限グラフ上の測度に値をとる拡散過程として一般化し、双対なマルコフ過程を導出した。完全グラフの場合はDirichlet過程に関連する新しい漸化式を与える。応用として、グラフの独立集合を発見するアルゴリズムが要する時間の評価と、グラフに値をとる標本の尤度を計算するアルゴリズムを導出し、論文を発表した。

采样算法在数据分析的所有领域都至关重要。通常使用近似采样，因此非近似采样特意称为直接采样。该代表针对Gelfand等人定义的GKZ超几何系统（A hypergeometric system）定义的离散概率分布族，设计了一种利用计算代数的直接采样算法。这项研究的目的是提高伴随计算的效率，并扩大具有更一般代数依赖性的离散概率结构的采样。作为我们 2021 年研究的结果，我们发现了围绕量子计算的几个问题，这些问题涉及具有更一般代数依赖性的离散概率结构的开发（资助申请表研究方法 2）。量子霸权（在某些标准下，对于某些任务，经典计算相对于量子计算的优越性）已经在经典计算机生成随机生成的量子电路的输出的任务中得到了证明，其原因是由于分布依赖于计算函数在计算复杂性方面很困难的事实。通过使用贝叶斯方法，我们获得了一种与之前想象的不同的高效经典计算算法。研究结果将在研究会议上公布，目前正在撰写论文。此外，虽然是导数，但我们获得了与狄利克雷过程相关的采样结果，这也是本研究的起源。我们将狄利克雷过程概括为一种扩散过程，将平稳分布视为在有限图上的度量上取值的扩散过程，并推导了对偶马尔可夫过程。对于完整的图，我们给出了与狄利克雷过程相关的新的递推公式。作为一个应用，我们评估了算法在图中发现独立集所需的时间，并推导了计算样本在图中取值的可能性的算法，并发表了一篇论文。