論文の概要: Convergence guarantee for linearly-constrained combinatorial optimization with a quantum alternating operator ansatz

• arxiv url: http://arxiv.org/abs/2409.18829v1
• Date: Fri, 27 Sep 2024 15:23:47 GMT
• ステータス: 処理完了
• システム内更新日: 2024-10-01 09:08:34.809060
• Title: Convergence guarantee for linearly-constrained combinatorial optimization with a quantum alternating operator ansatz
• Title（参考訳）: 量子交互演算子アンザッツを用いた線形制約付き組合せ最適化の収束保証
• Authors: Brayden Goldstein-Gelb, Phillip C. Lotshaw,
• Abstract要約: 線形に制約された最適化問題のクラスを解く量子交互演算子アンサッツ(QAOA$+$)を提案する。 このクラスの問題に対して、回路層数が増加するにつれて、最適解に確実に収束する回路を考案する。 この分析はQAOA$+$の性能保証を線形に制約された問題のより一般的な集合に拡張し、将来の一般化のためのツールを提供する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We present a quantum alternating operator ansatz (QAOA$^+$) that solves a class of linearly constrained optimization problems by evolving a quantum state within a Hilbert subspace of feasible problem solutions. Our main focus is on a class of problems with a linear constraint containing sequential integer coefficients. For problems in this class, we devise QAOA$^+$ circuits that provably converge to the optimal solution as the number of circuit layers increases, generalizing previous guarantees for solving unconstrained problems or problems with symmetric constraints. Our approach includes asymmetric ``mixing" Hamiltonians that drive transitions between feasible states, as well as a method to incorporate an arbitrary known feasible solution as the initial state, each of which can be applied beyond the specific linear constraints considered here. This analysis extends QAOA$^+$ performance guarantees to a more general set of linearly-constrained problems and provides tools for future generalizations.
• Abstract（参考訳）: 本稿では,Hilbert部分空間内で量子状態を進化させることにより,線形に制約された最適化問題のクラスを解く量子交互演算子アンサッツ(QAOA$^+$)を提案する。 我々の主な焦点は、逐次整数係数を含む線形制約を持つ問題のクラスである。 このクラスの問題に対して、回路層の数が増えるにつれて最適解に確実に収束するQAOA$^+$回路を考案し、制約のない問題や対称制約のある問題を解くための以前の保証を一般化する。 我々のアプローチには、実現可能な状態間の遷移を駆動する非対称な「混合」ハミルトニアンと、任意の既知の実現可能な解を初期状態として組み込む方法が含まれており、これらはここで考慮される特定の線形制約を越えて適用することができる。 この分析はQAOA$^+$性能保証を線形制約された問題のより一般的な集合に拡張し、将来の一般化のためのツールを提供する。

関連論文リスト

• Cons-training tensor networks [2.8834278113855896]
  テンソルネットワークと呼ばれる新しいファミリーを導入する。 textitconstrained matrix product state (MPS) これらのネットワークは、不等式を含むちょうど任意の離散線型制約をスパースブロック構造に含んでいる。 これらのネットワークは、特に、可能空間上で厳密にサポートされた分散をモデル化するために調整されている。
  論文  参考訳（メタデータ） (2024-05-15T00:13:18Z)
• Symmetries and Dimension Reduction in Quantum Approximate Optimization Algorithm [1.3469999282609788]
  我々は、$n-要素$d$-ary文字列の集合上で定義される最適化問題の一般化された定式化に焦点を当てる。 我々の主な貢献は、当初提案されたQAOAの次元を含む。 アルゴリズムをより小さな次元の空間に制限することは、回路の量子シミュレーションと古典シミュレーションの両方を著しく加速させる可能性がある。
  論文  参考訳（メタデータ） (2023-09-25T00:35:40Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。 ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
  論文  参考訳（メタデータ） (2023-05-28T06:33:37Z)
• 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)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Modeling Linear Inequality Constraints in Quadratic Binary Optimization for Variational Quantum Eigensolver [0.0]
  本稿では, 変分量子固有解法における配向型変分形式の利用について紹介する。 通常、いくつかの最適化問題に現れる4つの制約がモデル化されている。 提案手法の主な利点は、変分形式のパラメータの数が一定であることである。
  論文  参考訳（メタデータ） (2020-07-26T23:36:22Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Constructing Driver Hamiltonians for Optimization Problems with Linear Constraints [0.0]
  我々は、線形制約を持つハミルトニアンの可換性について推論するための単純で直感的なフレームワークを開発する。 ユニタリ作用素はエルミート作用素の指数関数であるため、これらの結果は量子交互作用素アンザッツフレームワークにおけるミキサーの構成にも適用できる。
  論文  参考訳（メタデータ） (2020-06-22T06:47:50Z)

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

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