skip to main content
10.1145/2488608.2488719acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
research-article

Product-state approximations to quantum ground states

Published:01 June 2013Publication History

ABSTRACT

The local Hamiltonian problem consists of estimating the ground-state energy (given by the minimum eigenvalue) of a local quantum Hamiltonian. It can be considered as a quantum generalization of constraint satisfaction problems (CSPs) and has a key role in quantum complexity theory, being the first and most natural QMA-complete problem known. An interesting regime for the local Hamiltonian problem is that of extensive error, where one is interested in estimating the mean ground-state energy to constant accuracy. The problem is NP-hard by the PCP theorem, but whether it is QMA-hard is an important open question in quantum complexity theory. A positive solution would represent a quantum analogue of the PCP theorem. A key feature that distinguishes quantum Hamiltonians from classical CSPs is that the solutions may involve complicated entangled states. In this paper, we demonstrate several large classes of Hamiltonians for which product (i.e. unentangled) states can approximate the ground state energy to within a small extensive error.

First, we show the mere existence of a good product-state approximation for the ground-state energy of 2-local Hamiltonians with one of more of the following properties: (1) super-constant degree, (2) small expansion, or (3) a ground state with sublinear entanglement with respect to some partition into small pieces. The approximation based on degree is a new and surprising difference between quantum Hamiltonians and classical CSPs, since in the classical setting, higher degree is usually associated with harder CSPs. The approximation based on expansion is not new, but the approximation based on low entanglement was previously known only in the regime where the entanglement was close to zero. Since the existence of a low-energy product state can be checked in NP, this implies that any Hamiltonian used for a quantum PCP theorem should have: (1) constant degree, (2) constant expansion, (3) a ``volume law'' for entanglement with respect to any partition into small parts.

Second, we show that in several cases, good product-state approximations not only exist, but can be found in deterministic polynomial time: (1) 2-local Hamiltonians on any planar graph, solving an open problem of Bansal, Bravyi, and Terhal, (2) dense k-local Hamiltonians for any constant k, solving an open problem of Gharibian and Kempe, and (3) 2-local Hamiltonians on graphs with low threshold rank, via a quantum generalization of a recent result of Barak, Raghavendra and Steurer.

Our work involves two new tools which may be of independent interest. First, we prove a new quantum version of the de Finetti theorem which does not require the usual assumption of symmetry. Second, we describe a way to analyze the application of the Lasserre/Parrilo SDP hierarchy to local quantum Hamiltonians.

