The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size

Edward Farhi; Jeffrey Goldstone; Sam Gutmann; Leo Zhou

doi:10.22331/q-2022-07-07-759

The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size

Edward Farhi^1,2, Jeffrey Goldstone², Sam Gutmann, and Leo Zhou^1,3

¹Google Inc., Venice, CA 90291, USA
²Center for Theoretical Physics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA
³Department of Physics, Harvard University, Cambridge, MA 02138, USA

Published:	2022-07-07, volume 6, page 759
Eprint:	arXiv:1910.08187v4
Doi:	https://doi.org/10.22331/q-2022-07-07-759
Citation:	Quantum 6, 759 (2022).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

The Quantum Approximate Optimization Algorithm (QAOA) is a general-purpose algorithm for combinatorial optimization problems whose performance can only improve with the number of layers $p$. While QAOA holds promise as an algorithm that can be run on near-term quantum computers, its computational power has not been fully explored. In this work, we study the QAOA applied to the Sherrington-Kirkpatrick (SK) model, which can be understood as energy minimization of $n$ spins with all-to-all random signed couplings. There is a recent classical algorithm by Montanari that, assuming a widely believed conjecture, can efficiently find an approximate solution for a typical instance of the SK model to within $(1-\epsilon)$ times the ground state energy. We hope to match its performance with the QAOA.

Our main result is a novel technique that allows us to evaluate the typical-instance energy of the QAOA applied to the SK model. We produce a formula for the expected value of the energy, as a function of the $2p$ QAOA parameters, in the infinite size limit that can be evaluated on a computer with $O(16^p)$ complexity. We evaluate the formula up to $p=12$, and find that the QAOA at $p=11$ outperforms the standard semidefinite programming algorithm. Moreover, we show concentration: With probability tending to one as $n\to\infty$, measurements of the QAOA will produce strings whose energies concentrate at our calculated value. As an algorithm running on a quantum computer, there is no need to search for optimal parameters on an instance-by-instance basis since we can determine them in advance. What we have here is a new framework for analyzing the QAOA, and our techniques can be of broad interest for evaluating its performance on more general problems where classical algorithms may fail.

Featured image: Values achieved by the QAOA applied to the problem of minimizing the energy of the Sherrington-Kirkpatrick (SK) spin glass model. The values for depth $p\le8$ are based on optimizing the QAOA parameters. The values for $9\le p \le 12$ are from evaluating the QAOA at some parameters extrapolated from those at lower $p$ but not further optimized. At $p=11$ and higher, the QAOA surpasses the the value achieved by the standard semidefinite programming (SDP) algorithm.

Popular summary

This work studies the performance of a general-purpose quantum algorithm for combinatorial optimization, called the QAOA, applied to the famous Sherrington-Kirkpatrick (SK) model of spin glass. This is the problem of energy minimization of all-to-all randomly coupled spins. The authors produce a formula for calculating the expected value of the energy achieved by the QAOA in the limit of infinite system size, as a function of the algorithm parameters. They also prove that typical measurements of random instances of the problem concentrates at this value. These results allow for comparisons to the state-of-the-art classical algorithms. In particular, the authors find that the QAOA with 11 layers outperforms the standard semidefinite programming algorithm on this problem. It remains an open question how the performance scaling of the QAOA compares to the currently known best classical algorithm by Montanari.

► BibTeX data

