論文の概要: Regularized Warm-Started Quantum Approximate Optimization and Conditions for Surpassing Classical Solvers on the Max-Cut Problem

• arxiv url: http://arxiv.org/abs/2603.10191v1
• Date: Tue, 10 Mar 2026 19:34:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-12 16:22:32.668495
• Title: Regularized Warm-Started Quantum Approximate Optimization and Conditions for Surpassing Classical Solvers on the Max-Cut Problem
• Title（参考訳）: 量子近似最適化の正規化とMax-Cut問題における古典解の超越条件
• Authors: Zichang He, Anuj Apte, Brandon Augustino, Arman Babakhani, Abid Khan, Sivaprasad Omanakuttan, Ruslan Shaydulin,
• Abstract要約: 本稿では,QAOAの停止を防止し,QAOAが停止するのを防ぐ正規化器を用いて,期待エネルギーを最小化してキュービットを初期化する正則化ウォームスタートQAOA(RWS-QAOA)を紹介する。 ランダムな正則グラフに対するMax-Cut問題に対するRWS-QAOAの評価を行い、このプロトコルは3つの相補的な設定で、一定の深さの量子回路を生成する。 以上の結果から,量子回路と古典的ウォームスタートが組み合わさった定数深度量子回路は,将来の量子コンピュータ上での実行において,Max-Cut問題における古典的解法を克服できる可能性が示唆された。
• 参考スコア（独自算出の注目度）: 0.7520006166976945
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Demonstrating quantum heuristics that outperform strong classical solvers on large-scale optimization remains an open challenge. Here we introduce Regularized Warm-Started QAOA (RWS-QAOA), which initializes qubits by minimizing expected energy with a regularizer that penalizes near-bitstring states, preventing QAOA from stalling. We further propose a protocol that yields fixed, instance-independent parameters, enabling RWS-QAOA to operate as a non-variational algorithm in which the quantum circuit parameters are fixed and only a classical warm starting step is instance-dependent. We evaluate RWS-QAOA on the Max-Cut problem for random regular graphs, where this protocol yields a constant-depth quantum circuit, across three complementary settings. First, on Quantinuum's trapped-ion processor, RWS-QAOA outperforms the classical algorithms with the best provable guarantees for Max-Cut on $3$-regular graphs, namely Goemans-Williamson and Halperin-Livnat-Zwick, on $96$-node instances. Second, tensor-network simulations on graphs with up to $N{=}10{,}000$ nodes show that depth-$6$ RWS-QAOA, achieving an average cut fraction of $0.9167$, surpasses the best classical heuristics under matched restrictions (no local-search post-processing and no iterative refinement). Third, we remove these restrictions and benchmark against the strongest unrestricted classical heuristics, including an optimized parallel Burer-Monteiro solver that improves upon the MQLib implementation. Even against this stronger baseline, we project that surface-code RWS-QAOA reaches a quantum-classical runtime crossover below $0.2$ seconds on $3{,}000$-node graphs with fewer than $1.3$ million physical qubits. Our results show that constant-depth quantum circuits combined with a classical warm start have a credible potential to surpass classical solvers on the Max-Cut problem when executed on future quantum computers.
• Abstract（参考訳）: 大規模最適化において強い古典的解法よりも優れた量子ヒューリスティックを実証することは、未解決の課題である。 ここでは、QAOAの停止を防止し、ニアビットストリング状態のペナル化を行う正規化器を用いて、期待エネルギーを最小化し、キュービットを初期化する正規化ウォームスタートQAOA(RWS-QAOA)を紹介する。 さらに、RWS-QAOAが量子回路パラメータを固定し、古典的なウォームスタートステップのみをインスタンス依存とする非変分アルゴリズムとして動作するように、固定されたインスタンス非依存パラメータを出力するプロトコルを提案する。 ランダムな正則グラフに対するMax-Cut問題に対するRWS-QAOAの評価を行い、このプロトコルは3つの相補的な設定で、一定の深さの量子回路を生成する。 第一に、Quantinuumの閉じ込められたイオンプロセッサにおいて、RWS-QAOAは、960ドルのノードインスタンス上の3ドルの正規グラフ、すなわちGoemans-WilliamsonとHalperin-Livnat-Zwickにおいて、Max-Cutの最も証明可能な保証で古典的なアルゴリズムより優れている。 第二に、最大$N{=}10{,}000$ノードを持つグラフ上のテンソル・ネットワークシミュレーションは、深さが6$ RWS-QAOAで、平均カット分数0.9167$を達成し、マッチした制限の下での古典的ヒューリスティックスを上回る(局所的な後処理はなし、反復的な洗練はなし)。 第3に、これらの制約を排除し、MQLibの実装を改善する最適化された並列Burer-Monteiroソルバを含む、最強の制限のない古典的ヒューリスティックに対してベンチマークを行う。 この強いベースラインに対しても、サーフェスコード RWS-QAOA は、物理量子ビットが1.3億ドル未満の$3,000$ノードグラフ上で、0.2$秒以下で量子古典的ランタイムのクロスオーバーに達することを予測している。 以上の結果から,量子回路と古典的ウォームスタートが組み合わさった定数深度量子回路は,将来の量子コンピュータ上での実行において,Max-Cut問題における古典的解法を克服できる可能性が示唆された。

関連論文リスト

• Branch-and-bound digitized counterdiabatic quantum optimization [39.58317527488534]
  分岐とバウンドのアルゴリズムは、厳密な下界を得るために目的関数の緩和に依存する凸最適化問題を効果的に解く。 本稿では,緩和困難に対処する分枝・分枝・分枝・分枝・分枝対応量子最適化法 (BB-DCQO) を提案する。
  論文  参考訳（メタデータ） (2025-04-21T18:19:19Z)
• Performance guarantees of light-cone variational quantum algorithms for the maximum cut problem [12.148326652334598]
  変分量子アルゴリズム(VQA)は、古典的計算よりも短期的な量子コンピューティングの利点を実証することを約束している。 本稿では,標準VQAの最適ゲート列を選択することで,光円錐VQAを提案する。 1ラウンドの光円錐VQAはMaxCut問題に対して0.7926の近似比が得られることを示す。
  論文  参考訳（メタデータ） (2025-04-17T12:38:16Z)
• Large-scale quantum annealing simulation with tensor networks and belief propagation [0.0]
  3つの正則グラフに対する量子アニールは1000量子ビットと5000000量子ビットゲートのスケールでも古典的にシミュレートできることを示す。 非退化インスタンスの場合、一意解は最後の縮小された単一量子状態から読み出すことができる。 MaxCutのような退化問題に対して、グラフテンソル-ネットワーク状態に対する近似的な測定シミュレーションアルゴリズムを導入する。
  論文  参考訳（メタデータ） (2024-09-18T18:00:08Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• 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)
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm [0.7046417074932257]
  量子近似最適化アルゴリズム(QAOA)の性能を最先端の古典解法と比較する。 古典的解法は線形時間複雑性において高品質な近似解を生成することができる。 異なるグラフ、重み付けされたMaxCut、最大独立集合、および3-SATといった他の問題は、短期量子デバイスにおける量子優位性を達成するのに適しているかもしれない。
  論文  参考訳（メタデータ） (2022-06-07T20:59:19Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。 量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。 提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
  論文  参考訳（メタデータ） (2022-05-24T03:49:10Z)
• Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
  量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。 任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2020-11-26T18:22:21Z)

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

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