title: Computational difficulty of computing the density of states.
abstract: 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.
authors.affiliation: University of Virginia, Department of Physics, Charlottesville, Virginia 22904, USA.
authors.forename: Brielin
authors.initials: B
authors.lastname: Brown
authors.forename: Steven T
authors.initials: ST
authors.lastname: Flammia
authors.forename: Norbert
authors.initials: N
authors.lastname: Schuch