論文の概要: A Quantum Scaling Algorithm for Maximum-Weight Perfect Matching in General Graphs

• arxiv url: http://arxiv.org/abs/2609.39457v1
• Date: Wed, 30 Sep 2026 10:27:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:27.583217
• Title: A Quantum Scaling Algorithm for Maximum-Weight Perfect Matching in General Graphs
• Title（参考訳）: 一般グラフにおける最大ウェイト完全マッチングのための量子スケーリングアルゴリズム
• Abstract要約: 整数エッジ重み付き一般グラフにおける最大重み付き完全マッチング(MWPM)問題に対する量子アルゴリズムを提案する。 我々のアルゴリズムは ( widetildeO(n m2/3log W) ) 時間で実行され、$W$ はエッジウェイトの大きさの上限である。 これは、高密度な状態における最もよく知られた古典的境界 ( widetildeO(msqrt n log W) ) に対する改善である。
• 参考スコア（独自算出の注目度）: 0.04666493857924356
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum speed-ups have been obtained for many fundamental graph problems, including most variants of matching. A notable exception, however, is the maximum-weight perfect matching (MWPM) problem in general graphs with integer edge weights, which is arguably the most challenging variant of matching. We present a quantum algorithm for MWPM in general graphs that runs in \( \widetilde{O}(n m^{2/3}\log W) \) time, where $W$ is an upper bound on the magnitude of the edge weights. This is an improvement over the best known classical combinatorial bound of \( \widetilde{O}(m\sqrt n \log W) \) in the dense regime, where $m\ge n^{3/2}$. To the best of our knowledge, this is the first quantum algorithm to obtain an asymptotic improvement over the best classical combinatorial algorithm for the MWPM problem in general graphs. The running time of our method accounts for QRAM initialization and access overheads up to polylogarithmic factors, as well as all classical updates to the data structures. At a high level, our algorithm is based on a classical framework due to Duan, Pettie, and Su, but our algorithm requires replacing certain classical tasks with quantum methods, alternative analysis of classical procedures, and the use of alternative data structures that can be implemented effectively in the QRAM model.
• Abstract（参考訳）: 量子スピードアップは、マッチングのほとんどの変種を含む多くの基本的なグラフ問題に対して得られた。 しかし、注目すべき例外は、整数の辺の重みを持つ一般グラフにおける最大重み付き完全マッチング(MWPM)問題である。 MWPM の量子アルゴリズムは、( \widetilde{O}(n m^{2/3}\log W) \) 時間で走る一般グラフにおいて、$W$ はエッジウェイトの大きさの上限である。 これは、高密度な状態において、最もよく知られた古典的組合せ境界 \( \widetilde{O}(m\sqrt n \log W) \) に対する改善であり、$m\ge n^{3/2}$ である。 我々の知る限りでは、一般グラフにおけるMWPM問題に対する最良の古典的組合せアルゴリズムよりも漸近的に改善された最初の量子アルゴリズムである。 我々の手法の実行時間は、QRAMの初期化とアクセスオーバーヘッド、およびデータ構造に対する古典的な更新を考慮に入れている。 高レベルでは、我々のアルゴリズムは、Duan, Pettie, Suによる古典的なフレームワークに基づいているが、我々のアルゴリズムは、ある種の古典的なタスクを量子的手法に置き換えること、古典的な手続きの代替分析、QRAMモデルで効果的に実装できる代替データ構造の使用が必要である。

関連論文リスト

• Quantum Speedup for Sampling Random Spanning Trees [2.356162747014486]
  我々は、$widetildeO(sqrtmn)$ timeの重み付きグラフからランダムスパンニング木をサンプリングする量子アルゴリズムを提案する。 我々のアルゴリズムは、高密度グラフのサブ線形ランタイムを持ち、よく知られた古典的アルゴリズムの量子スピードアップを実現する。
  論文  参考訳（メタデータ） (2025-04-22T05:45:04Z)
• Performance of Variational Algorithms for Local Hamiltonian Problems on Random Regular Graphs [0.13654846342364307]
  グラフ上に定義された2-局所ハミルトニアンを最適化する2つの変分アルゴリズムを設計する。 無限大極限におけるランダム正則グラフに対して,これらのアルゴリズムによって達成されるエネルギーを高い確率で解析する公式を開発する。 アルゴリズムの5つの層だけで、QMCの基底状態エネルギーの1.62%の誤差を無限の1Dリングで生成できることが示される。
  論文  参考訳（メタデータ） (2024-12-19T18:27:39Z)
• 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)
• A quantum advantage over classical for local max cut [48.02822142773719]
  量子最適化近似アルゴリズム(QAOA)は、次数3グラフ上の古典的手法に匹敵する計算上の優位性を持つ。 結果として、最先端の量子ハードウェアに関係している小規模量子計算でさえ、比較可能な単純な古典よりも大きな優位性を持つ可能性が示唆された。
  論文  参考訳（メタデータ） (2023-04-17T16:42:05Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。 レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
  論文  参考訳（メタデータ） (2022-03-01T19:47:16Z)
• Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
  量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。 任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2020-11-26T18:22:21Z)
• Applying the Quantum Alternating Operator Ansatz to the Graph Matching Problem [0.5584060970507505]
  グラフの最大マッチングに関するいくつかの問題に対処するための導出手法を設計する。 入力として空の状態が与えられたとき、可能なすべてのマッチングに対する重ね合わせと、入力としてW-状態が与えられたとき、すべての最大マッチングに対する重ね合わせを得る。 本研究の主な成果は,QAOA+アルゴリズムの2正規グラフ上での実行時の出力状態に対応するマッチングの期待サイズが,全てのマッチングの均一分布から得られるマッチングサイズよりも大きいことである。
  論文  参考訳（メタデータ） (2020-11-24T06:36:11Z)

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

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