論文の概要: Provable Classical and Quantum Local Algorithms for Max-$k$-Cut and Quantum Advantage at Moderate Girth

• arxiv url: http://arxiv.org/abs/2609.39042v1
• Date: Wed, 30 Sep 2026 05:51:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:27.24591
• Title: Provable Classical and Quantum Local Algorithms for Max-$k$-Cut and Quantum Advantage at Moderate Girth
• Title（参考訳）: Max-$k$-Cutと量子アドバンテージの古典的および量子的局所アルゴリズム
• Abstract要約: 我々は、$d$正規グラフの$g$に対して、Max-$k$-Cutの局所古典的および量子的アルゴリズムを研究する。 我々のアルゴリズムは、既知の効率的な古典的アルゴリズムの中で、最も証明可能なカット分数保証を提供する。 我々は、Max-$k$-Cut問題にQAOAを適用することで明らかな量子優位性を得る。
• 参考スコア（独自算出の注目度）: 0.7661822096696312
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Broadening the study of quantum optimization algorithms from binary to $k$-element alphabets has been shown to open new avenues for potential quantum advantage. A quantum advantage claim for approximate optimization requires showing that, under the same assumptions, an efficient quantum algorithm provably achieves a better performance than can be proven for the best known efficient classical algorithms. We study local classical and quantum algorithms for Max-$k$-Cut on $d$-regular graphs of girth $g$. We advance classical algorithms for this problem by developing a local vector algorithm based on the explicit vector construction of Thompson, Parekh, and Marwaha (TPM). Our algorithm gives the best provable cut fraction guarantee among known efficient classical algorithms on regular graphs for $k\geq3$. To evaluate the performance of QAOA under identical assumptions of girth and regularity, we develop tensor network techniques for general $d$ and $k \geq 2$. In addition, using an equivalence to a coupled qudit--boson system, we compute the QAOA performance in the infinite-degree limit. Together, these techniques give provable guarantees on QAOA performance on large graphs. Despite the improvements we introduce to the classical algorithm, QAOA achieves a better cut fraction guarantee for depths $p\geq 9$, corresponding to girth $g\geq 20$, for both finite- and infinite-degree regimes. Thus, we obtain an apparent quantum advantage from applying QAOA to the Max-$k$-Cut problem.
• Abstract（参考訳）: 量子最適化アルゴリズムの研究を二進法から$k$要素アルファベットに拡大することで、潜在的な量子優位性のための新たな道を開くことが示されている。 近似最適化の量子優位性主張は、同じ仮定の下で、効率的な量子アルゴリズムが、最もよく知られた古典的アルゴリズムよりも優れた性能を確実に達成できることを示さなければならない。 girth $g$の$d$正規グラフ上で、Max-k$-Cutの局所古典的および量子的アルゴリズムを研究する。 我々は、トンプソン、パレフ、マルワハ(TPM)の明示的なベクトル構成に基づく局所ベクトルアルゴリズムを開発することにより、この問題に対する古典的アルゴリズムを推し進める。 我々のアルゴリズムは、正規グラフ上の既知の高効率な古典的アルゴリズムの中で、$k\geq3$で証明可能なカット分数保証を与える。 ガースと正則性の同じ仮定でQAOAの性能を評価するため、一般的な$d$と$k \geq 2$のテンソルネットワーク技術を開発した。 さらに、結合したキューディット-ボソン系に等価性を用いることで、無限次極限におけるQAOA性能を計算する。 これらの手法は、大きなグラフ上でのQAOA性能を証明可能な保証を与える。 古典的アルゴリズムに導入した改良にもかかわらず、QAOAは、有限次と無限次の両方の条件に対して、深さ$p\geq 9$, girth $g\geq 20$に対応する、より良いカット分数保証を達成する。 したがって、Max-$k$-Cut問題にQAOAを適用することで明らかな量子優位性が得られる。

関連論文リスト

• Quantum Approximate Optimization of Integer Graph Problems and Surpassing Semidefinite Programming for Max-k-Cut [0.8084252698425037]
  グラフ上の整数問題に適用された量子近似最適化アルゴリズム(QAOA)について検討する。 任意の大きさの高次$d$正則グラフ上で、深さ-p$QAOA予想に対する一般的な反復公式を導出する。 その結果、二進法から整数最適化問題への移動は、量子的優位性のために新しい道を開くことができることを示した。
  論文  参考訳（メタデータ） (2026-02-05T18:11:18Z)
• Warm Start Adaptive-Bias Quantum Approximate Optimization Algorithm [7.971068453222675]
  量子近似最適化アルゴリズム(QAOA)は、そのような「ウォームスタート」アプローチに適している。 Goemans-Williamson (GW) アルゴリズムによるウォームスタート適応バイアスQAOAは、40ドルから180ドルキュービットの問題で提案されたウォームスタート変種よりも優れていた。
  論文  参考訳（メタデータ） (2025-03-25T20:10:40Z)
• 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)
• Extending relax-and-round combinatorial optimization solvers with quantum correlations [0.0]
  量子近似最適化アルゴリズム (QAOA) を$pgeq 1$ の層に埋め込む。 Sherrington-Kirk メガネを含む多くの問題に対して、$p=1$とすると、その古典的な問題と同じくらい正確であることを示す。 古典的アルゴリズムに匹敵するパフォーマンスで、量子リラクゼーションとラウンドを網羅するフレームワークの道を開いた。
  論文  参考訳（メタデータ） (2023-07-11T22:02:01Z)
• A quantum advantage over classical for local max cut [48.02822142773719]
  量子最適化近似アルゴリズム(QAOA)は、次数3グラフ上の古典的手法に匹敵する計算上の優位性を持つ。 結果として、最先端の量子ハードウェアに関係している小規模量子計算でさえ、比較可能な単純な古典よりも大きな優位性を持つ可能性が示唆された。
  論文  参考訳（メタデータ） (2023-04-17T16:42:05Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
  量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。 任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2020-11-26T18:22:21Z)
• To quantum or not to quantum: towards algorithm selection in near-term quantum optimization [0.0]
  本稿では,QAOAが従来のアルゴリズムよりも有利になる確率の高い問題事例を検出する問題について検討する。 クロスバリデーションの精度は96%以上で、実用的な優位性が得られる。
  論文  参考訳（メタデータ） (2020-01-22T20:42:02Z)

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

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