論文の概要: An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
- arxiv url: http://arxiv.org/abs/2302.04479v2
- Date: Thu, 15 Feb 2024 07:00:30 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-17 00:24:35.737310
- Title: An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
- Title(参考訳): 低次元量子近似最適化のための表現型アンサッツ
- Authors: V. Vijendran, Aritra Das, Dax Enshan Koh, Syed M. Assad, Ping Koy Lam
- Abstract要約: 量子近似最適化アルゴリズム(QAOA)は、最適化問題を解くために用いられるハイブリッド量子古典アルゴリズムである。
QAOAはNISQデバイスに実装できるが、物理的制限は回路深さを制限し、性能を低下させる。
この研究は、より古典的なパラメータをアンサッツに割り当て、低深さでの性能を改善するeXpressive QAOA (XQAOA)を導入している。
- 参考スコア(独自算出の注目度): 0.23999111269325263
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The quantum approximate optimisation algorithm (QAOA) is a hybrid
quantum-classical algorithm used to approximately solve combinatorial
optimisation problems. It involves multiple iterations of a parameterised
ansatz comprising a problem and mixer Hamiltonian, with the parameters being
classically optimised. While QAOA can be implemented on NISQ devices, physical
limitations can limit circuit depth and decrease performance. To address these
limitations, this work introduces the eXpressive QAOA (XQAOA), an
overparameterised variant of QAOA that assigns more classical parameters to the
ansatz to improve its performance at low depths. XQAOA also introduces an
additional Pauli-Y component in the mixer Hamiltonian, allowing the mixer to
implement arbitrary unitary transformations on each qubit. To benchmark the
performance of XQAOA at unit depth, we derive its closed-form expression for
the MaxCut problem and compare it to QAOA, Multi-Angle QAOA (MA-QAOA), a
classical-relaxed algorithm, and the state-of-the-art Goemans-Williamson
algorithm on a set of unweighted regular graphs with 128 and 256 nodes for
degrees ranging from 3 to 10. Our results indicate that at unit depth, XQAOA
has benign loss landscapes, allowing it to consistently outperform QAOA,
MA-QAOA, and the classical-relaxed algorithm on all graph instances and the
Goemans-Williamson algorithm on graph instances with degrees greater than 4.
Small-scale simulations also reveal that unit-depth XQAOA surpasses both QAOA
and MA-QAOA on all tested depths up to five. Additionally, we find an infinite
family of graphs for which XQAOA solves MaxCut exactly and analytically show
that for some graphs in this family, XQAOA achieves a much larger approximation
ratio than QAOA. Overall, XQAOA is a more viable choice for variational quantum
optimisation on NISQ devices, offering competitive performance at low depths.
- Abstract(参考訳): 量子近似最適化アルゴリズム(QAOA)は、組合せ最適化問題を解くために用いられるハイブリッド量子古典アルゴリズムである。
問題とミキサーハミルトニアンからなるパラメータ化されたアンザッツの反復が複数含まれ、パラメータは古典的に最適化される。
QAOAはNISQデバイスに実装できるが、物理的制限は回路深さを制限し、性能を低下させる。
これらの制限に対処するため、この研究は、より古典的なパラメータをアザッツに割り当て、低深さでの性能を改善する、eXpressive QAOA (XQAOA)を導入した。
XQAOAはミキサー・ハミルトンにさらにパウリ-Y成分を導入し、ミキサーは各キュービットに任意のユニタリ変換を実装することができる。
単位深度でのXQAOAの性能をベンチマークするために、MaxCut問題に対するクローズドフォーム式を導出し、これをQAOA、Multi-Angle QAOA(MA-QAOA)、古典ラックスアルゴリズム、そして3から10の次数で128から256ノードの非重み付き正規グラフの集合上の最先端のゴーマンス・ウィリアムソンアルゴリズムと比較する。
以上の結果から,XQAOAは,全グラフインスタンス上でのQAOA,MA-QAOA,古典緩和アルゴリズム,および次数4以上のグラフインスタンス上でのGoemans-Williamsonアルゴリズムよりも常に優れることがわかった。
小型シミュレーションでは、単位深度XQAOAが最大5回の試験深度でQAOAとMA-QAOAを上回ります。
さらに、XQAOA が MaxCut を正確に解析的に解く無限のグラフ族が、この族のあるグラフに対して、XQAOA は QAOA よりもはるかに大きな近似比を達成することを示す。
全体として、XQAOA は NISQ デバイス上での変動量子最適化においてより有効な選択肢であり、低深さでの競合性能を提供する。
関連論文リスト
- MG-Net: Learn to Customize QAOA with Circuit Depth Awareness [51.78425545377329]
量子近似最適化アルゴリズム(QAOA)とその変種は、最適化問題に対処する大きな可能性を示している。
良好な性能を実現するために必要な回路深度は問題固有であり、しばしば現在の量子デバイスの最大容量を超える。
ミキサジェネレータネットワーク (MG-Net) は, 最適ミキサハミルトニアンを動的に定式化するための統合ディープラーニングフレームワークである。
論文 参考訳(メタデータ) (2024-09-27T12:28:18Z) - Modified Recursive QAOA for Exact Max-Cut Solutions on Bipartite Graphs: Closing the Gap Beyond QAOA Limit [4.364124102844566]
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、MAX-CUT問題などの最適化問題を概ね解くことを目的として提案された量子古典ハイブリッドアルゴリズムである。
まず、二部グラフ上のMAX-CUT問題の解法におけるレベル1QAOAの性能限界を解析的に証明する。
第2に、再帰的QAOA(RQAOA)は、QAOAをサブルーチンとしてグラフサイズを削減し、レベル1のQAOAを上回る性能を示す。
最後に,制限パラメータを持つRQAOAが,これらの制約に完全に対処可能であることを示す。
論文 参考訳(メタデータ) (2024-08-23T16:35:47Z) - Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA [0.0]
そこで本研究では,MaxCut問題のスケーラブルな解に対するQAOA2法の実装について述べる。
The limit of the Goemans-Williamson (GW) algorithm as a purely classical alternative to QAOA。
最大33量子ビットの大規模シミュレーションの結果は、ある場合におけるQAOAの利点と実装の効率性を示す。
論文 参考訳(メタデータ) (2024-06-25T09:02:31Z) - Tight Lieb-Robinson Bound for approximation ratio in Quantum Annealing [0.0]
本稿では,QAのパラメータ化バージョンを新たに導入し,アルゴリズムの正確な1局所解析を実現する。
1局所解析を持つ線形スケジュールQAは0.7020以上の近似比を達成し、既知の1局所アルゴリズムよりも優れていることを示す。
論文 参考訳(メタデータ) (2023-11-21T17:15:21Z) - 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) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。
問題の大きさと問題グラフの次数で指数関数的に増大する。
これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
論文 参考訳(メタデータ) (2022-01-06T21:02:30Z) - Quantum Approximate Optimization Algorithm Based Maximum Likelihood
Detection [80.28858481461418]
量子技術の最近の進歩は、ノイズの多い中間スケール量子(NISQ)デバイスへの道を開く。
量子技術の最近の進歩は、ノイズの多い中間スケール量子(NISQ)デバイスへの道を開く。
論文 参考訳(メタデータ) (2021-07-11T10:56:24Z) - Threshold-Based Quantum Optimization [0.0]
Th-QAOA(Threshold QAOA)は、量子交互演算子Ansatz(QAOA)の変種である。
GM-Th-QAOAをGroverの量子探索アルゴリズムの一般化と見なすことができる。
論文 参考訳(メタデータ) (2021-06-25T19:36:49Z) - Empirical performance bounds for quantum approximate optimization [0.27998963147546135]
パフォーマンスバウンダリの定量化は、QAOAが現実のアプリケーションの解決に有効である可能性についての洞察を提供する。
QAOA は、ほとんどのグラフに対して有界な Goemans-Williamson 近似比を超える。
得られたデータセットは、QAOAパフォーマンスに関する経験的バウンダリを確立するためのベンチマークとして提示される。
論文 参考訳(メタデータ) (2021-02-12T23:12:09Z) - Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。
任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文 参考訳(メタデータ) (2020-11-26T18:22:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。