@article{Farhi2022quantumapproximate,
  doi = {10.22331/q-2022-07-07-759},
  url = {https://doi.org/10.22331/q-2022-07-07-759},
  title = {The {Q}uantum {A}pproximate {O}ptimization {A}lgorithm and the {S}herrington-{K}irkpatrick {M}odel at {I}nfinite {S}ize},
  author = {Farhi, Edward and Goldstone, Jeffrey and Gutmann, Sam and Zhou, Leo},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {6},
  pages = {759},
  month = jul,
  year = {2022}
}

► References

[1] A. Montanari. ``Optimization of the Sherrington-Kirkpatrick Hamiltonian''. In Proceedings of the 60th Annual Symposium on Foundations of Computer Science (FOCS '19). Pages 1417–1433. (2019).
https://doi.org/10.1109/FOCS.2019.00087

[2] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A Quantum Approximate Optimization Algorithm'' (2014). arXiv:1411.4028.
arXiv:1411.4028

[3] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem'' (2015). arXiv:1412.6062.
arXiv:1412.6062

[4] Cedric Yen-Yu Lin and Yechao Zhu. ``Performance of QAOA on Typical Instances of Constraint Satisfaction Problems with Bounded Degree'' (2016). arXiv:1601.01744.
arXiv:1601.01744

[5] Fernando G. S. L. Brandao, Michael Broughton, Edward Farhi, Sam Gutmann, and Hartmut Neven. ``For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances'' (2018). arXiv:1812.04170.
arXiv:1812.04170

[6] G. Parisi. ``Infinite number of order parameters for spin-glasses''. Phys. Rev. Lett. 43, 1754–1756 (1979).
https://doi.org/10.1103/PhysRevLett.43.1754

[7] Dmitry Panchenko. ``The Sherrington-Kirkpatrick model''. Springer. New York (2013).
https://doi.org/10.1007/978-1-4614-6289-7

[8] A. Crisanti and T. Rizzo. ``Analysis of the ${\infty}$-replica symmetry breaking solution of the Sherrington-Kirkpatrick model''. Phys. Rev. E 65, 046137 (2002).
https://doi.org/10.1103/PhysRevE.65.046137

[9] Manuel J. Schmidt. ``Replica Symmetry Breaking at Low Temperatures''. PhD thesis. Julius-Maximilians-Universität Würzburg. (2008).

[10] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D. Lukin. ``Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices''. Phys. Rev. X 10, 021067 (2020).
https://doi.org/10.1103/PhysRevX.10.021067

[11] Gavin E. Crooks. ``Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem'' (2018). arXiv:1811.08419.
arXiv:1811.08419

[12] G. Parisi. Private communication.

[13] Michael Aizenman, Joel Lebowitz, and D. Ruelle. ``Some rigorous results on the Sherrington-Kirkpatrick spin glass model''. Commun. Math. Phys. 112, 3–20 (1987).
https://doi.org/10.1007/BF01217677

[14] Andrea Montanari and Subhabrata Sen. ``Semidefinite programs on sparse random graphs and their application to community detection''. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing (STOC '16). Pages 814–827. (2016). arXiv:1504.05910.
https://doi.org/10.1145/2897518.2897548
arXiv:1504.05910

[15] Afonso S. Bandeira, Dmitriy Kunisky, and Alexander S. Wein. ``Computational Hardness of Certifying Bounds on Constrained PCA Problems''. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Volume 151, pages 78:1–78:29. Dagstuhl, Germany (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, and Hartmut Neven. ``Barren plateaus in quantum neural network training landscapes''. Nature Communications 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, and Leo Zhou. ``The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model'' (2022). arXiv:2110.14206.
arXiv:2110.14206

[18] Wei Kuo Chen, David Gamarnik, Dmitry Panchenko, and Mustazee Rahman. ``Suboptimality of local algorithms for a class of max-cut problems''. Annals of Probability 47, 1587–1618 (2019). arXiv:1707.05386.
https://doi.org/10.1214/18-AOP1291
arXiv:1707.05386

[19] David Gamarnik and Aukosh Jagannath. ``The overlap gap property and approximate message passing algorithms for $p$-spin models''. Annals of Probability 49, 180–205 (2021). arXiv:1911.06943.
https://doi.org/10.1214/20-AOP1448
arXiv:1911.06943

[20] Ahmed El Alaoui and Andrea Montanari. ``Algorithmic Thresholds in Mean Field Spin Glasses'' (2020). arXiv:2009.11481.
arXiv:2009.11481

Cited by

[1] Kaitlin N. Smith, Michael A. Perlin, Pranav Gokhale, Paige Frederick, David Owusu-Antwi, Richard Rines, Victory Omole, and Frederic Chong, Proceedings of the 50th Annual International Symposium on Computer Architecture 1 (2023) ISBN:9798400700958.

[2] Nishant Jain, Brian Coyle, Elham Kashefi, and Niraj Kumar, "Graph neural network initialisation of quantum approximate optimisation", Quantum 6, 861 (2022).

[3] Francisco Chicano, Zakaria Dahi, and Gabriel Luque, Proceedings of the Companion Conference on Genetic and Evolutionary Computation 2187 (2023) ISBN:9798400701207.

[4] Stuart Hadfield, Tad Hogg, and Eleanor G Rieffel, "Analytical framework for quantum alternating operator ansätze", Quantum Science and Technology 8 1, 015017 (2023).

[5] Martin R. Albrecht, Miloš Prokop, Yixin Shen, and Petros Wallden, "Variational quantum solutions to the Shortest Vector Problem", Quantum 7, 933 (2023).

[6] Pablo Díez-Valle, Jorge Luis-Hita, Senaida Hernández-Santana, Fernando Martínez-García, Álvaro Díaz-Fernández, Eva Andrés, Juan José García-Ripoll, Escolástico Sánchez-Martínez, and Diego Porras, "Multiobjective variational quantum optimization for constrained problems: an application to cash handling", Quantum Science and Technology 8 4, 045009 (2023).

[7] Antonio A. Mele, Glen B. Mbeng, Giuseppe E. Santoro, Mario Collura, and Pietro Torta, "Avoiding barren plateaus via transferability of smooth solutions in a Hamiltonian variational ansatz", Physical Review A 106 6, L060401 (2022).

[8] Pablo Díez-Valle, Diego Porras, and Juan José García-Ripoll, "Quantum Approximate Optimization Algorithm Pseudo-Boltzmann States", Physical Review Letters 130 5, 050601 (2023).

[9] Daniil Rabinovich, Richik Sengupta, Ernesto Campos, Vishwanathan Akshay, and Jacob Biamonte, "Progress towards Analytically Optimal Angles in Quantum Approximate Optimisation", Mathematics 10 15, 2601 (2022).

[10] Eric R. Anschuetz and Bobak T. Kiani, "Quantum variational algorithms are swamped with traps", Nature Communications 13 1, 7760 (2022).

[11] G. Wendin, Reference Module in Materials Science and Materials Engineering (2023) ISBN:9780128035818.

[12] Laszlo Gyongyosi, "Adaptive Problem Solving Dynamics in Gate-Model Quantum Computers", Entropy 24 9, 1196 (2022).

[13] Boy Choy and David J. Wales, "Molecular Energy Landscapes of Hardware-Efficient Ansätze in Quantum Computing", Journal of Chemical Theory and Computation 19 4, 1197 (2023).

[14] Joao Basso, David Gamarnik, Song Mei, and Leo Zhou, 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) 335 (2022) ISBN:978-1-6654-5519-0.

[15] Phillip C. Lotshaw, Kevin D. Battles, Bryan Gard, Gilles Buchs, Travis S. Humble, and Creston D. Herold, "Modeling noise in global Mølmer-Sørensen interactions applied to quantum approximate optimization", Physical Review A 107 6, 062406 (2023).

[16] Paul M. Schindler, Tommaso Guaita, Tao Shi, Eugene Demler, and J. Ignacio Cirac, "VariationalAnsatzfor the Ground State of the Quantum Sherrington-Kirkpatrick Model", Physical Review Letters 129 22, 220401 (2022).

[17] Ye-Hong Chen, Adam Miranowicz, Xi Chen, Yan Xia, and Franco Nori, "Enhanced-Fidelity Ultrafast Geometric Quantum Computation Using Strong Classical Drives", Physical Review Applied 18 6, 064059 (2022).

[18] Pengzhan Zhao, Xiongfei Wu, Junjie Luo, Zhuo Li, and Jianjun Zhao, 2023 IEEE International Conference on Quantum Software (QSW) 68 (2023) ISBN:979-8-3503-0479-4.

[19] V. Akshay, H. Philathong, E. Campos, D. Rabinovich, I. Zacharov, Xiao-Ming Zhang, and J. D. Biamonte, "Circuit depth scaling for quantum approximate optimization", Physical Review A 106 4, 042438 (2022).

[20] Javier Romero-Alvarez, Jaime Alvarado-Valiente, Enrique Moguel, Jose Garcia-Alonso, and Juan M. Murillo, 2023 IEEE International Conference on Software Services Engineering (SSE) 1 (2023) ISBN:979-8-3503-4075-4.

[21] Thomas Grurl, Jürgen Fuß, and Robert Wille, 2023 IEEE 53rd International Symposium on Multiple-Valued Logic (ISMVL) 141 (2023) ISBN:978-1-6654-6416-1.

[22] David Headley and Frank K. Wilhelm, "Problem-size-independent angles for a Grover-driven quantum approximate optimization algorithm", Physical Review A 107 1, 012412 (2023).

[23] Fei Hua, Yuwei Jin, Yanhao Chen, Suhas Vittal, Kevin Krsulich, Lev S. Bishop, John Lapeyre, Ali Javadi-Abhari, and Eddy Z. Zhang, Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3 59 (2023) ISBN:9781450399180.

[24] Yun-Fei Niu, Shuo Zhang, Chen Ding, Wan-Su Bao, and He-Liang Huang, "Parameter-parallel distributed variational quantum algorithm", SciPost Physics 14 5, 132 (2023).

[25] Chenfeng Cao, Zheng An, Shi-Yao Hou, D. L. Zhou, and Bei Zeng, "Quantum imaginary time evolution steered by reinforcement learning", Communications Physics 5 1, 57 (2022).

[26] Daniil Rabinovich, Soumik Adhikary, Ernesto Campos, Vishwanathan Akshay, Evgeny Anikin, Richik Sengupta, Olga Lakhmanskaya, Kirill Lakhmanskiy, and Jacob Biamonte, "Ion-native variational ansatz for quantum approximate optimization", Physical Review A 106 3, 032418 (2022).

[27] Pietro Torta, Glen B. Mbeng, Carlo Baldassi, Riccardo Zecchina, and Giuseppe E. Santoro, "Quantum approximate optimization algorithm applied to the binary perceptron", Physical Review B 107 9, 094202 (2023).

[28] 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, and Alán Aspuru-Guzik, "Noisy intermediate-scale quantum algorithms", Reviews of Modern Physics 94 1, 015004 (2022).

[29] 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, L. B. Ioffe, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, 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, and Ryan Babbush, "Quantum approximate optimization of non-planar graph problems on a planar superconducting processor", Nature Physics 17 3, 332 (2021).

[30] Guillermo González-García, Rahul Trivedi, and J. Ignacio Cirac, "Error Propagation in NISQ Devices for Solving Classical Optimization Problems", PRX Quantum 3 4, 040326 (2022).

[31] Edward Farhi, David Gamarnik, and Sam Gutmann, "The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case", arXiv:2004.09002, (2020).

[32] Giacomo De Palma, Milad Marvian, Cambyse Rouzé, and Daniel Stilck França, "Limitations of Variational Quantum Algorithms: A Quantum Optimal Transport Approach", PRX Quantum 4 1, 010309 (2023).

[33] 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, and Andreas Wallraff, "Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets", PRX Quantum 1 2, 020304 (2020).

[34] Thais de Lima Silva, Márcio M. Taddei, Stefano Carrazza, and Leandro Aolita, "Fragmented imaginary-time evolution for early-stage quantum signal processors", arXiv:2110.13180, (2021).

[35] Pradeep Niroula, Ruslan Shaydulin, Romina Yalovetzky, Pierre Minssen, Dylan Herman, Shaohan Hu, and Marco Pistoia, "Constrained quantum optimization for extractive summarization on a trapped-ion quantum computer", Scientific Reports 12, 17171 (2022).

[36] Jarrod R. McClean, Matthew P. Harrigan, Masoud Mohseni, Nicholas C. Rubin, Zhang Jiang, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven, "Low-Depth Mechanisms for Quantum Optimization", PRX Quantum 2 3, 030312 (2021).

[37] Clemens Dlaska, Kilian Ender, Glen Bigan Mbeng, Andreas Kruckenhauser, Wolfgang Lechner, and Rick van Bijnen, "Quantum Optimization via Four-Body Rydberg Gates", Physical Review Letters 128 12, 120503 (2022).

[38] Jason Larkin, Matías Jonsson, Daniel Justice, and Gian Giacomo Guerreschi, "Evaluation of QAOA based on the approximation ratio of individual samples", Quantum Science and Technology 7 4, 045014 (2022).

[39] Matteo M. Wauters, Emanuele Panizon, Glen B. Mbeng, and Giuseppe E. Santoro, "Reinforcement-learning-assisted quantum optimization", Physical Review Research 2 3, 033446 (2020).

[40] V. Akshay, D. Rabinovich, E. Campos, and J. Biamonte, "Parameter concentrations in quantum approximate optimization", Physical Review A 104 1, L010401 (2021).

[41] Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, and Leo Zhou, "The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model", arXiv:2110.14206, (2021).

[42] P. Chandarana, N. N. Hegade, K. Paul, F. Albarrán-Arriagada, E. Solano, A. del Campo, and Xi Chen, "Digitized-counterdiabatic quantum approximate optimization algorithm", Physical Review Research 4 1, 013141 (2022).

[43] Luca Lumia, Pietro Torta, Glen B. Mbeng, Giuseppe E. Santoro, Elisa Ercolessi, Michele Burrello, and Matteo M. Wauters, "Two-Dimensional Z<SUB>2</SUB> Lattice Gauge Theory on a Near-Term Quantum Simulator: Variational Quantum Optimization, Confinement, and Topological Order", PRX Quantum 3 2, 020320 (2022).

[44] G. Wendin, "Quantum information processing with superconducting circuits: a perspective", arXiv:2302.04558, (2023).

[45] Han Zheng, Zimu Li, Junyu Liu, Sergii Strelchuk, and Risi Kondor, "Speeding Up Learning Quantum States Through Group Equivariant Convolutional Quantum Ansätze", PRX Quantum 4 2, 020327 (2023).

[46] Hajo Leschke, Chokri Manai, Rainer Ruder, and Simone Warzel, "Existence of Replica-Symmetry Breaking in Quantum Glasses", Physical Review Letters 127 20, 207204 (2021).

[47] Ruslan Shaydulin, Phillip C. Lotshaw, Jeffrey Larson, James Ostrowski, and Travis S. Humble, "Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut", arXiv:2201.11785, (2022).

[48] Filip B. Maciejewski, Flavio Baccari, Zoltán Zimborás, and Michał Oszmaniec, "Modeling and mitigation of cross-talk effects in readout noise with applications to the Quantum Approximate Optimization Algorithm", Quantum 5, 464 (2021).

[49] Pontus Vikstâl, Mattias Grönkvist, Marika Svensson, Martin Andersson, Göran Johansson, and Giulia Ferrini, "Applying the Quantum Approximate Optimization Algorithm to the Tail-Assignment Problem", Physical Review Applied 14 3, 034009 (2020).

[50] Prasanna Date, Davis Arthur, and Lauren Pusey-Nazzaro, "QUBO formulations for training machine learning models", Scientific Reports 11, 10029 (2021).

[51] Jordi R. Weggemans, Alexander Urech, Alexander Rausch, Robert Spreeuw, Richard Boucherie, Florian Schreck, Kareljan Schoutens, Jiří Minář, and Florian Speelman, "Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach", Quantum 6, 687 (2022).

[52] Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu, and Jonathan Shi, "Limitations of Local Quantum Algorithms on Random Max-k-XOR and Beyond", arXiv:2108.06049, (2021).

[53] Sami Boulebnane and Ashley Montanaro, "Predicting parameters for the Quantum Approximate Optimization Algorithm for MAX-CUT from the infinite-size limit", arXiv:2110.10685, (2021).

[54] Teague Tomesh, Pranav Gokhale, Victory Omole, Gokul Subramanian Ravi, Kaitlin N. Smith, Joshua Viszlai, Xin-Chuan Wu, Nikos Hardavellas, Margaret R. Martonosi, and Frederic T. Chong, "SupermarQ: A Scalable Quantum Benchmark Suite", arXiv:2202.11045, (2022).

[55] Wei-Feng Zhuang, Ya-Nan Pu, Hong-Ze Xu, Xudan Chai, Yanwu Gu, Yunheng Ma, Shahid Qamar, Chen Qian, Peng Qian, Xiao Xiao, Meng-Jun Hu, and Dong E. Liu, "Efficient Classical Computation of Quantum Mean Values for Shallow QAOA Circuits", arXiv:2112.11151, (2021).

[56] Phillip C. Lotshaw, George Siopsis, James Ostrowski, Rebekah Herrman, Rizwanul Alam, Sarah Powers, and Travis S. Humble, "Approximate Boltzmann Distributions in Quantum Approximate Optimization", arXiv:2212.01857, (2022).

[57] J. -H. Bae, Paul M. Alsing, Doyeol Ahn, and Warner A. Miller, "Quantum circuit optimization using quantum Karnaugh map", Scientific Reports 10, 15651 (2020).

[58] Akel Hashim, Rich Rines, Victory Omole, Ravi K. Naik, John Mark Kreikebaum, David I. Santiago, Frederic T. Chong, Irfan Siddiqi, and Pranav Gokhale, "Optimized SWAP networks with equivalent circuit averaging for QAOA", Physical Review Research 4 3, 033028 (2022).

[59] Vasiliy Usatyuk, Sergey Egorov, and Denis Sapozhnikov, "Spherical and Hyperbolic Toric Topology-Based Codes On Graph Embedding for Ising MRF Models: Classical and Quantum Topology Machine Learning", arXiv:2307.15778, (2023).

[60] Gregory Quiroz, Paraj Titum, Phillip Lotshaw, Pavel Lougovski, Kevin Schultz, Eugene Dumitrescu, and Itay Hen, "Quantifying the Impact of Precision Errors on Quantum Approximate Optimization Algorithms", arXiv:2109.04482, (2021).

[61] Laszlo Gyongyosi and Sandor Imre, "Circuit Depth Reduction for Gate-Model Quantum Computers", Scientific Reports 10, 11229 (2020).

[62] Laszlo Gyongyosi, "Quantum State Optimization and Computational Pathway Evaluation for Gate-Model Quantum Computers", Scientific Reports 10, 4543 (2020).

[63] Yuval R. Sanders, Dominic W. Berry, Pedro C. S. Costa, Louis W. Tessler, Nathan Wiebe, Craig Gidney, Hartmut Neven, and Ryan Babbush, "Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization", arXiv:2007.07391, (2020).

[64] Jahan Claes and Wim van Dam, "Instance Independence of Single Layer Quantum Approximate Optimization Algorithm on Mixed-Spin Models at Infinite Size", Quantum 5, 542 (2021).

[65] E. Campos, D. Rabinovich, V. Akshay, and J. Biamonte, "Training saturation in layerwise quantum approximate optimization", Physical Review A 104 3, L030401 (2021).

[66] Ioannis Kolotouros and Petros Wallden, "Evolving objective function for improved variational quantum optimization", Physical Review Research 4 2, 023225 (2022).

[67] Dennis Willsch, Madita Willsch, Fengping Jin, Kristel Michielsen, and Hans De Raedt, "GPU-accelerated simulations of quantum annealing and the quantum approximate optimization algorithm", Computer Physics Communications 278, 108411 (2022).

[68] Benjamin Tan, Marc-Antoine Lemonde, Supanut Thanasilp, Jirawat Tangpanitanon, and Dimitris G. Angelakis, "Qubit-efficient encoding schemes for binary optimisation problems", Quantum 5, 454 (2021).

[69] David Joseph, Antonio J. Martinez, Cong Ling, and Florian Mintert, "Quantum mean-value approximator for hard integer-value problems", Physical Review A 105 5, 052419 (2022).

[70] Laszlo Gyongyosi, "Dynamics of entangled networks of the quantum Internet", Scientific Reports 10, 12909 (2020).

[71] Shree Hari Sureshbabu, Dylan Herman, Ruslan Shaydulin, Joao Basso, Shouvanik Chakrabarti, Yue Sun, and Marco Pistoia, "Parameter Setting in Quantum Approximate Optimization of Weighted Problems", arXiv:2305.15201, (2023).

[72] Teppei Suzuki and Michio Katouda, "Predicting toxicity by quantum machine learning", Journal of Physics Communications 4 12, 125012 (2020).

[73] Laszlo Gyongyosi, "Unsupervised Quantum Gate Control for Gate-Model Quantum Computers", Scientific Reports 10, 10701 (2020).

[74] Xuchen You and Xiaodi Wu, "Exponentially Many Local Minima in Quantum Neural Networks", arXiv:2110.02479, (2021).

[75] Daniil Rabinovich, Ernesto Campos, Soumik Adhikary, Ekaterina Pankovets, Dmitry Vinichenko, and Jacob Biamonte, "On the gate-error robustness of variational quantum algorithms", arXiv:2301.00048, (2022).

[76] Asier Ozaeta, Wim van Dam, and Peter L. McMahon, "Expectation values from the single-layer quantum approximate optimization algorithm on Ising problems", Quantum Science and Technology 7 4, 045036 (2022).

[77] Laszlo Gyongyosi and Sandor Imre, "Scalable distributed gate-model quantum computers", Scientific Reports 11, 5172 (2021).

[78] Hari Krovi, "Average-case hardness of estimating probabilities of random quantum circuits with a linear scaling in the error exponent", arXiv:2206.05642, (2022).

[79] Joao Basso, David Gamarnik, Song Mei, and Leo Zhou, "Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models", arXiv:2204.10306, (2022).

[80] Michelle Chalupnik, Hans Melo, Yuri Alexeev, and Alexey Galda, "Augmenting QAOA Ansatz with Multiparameter Problem-Independent Layer", arXiv:2205.01192, (2022).

[81] Sinan Bugu, Fatih Ozaydin, and Tetsuo Kodera, "Surpassing the classical limit in magic square game with distant quantum dots coupled to optical cavities", Scientific Reports 10, 22202 (2020).

[82] Laszlo Gyongyosi and Sandor Imre, "Routing space exploration for scalable routing in the quantum Internet", Scientific Reports 10, 11874 (2020).

[83] Ioannis D. Leonidas, Alexander Dukakis, Benjamin Tan, and Dimitris G. Angelakis, "Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors", arXiv:2306.08507, (2023).

[84] Laszlo Gyongyosi, "Objective function estimation for solving optimization problems in gate-model quantum computers", Scientific Reports 10, 14220 (2020).

[85] Gabriel Matos, Sonika Johri, and Zlatko Papić, "Quantifying the efficiency of state preparation via quantum variational eigensolvers", arXiv:2007.14338, (2020).

[86] Laszlo Gyongyosi, "Decoherence dynamics estimation for superconducting gate-model quantum computers", Quantum Information Processing 19 10, 369 (2020).

[87] Kyle Mills, Pooya Ronagh, and Isaac Tamblyn, "Controlled Online Optimization Learning (COOL): Finding the ground state of spin Hamiltonians with reinforcement learning", arXiv:2003.00011, (2020).

[88] Aida Ahmadzadegan, Petar Simidzija, Ming Li, and Achim Kempf, "Neural networks can learn to utilize correlated auxiliary noise", Scientific Reports 11, 21624 (2021).

[89] Sami Boulebnane, "Improving the Quantum Approximate Optimization Algorithm with postselection", arXiv:2011.05425, (2020).

[90] E. Campos, D. Rabinovich, V. Akshay, and J. Biamonte, "Training Saturation in Layerwise Quantum Approximate Optimisation", arXiv:2106.13814, (2021).

[91] Matteo M. Wauters, Emanuele Panizon, Glen B. Mbeng, and Giuseppe E. Santoro, "Reinforcement Learning assisted Quantum Optimization", arXiv:2004.12323, (2020).

[92] G. Pederiva, A. Bazavov, B. Henke, L. Hostetler, D. Lee, H. W. Lin, and A. Shindler, "Quantum State Preparation for the Schwinger Model", The 38th International Symposium on Lattice Field Theory 47 (2022).

[93] Alexey Uvarov, Daniil Rabinovich, Olga Lakhmanskaya, Kirill Lakhmanskiy, Jacob Biamonte, and Soumik Adhikary, "Mitigating Quantum Gate Errors for Variational Eigensolvers Using Hardware-Inspired Zero-Noise Extrapolation", arXiv:2307.11156, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2023-09-28 06:12:19) and SAO/NASA ADS (last updated successfully 2023-09-28 06:12:20). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.