論文の概要: QAOA with random and subgraph phase operators
- arxiv url: http://arxiv.org/abs/2402.18412v2
- Date: Mon, 18 Mar 2024 15:00:09 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-20 23:01:00.203943
- Title: QAOA with random and subgraph phase operators
- Title(参考訳): ランダム位相演算子とサブグラフ位相演算子を用いたQAOA
- Authors: Anthony Wilkie, Igor Gaidai, James Ostrowski, Rebekah Herrman,
- Abstract要約: カスタム位相演算子と呼ばれる通常のコスト以外のハミルトニアンの使用がQAOAの性能に与える影響について検討する。
これらのカスタム位相演算子のいくつかは、元のアルゴリズムの実装よりも高い近似比を達成可能であることを数値的に示す。
- 参考スコア(独自算出の注目度): 1.8749305679160366
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The quantum approximate optimization algorithm (QAOA) is a promising quantum algorithm that can be used to approximately solve combinatorial optimization problems. The usual QAOA ansatz consists of an alternating application of the cost and mixer Hamiltonians. In this work, we study how using Hamiltonians other than the usual cost Hamiltonian, dubbed custom phase operators, can affect the performance of QAOA. We derive an expected value formula for QAOA with custom phase operators at p = 1 and show numerically that some of these custom phase operators can achieve higher approximation ratio than the original algorithm implementation. Out of all the graphs tested, 0.036\% of the random custom phase operators, 75.9\% of the subgraph custom phase operators, 95.1\% of the triangle-removed custom phase operators, and 93.9\% of the maximal degree edge-removed custom phase operators have a higher approximation ratio than the original QAOA implementation. This finding opens up the question of whether better phase operators can be designed to further improve the performance of QAOA.
- Abstract(参考訳): 量子近似最適化アルゴリズム(QAOA)は、組合せ最適化問題を解くのに使える有望な量子アルゴリズムである。
通常のQAOAアンザッツは、コストとミキサーハミルトンの交互に応用される。
本研究では,従来のコストであるハミルトン演算子以外のハミルトニアンの使用がQAOAの性能に与える影響について検討する。
p = 1のカスタム位相演算子を持つQAOAの期待値式を導出し、これらのカスタム位相演算子のうちいくつかが元のアルゴリズムよりも高い近似比を達成できることを数値的に示す。
テストされた全てのグラフのうち、ランダムなカスタム位相演算子の0.036\%、サブグラフのカスタム位相演算子の75.9\%、三角形を除去したカスタム位相演算子の95.1\%、最大次エッジを除去したカスタム位相演算子の93.9\%は、元のQAOA実装よりも高い近似比を持つ。
この発見は、QAOAの性能をさらに向上させるために、より良い位相演算子を設計できるかどうかという疑問を提起する。
関連論文リスト
- Proactively incremental-learning QAOA [9.677961025372115]
逐次学習に基づく量子近似最適化アルゴリズム(QAOA)を提案する。
本手法は, 近似比(AR)とトレーニング時間において, 一般的なQAOAよりも優れた性能を有する。
論文 参考訳(メタデータ) (2023-11-04T02:15:26Z) - Amplitude amplification-inspired QAOA: Improving the success probability
for solving 3SAT [55.78588835407174]
振幅増幅アルゴリズムは、可変代入を満たすために非構造化探索に適用することができる。
Quantum Approximate Optimization Algorithm (QAOA)は、ノイズのある中間量子デバイスのための3SATを解くための有望な候補である。
振幅増幅によるQAOAの変種を導入し、3SATの成功確率を改善する。
論文 参考訳(メタデータ) (2023-03-02T11:52:39Z) - A Parameter Setting Heuristic for the Quantum Alternating Operator
Ansatz [0.0]
本稿では,問題の大きさに応じて異なるコスト値の数が増加する場合に適したパラメータ設定戦略を提案する。
我々は、完全均一性が正確に保持され、状態と期待値の両方を記述する情報が得られるQAOAの古典的同次プロキシを定義する。
最大3ドルのQAOAレベルでは、これまでのグローバルに最適化されたアプローチによって返される近似比にマッチするパラメータを容易に見つけることができます。
論文 参考訳(メタデータ) (2022-11-17T00:18:06Z) - 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) - Quantum Approximate Optimization Algorithm with Sparsified Phase
Operator [5.578620080495951]
目的関数を符号化する位相演算子の代わりに、代替位相演算子を実装するための簡単な方法が利用できることを示す。
本稿では,QAOAの資源要求を緩和するスパーシフィケーション戦略を提案する。
論文 参考訳(メタデータ) (2022-04-30T00:36:49Z) - 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) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳(メタデータ) (2021-06-22T11:07:38Z) - Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。
任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文 参考訳(メタデータ) (2020-11-26T18:22:21Z) - Evaluation of QAOA based on the approximation ratio of individual
samples [0.0]
我々は、Max-Cut問題に適用されたQAOAの性能をシミュレートし、いくつかの古典的代替品と比較する。
QAOA計算複雑性理論のガイダンスが進化しているため、量子的優位性を求めるためのフレームワークを利用する。
論文 参考訳(メタデータ) (2020-06-08T18:00:18Z) - Differentiable Top-k Operator with Optimal Transport [135.36099648554054]
SOFTトップk演算子は、エントロピック最適輸送(EOT)問題の解として、トップk演算の出力を近似する。
提案した演算子をk-アネレスト近傍およびビーム探索アルゴリズムに適用し,性能向上を示す。
論文 参考訳(メタデータ) (2020-02-16T04:57:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。