論文の概要: Warm-Starting MaxCut Relaxation via Low-Depth Quantum Approximate Optimization Algorithm
- arxiv url: http://arxiv.org/abs/2608.06212v1
- Date: Thu, 06 Aug 2026 16:04:14 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-07 15:25:20.949203
- Title: Warm-Starting MaxCut Relaxation via Low-Depth Quantum Approximate Optimization Algorithm
- Title（参考訳）: 低深さ量子近似最適化アルゴリズムによるワームスタートMaxCut緩和
- Abstract要約: 最先端の古典的解法は、実用性に対する強硬なベンチマークのままである。
本稿では、量子情報を用いて古典的解法を先導するハイブリッド戦略を提案する。
- 参考スコア（独自算出の注目度）: 1.4062671086456255
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Quantum optimization has attracted growing interest as quantum hardware continues to improve, yet state-of-the-art classical solvers remain a formidable benchmark for practical utility. Rather than seeking a fully quantum replacement for classical optimization, we propose a hybrid strategy that uses quantum information to enhance leading classical heuristics. Specifically, we introduce a warm-start method based on local correlators obtained from the Quantum Approximate Optimization Algorithm (QAOA), and use this information to initialize the Burer-Monteiro (BM) rank-two relaxation. We demonstrate numerically that, compared to a random, multi-start initialization baseline (a standard strategy used for BM), this quantum-informed initialization offers a significant head start, i.e., high-quality solutions with very small number of iterations, for two problem classes -- random Erdős Rényi graphs with edge density of $10\%$ (ER-10) and fully-connected Sherrington Kirkpatrick (SK) spin glass models, at $n=500$ and $n=1000$ qubits. At the same time, given enough iterations, the random baseline often eventually catches up and slightly outperforms the warm-start strategy on average, an effect visibly stronger for $n=500$ than for $n=1000$. The results demonstrate an exploitation/exploration tradeoff of using WS to quickly arrive at very good solutions vs exploring slightly better solutions with a larger iterations budget via a standard strategy. Our results highlight how low-depth quantum circuits can provide useful structural information for classical optimization and suggest a promising route toward near-term quantum utility through quantum-assisted initialization.
- Abstract（参考訳）: 量子ハードウェアの改善が進み、量子最適化への関心が高まっている。
古典最適化の完全量子置換を求めるのではなく、量子情報を用いて古典的ヒューリスティックを導くハイブリッド戦略を提案する。
具体的には、Quantum Approximate Optimization Algorithm (QAOA) から得られた局所相関子に基づくウォームスタート法を導入し、この情報を用いて、Burer-Monteiro (BM) ランク2の緩和を初期化する。
我々は、ランダムなマルチスタート初期化ベースライン(BMの標準戦略)と比較して、この量子インフォームド初期化は、非常に少ないイテレーション数を持つ高品質な解、すなわち、エッジ密度が 10\%$ (ER-10) のランダムエルデシュ・レニーグラフと、完全に連結されたシェリントン・カークパトリック(SK)スピングラスモデル($n=500$ および$n=1000$ qubits の2つの問題クラスに対して、重要なヘッドスタートを提供することを示した。
同時に、十分なイテレーションが与えられた場合、ランダムなベースラインは最終的に追いつき、平均的なウォームスタート戦略よりもわずかに優れ、この効果は$n=500$に対して$n=1000$よりも目に見えるほど強い。
結果は、WSを使用して非常に優れたソリューションに素早く到達し、標準戦略を通じてより大規模なイテレーション予算で少し良いソリューションを探索することによる、エクスプロイト/探索のトレードオフを示しています。
この結果から,量子回路が古典的最適化に有用な構造情報を提供し,量子支援初期化による短期量子ユーティリティへの道のりが示唆された。
関連論文リスト
- Automatic De-Quantization of Quantum Programs Using Constant Propagation [42.89658025409898]
すべての量子演算は費用がかかるため、短期的なアルゴリズムにおける量子リソースの使用を最小限に抑えることが重要である。
本研究では、量子演算を可能な限り古典計算に非量子化することに焦点を当てる。
量子古典的定数伝播のためのハイブリッド状態モデルを形式化し、オープンソースのMQT Coreツールで最適化を実装し、ベンチマーク回路上で評価する。
論文 参考訳（メタデータ） (2026-05-21T19:21:11Z) - Iterative warm-start optimization with quantum imaginary time evolution [0.06999740786886534]
近似最適化は量子コンピュータにとって有望なユースケースである。
ここでは、これらのアイデアを用いて、いくつかの最適化のために非変分量子アルゴリズムを設計する。
この手法は、大域最適化の95%以内の中央値解を求め、11%以上の場合において最適解を求める。
論文 参考訳（メタデータ） (2026-04-28T18:32:11Z) - Optimal Quantum Likelihood Estimation [0.0]
ハイブリッド量子古典アルゴリズム(英: hybrid quantum-classical algorithm)は、量子回路を用いて情報を抽出する計算手法である。
我々は,情報理論の原理的最適化により,ハイブリッドアルゴリズムの性能を向上する。
論文 参考訳（メタデータ） (2025-08-31T12:51:44Z) - Quantum-Enhanced Optimization by Warm Starts [1.1666234644810893]
本稿では,量子化最適化(quantum-enhanced optimization)と呼ぶ手法を提案し,量子サンプルを利用して古典最適化アルゴリズムを高速化する。
我々の方法は、量子生成サンプルを古典的なサンプリングの温暖化に利用して、Max-CutやMaximum Independent Set (MIS)のような新しい問題を解決する。
論文 参考訳（メタデータ） (2025-08-22T11:36:19Z) - Optimizing random local Hamiltonians by dissipation [44.99833362998488]
簡単な量子ギブスサンプリングアルゴリズムが最適値の$Omega(frac1k)$-fraction近似を達成することを証明した。
この結果から, 局所スピンおよびフェルミオンモデルに対する低エネルギー状態の発見は量子的に容易であるが, 古典的には非自明であることが示唆された。
論文 参考訳（メタデータ） (2024-11-04T20:21:16Z) - A Multilevel Approach For Solving Large-Scale QUBO Problems With Noisy Hybrid Quantum Approximate Optimization [3.3493770627144004]
既存の量子処理ユニット(QPU)がマルチレベル戦略においてサブソルバとしてどのように機能するかを実験的に検証する。
完全連結な 82$-qubit Sherrington-Kirkpatrick グラフに対して 10$ の近似解を求める。
量子最適化の結果は古典学と比較して解の質に関して競争力がある。
論文 参考訳（メタデータ） (2024-08-14T20:06:32Z) - Warm-Start Variational Quantum Policy Iteration [39.04157716488156]
強化学習は、非常に複雑な意思決定シナリオにおける最適な行動を決定するための強力なフレームワークである。
NISQ互換の量子化サブルーチンを用いて,変分量子ポリシー反復(VarQPI)アルゴリズムを提案する。
そのスケーラビリティは、一般的な強化学習環境の構造の分析によって支えられている。
論文 参考訳（メタデータ） (2024-04-16T13:16:19Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Randomized Benchmarking of Local Zeroth-Order Optimizers for Variational
Quantum Systems [65.268245109828]
古典学のパフォーマンスを、半ランダム化された一連のタスクで比較する。
量子システムにおける一般に好適な性能とクエリ効率のため、局所ゼロ階数に着目する。
論文 参考訳（メタデータ） (2023-10-14T02:13:26Z) - Efficient DCQO Algorithm within the Impulse Regime for Portfolio
Optimization [41.94295877935867]
本稿では,デジタルカウンセバティック量子最適化(DCQO)パラダイムを用いて,ポートフォリオ最適化のための高速なディジタル量子アルゴリズムを提案する。
提案手法は,アルゴリズムの回路深度要件を特に低減し,解の精度を向上し,現在の量子プロセッサに適している。
我々は,IonQトラップイオン量子コンピュータ上で最大20量子ビットを使用するプロトコルの利点を実験的に実証した。
論文 参考訳（メタデータ） (2023-08-29T17:53:08Z) - Automatic and effective discovery of quantum kernels [41.61572387137452]
量子コンピューティングは、カーネルマシンが量子カーネルを利用してデータ間の類似度を表現できるようにすることで、機械学習モデルを強化することができる。
本稿では,ニューラルアーキテクチャ検索やAutoMLと同じような最適化手法を用いて,この問題に対するアプローチを提案する。
その結果、高エネルギー物理問題に対する我々のアプローチを検証した結果、最良のシナリオでは、手動設計のアプローチに関して、テストの精度を一致または改善できることが示された。
論文 参考訳（メタデータ） (2022-09-22T16:42:14Z) - GEO: Enhancing Combinatorial Optimization with Classical and Quantum
Generative Models [62.997667081978825]
我々は、生成モデルとして知られる機械学習モデルを活用する新しいフレームワークを導入し、最適化問題を解決する。
我々は、テンソルネットワークマシンに依存するGEOの量子インスパイアされたバージョンに注力する。
関数呼び出し数に対する固定予算が与えられた場合、その目標が最小限の最小値を求める場合、その優れた性能を示す。
論文 参考訳（メタデータ） (2021-01-15T18:18:38Z) - Warm-starting quantum optimization [6.832341432995627]
最適化問題の緩和解に対応する初期状態を用いて量子最適化を温める方法について論じる。
これにより、量子アルゴリズムは古典的なアルゴリズムの性能保証を継承することができる。
同じ考えを他のランダム化ラウンドスキームや最適化問題に適用するのは簡単である。
論文 参考訳（メタデータ） (2020-09-21T18:00:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。