Published July 20, 2011
| Published + Supplemental Material
Journal Article
Open
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.
Additional Information
© 2011 American Physical Society. Received 26 October 2010; revised 28 May 2011; published 20 July 2011. We thank S. Aaronson, D. Gottesman, D. Gross, Y. Shi, M. van den Nest, J. Watrous, and S. Zhang for helpful discussions and comments. Research at PI is supported by Industry Canada and Ontario MRI. N. S. is supported by the Gordon and Betty Moore Foundation through Caltech's Center for the Physics of Information and NSF Grant No. PHY-0803371.Attached Files
Published - Brown2011p15420Phys_Rev_Lett.pdf
Supplemental Material - README.TXT
Supplemental Material - supplement-v2.pdf
Supplemental Material - supplement-v2.tex
Files
Brown2011p15420Phys_Rev_Lett.pdf
Additional details
- Eprint ID
- 24727
- Resolver ID
- CaltechAUTHORS:20110808-100520724
- Industry Canada
- Gordon and Betty Moore Foundation
- PHY-0803371
- NSF
- Ontario MRI
- Created
-
2011-08-08Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field
- Caltech groups
- Institute for Quantum Information and Matter