バークレー量子情報計算センター、カリフォルニア大学バークレー、カリフォルニア 94720、米国
この論文を興味深いと思うか、議論したいですか？ SciRateを引用するかコメントを残す.
抽象
$p$ ステージの量子近似最適化アルゴリズム (QAOA$_p$) は、ノイズの多い中間スケール量子 (NISQ) デバイスでの組み合わせ最適化の有望なアプローチですが、その理論的な動作は $p=1$ 以降ではよく理解されていません。 $textit{最大カット問題}$ (MAX-CUT) について QAOA$_2$ を分析し、周囲 $> 5$ (つまり、三角形、正方形、または五角形がない) の $D$-正規グラフ上で予想されるカット率のグラフ サイズに依存しない式を導き出します。
すべての次数 $D ge 2$ と胴回り $> 5$ のすべての $D$ 正規グラフ $G$ において、QAOA$_2$ は $G$ の QAOA$_1$ よりも大きな予想カット率を持つことを示します。 ただし、$A$ がすべての $G$ で QAOA$_2$ よりも大きな予想カット率を持つような、$2$ ローカルのランダム化 $textit{classical}$ アルゴリズム $A$ が存在することも示します。 これは、すべての定数 $p$ に対して、すべてのグラフで QAOA$_p$ と同様に機能するローカルな古典的な MAX-CUT アルゴリズムが存在するという推測を裏付けます。
注目の画像: 周囲径が 5 を超える通常のグラフの MAX-CUT での QAOA とローカル古典アルゴリズムの予想パフォーマンスのプロット。 1 ローカル古典アルゴリズムが $p=1$ QAOA より優れているのと同じように、関連する 2 ローカル古典アルゴリズムは $p=2$ QAOA より優れています。
さらに詳しく知りたい場合は、プレゼンテーションを参照してください QAOA に対する地元の競合企業
►BibTeXデータ
►参照
【1] F. アルテ、K. アリヤ、R. バブシュ 他平面超伝導プロセッサ上の非平面グラフ問題の量子近似最適化。 2004.04197、doi:10.1038/s41567-020-01105-y。
https：/ / doi.org/ 10.1038 / s41567-020-01105-y
arXiv：2004.04197
【2] B. Barak、A. Moitra、R. O'Donnell、他有界次数の制約充足問題でランダム割り当てを破る。 1505.03424。
arXiv：1505.03424
【3] E. ファルヒ、J. ゴールドストーン、S. ガットマン。 量子近似最適化アルゴリズム。 1411.4028。
arXiv：1411.4028
【4] E. ファルヒ、J. ゴールドストーン、S. ガットマン。 有界出現制約問題に適用される量子近似最適化アルゴリズム。 1412.6062。
arXiv：1412.6062
【5] MXゴーマンズとDPウィリアムソン。 半正定計画法を使用した最大カットおよび充足可能性問題の近似アルゴリズムが改善されました。 Journal of the ACM (JACM)、42(6):1115–1145、1995。doi:10.1145/ 227683.227684、URL http:// / www-math.mit.edu/ goemans/ PAPERS/ maxcut-jacm.pdf。
https：/ / doi.org/ 10.1145 / 227683.227684
http://www-math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf
【6] MBヘイスティングス。 古典的および量子有界深さ近似アルゴリズム。 1905.07047。
arXiv：1905.07047
【7] J. ヒルボネン、J. リビッキ、S. シュミット、J. スオメラ。 三角形のないグラフでローカル アルゴリズムを使用した大幅なカット。 1402.2543。
arXiv：1402.2543
【8] S.コート。 ユニークな 2 プルーバー 1 ラウンド ゲームの威力について。 コンピューティング理論に関する第 02 回年次 ACM シンポジウム議事録、STOC '767、775 ～ 2002 ページ、ニューヨーク、ニューヨーク、米国、10.1145 年。コンピューティング機械協会。 土井：509907.510017/ XNUMX。
https：/ / doi.org/ 10.1145 / 509907.510017
【9] GBムベン、R.ファツィオ、G.サントロ。 量子アニーリング: デジタル化、制御、およびハイブリッド量子変分スキームを通過する旅。 1906.08948。
arXiv：1906.08948
【10] JR マクリーン、J. ロメロ、R. バブシュ、A. アスプル グジク。 変分ハイブリッド量子古典アルゴリズムの理論。 New Journal of Physics、18(2):023023、2016 年 10.1088 月。doi:1367/ 2630-18/ 2/ 023023/ XNUMX。
https://doi.org/10.1088/1367-2630/18/2/023023
【11] A. Meurer、CP Smith、M. Paprocki、他。 Sympy: Python でのシンボリック コンピューティング。 PeerJ コンピュータ サイエンス、3:e103、2017 年 10.7717 月。doi:103/ peerj-cs.XNUMX。
https:/ / doi.org/ 10.7717/ peerj-cs.103
【12] F・ペレスとBE・グレンジャー。 IPython: インタラクティブな科学技術コンピューティングのためのシステム。 Computing in Science and Engineering、9(3):21–29、2007 年 10.1109 月。doi:2007.53/ MCSE.XNUMX、URL https:// / ipython.org。
https：/ / doi.org/ 10.1109 / MCSE.2007.53
https://ipython.org
【13] J. プレスキル。 nisq 時代とその後の量子コンピューティング。 クォンタム、2:79、2018 年 10.22331 月。doi:2018/ q-08-06-79-XNUMX。
https://doi.org/10.22331/q-2018-08-06-79
【14] JB・シアラー。 三角形のないグラフの 3 部部分グラフに関するメモ。 ランダム構造とアルゴリズム、2(223):226–1992、10.1002。doi:3240030211/rsa.XNUMX。
https：/ / doi.org/ 10.1002 / rsa.3240030211
【15] M.セゲディ。 qaoa エネルギーはグラフについて何を明らかにしますか? 1912.12277。
arXiv：1912.12277
【16] P. Virtanen、R. Gommers、TE Oliphant、他SciPy 1.0: Python での科学コンピューティングの基本アルゴリズム。 Nature Methods、17:261–272、2020。doi:10.1038/ s41592-019-0686-2。
https://doi.org/10.1038/s41592-019-0686-2
【17] Z. ワン、S. ハドフィールド、Z. ジャン、EG リーフェル。 maxcut の量子近似最適化アルゴリズム: フェルミオン的ビュー。 物理学。 Rev. A、97:022304、2018 年 10.1103 月。doi:97.022304/PhysRevA.XNUMX。
https：/ / doi.org/ 10.1103 / PhysRevA.97.022304
【18] J・ウルツとPJ・ラブ。 p$>$1 の maxcut qaoa パフォーマンスの制限。 2010.11209。
arXiv：2010.11209
【19] L. チョウ、S.-T. Wang、S. Choi、他量子近似最適化アルゴリズム: パフォーマンス、メカニズム、および近い将来のデバイスへの実装。 Physical Review X、10(2)、2020 年 10.1103 月。doi:10.021067/ physrevx.XNUMX。
https：/ / doi.org/ 10.1103 / physrevx.10.021067
によって引用
この論文は、 Creative Commons Attribution 4.0 International（CC BY 4.0） ライセンス。 著作権は、著者やその機関などの元の著作権者にあります。
コインスマート。 BesteBitcoin-ヨーロッパのBörse
ソース：https://quantum-journal.org/papers/q-2021-04-20-437/
