論文の概要: Improving QAOA to find approximate QUBO solutions in O(1) shots

• arxiv url: http://arxiv.org/abs/2509.19035v1
• Date: Tue, 23 Sep 2025 14:07:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-24 20:41:27.883288
• Title: Improving QAOA to find approximate QUBO solutions in O(1) shots
• Title（参考訳）: O(1)ショットにおける近似QUBO解探索のためのQAOAの改良
• Authors: A. Yu. Chernyavskiy, D. A. Kulikov, B. I. Bantysh, Yu. I. Bogdanov, A. K. Fedorov, E. O. Kiktenko,
• Abstract要約: 本稿では,目標近似比(AR)を達成する確率を,正確な最適化を必要とせず考慮した修正fpQAOA方式を提案する。 この組み合わせは、問題の大きさが大きくなるにつれて、近似解を得るために必要なショットの中央値の減少につながることを実証する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum Approximate Optimization Algorithm (QAOA) provides one of the most promising quantum frameworks for addressing discrete optimization problems with broad real-world applications, particularly quadratic unconstrained binary optimization (QUBO) problems. However, the widely used hybrid quantum--classical implementation faces significant challenges due to statistical noise and barren plateaus. A prominent approach to mitigate these issues is fixed-point QAOA (fpQAOA), where circuit parameters are trained on small problem instances and subsequently transferred to larger ones. In this work, we develop a modified fpQAOA scheme that combines (i) considering the probability of achieving a target approximation ratio (AR) rather than requiring the exact optimum, (ii) setting the number of layers equal to the problem size with the sine--cosine encoding of QAOA angles, and (iii) rescaling the problem coefficient matrices to unit Frobenius norm. We demonstrate that this combination leads to a decreasing median number of shots required to obtain approximate solutions as the problem size increases, with ARs being within a few percent from the optimum for the considered problem classes. Extrapolation of these results suggests an $O(1)$ shot complexity while retaining at most quadratic circuit depth, underscoring the potential of our approach to overcome key bottlenecks in QAOA implementations and scalability estimations. Remarkably, omitting even a single one of the modifications (i)--(iii) results in exponential growth of the number of shots required as the problem size increases.
• Abstract（参考訳）: 量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、より広い現実世界のアプリケーション、特に2次非制約バイナリ最適化(QUBO)問題における離散最適化問題に対処するための最も有望な量子フレームワークの1つである。 しかし、広く使われているハイブリッド量子-古典的な実装は、統計ノイズと不規則な高原のために大きな課題に直面している。 これらの問題を緩和するための顕著なアプローチは固定点QAOA(fpQAOA)である。 本研究は,fpQAOAを組み込んだ改良型fpQAOAスキームの開発である。 一 正確な最適化を必要とせず、目標近似比(AR)を達成する確率を考慮すること。 (二)QAOA角の正弦符号で問題の大きさに等しい層数を設定すること。 3) 問題係数行列を単位フロベニウスノルムに再スケーリングする。 この組み合わせによって、問題の大きさが大きくなるにつれて、近似解を得るのに必要なショットの中央値が減少し、ARは検討された問題クラスの最適値から数パーセント以内に収まることが実証された。 これらの結果の補間により、QAOA実装における重要なボトルネックとスケーラビリティ推定を克服するための我々のアプローチの可能性を強調しつつ、ほとんどの二次回路深さを維持しながら、$O(1)$ショットの複雑さが示唆された。 注目すべきは、修正の1つでも省略すること。 (i)-- 3) 問題の大きさが大きくなるにつれて, 必要なショット数が指数関数的に増加する。

関連論文リスト

• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems [3.757262277494307]
  本稿では,量子近似最適化Ansatzのための制約符号化手法の新たな組み合わせを提案する。 ワンホット制約は、検索空間を実現可能なサブ空間に自然に制限する$XY$-mixerによって強制される。 XY$-mixersは検索スペースを制限するため、特定の状態ベクトルエントリは常にゼロであり、シミュレーションから省略することができ、貴重なメモリとコンピューティングリソースを節約できる。
  論文  参考訳（メタデータ） (2025-06-03T17:46:53Z)
• Solving Constrained Combinatorial Optimization Problems with Variational Quantum Imaginary Time Evolution [4.266376725904727]
  本稿では,VarQITEが従来の手法に比べて平均最適性ギャップを著しく小さくすることを示す。 ハミルトニアンのスケーリングにより、最適化コストをさらに削減し、収束を加速できることを実証する。
  論文  参考訳（メタデータ） (2025-04-17T03:09:37Z)
• Distributed Quantum Approximate Optimization Algorithm on a Quantum-Centric Supercomputing Architecture [1.953969470387522]
  量子近似最適化アルゴリズム(QAOA)は、ゲートベースの量子コンピューティングシステムに量子スピードアップを提供することで、最適化問題を解くことを約束している。 しかしQAOAは、大量の量子ビットと深部回路の複雑さのため、高次元問題に対する課題に直面している。 本稿では,分散QAOA(DQAOA)を,より少ないキュービットと浅い回路を必要とするタスクに分割する。
  論文  参考訳（メタデータ） (2024-07-29T17:42:25Z)
• Evaluating the Practicality of Quantum Optimization Algorithms for Prototypical Industrial Applications [44.88678858860675]
  本稿では,量子近似最適化アルゴリズム (QAOA) と量子断熱アルゴリズム (QAA) の応用について検討する。 我々は,これらの2つのアルゴリズムの性能を,選択した評価指標を用いて,ソリューションの品質の観点から比較する。
  論文  参考訳（メタデータ） (2023-11-20T09:09:55Z)
• Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios [0.0]
  本稿では、QAOAに必要なラウンド数(QAOAランタイムの主成分)について、最初の低い係数をいくつか提示する。 従来の横フィールドミキサーの場合、(iv)我々のフレームワークは、すべての有界共起局所コスト問題に自明な下限を与える。 厳密には$k$-local cost Hamiltonian matching known results that constant approximation ratio is obtained with a constant-round QAOA。
  論文  参考訳（メタデータ） (2023-08-29T17:10:20Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。 超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。 数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
  論文  参考訳（メタデータ） (2022-09-27T17:56:15Z)
• 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)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。 問題の大きさと問題グラフの次数で指数関数的に増大する。 これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
  論文  参考訳（メタデータ） (2022-01-06T21:02:30Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)

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

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