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.
- S. Aaronson. The quantum PCP manifesto, 2006. http://www.scottaaronson.com/blog/?p=139.Google Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarCross Ref
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- S. Arora and S. Safra. Probabilistic checking of proofs: A new characterization of NP. JACM, 45(1):70-122, 1998. Google ScholarDigital Library
- B. Baker. Approximation algorithms for NP-complete problems on planar graphs. JACM, 41(1):153-180, 1994. Google ScholarDigital Library
- 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 ScholarDigital Library
- B. Barak, P. Raghavendra, and D. Steurer. Rounding semidefinite programming hierarchies via global correlation. In FOCS '11, 2011, arXiv:1104.4680. Google ScholarDigital Library
- 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 ScholarCross Ref
- 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 ScholarCross Ref
- F. G. Brandão and A.W. Harrow. Quantum de Finetti theorems under local measurements and applications, 2012, arXiv:1210.6367. Google ScholarDigital Library
- 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 ScholarCross Ref
- 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 ScholarCross Ref
- 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 ScholarDigital Library
- W. Brown and D. Poulin. Quantum Markov networks and commuting Hamiltonians, 2012, arXiv:1206.0755.Google Scholar
- 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 ScholarCross Ref
- 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 ScholarCross Ref
- P. Diaconis and D. Freedman. Finite exchangeable sequences. Annals of Probability, 8:745-764, 1980.Google ScholarCross Ref
- I. Dinur. The PCP theorem by gap amplification. J. ACM, 54(3), June 2007. Google ScholarDigital Library
- 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 ScholarDigital Library
- A. C. Doherty and S. Wehner. Convergence of sdp hierarchies for polynomial optimization on the hypersphere, 2012, arXiv:1210.5048.Google Scholar
- S. Gharibian and J. Kempe. Approximation algorithms for qma-complete problems. SIAM J. Comput., 41(4):1028-1050, 2012, arXiv:1101.3884.Google ScholarCross Ref
- 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 ScholarDigital Library
- M. Hastings. Matrix product operators and central elements: Classical description of a quantum state, 2012, arXiv:1207.1671.Google Scholar
- M. B. Hastings. Trivial low energy states for commuting Hamiltonians, and the quantum pcp conjecture, 2012, arXiv:1201.3387. Google ScholarDigital Library
- S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439-562, 2006.Google ScholarCross Ref
- R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki. Quantum entanglement. Rev. Mod. Phys., 81:865-942, Jun 2009, arXiv:quant-ph/0702225.Google ScholarCross Ref
- 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 ScholarCross Ref
- 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 ScholarDigital Library
- A. Y. Kitaev, A. H. Shen, and M. N. Vyalyi. Classical and Quantum Computation, volume 47 of Graduate Studies in Mathematics. AMS, 2002. Google ScholarDigital Library
- 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 ScholarCross Ref
- 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 Scholar
- 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 ScholarDigital Library
- T. Osborne. Hamiltonian complexity, 2011, arXiv:1106.5875.Google Scholar
- 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 ScholarDigital Library
- 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 Scholar
- G. A. Raggio and R. F. Werner. Quantum statistical mechanics of general mean field systems. Helv. Phys. Acta, 62:980-1003, 1989.Google Scholar
- 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 ScholarDigital Library
- R. Raz. A parallel repetition theorem. SIAM J. Comput., 27(3):763-803, 1998. Google ScholarDigital Library
- R. Renner. Symmetry implies independence. Nature Physics, 3:645-649, 2007, arXiv:quant-ph/0703069.Google ScholarCross Ref
- I. Rodnianski and B. Schlein. Quantum fluctuations and rate of convergence towards mean field dynamics, 2007, arXiv:0711.3087.Google Scholar
- 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 ScholarDigital Library
- 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 ScholarCross Ref
- E. Størmer. Symmetric states of infinite tensor products of C*-algebras. J. Funct. Anal., 3:48, 1969.Google ScholarCross Ref
- B. Terhal. Is entanglement monogamous?, 2003, arXiv:quant-ph/0307120. Google ScholarDigital Library
- V. Vazirani. Approximation Algorithms. Springer, 2010. Google ScholarDigital Library
- J. Watrous. Quantum computational complexity, 2008, arXiv:0804.3401.Google Scholar
- R. F. Werner. An application of Bell's inequalities to a quantum state extension problem. Lett. Math. Phys., 17:359, 1989.Google ScholarCross Ref
- D. Yang. A simple proof of monogamy of entanglement. Physics Letters A, 360(2):249-250, 2006, arXiv:quant-ph/0604168.Google ScholarCross Ref
- 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 ScholarDigital Library
Index Terms
Product-state approximations to quantum ground states
Recommendations
The Power of Unentangled Quantum Proofs with Non-negative Amplitudes
STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of ComputingQuantum entanglement is a fundamental property of quantum mechanics and it serves as a basic resource in quantum computation and information. Despite its importance, the power and limitations of quantum entanglement are far from being fully ...
The detectability lemma and quantum gap amplification
STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computingThe quantum analogue of the constraint satisfaction problem is the fundamental physics question of finding the minimal energy state of a local Hamiltonian --- each term of the Hamiltonian specifies a local constraint whose violation contributes to the ...
Kraus operator formalism for quantum multiplexer operations for arbitrary two-qubit mixed states
AbstractThe dynamics of open quantum systems are described using a set of operators called Kraus operators. In this paper, we show how to find system parameters for a closed system of two qubits undergoing quantum multiplexer operations such that Kraus ...
Comments