論文の概要: Iterative Quantum Optimization: From Greedy Reductions to Branch-and-Bound
- arxiv url: http://arxiv.org/abs/2611.00678v1
- Date: Sat, 31 Oct 2026 06:16:09 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-13 17:17:19.94552
- Title: Iterative Quantum Optimization: From Greedy Reductions to Branch-and-Bound
- Title(参考訳): 反復量子最適化:グリーディリダクションからブランチ・アンド・バウンドへ
- Abstract要約: 反復量子最適化(IQO)は、量子生成情報を用いて古典的な問題削減のシーケンスを選択する。
本稿では,この反復構造と有界・可逆探索を組み合わせたバウンド・アウェア・ツリーIQOを提案する。
バックトラッキングを組み込むことで、最高の実現可能なソリューションを返す任意のメソッドが得られます。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Iterative quantum optimization (IQO) uses quantum-generated information to select a sequence of classical problem reductions. We introduce Bound-Aware Tree-IQO which combines this iterative structure with bounds and reversible search. Feasible measured samples update a shared incumbent, while valid classical bounds prune branches that cannot improve it. Incorporating backtracking yields an anytime method that returns the best feasible solution found when interrupted, or can be run as a complete search to return and certify the optimum. For suitable single-variable or pairwise reductions, an initial IQO path can determine the branching schedule without further quantum calls, though certifying the optimum may take superpolynomial classical time. To motivate our framework, we prove two limitations of irreversible IQO reductions based on the quantum approximate optimization algorithm (QAOA). We show an infinite family of unweighted MaxCut instances on which globally optimized level-1 QAOA makes standard Recursive QAOA strictly prefer a first reduction that excludes every optimal solution, and limits that branch to an approximation ratio of at most $2/3+o(1)$. In contrast, a single backtrack recovers an optimal solution using the same quantum information. Causal cone arguments give a complementary obstruction at every fixed depth of standard QAOA: a weighted MaxCut instance is shown to contain two edges with identical two-qubit reduced states, even though every optimum requires opposite edge parities. MaxCut experiments show that QAOA-guided ordering is nonrandom in exact-certification tests through $n=28$, while demonstrating that quantum samples can strengthen the incumbent and enable further pruning. Our results suggest that quantum data could provide useful guidance toward solving hard combinatorial optimization problems more effectively than either quantum or classical algorithms alone.
- Abstract(参考訳): 反復量子最適化(IQO)は、量子生成情報を用いて古典的な問題削減のシーケンスを選択する。
本稿では,この反復構造と有界・可逆探索を組み合わせたバウンド・アウェア・ツリーIQOを提案する。
測定可能なサンプルは共有現像体を更新し、有効な古典的境界プルー分岐は改善できない。
バックトラックを組み込むと、割り込み時に見つかった最良の実現可能なソリューションを返却する任意のメソッドが得られ、また、最適な解を返却し認証するために完全なサーチとして実行できる。
適切な単変数またはペアの還元のために、初期IQOパスは、さらなる量子呼び出しなしで分岐スケジュールを決定することができるが、最適の証明には超ポリノミカルな時間を要する可能性がある。
我々のフレームワークを動機づけるために、量子近似最適化アルゴリズム(QAOA)に基づく非可逆IQO削減の2つの限界を証明した。
グローバルに最適化されたレベル-1 QAOA が標準再帰的 QAOA を厳密に好んでおり、全ての最適解を除外し、その分岐を少なくとも 2/3+o(1)$ の近似比に制限する。
対照的に、単一のバックトラックは同じ量子情報を用いて最適解を復元する。
コーサルコーンの議論は、標準QAOAのすべての固定された深さで補的障害を与える: 重み付けされたマックスコートのインスタンスは、すべての最適条件が反対のエッジパリティを必要とするにもかかわらず、同じ2ビットの還元状態を持つ2つのエッジを含むことが示される。
MaxCut の実験では、QAOA 誘導順序付けは、$n=28$ による正確な認証テストでは非ランダムであり、量子サンプルが既存の値を強化し、さらなるプルーニングを可能にすることを示した。
以上の結果から,量子データにより,量子アルゴリズムと古典アルゴリズムのどちらよりも効率的な組合せ最適化問題の解法が期待できる可能性が示唆された。
関連論文リスト
- Quantum Approximate Optimization Algorithm for Maximum Likelihood Detection in Massive MIMO [21.477208706334608]
本稿では,二項記号の最大度検出解法をQAOAに基づいて提案する。
最先端のQAOAベースのML検出アルゴリズムと比較して,提案手法は1レベルQAOAのより普遍的でコンパクトな期待値式を持つ。
論文 参考訳(メタデータ) (2025-10-15T09:37:21Z) - Learning Feasible Quantum States for Quadratic Constrained Binary Optimization Problems [41.23247424467223]
我々はQCBOの制約を満たす量子状態の同値重ね合わせを生成する変動的アプローチを開発する。
結果として生じる同値な重ね合わせは、QUBO/QCBOを解く量子アルゴリズムの初期状態として使用できる。
論文 参考訳(メタデータ) (2025-08-04T16:44:53Z) - Branch-and-bound digitized counterdiabatic quantum optimization [39.58317527488534]
分岐とバウンドのアルゴリズムは、厳密な下界を得るために目的関数の緩和に依存する凸最適化問題を効果的に解く。
本稿では,緩和困難に対処する分枝・分枝・分枝・分枝・分枝対応量子最適化法 (BB-DCQO) を提案する。
論文 参考訳(メタデータ) (2025-04-21T18:19:19Z) - Recursive Quantum Relaxation for Combinatorial Optimization Problems [3.3053321430025258]
本稿では,既存の量子最適化手法を解法に統一して二項解を求める方法を示す。
MAX-CUT問題における数百ノードの標準ベンチマークグラフの実験は、完全に古典的な方法で行われた。
論文 参考訳(メタデータ) (2024-03-04T13:48:21Z) - An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation [0.23999111269325263]
量子近似最適化アルゴリズム(QAOA)は、最適化問題を解くために用いられるハイブリッド量子古典アルゴリズムである。
QAOAはNISQデバイスに実装できるが、物理的制限は回路深さを制限し、性能を低下させる。
この研究は、より古典的なパラメータをアンサッツに割り当て、低深さでの性能を改善するeXpressive QAOA (XQAOA)を導入している。
論文 参考訳(メタデータ) (2023-02-09T07:47:06Z) - 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) - Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary
Optimization [44.96576908957141]
本稿では,量子コンピュータ上での2次線形反復問題を解くために,フランク・ウルフアルゴリズム(Q-FW)に基づく古典量子ハイブリッドフレームワークを提案する。
論文 参考訳(メタデータ) (2022-03-23T18:00:03Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。
本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。
Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文 参考訳(メタデータ) (2021-05-06T17:59:38Z) - Improving the Quantum Approximate Optimization Algorithm with
postselection [0.0]
組合せ最適化は、短期的およびフォールトトレラントな量子コンピュータに想定される主な応用の1つである。
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は3つの正則グラフ上のMaxCut問題に適用される。
理論上界と下界を導いており、満たされた辺の分数の一定(小さい)増加が実際に達成可能であることを示す。
論文 参考訳(メタデータ) (2020-11-10T22:17:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。