Document Open Access Logo

The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate

Authors Lennart Bittel , Sevag Gharibian , Martin Kliesch

PDF

File

Thumbnail PDF
PDF
LIPIcs.CCC.2023.34.pdf
  • Filesize: 0.93 MB
  • 24 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum complexity theory
Keywords
  • Variational quantum algorithms (VQA)
  • Quantum Approximate Optimization Algorithm (QAOA)
  • circuit depth minimization
  • Quantum-Classical Merlin-Arthur (QCMA)
  • hardness of approximation
  • hybrid quantum algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

Variational Quantum Algorithms (VQAs), such as the Quantum Approximate Optimization Algorithm (QAOA) of [Farhi, Goldstone, Gutmann, 2014], have seen intense study towards near-term applications on quantum hardware. A crucial parameter for VQAs is the depth of the variational ansatz used - the smaller the depth, the more amenable the ansatz is to near-term quantum hardware in that it gives the circuit a chance to be fully executed before the system decoheres. In this work, we show that approximating the optimal depth for a given VQA ansatz is intractable. Formally, we show that for any constant ε > 0, it is QCMA-hard to approximate the optimal depth of a VQA ansatz within multiplicative factor N^(1-ε), for N denoting the encoding size of the VQA instance. (Here, Quantum Classical Merlin-Arthur (QCMA) is a quantum generalization of NP.) We then show that this hardness persists in the even "simpler" QAOA-type settings. To our knowledge, this yields the first natural QCMA-hard-to-approximate problems.

Cite As Get BibTex

Lennart Bittel, Sevag Gharibian, and Martin Kliesch. The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 34:1-34:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.CCC.2023.34

Author Details

Lennart Bittel
  • Institute for Theoretical Physics, Heinrich Heine University Düsseldorf, Germany
Sevag Gharibian
  • Department of Computer Science, and Institute for Photonic Quantum Systems, Universität Paderborn, Germany
Martin Kliesch
  • Institute for Theoretical Physics, Heinrich Heine University Düsseldorf, Germany
  • Institute for Quantum-Inspired and Quantum Optimization, Technische Universtiät Hamburg, Germany

Funding

Lennart Bittel and Martin Kliesch: German Federal Ministry of Education and Research (BMBF), funding program "Quantum Technologies - from Basic Research to Market" via the joint project MANIQU (grant number 13N15578); Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under the grant number 441423094 within the Emmy Noether Program.
  • Gharibian, Sevag: DFG under grant numbers 450041824 and 432788384; the BMBF within the funding program "Quantum Technologies - from Basic Research to Market" via project PhoQuant (grant number 13N16103); project "PhoQC" from the programme "Profilbildung 2020", an initiative of the Ministry of Culture and Science of the State of North Rhine-Westphalia.

Acknowledgements

We thank Ashley Montanaro for helpful discussions.

