Reachability Deficits in Quantum Approximate Optimization of Graph Problems

V. Akshay, H. Philathong, I. Zacharov, and J. Biamonte

Skolkovo Institute of Science and Technology, 3 Nobel Street, Moscow, Russia 121205

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

Abstract

The quantum approximate optimization algorithm (QAOA) has become a cornerstone of contemporary quantum applications development. Here we show that the $density$ of problem constraints versus problem variables acts as a performance indicator. Density is found to correlate strongly with approximation inefficiency for fixed depth QAOA applied to random graph minimization problem instances. Further, the required depth for accurate QAOA solution to graph problem instances scales critically with density. Motivated by Google's recent experimental realization of QAOA, we preform a reanalysis of the reported data reproduced in an ideal noiseless setting. We found that the reported capabilities of instances addressed experimentally by Google, approach a rapid fall-off region in approximation quality experienced beyond intermediate-density. Our findings offer new insight into performance analysis of contemporary quantum optimization algorithms and contradict recent speculation regarding low-depth QAOA performance benefits.

► BibTeX data

► References

[1] Matthew P Harrigan, Kevin J Sung, Matthew Neeley, Kevin J Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C Bardin, Rami Barends, Sergio Boixo, et al. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. Nature Physics, 17 (3): 332–336, 2021. 10.1038/​s41567-020-01105-y.
https:/​/​doi.org/​10.1038/​s41567-020-01105-y

[2] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al. Quantum supremacy using a programmable superconducting processor. Nature, 574 (7779): 505–510, 2019. 10.1038/​s41586-019-1666-5.
https:/​/​doi.org/​10.1038/​s41586-019-1666-5

[3] Alán Aspuru-Guzik, Anthony D Dutoi, Peter J Love, and Martin Head-Gordon. Simulated quantum computation of molecular energies. Science, 309 (5741): 1704–1707, 2005. 10.1126/​science.1113479.
https:/​/​doi.org/​10.1126/​science.1113479

[4] Peter JJ O’Malley, Ryan Babbush, Ian D Kivlichan, Jonathan Romero, Jarrod R McClean, Rami Barends, Julian Kelly, Pedram Roushan, Andrew Tranter, Nan Ding, et al. Scalable quantum simulation of molecular energies. Physical Review X, 6 (3): 031007, 2016. 10.1103/​PhysRevX.6.031007.
https:/​/​doi.org/​10.1103/​PhysRevX.6.031007

[5] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, 549 (7671): 195–202, 2017. 10.1038/​nature23474.
https:/​/​doi.org/​10.1038/​nature23474

[6] Rongxin Xia and Sabre Kais. Quantum machine learning for electronic structure calculations. Nature communications, 9 (1): 1–6, 2018. 10.1038/​s41467-018-06598-z.
https:/​/​doi.org/​10.1038/​s41467-018-06598-z

[7] Seth Lloyd. Universal quantum simulators. Science, pages 1073–1078, 1996. URL https:/​/​www.jstor.org/​stable/​2899535.
https:/​/​www.jstor.org/​stable/​2899535

[8] Lucas Lamata, Antonio Mezzacapo, Jorge Casanova, and Enrique Solano. Efficient quantum simulation of fermionic and bosonic models in trapped ions. EPJ Quantum Technology, 1 (1): 9, 2014. 10.1140/​epjqt9.
https:/​/​doi.org/​10.1140/​epjqt9

[9] Tadashi Kadowaki and Hidetoshi Nishimori. Quantum annealing in the transverse ising model. Physical Review E, 58 (5): 5355, 1998. 10.1103/​PhysRevE.58.5355.
https:/​/​doi.org/​10.1103/​PhysRevE.58.5355

[10] Guido Pagano, Aniruddha Bapat, Patrick Becker, Katherine S Collins, Arinjoy De, Paul W Hess, Harvey B Kaplan, Antonis Kyprianidis, Wen Lin Tan, Christopher Baldwin, et al. Quantum approximate optimization of the long-range ising model with a trapped-ion quantum simulator. Proceedings of the National Academy of Sciences, 117 (41): 25396–25401, 2020. 10.1073/​pnas.2006373117.
https:/​/​doi.org/​10.1073/​pnas.2006373117

