論文の概要: Quantum Speedup for Sampling Random Spanning Trees

• arxiv url: http://arxiv.org/abs/2504.15603v2
• Date: Thu, 24 Apr 2025 10:30:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-02 19:15:52.770317
• Title: Quantum Speedup for Sampling Random Spanning Trees
• Title（参考訳）: ランダムスパンニングツリーサンプリングのための量子スピードアップ
• Authors: Simon Apers, Minbo Gao, Zhengfeng Ji, Chenghua Liu,
• Abstract要約: 我々は、$widetildeO(sqrtmn)$ timeの重み付きグラフからランダムスパンニング木をサンプリングする量子アルゴリズムを提案する。 我々のアルゴリズムは、高密度グラフのサブ線形ランタイムを持ち、よく知られた古典的アルゴリズムの量子スピードアップを実現する。
• 参考スコア（独自算出の注目度）: 2.356162747014486
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a quantum algorithm for sampling random spanning trees from a weighted graph in $\widetilde{O}(\sqrt{mn})$ time, where $n$ and $m$ denote the number of vertices and edges, respectively. Our algorithm has sublinear runtime for dense graphs and achieves a quantum speedup over the best-known classical algorithm, which runs in $\widetilde{O}(m)$ time. The approach carefully combines, on one hand, a classical method based on ``large-step'' random walks for reduced mixing time and, on the other hand, quantum algorithmic techniques, including quantum graph sparsification and a sampling-without-replacement variant of Hamoudi's multiple-state preparation. We also establish a matching lower bound, proving the optimality of our algorithm up to polylogarithmic factors. These results highlight the potential of quantum computing in accelerating fundamental graph sampling problems.
• Abstract（参考訳）: 重み付きグラフからランダムスパンニング木をサンプリングする量子アルゴリズムを$\widetilde{O}(\sqrt{mn})$ time, ここでは$n$と$m$はそれぞれ頂点数と辺数を表す。 我々のアルゴリズムは、高密度グラフのサブ線形ランタイムを持ち、$\widetilde{O}(m)$ timeで実行される、よく知られた古典的アルゴリズムの量子スピードアップを達成する。 このアプローチは、「大ステップ」のランダムウォークに基づく古典的な手法を慎重に組み合わせて混合時間を短縮し、一方、量子グラフのスパーシフィケーションや、ハムーディの多重状態準備のサンプリングなし置換版を含む量子アルゴリズムの手法を巧みに組み合わせている。 また、一致した下界を確立し、アルゴリズムの最適性を多対数因子まで証明する。 これらの結果は、基本グラフサンプリング問題を加速させる量子コンピューティングの可能性を強調している。

関連論文リスト

• Quantum Algorithms for Stochastic Differential Equations: A Schrödingerisation Approach [29.662683446339194]
  線形微分方程式に対する量子アルゴリズムを提案する。 アルゴリズムのゲートの複雑さは、次元に依存する$mathcalO(dlog(Nd))$を示す。 アルゴリズムはOrnstein-Uhlenbeck過程、ブラウン運動、L'evy飛行に対して数値的に検証される。
  論文  参考訳（メタデータ） (2024-12-19T14:04:11Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。 この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。 我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
  論文  参考訳（メタデータ） (2024-05-02T10:29:06Z)
• Comparison among Classical, Probabilistic and Quantum Algorithms for Hamiltonian Cycle problem [0.0]
  ハミルトニアンサイクル問題(HCP)は、n 個のノードと m 個のエッジを持つグラフ G を持ち、各ノードを正確に1度に接続する経路を見つけることである。 本稿では、計算の異なるモデル、特に確率的および量子的モデルを用いて、aHCPを解くアルゴリズムを比較する。
  論文  参考訳（メタデータ） (2023-11-18T02:36:10Z)
• Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions [13.16814860487575]
  非対数確率分布からサンプリングする量子アルゴリズムを提案する。 f$ は有限和 $f(x):= frac1Nsum_k=1N f_k(x)$ と書くことができる。
  論文  参考訳（メタデータ） (2023-10-17T17:55:32Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Faster quantum mixing of Markov chains in non-regular graph with fewer qubits [0.0]
  量子の場合、マルコフ連鎖からのqsamplingは、定常分布の平方根に任意に近い振幅を持つ量子状態の準備として構成することができる。 本稿では,すべての可逆マルコフ連鎖に対する新しいqsamplingアルゴリズムを離散時間量子ウォークを用いて構築する。 非正規グラフでは、量子高速フォワードアルゴリズムの起動は、離散時間と連続時間の両方で既存の最先端のqsamplingアルゴリズムを加速させる。
  論文  参考訳（メタデータ） (2022-05-12T14:08:08Z)
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays [39.76254807200083]
  最大独立集合問題の解法として量子アルゴリズムを実験的に検討する。 問題の難易度は解の縮退と局所ミニマの数によって制御される。 最も難しいグラフでは、正確な解を見つける際に超線形量子スピードアップを観測する。
  論文  参考訳（メタデータ） (2022-02-18T19:00:01Z)
• Quantum Sampling Algorithms for Near-Term Devices [0.0]
  ギブス分布全体を符号化することで、偏りのないサンプルを提供する量子アルゴリズムのファミリを導入する。 このアプローチが従来のマルコフ連鎖アルゴリズムの高速化につながることを示す。 短期量子デバイス上で、潜在的に有用なサンプリングアルゴリズムを探索する扉を開く。
  論文  参考訳（メタデータ） (2020-05-28T14:46:20Z)
• Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving [1.0660480034605238]
  スペクトルスペーシフィケーション」は、ノード数でエッジの数をほぼ直線に減らす。 スペクトルスカラー化のための量子スピードアップとその多くの応用について述べる。 我々のアルゴリズムはラプラシア系を解くための量子スピードアップを意味する。
  論文  参考訳（メタデータ） (2019-11-17T17:29:40Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。