1Google Inc.，威尼斯，CA 90291，美国
2麻省理工学院理论物理中心，剑桥，MA 02139，美国
3哈佛大学物理系，美国马萨诸塞州剑桥02138
觉得本文有趣或想讨论？ 在SciRate上发表评论或发表评论.
抽象
量子近似优化算法 (QAOA) 是一种用于组合优化问题的通用算法，其性能只能随着层数 $p$ 的增加而提高。 虽然 QAOA 有望成为一种可以在近期量子计算机上运行的算法，但其计算能力尚未得到充分探索。 在这项工作中，我们研究了应用于 Sherrington-Kirkpatrick (SK) 模型的 QAOA，该模型可以理解为具有全对全随机符号耦合的 $n$ 自旋的能量最小化。 Montanari 最近有一个经典算法，假设一个广泛相信的猜想，可以有效地找到 SK 模型的典型实例的近似解，在 $(1-epsilon)$ 倍的基态能量内。 我们希望将其性能与 QAOA 相匹配。
我们的主要成果是一种新技术，它使我们能够评估应用于 SK 模型的 QAOA 的典型实例能量。 我们生成了一个能量期望值的公式，作为 $2p$ QAOA 参数的函数，在无限大小的限制中，可以在具有 $O(16^p)$ 复杂度的计算机上进行评估。 我们将公式评估到 $p=12$，并发现 $p=11$ 处的 QAOA 优于标准的半定规划算法。 此外，我们展示了集中度：随着概率趋于 XNUMX 为 $ntoinfty$，QAOA 的测量将产生其能量集中在我们计算值的字符串。 作为在量子计算机上运行的算法，我们无需逐个实例地寻找最优参数，因为我们可以提前确定它们。 我们这里有一个用于分析 QAOA 的新框架，我们的技术可以广泛用于评估其在经典算法可能失败的更一般问题上的性能。
特色图片：QAOA 获得的值应用于最小化 Sherrington-Kirkpatrick (SK) 自旋玻璃模型的能量问题。 深度 $ple8$ 的值基于优化 QAOA 参数。 $9le p le 12$ 的值来自评估 QAOA 的某些参数，这些参数是从较低 $p$ 的参数推断出来的，但没有进一步优化。 在 $p=11$ 或更高时，QAOA 超过了标准半定规划 (SDP) 算法所达到的值。
[嵌入的内容]
热门摘要
►BibTeX数据
►参考
[1] A.蒙塔纳里。 “Sherrington-Kirkpatrick Hamiltonian 的优化”。 在第 60 届计算机科学基础年度研讨会论文集（FOCS '19）中。 第 1417-1433 页。 （2019）。
https：///doi.org/10.1109/FOCS.2019.00087
[2] 爱德华·法希、杰弗里·戈德斯通和山姆·古特曼。 “一种量子近似优化算法”（2014 年）。 arXiv：1411.4028。
的arXiv：1411.4028
[3] 爱德华·法希、杰弗里·戈德斯通和山姆·古特曼。 “应用于有界出现约束问题的量子近似优化算法”（2015 年）。 arXiv:1412.6062。
的arXiv：1412.6062
[4] Cedric Yen-Yu Lin 和 Yechao Zhu。 “QAOA 在有界度约束满足问题典型实例上的性能”（2016 年）。 arXiv：1601.01744。
的arXiv：1601.01744
[5] Fernando GSL Brandao、Michael Broughton、Edward Farhi、Sam Gutmann 和 Hartmut Neven。 “对于固定控制参数，量子近似优化算法的目标函数值集中在典型实例中”（2018 年）。 arXiv：1812.04170。
的arXiv：1812.04170
[6] G.帕里西。 “旋转玻璃的无限数量的订单参数”。 物理。 牧师莱特。 43, 1754–1756 (1979)。
https：/ / doi.org/ 10.1103 / PhysRevLett.43.1754
[7] 德米特里·潘琴科。 “谢灵顿-柯克帕特里克模型”。 施普林格。 纽约（2013 年）。
https://doi.org/10.1007/978-1-4614-6289-7
[8] A. Crisanti 和 T. Rizzo。 “Sherrington-Kirkpatrick 模型的 ${infty}$-replica 对称破坏解的分析”。 物理。 修订版 E 65, 046137 (2002)。
https：/ / doi.org/ 10.1103 / PhysRevE.65.046137
[9] 曼努埃尔·J·施密特。 “复制品对称性在低温下破裂”。 博士论文。 朱利叶斯-马克西米利安-维尔茨堡大学。 （2008 年）。
[10] Leo Zhou、Sheng-Tao Wang、Soonwon Choi、Hannes Pichler 和 Mikhail D. Lukin。 “量子近似优化算法：近期设备的性能、机制和实现”。 物理。 修订版 X 10, 021067 (2020)。
https：/ / doi.org/ 10.1103 / PhysRevX.10.021067
[11] 加文·E·克鲁克斯。 “量子近似优化算法在最大切割问题上的性能”（2018 年）。 arXiv:1811.08419。
的arXiv：1811.08419
[12] G.帕里西。 私人交流。
[13] Michael Aizenman、Joel Lebowitz 和 D. Ruelle。 “关于 Sherrington-Kirkpatrick 旋转玻璃模型的一些严格结果”。 交流。 数学。 物理。 112, 3-20 (1987)。
https：/ / doi.org/ 10.1007 / BF01217677
[14] Andrea Montanari 和 Subhabrata Sen。“稀疏随机图上的半定程序及其在社区检测中的应用”。 在第四十八届年度 ACM 计算理论研讨会论文集 (STOC '16)。 第 814-827 页。 （2016 年）。 arXiv:1504.05910。
https：/ / doi.org/10.1145/ 2897518.2897548
的arXiv：1504.05910
[15] Afonso S. Bandeira、Dmitriy Kunisky 和 Alexander S. Wein。 “约束 PCA 问题上证明界限的计算硬度”。 在第 11 届理论计算机科学创新会议 (ITCS 2020) 上。 第 151 卷，第 78:1-78:29 页。 德国达格施图尔（2020 年）。 Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik。 arXiv:1902.07324。
https：///doi.org/10.4230/LIPIcs.ITCS.2020.78
的arXiv：1902.07324
[16] Jarrod R. McClean、Sergio Boixo、Vadim N. Smelyanskiy、Ryan Babbush 和 Hartmut Neven。 “量子神经网络训练领域的贫瘠高原”。 自然通讯 9, 4812 (2018)。 arXiv:1803.11173。
https://doi.org/10.1038/s41467-018-07090-4
的arXiv：1803.11173
[17] Joao Basso、Edward Farhi、Kunal Marwaha、Benjamin Villalonga 和 Leo Zhou。 “大周长正则图和 Sherrington-Kirkpatrick 模型上 MaxCut 的高深度量子近似优化算法”（2022 年）。 arXiv：2110.14206。
的arXiv：2110.14206
[18] Wei Kuo Chen、David Gamarnik、Dmitry Panchenko 和 Mustazee Rahman。 “一类最大切问题的局部算法的次优性”。 概率年鉴 47, 1587–1618 (2019)。 arXiv:1707.05386。
https:/ / doi.org/ 10.1214/ 18-AOP1291
的arXiv：1707.05386
[19] 大卫 Gamarnik 和 Aukosh Jagannath。 “$p$-spin 模型的重叠间隙属性和近似消息传递算法”。 概率年鉴 49, 180–205 (2021)。 arXiv：1911.06943。
https:/ / doi.org/ 10.1214/ 20-AOP1448
的arXiv：1911.06943
[20] Ahmed El Alaoui 和 Andrea Montanari。 “平均场自旋玻璃中的算法阈值”（2020 年）。 arXiv:2009.11481。
的arXiv：2009.11481
被引用
[1] Kishor Bharti、Alba Cervera-Lierta、Thi Ha Kyaw、Tobias Haug、Sumner Alperin-Lea、Abhinav Anand、Matthias Degroote、Hermanni Heimonen、Jakob S. Kottmann、Tim Menke、Wai-Keong Mok、Sukin Sim、Leong- Chuan Kwek 和 Alán Aspuru-Guzik，“嘈杂的中尺度量子算法”， 现代物理学评论94 1，015004（2022）.
[2] Matthew P. Harrigan、Kevin J. Sung、Matthew Neeley、Kevin J. Satzinger、Frank Arute、Kunal Arya、Juan Atalaya、Joseph C. Bardin、Rami Barends、Sergio Boixo、Michael Broughton、Bob B. Buckley、David A. Buell, Brian Burkett, Nicholas Bushnell, Yu Chen, Zijun Chen, Collins Ben Chiaro, William Courtney, Sean Demura, Andrew Dunsworth, Daniel Eppens, Austin Fowler, Brooks Foxen, Craig Gidney, Marissa Giustina, Rob Graff, Steve Habegger, Alan Ho、Sabrina Hong、Trent Huang、LB Ioffe、Sergei V. Isakov、Evan Jeffrey、张江、Cody Jones、Dvir Kafri、Kostyantyn Kechedzhi、Julian Kelly、Seon Kim、Paul V. Klimov、Alexander N. Korotkov、Fedor Kostritsa , David Landhuis, Pavel Laptev, Mike Lindmark, Martin Leib, Orion Martin, John M. Martinis, Jarrod R. McClean, Matt McEwen, Anthony Megrant, Xiao Mi, Masoud Mohseni, Wojciech Mruczkiewicz, Josh Mutus, Ofer Naaman, Charles Neill, Florian Neukart, Murphy Yuezhen Niu, Thomas E. O'Brien, Bryan O'Gorman, Eric Ostby, Andre Petukhov, Harald Putterman,Chris Quintana、Pedram Roushan、Nicholas C. Rubin、Daniel Sank、Andrea Skolik、Vadim Smelyanskiy、Doug Strain、Michael Streif、Marco Szalay、Amit Vainsencher、Theodore White、Z. Jamie Yao、Ping Yeh、Adam Zalcman、Leo Zhou、Hartmut Neven、Dave Bacon、Erik Lucero、Edward Farhi 和 Ryan Babbush，“平面超导处理器上非平面图问题的量子近似优化”， 自然物理学17 3，332（2021）.
[3] Filip B. Maciejewski、Flavio Baccari、Zoltán Zimborás 和 Michał Oszmaniec，“利用量子近似优化算法对读出噪声中的串扰效应进行建模和缓解”， 的arXiv：2101.02331.
[4] Edward Farhi、David Gamarnik 和 Sam Gutmann，“量子近似优化算法需要查看整个图：一个典型案例”， 的arXiv：2004.09002.
[5] Antonio Anna Mele、Glen Bigan Mbeng、Giuseppe Ernesto Santoro、Mario Collura 和 Pietro Torta，“通过 Hamiltonian Variational Ansatz 中平滑解的可转移性避免贫瘠高原”， 的arXiv：2206.01982.
[6] Thais de Lima Silva、Márcio M. Taddei、Stefano Carrazza 和 Leandro Aolita，“早期量子信号处理器的分段虚时间演化”， 的arXiv：2110.13180.
[7] Clemens Dlaska、Kilian Ender、Glen Bigan Mbeng、Andreas Kruckenhauser、Wolfgang Lechner 和 Rick van Bijnen，“通过四体里德堡门进行量子优化”， 体检信128 12，120503（2022）.
[8] Jason Larkin、Matías Jonsson、Daniel Justice 和 Gian Giacomo Guerreschi，“基于单个样本近似比的 QAOA 评估”， 的arXiv：2006.04831.
[9] Jarrod R. McClean、Matthew P. Harrigan、Masoud Mohseni、Nicholas C. Rubin、Zhang Jiang、Sergio Boixo、Vadim N. Smelyanskiy、Ryan Babbush 和 Hartmut Neven，“量子优化的低深度机制”， PRX 量子 2 3, 030312 (2021).
[10] V. Akshay、D. Rabinovich、E. Campos 和 J. Biamonte，“量子近似优化中的参数浓度”， 物理评论 A 104 1, L010401 (2021).
[11] Chenfeng Cao, Zheng An, Shi-Yao Hou, DL Zhou, and Bei Zeng，“强化学习引导的量子虚时间演化”， 通讯物理学5 1，57（2022）.
[12] Jordi R. Weggemans、Alexander Urech、Alexander Rausch、Robert Spreeuw、Richard Boucherie、Florian Schreck、Kareljan Schoutens、Jiří Minář 和 Florian Speelman，“使用 QAOA 和 Rydberg qudit 系统解决相关聚类：全栈方法”, 的arXiv：2106.11672.
[13] Giacomo De Palma、Milad Marvian、Cambyse Rouzé 和 Daniel Stilck França，“变分量子算法的局限性：一种量子最优传输方法”， 的arXiv：2204.03455.
[14] Nathan Lacroix、Christoph Hellings、Christian Kraglund Andersen、Agustin Di Paolo、Ants Remm、Stefania Lazar、Sebastian Krinner、Graham J. Norris、Mihai Gabureac、Johannes Heinsoo、Alexandre Blais、Christopher Eichler 和 Andreas Wallraff，“改善具有连续门集的深度量子优化算法的性能”， PRX 量子 1 2, 020304 (2020).
[15] Joao Basso、Edward Farhi、Kunal Marwaha、Benjamin Villalonga 和 Leo Zhou，“MaxCut 在大周长正则图和 Sherrington-Kirkpatrick 模型上的高深度量子近似优化算法”， 的arXiv：2110.14206.
[16] Matteo M. Wauters、Emanuele Panizon、Glen B. Mbeng 和 Giuseppe E. Santoro，“强化学习辅助量子优化”， 物理评论研究2 3，033446（2020）.
[17] Hajo Leschke、Chokri Manai、Rainer Ruder 和 Simone Warzel，“量子眼镜中存在复制对称性破坏”， 体检信127 20，207204（2021）.
[18] Teague Tomesh、Pranav Gokhale、Victory Omole、Gokul Subramanian Ravi、Kaitlin N. Smith、Joshua Viszlai、Xin-Chuan Wu、Nikos Hardavellas、Margaret R. Martonosi 和 Frederic T. Chong，“SupermarQ：可扩展的量子基准套房”， 的arXiv：2202.11045.
[19] Luca Lumia、Pietro Torta、Glen B. Mbeng、Giuseppe E. Santoro、Elisa Ercolessi、Michele Burrello 和 Matteo M. Wauters，“近期量子模拟器上的二维 Z 2晶格规范理论：变分量子优化、约束和拓扑顺序”， PRX 量子 3 2, 020320 (2022).
[20] Nishant Jain、Brian Coyle、Elham Kashefi 和 Niraj Kumar，“量子近似优化的图神经网络初始化”， 的arXiv：2111.03016.
[21] Stuart Hadfield、Tad Hogg 和 Eleanor G. Rieffel，“量子交替算子 Ansätze 的分析框架”， 的arXiv：2105.06996.
[22] Akel Hashim、Rich Rines、Victory Omole、Ravi K. Naik、John Mark Kreikebaum、David I. Santiago、Frederic T. Chong、Irfan Siddiqi 和 Pranav Gokhale，“针对 QAOA 进行等效电路平均的优化 SWAP 网络”， 物理评论研究4 3，033028（2022）.
[23] Dennis Willsch、Madita Willsch、Fengping Jin、Kristel Michielsen 和 Hans De Raedt，“GPU 加速模拟量子退火和量子近似优化算法”， 计算机物理通信 278、108411 (2022).
[24] Pontus Vikstâl、Mattias Grönkvist、Marika Svensson、Martin Andersson、Göran Johansson 和 Giulia Ferrini，“将量子近似优化算法应用于尾部分配问题”， 物理评论应用14 3，034009（2020）.
[25] P. Chandarana、NN Hegade、K. Paul、F. Albarrán-Arriagada、E. Solano、A. del Campo 和 Xi Chen，“数字化反绝热量子近似优化算法”， 物理评论研究4 1，013141（2022）.
[26] 庄伟峰、浦亚楠、徐宏泽、柴旭丹、顾彦武、马云恒、Shahid Qamar、陈倩、钱鹏、肖晓、胡孟军、刘东娥， “浅 QAOA 电路的量子平均值的有效经典计算”， 的arXiv：2112.11151.
[27] Jahan Claes 和 Wim van Dam，“无限大小混合自旋模型上单层量子近似优化算法的实例独立性”， 的arXiv：2102.12043.
[28] Han Zheng、Zimu Li、Junyu Liu、Sergii Strelchuk 和 Risi Kondor，“通过群等变卷积量子 Ansätze 加速学习量子态”， 的arXiv：2112.07611.
[29] Chi-Ning Chou、Peter J. Love、Juspreet Singh Sandhu 和 Jonathan Shi，“局部量子算法对随机 Max-k-XOR 及其他算法的限制”， 的arXiv：2108.06049.
[30] Ioannis Kolotouros 和 Petros Wallden，“改进变分量子优化的演化目标函数”， 物理评论研究4 2，023225（2022）.
[31] Prasanna Date、Davis Arthur 和 Lauren Pusey-Nazzaro，“用于训练机器学习模型的 QUBO 公式”， 科学报告11，10029（2021）.
[32] Yuval R. Sanders、Dominic W. Berry、Pedro CS Costa、Louis W. Tessler、Nathan Wiebe、Craig Gidney、Hartmut Neven 和 Ryan Babbush，“用于组合优化的容错量子启发式编译”， 的arXiv：2007.07391.
[33] Benjamin Tan、Marc-Antoine Lemonde、Supanut Thanasilp、Jirawat Tangpanitanon 和 Dimitris G. Angelakis，“二进制优化问题的量子比特高效编码方案”， 的arXiv：2007.01774.
[34] Paul M. Schindler、Tommaso Guaita、Tao Shi、Eugene Demler 和 J. Ignacio Cirac，“量子 Sherrington-Kirkpatrick 模型基态的变分 Ansatz”， 的arXiv：2204.02923.
[35] Laszlo Gyongyosi，“门模型量子计算机的量子状态优化和计算路径评估”， 科学报告10，4543（2020）.
[36] Joao Basso、David Gamarnik、Song Mei 和 Leo Zhou，“QAOA 在大型稀疏超图和自旋玻璃模型上的恒定水平的性能和局限性”， 的arXiv：2204.10306.
[37] David Joseph、Antonio J. Martinez、Cong Ling 和 Florian Mintert，“硬整数值问题的量子均值逼近器”， 物理评论A 105 5，052419（2022）.
[38] Laszlo Gyongyosi 和 Sandor Imre，“门模型量子计算机的电路深度缩减”， 科学报告10，11229（2020）.
[39] J.-H. Bae、Paul M. Alsing、Doyeol Ahn 和 Warner A. Miller，“使用量子卡诺图进行量子电路优化”， 科学报告10，15651（2020）.
[40] Bingzhi Zhang、Akira Sone 和 Quntao Zhuang，“组合问题中的量子计算相变”， 的arXiv：2109.13346.
[41] E. Campos、D. Rabinovich、V. Akshay 和 J. Biamonte，“在分层量子近似优化中训练饱和度”， 的arXiv：2106.13814.
[42] Sami Boulebnane，“通过后选择改进量子近似优化算法”， 的arXiv：2011.05425.
[43] Gabriel Matos，Sonika Johri和ZlatkoPapić，“通过量子变分本征求解器量化状态准备的效率”， 的arXiv：2007.14338.
[44] Gregory Quiroz、Paraj Titum、Philliplotshaw、Pavel Lougovski、Kevin Schultz、Eugene Dumitrescu 和 Itay Hen，“量化精度误差对量子近似优化算法的影响”， 的arXiv：2109.04482.
[45] Kyle Mills、Pooya Ronagh 和 Isaac Tamblyn，“受控在线优化学习 (COOL)：通过强化学习找到自旋哈密顿量的基态”， 的arXiv：2003.00011.
[46] Teppei Suzuki 和 Michio Katouda，“通过量子机器学习预测毒性”， 物理通讯杂志 4 12, 125012 (2020).
[47] Ruslan Shaydulin、Phillip C.Lotshaw、Jeffrey Larson、James Ostrowski 和 Travis S. Humble，“加权 MaxCut 的量子近似优化的参数传递”， 的arXiv：2201.11785.
[48] Laszlo Gyongyosi，“用于解决门模型量子计算机优化问题的目标函数估计”， 科学报告10，14220（2020）.
[49] Xuchen You 和 Xiaodi Wu，“量子神经网络中的指数级多个局部最小值”， 的arXiv：2110.02479.
[50] Laszlo Gyongyosi，“门模型量子计算机的无监督量子门控制”， 科学报告10，10701（2020）.
[51] V. Akshay、H. Philathong、E. Campos、D. Rabinovich、I. Zacharov、Xiao-Ming Zhang 和 J. Biamonte，“关于量子近似优化的电路深度缩放”， 的arXiv：2205.01698.
[52] Laszlo Gyongyosi，“量子互联网纠缠网络的动力学”， 科学报告10，12909（2020）.
[53] Sami Boulebnane 和 Ashley Montanaro，“Predicting parameters for the Quantum Approximate Optimization Algorithm for MAX-CUT from the infinite-size limit”， 的arXiv：2110.10685.
[54] Laszlo Gyongyosi 和 Sandor Imre，“可扩展分布式门模型量子计算机”， 科学报告11，5172（2021）.
[55] Laszlo Gyongyosi 和 Sandor Imre，“量子互联网中可扩展路由的路由空间探索”， 科学报告10，11874（2020）.
[56] G. Pederiva、A. Bazavov、B. Henke、L. Hostetler、D. Lee、HW Lin 和 A. Shindler，“Schwinger 模型的量子态准备”，第 38 届国际晶格场论研讨会 47 （2022）。
[57] Sinan Bugu、Fatih Ozaydin 和 Tetsuo Kodera，“通过与光学腔耦合的远距离量子点超越魔方游戏中的经典极限”， 科学报告10，22202（2020）.
[58] Laszlo Gyongyosi，“超导门模型量子计算机的退相干动力学估计”， 量子信息处理19 10，369（2020）.
[59] Aida Ahmadzadegan、Petar Simidzija、Ming Li 和 Achim Kempf，“神经网络可以学习利用相关辅助噪声”， 科学报告11，21624（2021）.
[60] Michelle Chalupnik、Hans Melo、Yuri Alexeev 和 Alexey Galda，“使用多参数问题独立层增强 QAOA Ansatz”， 的arXiv：2205.01192.
[61] Hari Krovi，“在误差指数中具有线性标度的随机量子电路概率估计的平均情况硬度”， 的arXiv：2206.05642.
[62] Daniil Rabinovich、Soumik Adhikary、Ernesto Campos、Vishwanathan Akshay、Evgeny Anikin、Richik Sengupta、Olga Lakhmanskaya、Kiril Lakhmanskiy 和 Jacob Biamonte，“用于量子近似优化的离子原生变分 ansatz”， 的arXiv：2206.11908.
以上引用来自 SAO / NASA广告 （最近成功更新为2022-07-27 14:28:25）。 该列表可能不完整，因为并非所有发布者都提供合适且完整的引用数据。
On Crossref的引用服务 找不到有关引用作品的数据（上一次尝试2022-07-27 14:28:23）。
该论文发表在《量子》杂志上 国际知识共享署名署名4.0（CC BY 4.0） 执照。 版权归原始版权持有者所有，例如作者或其所在机构。
