論文の概要: Quantum approximate optimization algorithm with random and subgraph phase operators
- arxiv url: http://arxiv.org/abs/2402.18412v3
- Date: Wed, 30 Oct 2024 21:13:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-01 16:56:38.138722
- Title: Quantum approximate optimization algorithm with random and subgraph phase operators
- Title（参考訳）: ランダム位相演算子とサブグラフ位相演算子を用いた量子近似最適化アルゴリズム
- Authors: Anthony Wilkie, Igor Gaidai, James Ostrowski, Rebekah Herrman,
- Abstract要約: カスタム位相演算子と呼ばれる通常のコスト以外のハミルトニアンの使用がQAOAの性能に与える影響について検討する。
これらのカスタム位相演算子のいくつかは、元のアルゴリズムの実装よりも高い近似比を達成可能であることを数値的に示す。
- 参考スコア（独自算出の注目度）: 1.8749305679160366
- License:
- 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 at $p=1$, 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. Furthermore, we numerically simulate these phase operators for $p=2$ and $p=3$ levels of QAOA and find that there exist a large number of subgraph, triangle-removed, and maximal degree edge-removed custom phase operators that have a higher approximation ratio than QAOA at the same depth. These findings open up the question of whether better phase operators can be designed to further improve the performance of QAOA.
- Abstract（参考訳）: 量子近似最適化アルゴリズム(QAOA)は、組合せ最適化問題を解くのに使える有望な量子アルゴリズムである。
通常のQAOAアンザッツは、コストとミキサーハミルトンの交互に応用される。
本研究では,従来のコストであるハミルトン演算子以外のハミルトニアンの使用がQAOAの性能に与える影響について検討する。
我々は、QAOAの期待値式を、カスタム位相演算子の$p = 1$で導き、これらのカスタム位相演算子のいくつかが元のアルゴリズム実装よりも高い近似比を達成できることを数値的に示す。
p=1$で試験された全てのグラフのうち、ランダムなカスタム位相演算子の0.036\%、サブグラフのカスタム位相演算子の75.9\%、三角形を除去したカスタム位相演算子の95.1\%、および最大次エッジを除去したカスタム位相演算子の93.9\%は、元のQAOA実装よりも高い近似比を持つ。
さらに、これらの位相演算子をQAOAの$p=2$および$p=3$レベルで数値的にシミュレートし、同じ深さでQAOAよりも高い近似比を持つ、多くの部分グラフ、三角形除去および最大次エッジ除去されたカスタム位相演算子が存在することを確認する。
これらの結果から,QAOAの性能向上のために,より優れた位相演算子を設計できるかどうかという疑問が浮かび上がっている。
関連論文リスト
- Optimal Coherent Quantum Phase Estimation via Tapering [0.0]
量子位相推定は、多くの量子アルゴリズムを支える基本的なプリミティブの1つである。
我々は,テープ型量子位相推定アルゴリズムと呼ばれる標準アルゴリズムの改良版を提案する。
提案アルゴリズムは,高コストなコヒーレント中央値手法を必要とせず,最適なクエリ複雑性を実現する。
論文 参考訳（メタデータ） (2024-03-27T18:17:23Z) - Proactively incremental-learning QAOA [9.677961025372115]
逐次学習に基づく量子近似最適化アルゴリズム(QAOA)を提案する。
本手法は, 近似比(AR)とトレーニング時間において, 一般的なQAOAよりも優れた性能を有する。
論文 参考訳（メタデータ） (2023-11-04T02:15:26Z) - Alignment between Initial State and Mixer Improves QAOA Performance for
Constrained Optimization [11.445200448951072]
量子交互演算子 ansatz (QAOA) は断熱アルゴリズムと強い関係を持つ。
本稿では, 断熱アルゴリズムの直感がQAOA初期状態を選択するタスクに適用できることを実証する。
論文 参考訳（メタデータ） (2023-05-05T21:54:28Z) - 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) - Reducing the Variance of Gaussian Process Hyperparameter Optimization
with Preconditioning [54.01682318834995]
プレコンディショニングは、行列ベクトル乗算を含む反復的な方法にとって非常に効果的なステップである。
プレコンディショニングには、これまで検討されていなかった付加的なメリットがあることを実証する。
基本的に無視可能なコストで、同時に分散を低減することができる。
論文 参考訳（メタデータ） (2021-07-01T06:43:11Z) - 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) - Differentiable Top-k Operator with Optimal Transport [135.36099648554054]
SOFTトップk演算子は、エントロピック最適輸送(EOT)問題の解として、トップk演算の出力を近似する。
提案した演算子をk-アネレスト近傍およびビーム探索アルゴリズムに適用し,性能向上を示す。
論文 参考訳（メタデータ） (2020-02-16T04:57:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。