[11] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014. URL https:/​/​arxiv.org/​abs/​1411.4028.
arXiv:1411.4028

[12] Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik. The theory of variational hybrid quantum-classical algorithms. New Journal of Physics, 18 (2): 023023, 2016. 10.1088/​1367-2630/​18/​2/​023023.
https:/​/​doi.org/​10.1088/​1367-2630/​18/​2/​023023

[13] Jacob Biamonte. Universal variational quantum computation. Phys. Rev. A, 103: L030401, Mar 2021. 10.1103/​PhysRevA.103.L030401.
https:/​/​doi.org/​10.1103/​PhysRevA.103.L030401

[14] Seth Lloyd. Quantum approximate optimization is computationally universal. arXiv preprint arXiv:1812.11075, 2018. URL https:/​/​arxiv.org/​abs/​1812.11075.
arXiv:1812.11075

[15] Mauro ES Morales, Jacob D Biamonte, and Zoltán Zimborás. On the universality of the quantum approximate optimization algorithm. Quantum Information Processing, 19 (9): 1–26, 2020. 10.1007/​s11128-020-02748-9.
https:/​/​doi.org/​10.1007/​s11128-020-02748-9

[16] Cedric Yen-Yu Lin and Yechao Zhu. Performance of QAOA on Typical Instances of Constraint Satisfaction Problems with Bounded Degree. arXiv e-prints, art. arXiv:1601.01744, January 2016. URL https:/​/​arxiv.org/​abs/​1601.01744.
arXiv:1601.01744

[17] Gavin E Crooks. Performance of the quantum approximate optimization algorithm on the maximum cut problem. arXiv preprint arXiv:1811.08419, 2018. URL https:/​/​arxiv.org/​abs/​1811.08419.
arXiv:1811.08419

[18] Samuel Marsh and JB Wang. A quantum walk-assisted approximate algorithm for bounded np optimisation problems. Quantum Information Processing, 18 (3): 61, 2019. 10.1007/​s11128-019-2171-3.
https:/​/​doi.org/​10.1007/​s11128-019-2171-3

[19] Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G Rieffel. Quantum approximate optimization algorithm for maxcut: A fermionic view. Physical Review A, 97 (2): 022304, 2018. 10.1103/​PhysRevA.97.022304.
https:/​/​doi.org/​10.1103/​PhysRevA.97.022304

[20] Zhang Jiang, Eleanor G Rieffel, and Zhihui Wang. Near-optimal quantum circuit for grover's unstructured search using a transverse field. Physical Review A, 95 (6): 062317, 2017. 10.1103/​PhysRevA.95.062317.
https:/​/​doi.org/​10.1103/​PhysRevA.95.062317

[21] Mauro ES Morales, Timur Tlyachev, and Jacob Biamonte. Variational learning of grover's quantum search algorithm. Physical Review A, 98 (6): 062333, 2018. 10.1103/​PhysRevA.98.062333.
https:/​/​doi.org/​10.1103/​PhysRevA.98.062333

[22] V. Akshay, H. Philathong, M. E. S. Morales, and J. D. Biamonte. Reachability deficits in quantum approximate optimization. Phys. Rev. Lett., 124: 090504, Mar 2020. 10.1103/​PhysRevLett.124.090504.
https:/​/​doi.org/​10.1103/​PhysRevLett.124.090504

[23] JS Otterbach, R Manenti, N Alidoust, A Bestwick, M Block, B Bloom, S Caldwell, N Didier, E Schuyler Fried, S Hong, et al. Unsupervised machine learning on a hybrid quantum computer. arXiv preprint arXiv:1712.05771, 2017. URL https:/​/​arxiv.org/​abs/​1712.05771.
arXiv:1712.05771

[24] Madita Willsch, Dennis Willsch, Fengping Jin, Hans De Raedt, and Kristel Michielsen. Benchmarking the quantum approximate optimization algorithm. Quantum Information Processing, 19: 197, 2020. 10.1007/​s11128-020-02692-8.
https:/​/​doi.org/​10.1007/​s11128-020-02692-8

[25] Deanna M Abrams, Nicolas Didier, Blake R Johnson, Marcus P da Silva, and Colm A Ryan. Implementation of xy entangling gates with a single calibrated pulse. Nature Electronics, 3 (12): 744–750, 2020. 10.1038/​s41928-020-00498-1.
https:/​/​doi.org/​10.1038/​s41928-020-00498-1

[26] Andreas Bengtsson, Pontus Vikstål, Christopher Warren, Marika Svensson, Xiu Gu, Anton Frisk Kockum, Philip Krantz, Christian Križan, Daryoush Shiri, Ida-Maria Svensson, et al. Improved success probability with greater circuit depth for the quantum approximate optimization algorithm. Physical Review Applied, 14 (3): 034010, 2020. 10.1103/​PhysRevApplied.14.034010.
https:/​/​doi.org/​10.1103/​PhysRevApplied.14.034010

[27] Xiaogang Qiang, Xiaoqi Zhou, Jianwei Wang, Callum M Wilkes, Thomas Loke, Sean O’Gara, Laurent Kling, Graham D Marshall, Raffaele Santagati, Timothy C Ralph, et al. Large-scale silicon quantum photonics implementing arbitrary two-qubit processing. Nature photonics, 12 (9): 534–539, 2018. 10.1038/​s41566-018-0236-y.
https:/​/​doi.org/​10.1038/​s41566-018-0236-y

[28] Igor Zacharov, Rinat Arslanov, Maksim Gunin, Daniil Stefonishin, Andrey Bykov, Sergey Pavlov, Oleg Panarin, Anton Maliutin, Sergey Rykovanov, and Maxim Fedorov. "zhores" — petaflops supercomputer for data-driven modeling, machine learning and artificial intelligence installed in skolkovo institute of science and technology. Open Engineering, 9 (1): 512–520, October 2019. 10.1515/​eng-2019-0059.
https:/​/​doi.org/​10.1515/​eng-2019-0059

Cited by

[1] Maxime Dupont, Nicolas Didier, Mark J. Hodson, Joel E. Moore, and Matthew J. Reagor, "Entanglement perspective on the quantum approximate optimization algorithm", Physical Review A 106 2, 022423 (2022).

[2] Felix Truger, Martin Beisel, Johanna Barzen, Frank Leymann, and Vladimir Yussupov, "Selection and Optimization of Hyperparameters in Warm-Started Quantum Optimization for the MaxCut Problem", Electronics 11 7, 1033 (2022).

[3] 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).

[4] 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).

[5] 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).

[6] Ajinkya Borle, Vincent Elfving, and Samuel J. Lomonaco, "Quantum approximate optimization for hard problems in linear algebra", SciPost Physics Core 4 4, 031 (2021).

[7] Ruslan Shaydulin, Kunal Marwaha, Jonathan Wurtz, and Phillip C. Lotshaw, 2021 IEEE/ACM Second International Workshop on Quantum Computing Software (QCS) 64 (2021) ISBN:978-1-7281-8674-0.

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

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

[10] 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).

[11] Shi-Xin Zhang, Chang-Yu Hsieh, Shengyu Zhang, and Hong Yao, "Neural predictor based quantum architecture search", Machine Learning: Science and Technology 2 4, 045027 (2021).

[12] 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.

[13] Rebekah Herrman, Lorna Treffert, James Ostrowski, Phillip C. Lotshaw, Travis S. Humble, and George Siopsis, "Impact of Graph Structures for QAOA on MaxCut", arXiv:2102.05997.

[14] Ruslan Shaydulin, Kunal Marwaha, Jonathan Wurtz, and Phillip C. Lotshaw, "QAOAKit: A Toolkit for Reproducible Study, Application, and Verification of the QAOA", arXiv:2110.05555.

[15] Hariphan Philathong, Vishwa Akshay, Ksenia Samburskaya, and Jacob Biamonte, "Computational phase transitions: benchmarking Ising machines and quantum optimisers", Journal of Physics: Complexity 2 1, 011002 (2021).

The above citations are from Crossref's cited-by service (last updated successfully 2022-09-24 09:03:17) and SAO/NASA ADS (last updated successfully 2022-09-24 09:03:18). The list may be incomplete as not all publishers provide suitable and complete citation data.