論文の概要: Adaptive Qubit Freezing Enables Robust Graph Partitioning for Divide-and-Conquer QAOA

• arxiv url: http://arxiv.org/abs/2607.08138v1
• Date: Thu, 09 Jul 2026 06:19:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-10 14:45:27.424743
• Title: Adaptive Qubit Freezing Enables Robust Graph Partitioning for Divide-and-Conquer QAOA
• Title（参考訳）: Adaptive Qubit Freezingは、分割およびコンカレントQAOAのためのロバストグラフ分割を可能にする
• Abstract要約: 仮定から強制可能な性質へ分割性を変換する適応分解フレームワークであるFrozenLGPを紹介する。 FrozenLGPは、高結合性インスタンス上での標準分割およびコンカヤベースラインの4.6%と比較して100%の分解カバレッジを実現している。
• 参考スコア（独自算出の注目度）: 3.7768601360100647
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Divide-and-conquer variants of the Quantum Approximate Optimization Algorithm (QAOA) provide a promising route for executing combinatorial optimization problems beyond the qubit capacity of near-term quantum devices. However, existing approaches rely on the existence of small vertex separators and fail entirely on dense or highly connected graphs where such decompositions do not exist. We introduce Frozen Large Graph Partitioning (FrozenLGP), an adaptive decomposition framework that transforms partitionability from an assumption into an enforceable property. When standard partitioning fails, FrozenLGP identifies the minimum set of obstructing vertices through a minimum-vertex-cut computation based on max-flow and classically freezes their spin assignments. The energetic contributions of the removed interactions are rigorously preserved by folding them into linear bias terms in the Ising Hamiltonian of neighboring active qubits. Across graph sizes up to 10,000 vertices and multiple topology families, FrozenLGP achieves 100\% decomposition coverage, compared with 4.6\% for the standard divide-and-conquer baseline on high-connectivity instances. End-to-end MaxCut experiments demonstrate that FrozenLGP preserves approximation quality on instances already solvable by conventional divide-and-conquer QAOA while extending applicability to previously unsupported graphs, and outperforming alternative full-coverage decomposition strategies. Noise simulations further show improved robustness arising from reduced entangling-gate requirements. These results establish FrozenLGP as a topology-robust front end for distributed QAOA on near-term quantum hardware.
• Abstract（参考訳）: 量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、量子デバイスにおける量子ビット容量を超えた組合せ最適化問題を実行するための有望な経路を提供する。 しかし、既存のアプローチは小さな頂点分離器の存在に依存しており、そのような分解が存在しないような密あるいは高連結なグラフに完全に失敗する。 本稿では,Frozen Large Graph Partitioning (FrozenLGP)を紹介した。 標準的なパーティショニングが失敗すると、FrozenLGPは最大フローに基づく最小頂点カット計算によって最小限の妨害頂点を識別し、古典的にはスピン割り当てを凍結する。 除去された相互作用のエネルギー的寄与は、隣接する活性量子ビットのイジング・ハミルトニアンにおいて、それらを線型バイアス項に折り畳むことで厳密に保存される。 グラフのサイズは最大10,000の頂点と複数のトポロジーファミリーにまたがるが、FrozenLGPは100\%の分解カバレッジを達成している。 エンドツーエンドのMaxCut実験では、FrozenLGPは従来の分割およびコンカレントQAOAで解決可能なインスタンス上での近似品質を保ちつつ、前述したグラフへの適用性を拡張し、代替のフルカバレッジ分解戦略より優れていることを示した。 騒音シミュレーションは、エンタングゲート要求の低減に起因するロバスト性をさらに向上させる。 これらの結果から、FrozenLGPは、短期量子ハードウェア上の分散QAOAのトポロジロバストフロントエンドとして確立される。

関連論文リスト

