論文の概要: Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State
Preparation
- arxiv url: http://arxiv.org/abs/2006.00354v2
- Date: Fri, 2 Oct 2020 21:02:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-17 22:38:21.627552
- Title: Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State
Preparation
- Title(参考訳): QAOA用グラバーミキサー:ミキサ設計から状態形成への複雑さのシフト
- Authors: Andreas B\"artschi and Stephan Eidenbenz
- Abstract要約: 本稿では,Grover 様選択位相シフト混合演算子を用いた量子交互演算子 Ansatz (QAOA) の変種を提案する。
GM-QAOA は任意のNP最適化問題に取り組み、全ての実現可能な解の同値な重ね合わせを効率的に作成することができる。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose GM-QAOA, a variation of the Quantum Alternating Operator Ansatz
(QAOA) that uses Grover-like selective phase shift mixing operators. GM-QAOA
works on any NP optimization problem for which it is possible to efficiently
prepare an equal superposition of all feasible solutions; it is designed to
perform particularly well for constraint optimization problems, where not all
possible variable assignments are feasible solutions. GM-QAOA has the following
features: (i) It is not susceptible to Hamiltonian Simulation error (such as
Trotterization errors) as its operators can be implemented exactly using
standard gate sets and (ii) Solutions with the same objective value are always
sampled with the same amplitude.
We illustrate the potential of GM-QAOA on several optimization problem
classes: for permutation-based optimization problems such as the Traveling
Salesperson Problem, we present an efficient algorithm to prepare a
superposition of all possible permutations of $n$ numbers, defined on $O(n^2)$
qubits; for the hard constraint $k$-Vertex-Cover problem, and for an
application to Discrete Portfolio Rebalancing, we show that GM-QAOA outperforms
existing QAOA approaches.
- Abstract(参考訳): 我々は、グローバー様選択位相シフト混合演算子を用いた量子交流作用素 ansatz (qaoa) の変種 gm-qaoa を提案する。
GM-QAOAは、全ての実現可能な解を効率的に重ね合わせることができるNP最適化問題に取り組み、可能変数の割り当てが実現可能な解ではないような制約最適化問題に対して特にうまく機能するように設計されている。
GM-QAOAには以下の機能がある。
(i)その作用素は標準ゲート集合を用いて正確に実装できるため、ハミルトニアンシミュレーション誤差(ロータライズ誤差など)に影響を受けない。
(ii)同じ目的値の解は常に同じ振幅でサンプリングされる。
いくつかの最適化問題クラスにおけるGM-QAOAの可能性について説明する: トラベリングセールスパーソン問題のような置換に基づく最適化問題に対して、$O(n^2)$ qubitsで定義された$n$数値の可能な全ての置換を重畳する効率的なアルゴリズムを提案する; ハード制約の$k$-Vertex-Cover問題に対して、 GM-QAOAが既存のQAOAアプローチより優れていることを示す。
関連論文リスト
- Variational quantum algorithm-preserving feasible space for solving the
uncapacitated facility location problem [3.3682090109106446]
本稿では,変分量子アルゴリズムで実現可能な空間(VQA-PFS)アンサッツを提案する。
このアンザッツは制約変数に混合演算子を適用し、非制約変数にハードウェア効率アンザッツ(HEA)を用いる。
その結果, VQA-PFSは成功確率を著しく向上し, より高速な収束を示すことがわかった。
論文 参考訳(メタデータ) (2023-12-12T01:36:49Z) - Graph-controlled Permutation Mixers in QAOA for the Flexible Job-Shop
Problem [0.0]
Quantum Alternating Operator Ansatzは制約付き最適化ソリューションのためのアルゴリズムフレームワークを提供する。
既知の標準QAOAプロトコルとは対照的に、最適化問題の制約はアンザッツ回路の混合層に組み込まれている。
フレキシブルなジョブショップ問題を含む幅広いスケジューリング問題に対する混合演算子を開発した。
論文 参考訳(メタデータ) (2023-11-07T16:16:52Z) - Variational Amplitude Amplification for Solving QUBO Problems [0.0]
本研究は、キュービット重畳状態に適したQUBO問題に焦点をあてる。
我々は、QUBOをコストオラクルの演算として符号化する回路設計を、標準Grover拡散演算子$U_textrms$と組み合わせると、最適および近似最適解に対応する状態の測定確率が高くなることを示す。
論文 参考訳(メタデータ) (2023-01-31T14:33:40Z) - Unbalanced penalization: A new approach to encode inequality constraints
of combinatorial problems for quantum optimization algorithms [58.720142291102135]
余分なスラック変数を必要としない代替手法を提案する。
我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。
この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
論文 参考訳(メタデータ) (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) - Free Job-Shop Scheduling With Hardcoded Constraints [0.0]
同様に構築されたミキサーの所望の特性は、純粋に古典的な対象に直接リンク可能であることを示す。
より自然にグループ構造を組み込む新しい変分量子アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-11-10T19:25:20Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳(メタデータ) (2022-06-30T03:15:23Z) - 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) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。
我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。
我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
論文 参考訳(メタデータ) (2022-03-11T17:19:26Z) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文 参考訳(メタデータ) (2022-03-01T19:47:16Z) - Threshold-Based Quantum Optimization [0.0]
Th-QAOA(Threshold QAOA)は、量子交互演算子Ansatz(QAOA)の変種である。
GM-Th-QAOAをGroverの量子探索アルゴリズムの一般化と見なすことができる。
論文 参考訳(メタデータ) (2021-06-25T19:36:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。