論文の概要: Quantum Sampling of Random Spanning Trees via Amortized Data Structures
- arxiv url: http://arxiv.org/abs/2609.40314v1
- Date: Wed, 30 Sep 2026 17:53:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-01 18:57:28.288877
- Title: Quantum Sampling of Random Spanning Trees via Amortized Data Structures
- Title（参考訳）: Amortized Data Structureによるランダムスパンニング木の量子サンプリング
- Abstract要約: 本稿では,グラフの分布木上の一様重ね合わせを生成する量子アルゴリズムを提案する。
これは、古典的なサンプルを生成することに焦点を当てた以前の作業を超えています。
- 参考スコア（独自算出の注目度）: 0.6308539010172308
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a quantum algorithm that generates a uniform superposition over the spanning trees of a graph -- also known as a q-sample -- using only a sub-linear number of queries to the graph. This goes beyond previous work that focuses on generating classical samples, including a recent quantum algorithm by Apers, Gao, Ji, and Liu [ICALP 2025]. For an $n$-vertex, $m$-edge graph, our algorithm admits a pre-processing step of $\tilde{O}(\sqrt{mn} + m^{1-δ})$, after which each q-sample can be generated in $\tilde{O}(n^{1+2δ})$ for any $δ$. Alternatively, $k$ independent q-samples can be generated at a total cost of $\tilde{O}(\sqrt{kmn})$. We also prove a matching lower bound up to logarithmic factors, showing that our algorithm is essentially optimal. Further tradeoffs are given in the paper. In comparison, the optimal classical algorithms (Anari, Liu and Vuong [FOCS 2022]) need an $\tilde{O}(m)$ pre-processing step, after which each sample costs $\tilde{O}(n)$ operations. These results yield faster quantum walk-based algorithms for counting spanning trees or finding a marked one. Our result is obtained via quantum walk sampling over a sequence of slowly-changing Markov chains. Each chain is an isotropized up-down walk that mixes rapidly to the spanning tree distribution of the input graph. A key ingredient is an amortized data structure supporting fast implementation of the associated quantum walk operators throughout the sequence. This data structure maintains access to a spectral sparsifier and a leverage score sampler that evolve with the underlying graph.
- Abstract（参考訳）: グラフへのクエリのサブ線形数のみを用いて、グラフの分散木(qサンプルとしても知られる)上の均一な重ね合わせを生成する量子アルゴリズムを提案する。
Apers氏、Gao氏、Ji氏、Liu氏(ICALP 2025)による最近の量子アルゴリズムなど、古典的なサンプルを生成することに焦点を当てた以前の研究を超えています。
n$-vertex, $m$-edge graph に対して、我々のアルゴリズムは $\tilde{O}(\sqrt{mn} + m^{1-δ})$ の前処理ステップを認め、その後、任意の$δ$に対して $\tilde{O}(n^{1+2δ})$ で各 q-サンプルを生成することができる。
あるいは、$k$ 独立 q-サンプルを$\tilde{O}(\sqrt{kmn})$で生成することができる。
また,アルゴリズムが本質的に最適であることを示すために,対数的因子の一致した下界を証明した。
論文にはさらなるトレードオフが記載されている。
比較すると、最適古典アルゴリズム (Anari, Liu and Vuong [FOCS 2022]) は$\tilde{O} を必要とする。
(m)$プリプロセッシングステップの後、各サンプルは$\tilde{O}
(n)$オペレーション。
これらの結果は、木を数えたり、目立ったものを見つけるために、より高速な量子ウォークベースのアルゴリズムをもたらす。
この結果は、ゆっくりと変化するマルコフ鎖の列上での量子ウォークサンプリングによって得られる。
各チェーンは異方性のあるアップダウンウォークであり、入力グラフの木の分布に急速に混ざり合う。
鍵となる要素は、シーケンス全体を通して関連する量子ウォーク演算子の高速な実装をサポートする償却データ構造である。
このデータ構造は、スペクトルスペーサーと、基礎となるグラフで進化するレバレッジスコアサンプリングへのアクセスを維持する。
関連論文リスト
- Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。
我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
論文 参考訳（メタデータ） (2026-09-30T17:51:21Z) - Quantum Speedup for Sampling Random Spanning Trees [2.356162747014486]
我々は、$widetildeO(sqrtmn)$ timeの重み付きグラフからランダムスパンニング木をサンプリングする量子アルゴリズムを提案する。
我々のアルゴリズムは、高密度グラフのサブ線形ランタイムを持ち、よく知られた古典的アルゴリズムの量子スピードアップを実現する。
論文 参考訳（メタデータ） (2025-04-22T05:45:04Z) - Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。
本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
論文 参考訳（メタデータ） (2024-08-10T04:26:19Z) - Do you know what q-means? [42.96240569413475]
古典的な$varepsilon$-$k$-meansアルゴリズムは、ロイドのアルゴリズムの1つの反復の近似バージョンを時間的複雑さで実行する。
また,時間的複雑さを考慮した$q$-means量子アルゴリズムも提案する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文 参考訳（メタデータ） (2022-10-12T19:10:43Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - Quantum Approximate Counting for Markov Chains and Application to
Collision Counting [0.0]
我々は,ブラザード,ホイヤー,タップ(ICALP 1998)によって開発された量子近似計数法を一般化し,マルコフ連鎖のマーク状態の数を推定する方法を示す。
これにより、Magniez、Nayak、Roland、Santhaによって確立された強力な"量子ウォークベースサーチ"フレームワークに基づいて、量子検索アルゴリズムから量子近似カウントアルゴリズムを構築することができる。
論文 参考訳（メタデータ） (2022-04-06T03:04:42Z) - How to simulate quantum measurement without computing marginals [3.222802562733787]
量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。
我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
論文 参考訳（メタデータ） (2021-12-15T21:44:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。