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 gen-eralization of constraint satisfaction problems (CSPs) and has a central role both in quantum many-body physics and quantum complexity theory. A key feature that distinguishes quan-tum 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 existence of a good product-state approximation for the ground-state en-ergy of 2-local Hamiltonians with one or more of the following properties: (1) high degree, (2) small expansion, or (3) a ground state with sublinear entanglement with respect to some parti-tion into small pieces. The approximation based on degree is a surprising difference between quantum Hamiltonians and classical CSPs, since in the classical setting, higher degree is usu-ally associated with harder CSPs. The approximation based on low entanglement, in turn, was
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.
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.
The calculation of ground-state energies of physical systems can be formalized as the
k-local Hamiltonian problem, which is a natural quantum analogue of classical constraint satisfaction problems. One way of making the problem more physically meaningful is to restrict the Hamiltonian in question by picking its terms from a fixed set
S and scaling them by arbitrary weights. Examples of such special cases are the Heisenberg and Ising models from condensed-matter physics. In this work we characterize the complexity of this problem for all 2-local qubit Hamiltonians. Depending on the subset
S, the problem falls into one of the following categories: in
P;
NP-complete; polynomial-time equivalent to the Ising model with transverse magnetic fields; or
QMA-complete. The third of these classes has been shown to be
StoqMA-complete by Bravyi and Hastings. The characterization holds even if
S does not contain any 1-local terms; for example, we prove for the first time
QMA-completeness of the Heisenberg and XY interactions in this setting. If
S is assumed to contain all 1-local terms, which is the setting considered by previous work, we have a characterization that goes beyond 2-local interactions: for any constant
k, all
k-local qubit Hamiltonians whose terms are picked from a fixed set
S correspond to problems either in
P; polynomial-time equivalent to the Ising model with transverse magnetic fields; or
QMA-complete. These results are a quantum analogue of the maximization variant of Schaefer's dichotomy theorem for Boolean constraint satisfaction problems.
We consider the power of local algorithms for approximately solving Max k XOR, a generalization of two constraint satisfaction problems previously studied with classical and quantum algorithms (MaxCut and Max E3LIN2). In Max k XOR each constraint is the XOR of exactly k variables and a parity bit. On instances with either random signs (parities) or no overlapping clauses and D+1 clauses per variable, we calculate the expected satisfying fraction of the depth-1 QAOA from Farhi et al [arXiv:1411.4028] and compare with a generalization of the local threshold algorithm from Hirvonen et al [arXiv:1402.2543]. Notably, the quantum algorithm outperforms the threshold algorithm for k > 4 .On the other hand, we highlight potential difficulties for the QAOA to achieve computational quantum advantage on this problem. We first compute a tight upper bound on the maximum satisfying fraction of nearly all large random regular Max k XOR instances by numerically calculating the ground state energy density P(k) of a mean-field k -spin glass [arXiv:1606.02365]. The upper bound grows with k much faster than the performance of both one-local algorithms. We also identify a new obstruction result for low-depth quantum circuits (including the QAOA) when k=3 , generalizing a result of Bravyi et al [arXiv:1910.08980] when k=2 . We conjecture that a similar obstruction exists for all k .
The calculation of ground-state energies of physical systems can be formalised as the k-local Hamiltonian problem, which is the natural quantum analogue of classical constraint satisfaction problems. One way of making the problem more physically meaningful is to restrict the Hamiltonian in question by picking its terms from a fixed set S. Examples of such special cases are the Heisenberg and Ising models from condensed-matter physics. In this work we characterise the complexity of this problem for all 2-local qubit Hamiltonians. Depending on the subset S, the problem falls into one of the following categories: in P; NP-complete; polynomial-time equivalent to the Ising model with transverse magnetic fields; or QMA-complete. The third of these classes has been shown to be StoqMA-complete by Bravyi and Hastings. The characterisation holds even if S does not contain any 1-local terms; for example, we prove for the first time QMA-completeness of the Heisenberg and XY interactions in this setting. If S is assumed to contain all 1-local terms, which is the setting considered by previous work, we have a characterisation that goes beyond 2-local interactions: for any constant k, all k-local qubit Hamiltonians whose terms are picked from a fixed set S correspond to problems either in P; polynomial-time equivalent to the Ising model with transverse magnetic fields; or QMA-complete. These results are a quantum analogue of Schaefer's dichotomy theorem for boolean constraint satisfaction problems.