論文の概要: Quantum Alternating Operator Ansatz for Solving the Minimum Exact Cover
Problem
- arxiv url: http://arxiv.org/abs/2211.15266v1
- Date: Mon, 28 Nov 2022 12:45:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-17 15:09:18.667274
- Title: Quantum Alternating Operator Ansatz for Solving the Minimum Exact Cover
Problem
- Title(参考訳): 量子交互演算子アンザッツによる最小被覆問題の解法
- Authors: Sha-Sha Wang, Hai-Ling Liu, Su-Juan Qin, Fei Gao, and Qiao-Yan Wen
- Abstract要約: 量子交互演算子 ansatz (QAOA+) を用いて最小被覆(MEC)問題を解く。
数値計算の結果,アルゴリズムのレベル$p$が低い場合,高い確率で解が得られることがわかった。
また、1量子ビット回転ゲートを$R_Z$で除去することで量子回路を最適化する。
- 参考スコア(独自算出の注目度): 4.697039614904225
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The minimum exact cover (MEC) is a common combinatorial optimization problem,
with wide applications in tail-assignment and vehicle routing. In this paper,
we adopt quantum alternating operator ansatz (QAOA+) to solve MEC problem. In
detail, to obtain a trivial feasible solution, we first transform MEC into a
constrained optimization problem with two objective functions. Then, we adopt
the linear weighted sum method to solve the above constrained optimization
problem and construct the corresponding target Hamiltonian. Finally, to improve
the performance of this algorithm, we adopt parameters fixing strategy to
simulate, where the experimental instances are 6, 8, and 10 qubits. The
numerical results show that the solution can be obtained with high probability
when level $p$ of the algorithm is low. Besides, we optimize the quantum
circuit by removing single-qubit rotating gates $R_Z$. We found that the number
of quantum gates is reduced by $np$ for $p$-level optimized circuit.
Furthermore, $p$-level optimized circuit only needs $p$ parameters, which can
achieve an experimental effect similar to original circuit with $2p$
parameters.
- Abstract(参考訳): 最小完全被覆(MEC)は一般的な組合せ最適化問題であり、テールアサインメントや車両ルーティングに広く応用されている。
本稿では,MEC 問題を解くために量子交互演算子 ansatz (QAOA+) を用いる。
詳しくは、自明な実現可能な解を得るために、まずMECを2つの目的関数を持つ制約付き最適化問題に変換する。
そこで,線形重み付き和法を用いて上記の制約付き最適化問題を解き,対応する対象ハミルトニアンを構成する。
最後に,本アルゴリズムの性能向上のために,実験例が6,8,10キュービットである場合のシミュレーションにパラメータ固定方式を採用する。
数値計算の結果,アルゴリズムのレベル$p$が低い場合,高い確率で解が得られることがわかった。
さらに、シングルキュービット回転ゲート$r_z$を除去して量子回路を最適化する。
量子ゲートの数は$np$ for $p$レベルの最適化回路で減少することがわかった。
さらに、$p$レベル最適化回路は$p$パラメータしか必要とせず、$p$パラメータを持つオリジナル回路と同様の実験的な効果を実現できる。
関連論文リスト
- Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping [3.47862118034022]
我々は,ある種の雑音を利用して二項最適化問題を解くメタアルゴリズムであるemphNoise-Directed Adaptive Remapping (NDAR)を提案する。
我々は,Rigetti Computingの超伝導デバイスAnkaa-2の最新世代のサブシステムを用いた実験において,プロトコルの有効性を実証する。
論文 参考訳(メタデータ) (2024-04-01T18:28:57Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳(メタデータ) (2024-01-17T18:59:38Z) - The Quantum Approximate Optimization Algorithm performance with low
entanglement and high circuit depth [0.0]
変分量子アルゴリズムは、現在の雑音量子コンピュータを使用する最も広範な方法の1つである。
最適化問題の解法における絡み合いの役割について検討する。
ここでは, 絡み合いが MaxCut と Exact Cover 3 問題において軽微な役割を担っていると結論づける。
論文 参考訳(メタデータ) (2022-07-07T16:21:36Z) - 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) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文 参考訳(メタデータ) (2022-03-01T19:47:16Z) - Unsupervised strategies for identifying optimal parameters in Quantum
Approximate Optimization Algorithm [3.508346077709686]
最適化なしでパラメータを設定するための教師なし機械学習手法について検討する。
繰り返しに使用するQAOAパラメータの数が3ドルに制限された場合、これらをRecursive-QAOAで3ドルまで紹介します。
我々は、アングルを広範囲に最適化し、多数のサーキットコールを省く場合と同じような性能を得る。
論文 参考訳(メタデータ) (2022-02-18T19:55:42Z) - Efficiently Solve the Max-cut Problem via a Quantum Qubit Rotation
Algorithm [7.581898299650999]
我々はQQRA(Quantum Qubit Rotation Algorithm)という単純なアルゴリズムを導入する。
最大カット問題の近似解は 1 に近い確率で得られる。
我々は、よく知られた量子近似最適化アルゴリズムと古典的なゲーマン・ウィリアムソンアルゴリズムと比較する。
論文 参考訳(メタデータ) (2021-10-15T11:19:48Z) - Globally optimizing QAOA circuit depth for constrained optimization
problems [0.2609784101826761]
我々は、最適化問題における$n$-variable monomialsを、より少ない変数におけるmonomialsを持つ等価なインスタンスに還元するグローバル変数置換法を開発した。
量子近似最適化アルゴリズムを用いて、削減された問題を解くために必要な最適量子回路深さを解析する。
論文 参考訳(メタデータ) (2021-08-06T19:25:45Z) - Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
Variisyハイブリッド量子古典アルゴリズムは、ノイズ中間量子デバイスの使用を最大化する強力なツールである。
我々は、変分量子アルゴリズムで使用されるそのようなアンサーゼを「効率的な回路訓練」(PECT)と呼ぶ戦略を提案する。
すべてのアンサッツパラメータを一度に最適化する代わりに、PECTは一連の変分アルゴリズムを起動する。
論文 参考訳(メタデータ) (2020-10-01T18:14:11Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳(メタデータ) (2020-06-11T17:43:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。