Document Open Access Logo

An Approximation Algorithm for the MAX-2-Local Hamiltonian Problem

Authors Sean Hallgren, Eunou Lee, Ojas Parekh

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2020.59.pdf
  • Filesize: 460 kB
  • 18 pages

Document Identifiers

Author Details

Sean Hallgren
  • Pennsylvania State University, State College, University Park, PA, USA
Eunou Lee
  • Pennsylvania State University, State College, University Park, PA, USA
Ojas Parekh
  • Sandia National Laboratories, Albuquerque, NM, USA

Funding

  • Hallgren, Sean: Partially supported by National Science Foundation awards CCF-1618287, CCF-1617710 and CNS-1617802, by a Vannevar Bush Faculty Fellowship from the US Department of Defense, and in part while the author was visiting the Simons Institute for the Theory of Computing.
  • Parekh, Ojas: 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. Supported by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Accelerated Research for Quantum Computing and Quantum Algorithms Teams programs.

Acknowledgements

Thanks to Jianqiang Li and Sevag Gharibian for interesting discussions and useful comments.

Cite AsGet BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 59:1-59:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.59

Abstract

We present a classical approximation algorithm for the MAX-2-Local Hamiltonian problem. This is a maximization version of the QMA-complete 2-Local Hamiltonian problem in quantum computing, with the additional assumption that each local term is positive semidefinite. The MAX-2-Local Hamiltonian problem generalizes NP-hard constraint satisfaction problems, and our results may be viewed as generalizations of approximation approaches for the MAX-2-CSP problem. We work in the product state space and extend the framework of Goemans and Williamson for approximating MAX-2-CSPs. The key difference is that in the product state setting, a solution consists of a set of normalized 3-dimensional vectors rather than boolean numbers, and we leverage approximation results for rank-constrained Grothendieck inequalities. For MAX-2-Local Hamiltonian we achieve an approximation ratio of 0.328. This is the first example of an approximation algorithm beating the random quantum assignment ratio of 0.25 by a constant factor.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Semidefinite programming
  • Theory of computation → Quantum complexity theory
Keywords
  • approximation algorithm
  • quantum computing
  • local Hamiltonian
  • mean-field theory
  • randomized rounding

Metrics

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

References

  1. Farid Alizadeh. Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM Journal on Optimization, 5:13-51, 1993. Google Scholar
  2. Anurag Anshu, David Gosset, and Karen Morenz. Beyond product state approximations for a quantum analogue of Max Cut. arXiv:2003.14394 [quant-ph], March 2020. URL: http://arxiv.org/abs/2003.14394.
  3. Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, and Muli Safra. On non-approximability for quadratic programs. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS '05, pages 206-215, Washington, DC, USA, 2005. IEEE Computer Society. URL: https://doi.org/10.1109/SFCS.2005.57.
  4. Per Austrin. Towards sharp inapproximability for any 2-CSP. SIAM Journal on Computing, 39(6):2430-2463, 2010. URL: https://doi.org/10.1137/070711670.
  5. 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. Quant. Inf. Comp. Vol. 9, No.8, p. 0701 (2009), 2007. arXiv:0705.1115v4. URL: http://arxiv.org/abs/0705.1115.
  6. Adam D. Bookatz. Qma-complete problems. Quantum Info. Comput., 14(5&6):361-383, April 2014. URL: http://dl.acm.org/citation.cfm?id=2638661.2638662.
  7. Fernando G. S. L. Brandão and Aram W. Harrow. Product-state approximations to quantum states. Communications in Mathematical Physics, 342(1):47-80, February 2016. URL: https://doi.org/10.1007/s00220-016-2575-1.
  8. 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. URL: https://doi.org/10.1063/1.5085428.
  9. Jop Briët, Fernando Mário de Oliveira Filho, and Frank Vallentin. The positive semidefinite Grothendieck problem with rank constraint. In Automata, Languages and Programming, pages 31-42, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. Google Scholar
  10. Moses Charikar and Anthony Wirth. Maximizing quadratic programs: Extending grothendieck’s inequality. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS '04, pages 54-60, Washington, DC, USA, 2004. IEEE Computer Society. URL: https://doi.org/10.1109/FOCS.2004.39.
  11. Toby Cubitt and Ashley Montanaro. Complexity classification of local hamiltonian problems. SIAM Journal on Computing, 45(2):268-316, 2016. Google Scholar
  12. Sevag Gharibian and Julia Kempe. Approximation algorithms for QMA-complete problems. SIAM Journal on Computing 41(4): 1028-1050, 2012, 2011. https://arxiv.org/abs/1101.3884v1. URL: https://doi.org/10.1137/110842272.
  13. Sevag Gharibian and Julia Kempe. Hardness of approximation for quantum problems, pages 387-398. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. URL: https://doi.org/10.1007/978-3-642-31594-7_33.
  14. 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, 2019. Google Scholar
  15. Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115-1145, November 1995. URL: https://doi.org/10.1145/227683.227684.
  16. Aram W. Harrow and Ashley Montanaro. Extremal eigenvalues of local Hamiltonians. Quantum, 1:6, April 2017. URL: https://doi.org/10.22331/q-2017-04-25-6.
  17. S. Khot, G. Kindler, E. Mossel, and R. O'Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs. In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 146-154, October 2004. URL: https://doi.org/10.1109/FOCS.2004.49.
  18. Subhash Khot and Assaf Naor. Grothendieck-type inequalities in combinatorial optimization. Communications on Pure and Applied Mathematics, 65(7):992-1035, July 2012. URL: https://doi.org/10.1002/cpa.21398.
  19. A. Yu. Kitaev, A. H. Shen, and M. N. Vyalyi. Classical and Quantum Computation. American Mathematical Society, Boston, MA, USA, 2002. Google Scholar
  20. Michael Lewin, Dror Livnat, and Uri Zwick. Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems. In Integer Programming and Combinatorial Optimization, pages 67-82, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg. Google Scholar
  21. Konstantin Makarychev and Yury Makarychev. Approximation algorithms for CSPs. In The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 287-325. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017. URL: https://doi.org/10.4230/DFU.Vol7.15301.287.
  22. Shiro Matuura and Tomomi Matsui. 0.863-approximation algorithm for MAX DICUT. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, pages 138-146, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg. Google Scholar
  23. Uri Zwick. Analyzing the MAX 2-SAT and MAX DI-CUT approximation algorithms of Feige and Goemans, 2000. 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