Document Open Access Logo

Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs

Authors Boaz Barak , Kunal Marwaha

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.14.pdf
  • Filesize: 1.53 MB
  • 21 pages

Document Identifiers

Author Details

Boaz Barak
  • Harvard University, Cambridge, MA, USA
Kunal Marwaha
  • Berkeley Center for Quantum Information and Computation, Berkeley, CA, USA

Funding

  • Barak, Boaz: NSF award CCF 1565264, a Simons Investigator Fellowship, and DARPA grant W911NF2010021

Acknowledgements

We thank Beatrice Nash for collaborating on early stages of this project. KM thanks Jeffrey M. Epstein and Matt Hastings for explaining details on Lieb-Robinson bounds. Matt Hastings proposed a question similar to this one. Ruslan Shaydulin offered suggestions on simulating QAOA. We thank Madelyn Cain, Eddie Farhi, Pravesh Kothari, Sam Hopkins, and Leo Zhou for useful discussions. Special thanks to Leo Zhou for sharing with us the code and data from the paper [Zhou et al., 2020].

Cite As Get BibTex

Boaz Barak and Kunal Marwaha. Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITCS.2022.14

Abstract

We study the performance of local quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) for the maximum cut problem, and their relationship to that of randomized classical algorithms.  
1) We prove that every (quantum or classical) one-local algorithm (where the value of a vertex only depends on its and its neighbors' state) achieves on D-regular graphs of girth > 5 a maximum cut of at most 1/2 + C/√D for C = 1/√2 ≈ 0.7071. This is the first such result showing that one-local algorithms achieve a value that is bounded away from the true optimum for random graphs, which is 1/2 + P_*/√D + o(1/√D) for P_* ≈ 0.7632 [Dembo et al., 2017].
2) We show that there is a classical k-local algorithm that achieves a value of 1/2 + C/√D - O(1/√k) for D-regular graphs of girth > 2k+1, where C = 2/π ≈ 0.6366. This is an algorithmic version of the existential bound of [Lyons, 2017] and is related to the algorithm of [Aizenman et al., 1987] (ALR) for the Sherrington-Kirkpatrick model. This bound is better than that achieved by the one-local and two-local versions of QAOA on high-girth graphs [M. B. Hastings, 2019; Marwaha, 2021].
3) Through computational experiments, we give evidence that the ALR algorithm achieves better performance than constant-locality QAOA for random D-regular graphs, as well as other natural instances, including graphs that do have short cycles.
While our theoretical bounds require the locality and girth assumptions, our experimental work suggests that it could be possible to extend them beyond these constraints. This points at the tantalizing possibility that O(1)-local quantum maximum-cut algorithms might be pointwise dominated by polynomial-time classical algorithms, in the sense that there is a classical algorithm outputting cuts of equal or better quality on every possible instance. This is in contrast to the evidence that polynomial-time algorithms cannot simulate the probability distributions induced by local quantum algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • approximation algorithms
  • QAOA
  • maximum cut
  • local distributions

Metrics

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

Related Versions

Supplementary Materials

