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.


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.

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

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

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

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

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

[7] Seth Lloyd. Universal quantum simulators. Science, pages 1073–1078, 1996. URL https:/​/​​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.

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

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

[11] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014. URL https:/​/​​abs/​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.

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

[14] Seth Lloyd. Quantum approximate optimization is computationally universal. arXiv preprint arXiv:1812.11075, 2018. URL https:/​/​​abs/​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.

[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:/​/​​abs/​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:/​/​​abs/​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.

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

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

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

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

[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:/​/​​abs/​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.

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

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

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

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

Cited by

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

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

[3] 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 (NISQ) algorithms", arXiv:2101.08448.

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

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

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

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

The above citations are from Crossref's cited-by service (last updated successfully 2021-12-08 10:26:57) and SAO/NASA ADS (last updated successfully 2021-12-08 10:26:58). The list may be incomplete as not all publishers provide suitable and complete citation data.