We study the computational difficulty of computing the ground state degeneracy and the density of states for local Hamiltonians. We show that the difficulty of both problems is exactly captured by a class which we call #BQP, which is the counting version of the quantum complexity class quantum Merlin Arthur. We show that #BQP is not harder than its classical counting counterpart #P, which in turn implies that computing the ground state degeneracy or the density of states for classical Hamiltonians is just as hard as it is for quantum Hamiltonians.
We study the computational difficulty of computing the ground state degeneracy and the density of states for local Hamiltonians. We show that the difficulty of both problems is exactly captured by a class which we call #BQP, which is the counting version of the quantum complexity class quantum Merlin Arthur. We show that #BQP is not harder than its classical counting counterpart #P, which in turn implies that computing the ground state degeneracy or the density of states for classical Hamiltonians is just as hard as it is for quantum Hamiltonians.
Here we present a problem related to the local Hamiltonian problem (identifying whether the ground-state energy falls within one of two ranges) which is restricted to being translationally invariant. We prove that for Hamiltonians with a fixed local dimension and O(log(N))-body local terms, or local dimension N and two-body terms, there are instances where finding the ground-state energy is quantum-Merlin-Arthur-complete and simulating the dynamics is BQP-complete (BQP denotes ``bounded error, quantum polynomial time''). We discuss the implications for the computational complexity of finding ground states of these systems and hence for any classical approximation techniques that one could apply including density-matrix renormalization group, matrix product states, and multiscale entanglement renormalization ansatz. One important example is a one-dimensional lattice of bosons with nearest-neighbor hopping at constant filling fraction---i.e., a generalization of the Bose-Hubbard model.
We study several problems related to properties of nonnegative matrices that arise at the boundary between quantum and classical probabilistic computation. Our results are twofold. First, we identify a large class of quantum Hamiltonians describing systems of qubits for which the adiabatic evolution can be efficiently simulated on a classical probabilistic computer. These are stoquastic local Hamiltonians with a “frustration-free” ground-state. A Hamiltonian belongs to this class iff it can be represented as H=∑aHa where (1) every term Ha acts nontrivially on a constant number of qubits, (2) every term Ha has real nonpositive off-diagonal matrix elements in the standard basis, and (3) the ground-state of H is a ground-state of every term Ha. Second, we generalize the Cook–Levin theorem proving NP-completeness of the satisfiability problem to the complexity class MA (Merlin–Arthur games)—a probabilistic analogue of NP. Specifically, we construct a quantum version of the k-SAT problem which we call “stoquastic k-SAT” such that stoquastic k-SAT is contained in MA for any constant k, and any promise problem in MA is Karp-reducible to stoquastic 6-SAT. This result provides the first nontrivial example of a MA-complete promise problem.
Computing the ground-state energy of interacting electron problems has recently been shown to be hard for quantum Merlin Arthur (QMA), a quantum analogue of the complexity class NP. Fermionic problems are usually hard, a phenomenon widely attributed to the so-called sign problem. The corresponding bosonic problems are, according to conventional wisdom, tractable. Here, we demonstrate that the complexity of interacting boson problems is also QMA hard. Moreover, the bosonic version of N-representability problem is QMA complete. Consequently, these problems are unlikely to have efficient quantum algorithms.
Counting ground state degeneracy of a k-local Hamiltonian is important in many fields of physics. Its complexity class is harder than that of finding the ground state of a k-local Hamiltonian. Very few methods can efficiently count the degeneracy of ground state while many are known for finding the ground state. This Letter proposes an algorithm for mapping the problem of counting ground state degeneracy into one for finding a special ground state of a k-local super Hamiltonian in an enlarged system with twice as many qubits or spins. We show that all traditional methods, designed for finding the ground state by evolution under a function of a Hamiltonian, can be employed to find the special ground state of the super Hamiltonian from a well-designed initial state and thus can be used to count the ground degeneracy. We combine our algorithm with the power method, the Lanczos method, and the quantum imaginary time evolution method for selective examples to illustrate the detection of phase boundaries, competition between frustration and quantum fluctuation, and potential implementation with quantum circuits.
Computing the ground-state energy of interacting electron problems has recently been shown to be hard for quantum Merlin Arthur (QMA), a quantum analogue of the complexity class NP. Fermionic problems are usually hard, a phenomenon widely attributed to the so-called sign problem. The corresponding bosonic problems are, according to conventional wisdom, tractable. Here, we demonstrate that the complexity of interacting boson problems is also QMA hard. Moreover, the bosonic version of N-representability problem is QMA complete. Consequently, these problems are unlikely to have efficient quantum algorithms.
An important task in quantum physics is the estimation of local quantities for ground states of local Hamiltonians. Recently, [Ambainis, CCC 2014] defined the complexity class PQMA[log] , and motivated its study by showing that the physical task of estimating the expectation value of a local observable against the ground state of a local Hamiltonian is PQMA[log] -complete. In this paper, we continue the study of PQMA[log] , obtaining the following lower and upper bounds.Lower bounds (hardness results): - The PQMA[log] -completeness result of [Ambainis, CCC 2014] requires O(logn) -local observables and Hamiltonians. We show that simulating even a single qubit measurement on ground states of 5 -local Hamiltonians is PQMA[log] -complete, resolving an open question of Ambainis.- We formalize the complexity theoretic study of estimating two-point correlation functions against ground states, and show that this task is similarly PQMA[log] -complete. - We identify a flaw in [Ambainis, CCC 2014] regarding a PUQMA[log] -hardness proof for estimating spectral gaps of local Hamiltonians. By introducing a ``query validation'' technique, we build on [Ambainis, CCC 2014] to obtain PUQMA[log] -hardness for estimating spectral gaps under polynomial-time Turing reductions. Upper bounds (containment in complexity classes): - PQMA[log] is thought of as ``slightly harder'' than QMA. We justify this formally by exploiting the hierarchical voting technique of [Beigel, Hemachandra, Wechsung, SCT 1989] to show PQMA[log]⊆PP . This improves the containment QMA⊆PP [Kitaev, Watrous, STOC 2000]. This work contributes a rigorous treatment of the subtlety involved in studying oracle classes in which the oracle solves a promise problem. This is particularly relevant for quantum complexity theory, where most natural classes such as BQP and QMA are defined as promise classes.