論文の概要: Recursive Quantum Alternating Operator Ansatz
- arxiv url: http://arxiv.org/abs/2611.17537v1
- Date: Thu, 12 Nov 2026 21:48:41 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-16 18:43:16.264117
- Title: Recursive Quantum Alternating Operator Ansatz
- Title(参考訳): 再帰的量子交互演算子アンザッツ
- Abstract要約: 我々は、量子交互演算子アンサッツに基づいて量子近似最適化アルゴリズム(RQAOA)を制約付き問題に拡張する。
提案手法は,再帰的でないQAOAと罰則に基づくQAOAとRQAOAの両方より優れていることを示す。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The recursive quantum approximate optimisation algorithm~(RQAOA) shrinks an unconstrained combinatorial optimisation problem by eliminating one variable at a time, guided by correlations measured in variational quantum states. We extend this recursion to constrained problems by building on the quantum alternating operator ansatz, which restricts the evolution to feasible solutions through a feasible initial state and feasibility-preserving mixers. However, every elimination alters the feasibility structure, so that such a mixer for the original problem generally fails to be one for the subproblems. Previous extensions to Maximum Independent Set and Minimum Vertex Cover sidestep this with tailored reduction rules that keep every subproblem within the original problem class. We resolve this by identifying, for a given constraint structure, a broader problem class that is closed under all eliminations, and by efficiently constructing feasible initial states and feasibility-preserving mixers for every class member. We do so for monotone constraints, such as for the knapsack problem, for linear equality constraints with polynomially bounded weights, including Hamming weight constraints, and for combinations of equality constraints with a single inequality constraint, such as the cardinality-constrained knapsack problem. Conversely, we show that these restrictions cannot be lifted in general without leaving the realm of efficient constructions. Exact simulations on knapsack and vertex-weighted max-bisection instances demonstrate that our recursive scheme can outperform both its non-recursive counterpart and penalty-based QAOA and RQAOA.
- Abstract(参考訳): 再帰的量子近似最適化アルゴリズム~(RQAOA)は、変動量子状態で測定された相関によって導かれる1つの変数を一度に排除することで、制約のない組合せ最適化問題を縮小する。
我々は、この再帰を量子交互演算子アンザッツ上に構築することで制限された問題に拡張し、実現可能な初期状態と実現可能な保存ミキサーを通して実現可能な解への進化を制限する。
しかし、全ての除去は実現可能性構造を変化させるため、元の問題に対するそのような混合器は一般にサブプロブレムに対するものであることに失敗する。
最大独立集合と最小頂点被覆の以前の拡張は、全てのサブプロブレムを元の問題クラス内に保持する調整された還元規則でこれを横取りする。
我々は、与えられた制約構造に対して、すべての排除の下で閉じたより広い問題クラスを特定し、全てのクラスメンバーに対して実行可能な初期状態と保存可能なミキサーを効率的に構築することで、これを解決する。
我々は、knapsack問題のような単調制約、ハミングウェイト制約を含む多項式有界重み付き線型等式制約、および濃度制約付きknapsack問題のような単一の不等式制約との等式制約の組み合わせに対してそうする。
逆に、これらの制約は、効率的な構築の領域を残さずに、一般的には解除できないことを示す。
knapsackとvertex-weighted max-bisectionインスタンスの厳密なシミュレーションにより、再帰的スキームは、非再帰的かつペナルティに基づくQAOAとRQAOAの両方より優れていることが示された。
関連論文リスト
- Pure and mixed Dicke state ansatz for equality and inequality constraints in variational quantum eigensolver [0.0]
組合せ最適化は、変分量子アルゴリズムによる量子コンピューティングに対処することができる。
中心的な課題は、最適解が存在するヒルベルト空間の可能な部分空間を探索するのに十分なアンザッツ表現を設計することである。
本研究では,ハミング重み制約最適化のための最初の実現可能性保存混合ディック状態アンサッツを提案する。
論文 参考訳(メタデータ) (2026-06-07T08:10:09Z) - Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。
既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。
これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
論文 参考訳(メタデータ) (2025-04-21T17:15:48Z) - Convergence guarantee for linearly-constrained combinatorial optimization with a quantum alternating operator ansatz [0.0]
線形に制約された最適化問題のクラスを解く量子交互演算子アンサッツ(QAOA$+$)を提案する。
このクラスの問題に対して、回路層数が増加するにつれて、最適解に確実に収束する回路を考案する。
この分析はQAOA$+$の性能保証を線形に制約された問題のより一般的な集合に拡張し、将来の一般化のためのツールを提供する。
論文 参考訳(メタデータ) (2024-09-27T15:23:47Z) - Imposing Constraints on Driver Hamiltonians and Mixing Operators: From Theory to Practical Implementation [0.0]
制約を満たすドライバー・ハミルトンと混合作用素は、多くの量子アルゴリズムにおけるアンサッツ構成の重要な部分である。
我々は、ハミルトン項を見つけるための一般代数式と、制約埋め込みを満たす類似のユニタリプリミティブを与える。
次に、これらのプリミティブをハミルトンドライバとユニタリミキサーに変換し、量子アニーリング(CQA)と量子交換演算子アンザッツ(QAOA)の構成に使用できるアルゴリズム的な手順を提案する。
論文 参考訳(メタデータ) (2024-07-02T06:23:02Z) - Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions [18.086061048484616]
平衡問題の幅広いクラスをモデル化した有限サム単調包含問題について検討する。
我々の主な貢献は、複雑性の保証を改善するために分散還元を利用する古典的ハルパーン反復の変種である。
我々は、この複雑さが単調なリプシッツ設定では改善できないと論じる。
論文 参考訳(メタデータ) (2023-10-04T17:24:45Z) - Approximation of optimization problems with constraints through kernel
Sum-Of-Squares [77.27820145069515]
我々は、点的不等式が非負の kSoS 関数のクラス内で等式となることを示す。
また, 等式制約に焦点をあてることで, 散乱不等式を用いることで, 制約のサンプリングにおける次元性の呪いを軽減することができることを示す。
論文 参考訳(メタデータ) (2023-01-16T10:30:04Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
余分なスラック変数を必要としない代替手法を提案する。
我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。
この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
論文 参考訳(メタデータ) (2022-11-25T06:05:18Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳(メタデータ) (2022-11-16T18:59:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。