Document Open Access Logo

Application of the Level-2 Quantum Lasserre Hierarchy in Quantum Approximation Algorithms

Authors Ojas Parekh, Kevin Thompson

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.102.pdf
  • Filesize: 0.75 MB
  • 20 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. Application of the Level-2 Quantum Lasserre Hierarchy in Quantum Approximation Algorithms. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 102:1-102:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.102

Abstract

The Lasserre Hierarchy is a set of semidefinite programs which yield increasingly tight bounds on optimal solutions to many NP-hard optimization problems. The hierarchy is parameterized by levels, with a higher level corresponding to a more accurate relaxation. High level programs have proven to be invaluable components of approximation algorithms for many NP-hard optimization problems. There is a natural analogous quantum hierarchy, which is also parameterized by level and provides a relaxation of many (QMA-hard) quantum problems of interest. In contrast to the classical case, however, there is only one approximation algorithm which makes use of higher levels of the hierarchy. Here we provide the first ever use of the level-2 hierarchy in an approximation algorithm for a particular QMA-complete problem, so-called Quantum Max Cut. We obtain modest improvements on state-of-the-art approximation factors for this problem, as well as demonstrate that the level-2 hierarchy satisfies many physically-motivated constraints that the level-1 does not satisfy. Indeed, this observation is at the heart of our analysis and indicates that higher levels of the quantum Lasserre Hierarchy may be very useful tools in the design of approximation algorithms for QMA-complete problems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Semidefinite programming
  • Theory of computation → Quantum complexity theory
Keywords
  • Quantum Max Cut
  • Quantum Approximation Algorithms
  • Lasserre Hierarchy
  • Local Hamiltonian
  • Heisenberg model

Metrics

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

References

  1. Milton Abramowitz and Irene A Stegun. Handbook of mathematical functions with formulas, graphs, and mathematical tables, volume 55. US Government printing office, 1948. Google Scholar
  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. ISSN: 1868-8969. Google Scholar
  3. Boaz Barak, Fernando G.S.L. Brandão, Aram W. Harrow, Jonathan Kelner, David Steurer, and Yuan Zhou. Hypercontractivity, sum-of-squares proofs, and their applications. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 307-326, 2012. Google Scholar
  4. Adam D. Bookatz. QMA-complete problems. Quantum Info. Comput., 14(5 & 6):361–383, 2014. Google Scholar
  5. Fernando G.S.L. Brandão and Aram W. Harrow. Product-state approximations to quantum ground states. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC '13, page 871–880, New York, NY, USA, 2013. Association for Computing Machinery. Google Scholar
  6. 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
  7. Eden Chlamtáč and Gyanit Singh. Improved approximation guarantees through higher levels of SDP hierarchies. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pages 49-62. Springer, 2008. Google Scholar
  8. 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
  9. Sevag Gharibian and Ojas Parekh. Almost optimal classical approximation algorithms for a quantum generalization of max-cut. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  10. 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
  11. Dima Grigoriev. Complexity of positivstellensatz proofs for the knapsack. computational complexity, 10(2):139-154, 2001. Google Scholar
  12. 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
  13. Ryszard Horodecki and Michał Horodecki. Information-theoretic aspects of inseparability of mixed states. Physical Review A, 54(3):1838, 1996. Google Scholar
  14. Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 767-775, 2002. Google Scholar
  15. Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM Journal on Computing, 37(1):319-357, 2007. Google Scholar
  16. Subhash Khot and Nisheeth K Vishnoi. On the unique games conjecture. In FOCS, volume 5, page 3. Citeseer, 2005. Google Scholar
  17. Alexei Yu Kitaev, Alexander Shen, Mikhail N Vyalyi, and Mikhail N Vyalyi. Classical and quantum computation. Number 47 in Graduate studies in mathematics. American Mathematical Soc., 2002. Google Scholar
  18. Jean B Lasserre. An explicit exact SDP relaxation for nonlinear 0-1 programs. In International Conference on Integer Programming and Combinatorial Optimization, pages 293-303. Springer, 2001. Google Scholar
  19. Jean B Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on optimization, 11(3):796-817, 2001. Google Scholar
  20. Elliott Lieb and Daniel Mattis. Ordering energy levels of interacting spin systems. Journal of Mathematical Physics, 3(4):749-751, 1962. Google Scholar
  21. Yi-Kai Liu. Consistency of local density matrices is QMA-complete. In Approximation, randomization, and combinatorial optimization. algorithms and techniques, pages 438-449. Springer, 2006. Google Scholar
  22. Ojas Parekh and Kevin Thompson. Beating random assignment for approximating quantum 2-local Hamiltonian problems. arXiv preprint, 2020. URL: http://arxiv.org/abs/2012.12347.
  23. Pablo A Parrilo. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. PhD thesis, California Institute of Technology, 2000. Google Scholar
  24. Stefano Pironio, Miguel Navascués, and Antonio Acìn. Convergent relaxations of polynomial optimization problems with noncommuting variables. SIAM Journal on Optimization, 20(5):2157-2180, 2010. Google Scholar
  25. William Pulleyblank and Jack Edmonds. Facets of 1-matching polyhedra. In Claude Berge and Dijen Ray-Chaudhuri, editors, Hypergraph Seminar, pages 214-242, Berlin, Heidelberg, 1974. Springer Berlin Heidelberg. Google Scholar
  26. Prasad Raghavendra and Ning Tan. Approximating CSPs with global cardinality constraints using SDP hierarchies. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 373-387. SIAM, 2012. Google Scholar
  27. Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer Science & Business Media, 2003. Google Scholar
  28. Lieven Vandenberghe and Stephen Boyd. Semidefinite programming. SIAM Review, 38(1):49-95, 1996. Publisher: Society for Industrial and Applied Mathematics. Google Scholar
  29. Vijay V Vazirani. Approximation algorithms. Springer Science & Business Media, 2013. Google Scholar
  30. David P Williamson and David B Shmoys. The design of approximation algorithms. Cambridge University Press, 2011. Google Scholar
  31. Fuzhen Zhang. The Schur complement and its applications, volume 4. Springer Science & Business Media, 2006. 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