Computational Difficulty of Computing the Density of States
arXiv:1010.3060 · doi:10.1103/PhysRevLett.107.040501
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 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.
v2: Accepted version. 9 pages, 1 figure
References in corpus (5)
Cited by in corpus (18)
- Quantum Chemistry in the Age of Quantum Computing
- Hamiltonian complexity
- Computational Complexity in Electronic Structure
- Quantum Algorithms for Estimating Physical Quantities using Block-Encodings
- Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
- Towards quantum advantage via topological data analysis
- Ground state connectivity of local Hamiltonians
- Density of States of Quantum Spin Systems from Isotropic Entanglement
- Estimating the Density of States of Frustrated Spin Systems
- Complexity of Supersymmetric Systems and the Cohomology Problem
- The complexity of simulating local measurements on quantum systems
- How Fast Can Quantum Annealers Count?
- Approximate symmetries of Hamiltonians
- Detailed Analysis of Circuit-to-Hamiltonian Mappings
- Oracle complexity classes and local measurements on physical Hamiltonians
- Eigenvalue approximation of sums of Hermitian matrices from eigenvector localization/delocalization
- On physical problems that are slightly more difficult than QMA
- Solving Sharp Bounded-error Quantum Polynomial Time Problem by Evolution methods