References

  1. Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 333-342, 2011. URL: https://arxiv.org/abs/1011.3245.
  2. Scott Aaronson and Lijie Chen. Complexity-theoretic foundations of quantum supremacy experiments. arXiv preprint, 2016. URL: https://arxiv.org/abs/1612.05903.
  3. Dorit Aharonov and Michael Ben-Or. Fault-tolerant quantum computation with constant error rate. SIAM Journal on Computing, 2008. Preliminary version in STOC 1997. URL: https://arxiv.org/abs/quant-ph/9611025.
  4. M. Aizenman, J. L. Lebowitz, and D. Ruelle. Some rigorous results on the sherrington-kirkpatrick spin glass model. Communications in Mathematical Physics, 112(1):3-20, March 1987. URL: https://doi.org/10.1007/BF01217677.
  5. 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. URL: https://www.nature.com/articles/s41586-019-1666-5.pdf.
  6. Antonio Auffinger, Wei-Kuo Chen, and Qiang Zeng. The sk model is infinite step replica symmetry breaking at zero temperature, 2021. URL: http://arxiv.org/abs/1703.06872.
  7. Ágnes Backhausz, Balázs Szegedy, and Bálint Virág. Ramanujan graphings and correlation decay in local algorithms. Random Structures & Algorithms, 47(3):424-435, 2015. URL: https://doi.org/10.1002/rsa.20562.
  8. Boaz Barak, Chi-Ning Chou, and Xun Gao. Spoofing linear cross-entropy benchmarking in shallow quantum circuits. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference, volume 185 of LIPIcs, pages 30:1-30:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ITCS.2021.30.
  9. Boaz Barak and David Steurer. Sum-of-squares proofs and the quest toward optimal algorithms. Proceedings of the International Congress of Mathematicians (ICM), 2014. URL: https://arxiv.org/abs/1404.5236.
  10. Juan Bermejo-Vega, Dominik Hangleiter, Martin Schwarz, Robert Raussendorf, and Jens Eisert. Architectures for quantum simulation showing a quantum speedup. Physical Review X, 8(2):021010, 2018. URL: https://arxiv.org/abs/1703.00466.
  11. 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, 2021. URL: http://arxiv.org/abs/2101.08448.
  12. Adam Bouland, Bill Fefferman, Zeph Landau, and Yunchao Liu. Noise and the frontier of quantum supremacy. arXiv preprint, 2021. URL: https://arxiv.org/abs/2102.01738.
  13. Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. On the complexity and verification of quantum random circuit sampling. Nature Physics, 15(2):159-163, 2019. URL: https://arxiv.org/abs/1803.04402.
  14. Sergey Bravyi, David Gosset, and Robert König. Quantum advantage with shallow circuits. Science, 362(6412):308-311, 2018. URL: https://arxiv.org/abs/1704.00690.
  15. Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. Obstacles to state preparation and variational optimization from symmetry protection. arXiv preprint, 2019. URL: https://arxiv.org/abs/1910.08980.
  16. Michael J Bremner, Richard Jozsa, and Dan J Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 467(2126):459-472, 2011. URL: https://arxiv.org/abs/1005.1407.
  17. Michael J Bremner, Ashley Montanaro, and Dan J Shepherd. Average-case complexity versus approximate simulation of commuting quantum computations. Physical review letters, 117(8):080501, 2016. URL: https://arxiv.org/abs/1504.07999.
  18. Wei-Kuo Chen, David Gamarnik, Dmitry Panchenko, and Mustazee Rahman. Suboptimality of local algorithms for a class of max-cut problems. The Annals of Probability, 47(3), May 2019. URL: https://doi.org/10.1214/18-aop1291.
  19. Endre Csóka, Balázs Gerencsér, Viktor Harangi, and Bálint Virág. Invariant gaussian processes and independent sets on regular graphs of large girth. Random Structures & Algorithms, 47(2):284-303, 2015. URL: https://arxiv.org/abs/1305.3977.
  20. Corwin de Boor. In search of degree-4 sum-of-squares lower bounds for maxcut. Technical Report CMU-CS-19-118, Carnegie Mellon University, 2019. URL: http://reports-archive.adm.cs.cmu.edu/anon/2019/CMU-CS-19-118.pdf.
  21. Amir Dembo, Andrea Montanari, and Subhabrata Sen. Extremal cuts of sparse random graphs. The Annals of Probability, 45(2):1190-1217, 2017. URL: http://arxiv.org/abs/1503.03923.
  22. William Evans, Claire Kenyon, Yuval Peres, and Leonard J Schulman. Broadcasting on trees and the ising model. Annals of Applied Probability, pages 410-433, 2000. URL: https://www.cs.ubc.ca/~will/papers/noisytrees.pdf.
  23. Edward Farhi, David Gamarnik, and Sam Gutmann. The quantum approximate optimization algorithm needs to see the whole graph: a typical case. arXiv preprint, 2020. URL: https://arxiv.org/abs/2004.09002.
  24. Edward Farhi, David Gamarnik, and Sam Gutmann. The quantum approximate optimization algorithm needs to see the whole graph: Worst case examples. arXiv preprint, 2020. URL: https://arxiv.org/abs/2005.08747.
  25. Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint, 2014. URL: http://arxiv.org/abs/1411.4028.
  26. Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Leo Zhou. The quantum approximate optimization algorithm and the sherrington-kirkpatrick model at infinite size, 2020. URL: http://arxiv.org/abs/1910.08187.
  27. Edward Farhi and Aram W Harrow. Quantum supremacy through the quantum approximate optimization algorithm, 2019. URL: http://arxiv.org/abs/1602.07674.
  28. Michel X Goemans and David P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6):1115-1145, 1995. URL: http://www-math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf.
  29. Matthew P. Harrigan, Kevin J. Sung, Matthew Neeley, et al. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. Nature Physics, 17(3):332-336, March 2021. URL: https://doi.org/10.1038/s41567-020-01105-y.
  30. Johan Håstad. Some optimal inapproximability results. Journal of the ACM (JACM), 48(4):798-859, 2001. URL: http://www.cs.umd.edu/~gasarch/BLOGPAPERS/max3satl.pdf.
  31. M. B. Hastings. Classical and quantum bounded depth approximation algorithms, 2019. URL: http://arxiv.org/abs/1905.07047.
  32. Juho Hirvonen, Joel Rybicki, Stefan Schmid, and Jukka Suomela. Large cuts with local algorithms on triangle-free graphs. The Electronic Journal of Combinatorics, pages P4-21, 2017. Preliminary version on arXiv, 2014. URL: https://arxiv.org/abs/1402.2543.
  33. Howard Karloff. How good is the goemans-williamson max cut algorithm? SIAM Journal on Computing, 29(1):336-350, 1999. URL: https://epubs.siam.org/doi/10.1137/S0097539797321481.
  34. Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, STOC '02, pages 767-775, New York, NY, USA, 2002. Association for Computing Machinery. URL: https://doi.org/10.1145/509907.510017.
  35. Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable csps? SIAM J. Comput., 37(1):319-357, 2007. Preliminary version in FOCS 2004. URL: https://doi.org/10.1137/S0097539705447372.
  36. A Yu Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics, 303(1):2-30, 2003. Preliminary version on arXiv 1997. URL: https://arxiv.org/abs/quant-ph/9707021.
  37. Emanuel Knill, Raymond Laflamme, and Wojciech H Zurek. Resilient quantum computation. Science, 279(5349):342-345, 1998. URL: https://www.jstor.org/stable/2894561.
  38. Jean B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM J. Optim., 11(3):796-817, 2001. URL: https://doi.org/10.1137/S1052623400366802.
  39. Leonid Anatolevich Levin. Universal sequential search problems. Problemy peredachi informatsii, 9(3):115-116, 1973. URL: http://www.mathnet.ru/eng/ppi914.
  40. Elliott H. Lieb and Derek W. Robinson. The finite group velocity of quantum spin systems. Communications in Mathematical Physics, 28(3):251-257, 1972. URL: https://doi.org/cmp/1103858407.
  41. Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on computing, 21(1):193-201, 1992. URL: https://www.cs.huji.ac.il/~nati/PAPERS/locality_dist_graph_algs.pdf.
  42. Russell Lyons. Factors of iid on trees. Combinatorics, Probability and Computing, 26(2):285-300, 2017. URL: http://arxiv.org/abs/1401.4197.
  43. Igor L Markov and Yaoyun Shi. Simulating quantum computation by contracting tensor networks. SIAM Journal on Computing, 38(3):963-981, 2008. URL: https://arxiv.org/abs/quant-ph/0511069.
  44. Kunal Marwaha. Local classical MAX-CUT algorithm outperforms p = 2 QAOA on high-girth regular graphs. Quantum, 5:437, April 2021. URL: https://doi.org/10.22331/q-2021-04-20-437.
  45. Andrea Montanari. Optimization of the sherrington-kirkpatrick hamiltonian. SIAM Journal on Computing, 0(0):FOCS19-1, 2021. Preliminary version in FOCS '19. URL: https://arxiv.org/abs/1812.10897.
  46. Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz. Noise stability of functions with low influences: Invariance and optimality. Annals of Mathematics, 171(1):295-341, 2010. Preliminary version in FOCS 2005. URL: https://arxiv.org/abs/math/0503503.
  47. John Napp, Rolando L La Placa, Alexander M Dalzell, Fernando GSL Brandao, and Aram W Harrow. Efficient classical simulation of random shallow 2d quantum circuits. arXiv preprint, 2019. URL: https://arxiv.org/abs/2001.00021.
  48. Feng Pan and Pan Zhang. Simulating the sycamore quantum supremacy circuits. arXiv preprint, 2021. URL: https://arxiv.org/abs/2103.03074.
  49. Dmitry Panchenko. The Sherrington-Kirkpatrick model. Springer Science & Business Media, 2013. URL: https://arxiv.org/abs/1211.1094.
  50. Pablo A Parrilo. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. PhD thesis, California Institute of Technology, 2000. URL: https://www.mit.edu/~parrilo/pubs/files/thesis.pdf.
  51. Hannes Pichler, Sheng Tao Wang, Leo Zhou, Soonwon Choi, and Mikhail Lukin. Quantum optimization for maximum independent set using rydberg atom arrays. Bulletin of the American Physical Society, 64, 2019. URL: https://arxiv.org/abs/1808.10816.
  52. John Preskill. Quantum computing in the nisq era and beyond. Quantum, 2:79, August 2018. URL: https://doi.org/10.22331/q-2018-08-06-79.
  53. Isabeau Prémont-Schwarz, Alioscia Hamma, Israel Klich, and Fotini Markopoulou-Kalamara. Lieb-robinson bounds for commutator-bounded operators. Physical Review A, 81(4), April 2010. URL: https://doi.org/10.1103/physreva.81.040102.
  54. James B Shearer. A note on bipartite subgraphs of triangle-free graphs. Random Structures & Algorithms, 3(2):223-226, 1992. URL: https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.3240030211.
  55. Peter W Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review, 41(2):303-332, 1999. Preliminary version in FOCS 1994. URL: https://arxiv.org/abs/quant-ph/9508027.
  56. Barbara M Terhal and David P DiVincenzo. Adaptive quantum computation, constant depth quantum circuits and arthur-merlin games. Quantum Information & Computation, 4(2):134-145, 2004. URL: https://arxiv.org/abs/quant-ph/0205133.
  57. 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. Physical Review X, 10(2), June 2020. URL: https://doi.org/10.1103/physrevx.10.021067.
  58. Yiqing Zhou, E Miles Stoudenmire, and Xavier Waintal. What limits the simulation of quantum computers? Physical Review X, 10(4):041038, 2020. URL: https://arxiv.org/abs/2002.07730.
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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact