Document Open Access Logo

Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian Problems

Authors Ojas Parekh, Kevin Thompson

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.74.pdf
  • Filesize: 0.77 MB
  • 18 pages

Document Identifiers

Author Details

Ojas Parekh
  • Sandia National Laboratories, Albuquerque, NM, USA
Kevin Thompson
  • Sandia National Laboratories, Albuquerque, NM, USA

Funding

Sandia National Laboratories is a multimission laboratory managed and operated by National Technology and Engineering Solutions of Sandia, LLC., a wholly owned subsidiary of Honeywell International, Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA-0003525. This work was supported by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Accelerated Research in Quantum Computing and Quantum Algorithms Teams programs.

Cite AsGet BibTex

Ojas Parekh and Kevin Thompson. Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian Problems. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 74:1-74:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ESA.2021.74

Abstract

The quantum k-Local Hamiltonian problem is a natural generalization of classical constraint satisfaction problems (k-CSP) and is complete for QMA, a quantum analog of NP. Although the complexity of k-Local Hamiltonian problems has been well studied, only a handful of approximation results are known. For Max 2-Local Hamiltonian where each term is a rank 3 projector, a natural quantum generalization of classical Max 2-SAT, the best known approximation algorithm was the trivial random assignment, yielding a 0.75-approximation. We present the first approximation algorithm beating this bound, a classical polynomial-time 0.764-approximation. For strictly quadratic instances, which are maximally entangled instances, we provide a 0.801 approximation algorithm, and numerically demonstrate that our algorithm is likely a 0.821-approximation. We conjecture these are the hardest instances to approximate. We also give improved approximations for quantum generalizations of other related classical 2-CSPs. Finally, we exploit quantum connections to a generalization of the Grothendieck problem to obtain a classical constant-factor approximation for the physically relevant special case of strictly quadratic traceless 2-Local Hamiltonians on bipartite interaction graphs, where a inverse logarithmic approximation was the best previously known (for general interaction graphs). Our work employs recently developed techniques for analyzing classical approximations of CSPs and is intended to be accessible to both quantum information scientists and classical computer scientists.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Semidefinite programming
  • Theory of computation → Quantum complexity theory
Keywords
  • Quantum Approximation Algorithms
  • Local Hamiltonian

Metrics

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

Related Versions

References

  1. Dorit Aharonov, Itai Arad, and Thomas Vidick. The quantum pcp conjecture, 2013. URL: http://arxiv.org/abs/1309.7495.
  2. Anurag Anshu, David Gosset, and Karen Morenz. Beyond Product State Approximations for a Quantum Analogue of Max Cut. In Steven T. Flammia, editor, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), volume 158 of Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1-7:15, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.TQC.2020.7.
  3. Sanjeev Arora, Eli Berger, Hazan Elad, Guy Kindler, and Muli Safra. On non-approximability for quadratic programs. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), pages 206-215. IEEE, 2005. Google Scholar
  4. Nikhil Bansal, Sergey Bravyi, and Barbara M. Terhal. Classical approximation schemes for the ground-state energy of quantum and classical ising spin hamiltonians on planar graphs. Quantum Info. Comput., 9(7):701–720, 2009. Google Scholar
  5. Salman Beigi and Peter W Shor. On the complexity of computing zero-error and holevo capacity of quantum channels. arXiv preprint arXiv:0709.2090, 2007. Google Scholar
  6. Hans Bethe. Zur theorie der metalle. Zeitschrift für Physik, 71(3-4):205-226, 1931. Google Scholar
  7. Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. URL: https://doi.org/10.1017/CBO9780511804441.
  8. Fernando GSL Brandao and Aram W Harrow. Product-state approximations to quantum states. Communications in Mathematical Physics, 342(1):47-80, 2016. Google Scholar
  9. Mark Braverman, Konstantin Makarychev, Yury Makarychev, and Assaf Naor. The grothendieck constant is strictly smaller than krivine’s bound. In Forum of Mathematics, Pi, volume 1. Cambridge University Press, 2013. Google Scholar
  10. Sergey Bravyi. Efficient algorithm for a quantum analogue of 2-sat. Contemporary Mathematics, 536:33-48, 2011. Google Scholar
  11. Sergey Bravyi, David Gosset, Robert König, and Kristan Temme. Approximation algorithms for quantum many-body problems. Journal of Mathematical Physics, 60(3):032203, 2019. Google Scholar
  12. Jop Briët, Fernando Mário de Oliveira Filho, and Frank Vallentin. The positive semidefinite grothendieck problem with rank constraint. In International Colloquium on Automata, Languages, and Programming, pages 31-42. Springer, 2010. Google Scholar
  13. Jop Briët, Fernando Mário de Oliveira Filho, and Frank Vallentin. Grothendieck inequalities for semidefinite programs with rank constraint. Theory of Computing, 10(4):77-105, 2014. URL: https://doi.org/10.4086/toc.2014.v010a004.
  14. Moses Charikar and Anthony Wirth. Maximizing quadratic programs: Extending grothendieck’s inequality. In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 54-60. IEEE, 2004. Google Scholar
  15. Irit Dinur and Samuel Safra. On the hardness of approximating minimum vertex cover. Annals of mathematics, pages 439-485, 2005. Google Scholar
  16. Andrew C Doherty, Yeong-Cherng Liang, Ben Toner, and Stephanie Wehner. The quantum moment problem and bounds on entangled multi-prover games. In 2008 23rd Annual IEEE Conference on Computational Complexity, pages 199-210. IEEE, 2008. Google Scholar
  17. Uriel Feige. A threshold of ln n for approximating set cover. J. ACM, 45(4):634–652, July 1998. URL: https://doi.org/10.1145/285055.285059.
  18. Sevag Gharibian and Julia Kempe. Approximation algorithms for qma-complete problems. SIAM Journal on Computing, 41(4):1028-1050, 2012. Google Scholar
  19. Sevag Gharibian and Ojas Parekh. Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut. In Dimitris Achlioptas and László A. Végh, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019), volume 145 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1-31:17, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.31.
  20. 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. Google Scholar
  21. Sean Hallgren, Eunou Lee, and Ojas Parekh. An approximation algorithm for the max-2-local hamiltonian problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  22. Aram W Harrow and Ashley Montanaro. Extremal eigenvalues of local hamiltonians. Quantum, 1:6, 2017. Google Scholar
  23. Johan Håstad. Clique is hard to approximate withinn^1- ε. Acta Mathematica, 182(1):105-142, 1999. Google Scholar
  24. Julia Kempe, Alexei Kitaev, and Oded Regev. The complexity of the local hamiltonian problem. SIAM Journal on Computing, 35(5):1070-1097, 2006. Google Scholar
  25. Alexei Yu Kitaev, Alexander Shen, Mikhail N Vyalyi, and Mikhail N Vyalyi. Classical and Quantum Computation. Number 47. American Mathematical Soc., 2002. Google Scholar
  26. Nikolai N. Lebedev (author) and Richard Silverman (translator). Special Functions and their Applications. Courier Corporation, 1972. Google Scholar
  27. Michael Lewin, Dror Livnat, and Uri Zwick. Improved rounding techniques for the max 2-sat and max di-cut problems. In International Conference on Integer Programming and Combinatorial Optimization, pages 67-82. Springer, 2002. Google Scholar
  28. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010. URL: https://doi.org/10.1017/CBO9780511976667.
  29. Tobias J Osborne. Hamiltonian complexity. Reports on Progress in Physics, 75(2):022001, 2012. Google Scholar
  30. Ojas Parekh and Kevin Thompson. Beating random assignment for approximating quantum 2-local hamiltonian problems, 2020. URL: http://arxiv.org/abs/2012.12347.
  31. Ojas Parekh and Kevin Thompson. Application of the Level-2 Quantum Lasserre Hierarchy in Quantum Approximation Algorithms. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 102:1-102:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.102.
  32. Stephen Piddock and Ashley Montanaro. The complexity of antiferromagnetic interactions and 2d lattices. arXiv preprint arXiv:1506.04014, 2015. Google Scholar
  33. Joanna Piotrowska, Jonah M Miller, and Erik Schnetter. Spectral methods in the presence of discontinuities. Journal of Computational Physics, 390:527-547, 2019. Google Scholar
  34. Stefano Pironio, Miguel Navascués, and Antonio Acin. Convergent relaxations of polynomial optimization problems with noncommuting variables. SIAM Journal on Optimization, 20(5):2157-2180, 2010. Google Scholar
  35. Norbert Schuch and Frank Verstraete. Computational complexity of interacting electrons and fundamental limitations of density functional theory. Nature Physics, 5(10):732-735, 2009. Google Scholar
  36. Henrik Sjögren. Rigorous Analysis of Approximation Algorithms for MAX 2-CSP. Skolan för datavetenskap och kommunikation, Kungliga Tekniska högskolan, 2009. Google Scholar
  37. Vijay V Vazirani. Approximation Algorithms. Springer Science & Business Media, 2013. Google Scholar
  38. David P Williamson and David B Shmoys. The Design of Approximation Algorithms. Cambridge university press, 2011. Google Scholar
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 Imprint Privacy Contact