Document Open Access Logo

Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut

Authors Sevag Gharibian, Ojas Parekh

PDF

File

Thumbnail PDF
PDF
LIPIcs.APPROX-RANDOM.2019.31.pdf
  • Filesize: 0.5 MB
  • 17 pages

Document Identifiers

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
  • Max-Cut
  • local Hamiltonian
  • QMA-hard
  • Heisenberg model
  • product state

Metrics

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

Abstract

Approximation algorithms for constraint satisfaction problems (CSPs) are a central direction of study in theoretical computer science. In this work, we study classical product state approximation algorithms for a physically motivated quantum generalization of Max-Cut, known as the quantum Heisenberg model. This model is notoriously difficult to solve exactly, even on bipartite graphs, in stark contrast to the classical setting of Max-Cut. Here we show, for any interaction graph, how to classically and efficiently obtain approximation ratios 0.649 (anti-feromagnetic XY model) and 0.498 (anti-ferromagnetic Heisenberg XYZ model). These are almost optimal; we show that the best possible ratios achievable by a product state for these models is 2/3 and 1/2, respectively.

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.31

Author Details

Sevag Gharibian
  • University of Paderborn, Germany
  • Virginia Commonwealth University, Richmond, VA, USA
Ojas Parekh
  • Sandia National Laboratories, Albuquerque, New Mexico, USA

Funding

  • Gharibian, Sevag: NSF grants CCF-1526189 and CCF-1617710
  • Parekh, Ojas: Laboratory Directed Research and Development program at Sandia National Laboratories, 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. Also supported by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Quantum Algorithms Teams program.

Acknowledgements

We thank David Gosset and Mark Wilde for helpful discussions, and an anonymous referee for catching a technical error in an earlier version of this draft.

References

  1. D. Aharonov, I. Arad, Z. Landau, and U. Vazirani. The detectibility lemma and quantum gap amplification. In Proceedings of 41st ACM Symposium on Theory of Computing (STOC 2009), volume 287, pages 417-426, 2009. Google Scholar
  2. 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.
  3. S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501-555, 1998. Prelim. version FOCS '92. Google Scholar
  4. 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. Google Scholar
  5. N. Bansal, S. Bravyi, and B. M. Terhal. Classical approximation schemes for the ground-state energy of quantum and classical Ising spin Hamiltonians on planar graphs. Quantum Information & Computation, 9(7&8):0701-0720, 2009. Google Scholar
  6. H. Bethe. Zur Theorie der Metalle. Zeitschrift für Physik, 71(3-4):205-226, 1931. Google Scholar
  7. F. Brandão and A. Harrow. Product-state Approximations to Quantum Ground States. In Proceedings of the 45th ACM Symposium on the Theory of Computing (STOC 2013), pages 871-880, 2013. Google Scholar
  8. S. Bravyi. Monte Carlo simulation of stoquastic Hamiltonians. Quantum Information & Computation, 15(13&14):1122-1140, 2015. Google Scholar
  9. S. Bravyi, D. Gosset, R. Koenig, and K. Temme. Approximation algorithms for quantum many-body problems. Available at arXiv.org e-Print quant-ph/arXiv:1808.01734, 2018. URL: http://arxiv.org/abs/1808.01734.
  10. S. Bravyi and M. Hastings. On complexity of the quantum Ising model. Communications in Mathematical Physics, 349(1):1-45, 2014. Google Scholar
  11. Sergey Bravyi and David Gosset. Polynomial-Time Classical Simulation of Quantum Ferromagnets. Physical Review Letters, 119:100503, September 2017. URL: https://doi.org/10.1103/PhysRevLett.119.100503.
  12. J. Briët, F. M. de Oliveira Filho, and F. Vallentin. Grothendieck inequalities for semidefinite programs with rank constraint. Theory of Computing, 10:77-105, 2014. Google Scholar
  13. 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
  14. T. Cubitt and A. Montanaro. Complexity classification of local Hamiltonian problems. SIAM Journal on Computing, 45(2):268-316, 2016. Google Scholar
  15. U. Fano. Pairs of two-level systems. Reviews of Modern Physics, 55:855-874, 1983. Google Scholar
  16. S. Gharibian and J. Kempe. Approximation algorithms for QMA-complete problems. Siam Journal on Computing, 41(4):1028-1050, 2012. Google Scholar
  17. S. Gharibian and J. Kempe. Hardness of approximation for quantum problems. In Proceedings of 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), pages 387-398, 2012. © 2012 Springer, www.springerlink.com. URL: https://doi.org/10.1007/978-3-642-31594-7.
  18. Sevag Gharibian, Yichen Huang, Zeph Landau, and Seung Woo Shin. Quantum Hamiltonian Complexity. Foundations and Trendsregistered in Theoretical Computer Science, 10(3):159-282, 2014. URL: https://doi.org/10.1561/0400000066.
  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. Google Scholar
  20. D. Hochbaum. Approximation Algorithms for NP-Hard Problems. Wadsworth Publishing Company, 1997. Google Scholar
  21. R. A. Horn and C. H. Johnson. Matrix Analysis. Cambridge University Press, 1990. Google Scholar
  22. R. Horodecki and M. Horodecki. Information-theoretic aspects of quantum inseparability of mixed states. Physical Review A, 54(3):1838-1843, 1996. Google Scholar
  23. R. Horodecki and P. Horodecki. Perfect correlations in the Einstein-Podolsky-Rosen experiment and Bell’s inequalities. Physics Letters A, 210:227, 1996. Google Scholar
  24. A. Kitaev, A. Shen, and M. Vyalyi. Classical and Quantum Computation. American Mathematical Society, 2002. Google Scholar
  25. E. Lee and S. Hallgren. Approximation of MAX-2-local Hamiltonians. To be presented at the 19th Asian Quantum Information Science Conference (AQIS), 2019. Google Scholar
  26. A. Natarajan and T. Vidick. Low-degree testing for quantum states, and a quantum entangled games PCP for QMA. In Proceedings of the 59th IEEE Symposium on Foundations of Computer Science (FOCS), pages 731-742, 2018. Google Scholar
  27. M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000. Google Scholar
  28. T. J. Osborne. Hamiltonian complexity. Reports on Progress in Physics, 75(2):022001, 2012. URL: http://stacks.iop.org/0034-4885/75/i=2/a=022001.
  29. Stephen Piddock and Ashley Montanaro. The Complexity of Antiferromagnetic Interactions and 2D Lattices. Quantum Information & Computation, 17(7-8):636-672, June 2017. URL: http://dl.acm.org/citation.cfm?id=3179553.3179559.
  30. V. Vazirani. Approximation Algorithms. Springer, 2001. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact