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 QMA. 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. Understanding the physical properties of correlated quantum many-body systems is a problem of central importance in condensed matter physics. The density of states, defined as the number of energy eigenstates per energy interval, plays a particularly crucial role in this endeavor. It is a key ingredient when deriving many thermodynamic properties from microscopic models, including specific heat capacity, thermal conductivity, band structure, and (near the Fermi energy) most electronic properties of metals. Computing the density of states can be a daunting task however, as it in principle involves diagonalizing a Hamiltonian acting on an exponentially large space, though other more efficient approaches which might take advantage of the structure of a given problem are not a priori ruled out. In this Letter, we precisely quantify the difficulty of computing the density of states by using the powerful tools of quantum complexity theory. Quantum complexity aims at generalizing the well-established field of classical complexity theory to assess the difficulty of tasks related to quantum mechanical problems, concerning both the classical difficulty of simulating quantum systems as well as the fundamental limits to the power of quantum computers. In particular, quantum complexity theory has managed to explain the difficulty of computing ground state properties of quantum spin systems in various settings, such as two-dimensional (2D) lattices [1] and even one-dimensional (1D) chains [2], as well as fermionic systems [3] . We will determine the computational difficulty of two problems: First, computing the density of states of a local Hamiltonian, and second, counting the ground state degeneracy of a local gapped Hamiltonian; in both cases, the result holds even if the Hamiltonian is restricted to act on a 2D lattice of qubits, or on a 1D chain. To this end, we will introduce the quantum counting class #BQP (sharp BQP), which constitutes the natural counting version of the class QMA (Quantum Merlin Arthur) which itself captures the difficulty of computing the ground state energy of a local Hamiltonian [4, 5] . Vaguely speaking, #BQP counts the number of possible "quantum solutions" to a quantum problem that can be verified using a quantum computer. We show that both problems, computing the density of states and counting the ground state degeneracy, are complete problems for the class #BQP, i.e., they are among the hardest problems in this class. Having quantified the difficulty of computing the density of states and counting the number of ground states, we proceed to relate #BQP to known classical counting complexity classes, and show that #BQP equals #P (under weakly parsimonious reductions). Here, the complexity class #P counts the number of satisfying assignments to any efficiently computable boolean function. This can be a very hard problem which is believed to take exponential time; in particular, it is at least as hard as deciding whether the function has at least one satisfying input, i.e., the complexity class NP. Examples for #P-complete problems (i.e., the hardest problems in that class) include counting the number of colorings of a graph, or computing the permanent of a matrix with binary entries. Phrased in terms of Hamiltonians, what we show is that computing the density of states and counting the ground state degeneracy of a classical spin system is just as hard as solving the same problem for a quantum Hamiltonian. Quantum complexity classes.-Let us start by introducing the relevant complexity classes. The central role in the following is taken by the verifier V , which verifies "quantum solutions" (also called proofs) to a given problem. More formally, a verifier checking an n-qubit quantum proof (that is, a quantum state |ψ ) consists of a T = poly(n) length quantum circuit U = U T · · · U 1 (with local gates U t ) acting on m = poly(n) qubits, which takes the n-qubit quantum state |ψ I as an input, together with m − n initialized ancillas, |0 A ≡ |0 · · · 0 A , applies U , and finally measures the first qubit in the {|0 1 , |1 1 } basis to return 1 ("proof accepted") or 0 ("proof rejected"). Then, the class QMA contains all problems of the form: "Decide whether there exists a |ψ such that p acc (V (ψ)) > a, or whether p acc (V (ψ)) < b for all |ψ , for some chosen a − b > 1/poly(n), given that one is the case". Here, the acceptance probability of a state |ψ is p acc (V (ψ)) := ψ|Ω|ψ , with which we illustrate in Fig. 1 .
Our problem of estimating the spectral gap is related to the degeneracy problem in REF : if the ground state is degenerate, the spectral gap is 0.
Computational Difficulty of Computing the Density of States
Phys. Rev. Lett. 107, 040501 (2011)
Medicine Physics Computer Science