Reachability Deficits in Quantum Approximate Optimization of Graph Problems

V. Akshay; H. Philathong; I. Zacharov; J. Biamonte

doi:10.22331/q-2021-08-30-532

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

Published:	2021-08-30, volume 5, page 532
Eprint:	arXiv:2007.09148v2
Doi:	https://doi.org/10.22331/q-2021-08-30-532
Citation:	Quantum 5, 532 (2021).

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.

🇺🇦 Quantum strongly condemns the 2022 invasion of Ukraine, the loss of life and war crimes inflicted by Russian forces. For more information on our policy on publishing articles by authors based in Russian institutions, see this post.

► BibTeX data

@article{Akshay2021reachability,
  doi = {10.22331/q-2021-08-30-532},
  url = {https://doi.org/10.22331/q-2021-08-30-532},
  title = {Reachability {D}eficits in {Q}uantum {A}pproximate {O}ptimization of {G}raph {P}roblems},
  author = {Akshay, V. and Philathong, H. and Zacharov, I. and Biamonte, J.},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {5},
  pages = {532},
  month = aug,
  year = {2021}
}

► 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] Ramin Fakhimi and Hamidreza Validi, Encyclopedia of Optimization 1 (2023) ISBN:978-3-030-54621-2.

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

[3] Huan-Yu Liu, Tai-Ping Sun, Yu-Chun Wu, Yong-Jian Han, and Guo-Ping Guo, "Mitigating barren plateaus with transfer-learning-inspired parameter initializations", New Journal of Physics 25 1, 013039 (2023).

[4] M. Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J. Coles, "Cost function dependent barren plateaus in shallow parametrized quantum circuits", Nature Communications 12 1, 1791 (2021).

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

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

[7] Yunlong Yu, Chenfeng Cao, Xiang-Bin Wang, Nic Shannon, and Robert Joynt, "Solution of SAT problems with the adaptive-bias quantum approximate optimization algorithm", Physical Review Research 5 2, 023147 (2023).

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

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

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

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

[12] Maxime Dupont, Nicolas Didier, Mark J. Hodson, Joel E. Moore, and Matthew J. Reagor, "Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm", PRX Quantum 3 4, 040339 (2022).

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

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

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

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

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

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

[19] 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, (2021).

[20] 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, (2021).

[21] 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 2023-09-22 21:23:46) and SAO/NASA ADS (last updated successfully 2023-09-22 21:23:46). 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.