• 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)
• Neural QAOA$^{2}$: Differentiable Joint Graph Partitioning and Parameter Initialization for Quantum Combinatorial Optimization [3.7086487199744127]
  本稿では,グラフ分割と初期パラメータを協調的に生成するエンドツーエンドの微分可能なフレームワークであるNeural QAOA$2$を提案する。 生成的評価ネットワーク(generative Evaluative Network, GEN)を統合することにより, 微分可能な量子評価器を高忠実度性能サロゲートとして利用する。 183 QUBO、Ising、MaxCutのインスタンス(21から1000変数)の実験は、勾配駆動のアプローチがベースラインを大きく上回ることを示した。
  論文  参考訳（メタデータ） (2026-05-13T06:43:10Z)
• Super-Level-Set Regression: Conditional Quantiles via Volume Minimization [46.298122008420414]
  我々はこの暗黙的な結合をうまく解決する新しい数学的枠組みであるスーパーレベル・セット・レグレッション(SLS)を導入する。 完全分布推定を回避し、フレキシブルな体積保存フロンティア関数を活用することにより、複素・多重モーダル・非共役条件構造をエンド・ツー・エンドにキャプチャする。
  論文  参考訳（メタデータ） (2026-05-07T13:14:45Z)
• Scalable Quantum Walk-Based Heuristics for the Minimum Vertex Cover Problem [0.0]
  連続時間量子ウォーク(CTQW)に基づく最小頂点被覆(MVC)問題に対する新しい量子アルゴリズムを提案する。 この枠組みでは、グラフ上の量子ウォーカーのコヒーレントな伝播は、その構造特性を状態振幅に符号化する。 我々は,CTQWに基づくアルゴリズムが優れた近似比を一貫して達成し,ネットワークトポロジに関して顕著な堅牢性を示すことを示す。
  論文  参考訳（メタデータ） (2025-12-02T17:04:57Z)
• Modified Recursive QAOA for Exact Max-Cut Solutions on Bipartite Graphs: Closing the Gap Beyond QAOA Limit [4.364124102844566]
  量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、MAX-CUT問題などの最適化問題を概ね解くことを目的として提案された量子古典ハイブリッドアルゴリズムである。 まず、二部グラフ上のMAX-CUT問題の解法におけるレベル1QAOAの性能限界を解析的に証明する。 第2に、再帰的QAOA(RQAOA)は、QAOAをサブルーチンとしてグラフサイズを削減し、レベル1のQAOAを上回る性能を示す。 最後に,制限パラメータを持つRQAOAが,これらの制約に完全に対処可能であることを示す。
  論文  参考訳（メタデータ） (2024-08-23T16:35:47Z)
• A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization [53.14532968909759]
  ALEXRと呼ばれる,効率的な単ループプリマル・デュアルブロック座標アルゴリズムを提案する。 本研究では, ALEXR の凸面および強凸面の収束速度を滑らか性および非滑らか性条件下で確立する。 CFCCO の ROC 曲線の下での GDRO および部分領域の実験結果から,提案アルゴリズムの有望な性能を示す。
  論文  参考訳（メタデータ） (2023-12-04T19:00:07Z)
• Nonconvex Stochastic Bregman Proximal Gradient Method with Application to Deep Learning [9.202586157819693]
  非合成対象函数のロバスト性を最小化する二次法は、典型的には微分可能部分のリプシッツ滑らか性に依存する。 本稿では適応性のみを考慮したBregman(SBPG)手法のファミリーを提案する。 MSBPGは運動量に基づく変種であり、ミニバッチサイズ要求を緩和することで収束感度を高める。
  論文  参考訳（メタデータ） (2023-06-26T08:54:46Z)
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation [0.23999111269325263]
  量子近似最適化アルゴリズム(QAOA)は、最適化問題を解くために用いられるハイブリッド量子古典アルゴリズムである。 QAOAはNISQデバイスに実装できるが、物理的制限は回路深さを制限し、性能を低下させる。 この研究は、より古典的なパラメータをアンサッツに割り当て、低深さでの性能を改善するeXpressive QAOA (XQAOA)を導入している。
  論文  参考訳（メタデータ） (2023-02-09T07:47:06Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。 キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。 オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
  論文  参考訳（メタデータ） (2023-02-08T08:17:43Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)

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

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