References

  1. S. Aaronson. The quantum PCP manifesto, 2006. http://www.scottaaronson.com/blog/?p=139.Google ScholarGoogle Scholar
  2. D. Aharonov, I. Arad, Z. Landau, and U. Vazirani. The detectability lemma and quantum gap amplification. In STOC '09, pages 417-426, 2009, arXiv:0811.3412. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. D. Aharonov and L. Eldar. On the complexity of commuting local Hamiltonians, and tight conditions for topological order in such systems. In FOCS '11, pages 334-343, 2011, arXiv:1102.0770. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. D. Aharonov, D. Gottesman, S. Irani, and J. Kempe. The power of quantum systems on a line. Commun. Math. Phys., 287(1):41-65, 2009, arXiv:0705.4077.Google ScholarGoogle ScholarCross RefCross Ref
  5. N. Alon, W. De La Vega, R. Kannan, and M. Karpinski. Random sampling and approximation of MAX-CSP problems. In STOC '02, pages 232-239, 2002. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. I. Arad. A note about a partial no-go theorem for quantum PCP. Quant. Inf. Comp., 11(11-12):1019-1027, 2011, arXiv:1012.3319. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. JACM, 45(3):501-555, 1998. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. S. Arora and S. Safra. Probabilistic checking of proofs: A new characterization of NP. JACM, 45(1):70-122, 1998. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. B. Baker. Approximation algorithms for NP-complete problems on planar graphs. JACM, 41(1):153-180, 1994. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. 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. Quant. Inf. Comp., 9(7):701-720, 2009, arXiv:0705.1115. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. B. Barak, P. Raghavendra, and D. Steurer. Rounding semidefinite programming hierarchies via global correlation. In FOCS '11, 2011, arXiv:1104.4680. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. T. Barthel and R. Hübener. Solving condensed-matter ground-state problems by semidefinite relaxations. Physical Review Letters, 108(20):200404, 2012, arXiv:1106.4966.Google ScholarGoogle ScholarCross RefCross Ref
  13. T. Baumgratz and M. Plenio. Lower bounds for ground states of condensed matter systems. New Journal of Physics, 14(2):023027, 2012, arXiv:1106.5275.Google ScholarGoogle ScholarCross RefCross Ref
  14. F. G. Brandão and A.W. Harrow. Quantum de Finetti theorems under local measurements and applications, 2012, arXiv:1210.6367. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. F. G. S. L. Brandão, M. Christandl, and J. Yard. Faithful squashed entanglement. Commun. Math. Phys., 306(3):805-830, 2011, arXiv:1010.1750.Google ScholarGoogle ScholarCross RefCross Ref
  16. S. Bravyi, D. DiVincenzo, D. Loss, and B. Terhal. Quantum simulation of many-body Hamiltonians using perturbation theory with bounded-strength interactions. Phys. Rev. Lett., 101(7):70503, 2008, arXiv:0803.2686.Google ScholarGoogle ScholarCross RefCross Ref
  17. S. Bravyi and M. Vyalyi. Commutative version of the local Hamiltonian problem and common eigenspace problem. Quant. Inf. Comp., 5(3):187-215, May 2005, arXiv:quant-ph/0308021. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. W. Brown and D. Poulin. Quantum Markov networks and commuting Hamiltonians, 2012, arXiv:1206.0755.Google ScholarGoogle Scholar
  19. C. M. Caves, C. A. Fuchs, and R. Schack. Unknown quantum states: The quantum de Finetti representation. J. Math. Phys., 43(9):4537-4559, 2002, arXiv:quant-ph/0104088.Google ScholarGoogle ScholarCross RefCross Ref
  20. M. Christandl, R. König, G. Mitchison, and R. Renner. One-and-a-half quantum de Finetti theorems. Commun. Math. Phys., 273:473-498, 2007, arXiv:quant-ph/0602130.Google ScholarGoogle ScholarCross RefCross Ref
  21. P. Diaconis and D. Freedman. Finite exchangeable sequences. Annals of Probability, 8:745-764, 1980.Google ScholarGoogle ScholarCross RefCross Ref
  22. I. Dinur. The PCP theorem by gap amplification. J. ACM, 54(3), June 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. A. Doherty, Y. Liang, B. Toner, and S. Wehner. The quantum moment problem and bounds on entangled multi-prover games. In CCC '08, pages 199-210, 2008, arXiv:0803.4373. Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. A. C. Doherty and S. Wehner. Convergence of sdp hierarchies for polynomial optimization on the hypersphere, 2012, arXiv:1210.5048.Google ScholarGoogle Scholar
  25. S. Gharibian and J. Kempe. Approximation algorithms for qma-complete problems. SIAM J. Comput., 41(4):1028-1050, 2012, arXiv:1101.3884.Google ScholarGoogle ScholarCross RefCross Ref
  26. D. Gottesman and S. Irani. The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems. In FOCS '09, pages 95-104, 2009, arXiv:0905.2419. Google ScholarGoogle ScholarDigital LibraryDigital Library
  27. M. Hastings. Matrix product operators and central elements: Classical description of a quantum state, 2012, arXiv:1207.1671.Google ScholarGoogle Scholar
  28. M. B. Hastings. Trivial low energy states for commuting Hamiltonians, and the quantum pcp conjecture, 2012, arXiv:1201.3387. Google ScholarGoogle ScholarDigital LibraryDigital Library
  29. S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439-562, 2006.Google ScholarGoogle ScholarCross RefCross Ref
  30. R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki. Quantum entanglement. Rev. Mod. Phys., 81:865-942, Jun 2009, arXiv:quant-ph/0702225.Google ScholarGoogle ScholarCross RefCross Ref
  31. R. L. Hudson and G. R. Moody. Locally normal symmetric states and an analogue of de Finetti's theorem. Z. Wahrschein. verw. Geb., 33:343-351, 1976.Google ScholarGoogle ScholarCross RefCross Ref
  32. J. Kempe, A. Kitaev, and O. Regev. The complexity of the local Hamiltonian problem. SIAM J. Comput., 35(5):1070-1097, 2006, arXiv:quant-ph/0406180. Google ScholarGoogle ScholarDigital LibraryDigital Library
  33. A. Y. Kitaev, A. H. Shen, and M. N. Vyalyi. Classical and Quantum Computation, volume 47 of Graduate Studies in Mathematics. AMS, 2002. Google ScholarGoogle ScholarDigital LibraryDigital Library
  34. R. Koenig and R. Renner. A de Finetti representation for finite symmetric quantum states. J. Math. Phys., 46(12):122108, 2005, arXiv:quant-ph/0410229.Google ScholarGoogle ScholarCross RefCross Ref
  35. M. Navascues, A. Garcia-Saez, A. Acin, S. Pironio, and M. Plenio. A paradox in bosonic energy calculations via semidefinite programming relaxations, 2012, arXiv:1203.3777.Google ScholarGoogle Scholar
  36. R. Oliveira and B. M. Terhal. The complexity of quantum spin systems on a two-dimensional square lattice. Quantum Info. Comput., 8(10):900-924, Nov. 2008, arXiv:quant-ph/0504050. Google ScholarGoogle ScholarDigital LibraryDigital Library
  37. T. Osborne. Hamiltonian complexity, 2011, arXiv:1106.5875.Google ScholarGoogle Scholar
  38. S. Pironio, M. Navascues, and A. Acin. Convergent relaxations of polynomial optimization problems with noncommuting variables. SIAM Journal on Optimization, 20(5):2157-2180, 2010, arXiv:0903.4368. Google ScholarGoogle ScholarDigital LibraryDigital Library
  39. D. Poulin and M. Hastings. Markov entropy decomposition: a variational dual for quantum belief propagation. Physical review letters, 106(8):80403, 2011, arXiv:1012.2050.Google ScholarGoogle Scholar
  40. G. A. Raggio and R. F. Werner. Quantum statistical mechanics of general mean field systems. Helv. Phys. Acta, 62:980-1003, 1989.Google ScholarGoogle Scholar
  41. P. Raghavendra and N. Tan. Approximating CSPs with global cardinality constraints using sdp hierarchies. In SODA '12, pages 373-387, 2012, arXiv:1110.1064. Google ScholarGoogle ScholarDigital LibraryDigital Library
  42. R. Raz. A parallel repetition theorem. SIAM J. Comput., 27(3):763-803, 1998. Google ScholarGoogle ScholarDigital LibraryDigital Library
  43. R. Renner. Symmetry implies independence. Nature Physics, 3:645-649, 2007, arXiv:quant-ph/0703069.Google ScholarGoogle ScholarCross RefCross Ref
  44. I. Rodnianski and B. Schlein. Quantum fluctuations and rate of convergence towards mean field dynamics, 2007, arXiv:0711.3087.Google ScholarGoogle Scholar
  45. N. Schuch. Complexity of commuting Hamiltonians on a square lattice of qubits. Quantum Information & Computation, 11(11-12):901-912, 2011, arXiv:1105.2843. Google ScholarGoogle ScholarDigital LibraryDigital Library
  46. N. Schuch and F. Verstraete. Computational complexity of interacting electrons and fundamental limitations of density functional theory. Nature Physics, 5(10):732-735, 2009, arXiv:0712.0483.Google ScholarGoogle ScholarCross RefCross Ref
  47. E. Størmer. Symmetric states of infinite tensor products of C*-algebras. J. Funct. Anal., 3:48, 1969.Google ScholarGoogle ScholarCross RefCross Ref
  48. B. Terhal. Is entanglement monogamous?, 2003, arXiv:quant-ph/0307120. Google ScholarGoogle ScholarDigital LibraryDigital Library
  49. V. Vazirani. Approximation Algorithms. Springer, 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  50. J. Watrous. Quantum computational complexity, 2008, arXiv:0804.3401.Google ScholarGoogle Scholar
  51. R. F. Werner. An application of Bell's inequalities to a quantum state extension problem. Lett. Math. Phys., 17:359, 1989.Google ScholarGoogle ScholarCross RefCross Ref
  52. D. Yang. A simple proof of monogamy of entanglement. Physics Letters A, 360(2):249-250, 2006, arXiv:quant-ph/0604168.Google ScholarGoogle ScholarCross RefCross Ref
  53. D. Yang, K. Horodecki, M. Horodecki, P. Horodecki, J. Oppenheim, and W. Song. Squashed entanglement for multipartite states and entanglement measures based on the mixed convex roof. IEEE Trans. Inf. Th., 55(7):3375-3387, July 2009, arXiv:0704.2236. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Product-state approximations to quantum ground states

    Recommendations

    Comments

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Sign in
    • Published in

      cover image ACM Conferences
      STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing
      June 2013
      998 pages
      ISBN:9781450320290
      DOI:10.1145/2488608

      Copyright © 2013 ACM

      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      • Published: 1 June 2013

      Permissions

      Request permissions about this article.

      Request Permissions

      Check for updates

      Qualifiers

      • research-article

      Acceptance Rates

      STOC '13 Paper Acceptance Rate100of360submissions,28%Overall Acceptance Rate1,469of4,586submissions,32%

      Upcoming Conference

      STOC '24
      56th Annual ACM Symposium on Theory of Computing (STOC 2024)
      June 24 - 28, 2024
      Vancouver , BC , Canada

    PDF Format

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader