論文の概要: Max-Cut QAOA on Non-Hardware-Native Graphs via MinLA Surrogates and Configuration Recovery
- arxiv url: http://arxiv.org/abs/2611.18002v1
- Date: Fri, 13 Nov 2026 10:27:33 GMT
- ステータス: 情報取得中
- システム内更新日: 2026-11-16 19:29:26.175447
- Title: Max-Cut QAOA on Non-Hardware-Native Graphs via MinLA Surrogates and Configuration Recovery
- Title(参考訳): MinLAサロゲートと構成回復による非ハードウェアネイティブグラフのMax-Cut QAOA
- Abstract要約: 非ハードウェアネイティブのtextscMAX-CUT インスタンスでは、Quantum Approximate Optimization Algorithm (QAOA) が追加で2ビットの深さオーバーヘッドを発生させることができる。
本稿では,相互作用を選択的に取り除き,解の質を回復させることにより,この深度を低減させるハイブリッド量子古典ワークフローを提案する。
- 参考スコア(独自算出の注目度): 0.0
- License:
- Abstract: For non-hardware-native \textsc{MAX-CUT} instances, the Quantum Approximate Optimization Algorithm (QAOA) can incur additional two-qubit depth overhead due to SWAP-based routing of interactions between non-adjacent qubits. We propose a hybrid quantum--classical workflow that reduces this depth by selectively removing interactions and subsequently recovers solution quality through classical optimization of the original \textsc{MAX-CUT} objective. We employ a Minimum Linear Arrangement (MinLA)-based vertex ordering to preferentially retain short-range interactions, thereby constructing a two-qubit depth-reduced surrogate QAOA ansatz. To compensate for the information lost through interaction removal, we develop classical \textit{recovery} strategies that refine QPU-sampled bitstrings directly on the original \textsc{MAX-CUT} objective. We develop two recovery strategies: signed-residue-based local search and bipartite-block optimization, where each conditional block problem is solved exactly using an $s$--$t$ minimum cut. Recovery is performed independently on each sampled configuration, ensuring monotonic improvement in cut value without additional QPU executions. We evaluate the workflow on \texttt{ibm\_kingston} for 120 distinct non-hardware-native instances comprising $6$-regular and Erdős--Rényi graphs with 40, 60 and 100 vertices. We verify that the surrogates substantially reduce transpiled two-qubit depth while staying within the prescribed two-qubit depth, and with recovery yield \textit{near-optimal} cuts on the original graphs. These results demonstrate the potential of hardware-aware interaction selection and classical recovery to extend QAOA to graph instances whose full cost Hamiltonians exceed practical circuit-depth budgets.
- Abstract(参考訳): 非ハードウェアネイティブな \textsc{MAX-CUT} インスタンスに対して、Quantum Approximate Optimization Algorithm (QAOA) は、非隣接量子ビット間の相互作用のSWAPベースのルーティングにより、追加の2ビット深さオーバーヘッドを発生させることができる。
本稿では、相互作用を選択的に除去してこの深さを削減するハイブリッド量子古典ワークフローを提案し、その後、元の \textsc{MAX-CUT} 目的の古典的な最適化によって解の質を回復する。
我々は,最小線形アレンジメント(MinLA)に基づく頂点命令を用いて,短距離相互作用を優先的に保持し,2ビットの深さ還元型サロゲートQAOAアンサッツを構築する。
相互作用除去によって失われる情報を補うために、QPUでサンプリングされたビットストリングを元の \textsc{MAX-CUT} の目的に直接洗練する古典的な \textit{recovery} 戦略を開発した。
我々は,各条件ブロック問題を$s$--$t$の最小カットで正確に解き,符号待ち行列に基づく局所探索と二部ブロック最適化という2つのリカバリ戦略を開発した。
回復はサンプル設定ごとに独立して行われ、追加のQPU実行なしでカット値の単調な改善が保証される。
我々は、40, 60, 100頂点を持つ6$正規およびエルデシュ-レーニグラフからなる120個の非ハードウェアネイティブなインスタンスに対して、texttt{ibm\_kingston} 上のワークフローを評価する。
そこで本研究では,サロゲートが所定2キュービットの深さに留まり,元のグラフ上でのリカバリ収率 \textit{near-optimal} カットにより,トランスパイルされた2キュービットの深さを大幅に減少させることを確認した。
これらの結果は、ハードウェア対応のインタラクション選択と古典的リカバリの可能性を示し、QAOAを実際の回路深度予算を超えるフルコストのハミルトニアンのグラフインスタンスに拡張する。
関連論文リスト
- QAOA for Layered Architecture Recovery: Feasibility, Limits, and the Role of Decomposition [0.6931453803691031]
階層化アーキテクチャリカバリ(LAR)は、システムのアーキテクチャレイヤをパッケージの依存関係から再構築する。
量子近似最適化アルゴリズム(QAOA)をLARに適用できるかどうかを検討する。
論文 参考訳(メタデータ) (2026-11-06T17:16:08Z) - Iterative Quantum Optimization: From Greedy Reductions to Branch-and-Bound [0.0]
反復量子最適化(IQO)は、量子生成情報を用いて古典的な問題削減のシーケンスを選択する。
本稿では,この反復構造と有界・可逆探索を組み合わせたバウンド・アウェア・ツリーIQOを提案する。
バックトラッキングを組み込むことで、最高の実現可能なソリューションを返す任意のメソッドが得られます。
論文 参考訳(メタデータ) (2026-10-31T06:16:09Z) - Reducing QUBO Complexity in Drone Delivery Through Classical Feasibility Preprocessing [0.0]
ドローン配達計画では、ルーティング決定とペイロード容量やオンボードエネルギーの制限といった運用上の制約を組み合わせる。
本研究は、候補ドローンのミッションを古典的に生成・評価するハイブリッド量子-古典的アプローチについて検討する。
論文 参考訳(メタデータ) (2026-10-14T22:53:39Z) - Closed-Form Spectral Regularization for Multi-Task Model Merging [96.82449201305234]
モデルマージは、個別に調整された複数の専門家をトレーニングデータなしで単一のマルチタスクモデルに結合する。
State-of-the-art merging method formulate merging as a layer-wise interference problem。
本稿では,逐次降下の勾配-流路に一致するソフト指数フィルタを組み合わせた閉形式手法SWUDIを提案する。
論文 参考訳(メタデータ) (2026-06-05T14:00:47Z) - Nonvariational quantum optimisation approaches to pangenome-guided sequence assembly [0.42970700836450487]
ゲノム組立問題に対する短期量子最適化手法を開発した。
固定された線形ランプQAOAスケジュールと反復的ウォームスタートバイアス更新を組み合わせたIterative-QAOAフレームワークを使用する。
カスタム回路コンパイル戦略は、標準ツールと比較してハードウェアゲートのオーバーヘッドを最大67%削減する。
論文 参考訳(メタデータ) (2026-04-07T17:17:34Z) - Scalable Quantum Walk-Based Heuristics for the Minimum Vertex Cover Problem [0.0]
連続時間量子ウォーク(CTQW)に基づく最小頂点被覆(MVC)問題に対する新しい量子アルゴリズムを提案する。
この枠組みでは、グラフ上の量子ウォーカーのコヒーレントな伝播は、その構造特性を状態振幅に符号化する。
我々は,CTQWに基づくアルゴリズムが優れた近似比を一貫して達成し,ネットワークトポロジに関して顕著な堅牢性を示すことを示す。
論文 参考訳(メタデータ) (2025-12-02T17:04:57Z) - MPQ-DMv2: Flexible Residual Mixed Precision Quantization for Low-Bit Diffusion Models with Temporal Distillation [74.34220141721231]
我々は,textbfMixed textbfPrecision textbfQuantizationフレームワークを改良したMPQ-DMv2を提案する。
論文 参考訳(メタデータ) (2025-07-06T08:16:50Z) - Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳(メタデータ) (2025-02-07T15:57:56Z) - 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) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳(メタデータ) (2021-06-05T09:16:28Z) - Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
敵対的レジリエントな分散最適化。
機械は独立して勾配を計算し 協力することができます
私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。
それは非常に実用的です:それはないときすべての前の方法の性能を改善します。
セッティングマシンがあります。
論文 参考訳(メタデータ) (2020-12-28T17:19:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。