References

  1. Dorit Aharonov, Itai Arad, and Thomas Vidick. Guest column: The quantum PCP conjecture. SIGACT News, 44(2):47-79, June 2013. URL: https://doi.org/10.1145/2491533.2491549.
  2. Dorit Aharonov and Tomer Naveh. Quantum NP - a survey, 2002. URL: https://arxiv.org/abs/quant-ph/0210077.
  3. Eric R. Anschuetz and Bobak T. Kiani. Beyond barren plateaus: Quantum variational algorithms are swamped with traps, 2022. URL: https://arxiv.org/abs/2205.05786.
  4. Anurag Anshu and Tony Metger. Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations, 2022. URL: https://arxiv.org/abs/2209.02715.
  5. S. Arora and S. Safra. Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM, 45(1):70-122, 1998. Prelim. version FOCS '92. URL: https://doi.org/10.1145/273865.273901.
  6. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501-555, 1998. Prelim. version FOCS '92. URL: https://doi.org/10.1145/278298.278306.
  7. 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, 2022. URL: https://doi.org/10.48550/arXiv.2204.10306.
  8. 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. Rev. Mod. Phys., 94(1):015004, January 2022. URL: https://doi.org/10.1103/RevModPhys.94.015004.
  9. Lennart Bittel and Martin Kliesch. Training variational quantum algorithms is NP-hard. Phys. Rev. Lett, 127:120502, September 2021. URL: https://doi.org/10.1103/PhysRevLett.127.120502.
  10. Sami Boulebnane and Ashley Montanaro. Solving boolean satisfiability problems with the quantum approximate optimization algorithm, 2022. URL: https://doi.org/10.48550/arXiv.2208.06909.
  11. Gregory Boyd and Bálint Koczor. Training variational quantum circuits with covar: covariance root finding with classical shadows, 2022. URL: https://arxiv.org/abs/2204.08494.
  12. Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. Obstacles to variational quantum optimization from symmetry protection. Phys. Rev. Lett., 125:260505, December 2020. URL: https://doi.org/10.1103/PhysRevLett.125.260505.
  13. M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick J. Coles. Variational quantum algorithms. Nat. Rev. Phys., 3:625-644, 2021. URL: https://doi.org/10.1038/s42254-021-00348-9.
  14. Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm, 2014. URL: https://arxiv.org/abs/1411.4028.
  15. Edward Farhi and Aram W Harrow. Quantum supremacy through the quantum approximate optimization algorithm, 2016. URL: https://arxiv.org/abs/1602.07674.
  16. Richard P Feynman. Quantum mechanical computers. Found. Phys., 16(6):507-531, 1986. URL: http://www.cs.princeton.edu/courses/archive/fall05/frs119/papers/feynman85_optics_letters.pdf.
  17. S. Gharibian and J. Sikora. Ground state connectivity of local Hamiltonians. In 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pages 617-628, 2015. URL: https://doi.org/10.1007/978-3-662-47672-7_50.
  18. Sevag Gharibian and Julia Kempe. Hardness of approximation for quantum problems. In 39th International Colloquium on Automata, Languages and Programming (ICALP), pages 387-398, 2012. URL: https://doi.org/10.1007/978-3-642-31594-7_33.
  19. M. Goemans and D. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42:1115-1145, 1995. URL: https://doi.org/10.1145/227683.227684.
  20. David Gosset, Jenish C. Mehta, and Thomas Vidick. QCMA hardness of ground space connectivity for commuting Hamiltonians. Quantum, 1:16, July 2017. URL: https://doi.org/10.22331/q-2017-07-14-16.
  21. Harper R. Grimsley, George S. Barron, Edwin Barnes, Sophia E. Economou, and Nicholas J. Mayhall. ADAPT-VQE is insensitive to rough parameter landscapes and barren plateaus, 2022. URL: https://arxiv.org/abs/2204.07179.
  22. Harper R. Grimsley, Sophia E. Economou, Edwin Barnes, and Nicholas J. Mayhall. An adaptive variational algorithm for exact molecular simulations on a quantum computer. Nat. Commun., 10:3007, July 2019. URL: https://doi.org/10.1038/s41467-019-10988-2.
  23. Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor G. Rieffel, Davide Venturelli, and Rupak Biswas. From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms, 12(2):34, 2019. URL: https://doi.org/https://www.mdpi.com/1999-4893/12/2/34.
  24. Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics, 16:1050-1057, June 2020. URL: https://doi.org/10.1038/s41567-020-0932-7.
  25. Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi. Classical and quantum computation, volume 47. American Mathematical Society, 2002. URL: https://bookstore.ams.org/gsm-47.
  26. Bálint Koczor and Simon C. Benjamin. Quantum analytic descent. Phys. Rev. Research, 4(2):023017, April 2022. URL: https://doi.org/10.1103/PhysRevResearch.4.023017.
  27. Martin Larocca, Nathan Ju, Diego García-Martín, Patrick J. Coles, and M. Cerezo. Theory of overparametrization in quantum neural networks, 2021. URL: https://arxiv.org/abs/2109.11676.
  28. Seth Lloyd. Universal quantum simulators. Science, 273(5278):1073-1078, 1996. URL: https://doi.org/10.1126/science.273.5278.1073.
  29. Guang Hao Low and Isaac L. Chuang. Optimal Hamiltonian simulation by quantum signal processing. Phys. Rev. Lett., 118:010501, January 2017. URL: https://doi.org/10.1103/PhysRevLett.118.010501.
  30. Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes. Nat. Commun., 9:4812, November 2018. URL: https://doi.org/10.1038/s41467-018-07090-4.
  31. Javier Rivera-Dean, Patrick Huembeli, Antonio Acín, and Joseph Bowles. Avoiding local minima in variational quantum algorithms with neural networks, 2021. URL: https://arxiv.org/abs/2104.02955.
  32. Lucas Slattery, Benjamin Villalonga, and Bryan K. Clark. Unitary block optimization for variational quantum algorithms. Phys. Rev. Research, 4(2):023072, April 2022. URL: https://doi.org/10.1103/PhysRevResearch.4.023072.
  33. Bobak Toussi Kiani, Seth Lloyd, and Reevu Maity. Learning unitaries by gradient descent, 2020. URL: https://arxiv.org/abs/2001.11897.
  34. C. Umans. Hardness of approximating Σ₂^p minimization problems. In 40th Symposium on Foundations of Computer Science, pages 465-474, 1999. Google Scholar
  35. J. D. Watson, J. Bausch, and S. Gharibian. The Complexity of Translationally Invariant Problems beyond Ground State Energies. In 40th Symposium on Theoretical Aspects of Computer Science (STACS 2023), 2023. Google Scholar
  36. David Wierichs, Christian Gogolin, and Michael Kastoryano. Avoiding local minima in variational quantum eigensolvers with the natural gradient optimizer. Phys. Rev. Research, 2(4):043246, November 2020. URL: https://doi.org/10.1103/PhysRevResearch.2.043246.
  37. Roeland Wiersema, Cunlu Zhou, Yvette de Sereville, Juan Felipe Carrasquilla, Yong Baek Kim, and Henry Yuen. Exploring entanglement and optimization within the Hamiltonian variational ansatz. PRX Quantum, 1:020319, 2020. URL: https://doi.org/10.1103/PRXQuantum.1.020319.
  38. P. Wocjan, D. Janzing, and T. Beth. Two QCMA-complete problems. Quantum Information & Computation, 3(6):635-643, 2003. URL: https://doi.org/10.5555/2011556.2011563.
  39. Dan-Bo Zhang and Tao Yin. Collective optimization for variational quantum eigensolvers. Phys. Rev. A, 101(3):032311, March 2020. URL: https://doi.org/10.1103/PhysRevA.101.032311.
  40. 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. URL: https://doi.org/10.1103/PhysRevX.10.021067.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact