Brown, Brielin and Flammia, Steven T. and Schuch, Norbert (2011) Computational Difficulty of Computing the Density of States. Physical Review Letters, 107 (4). Art. No. 040501. ISSN 0031-9007. doi:10.1103/PhysRevLett.107.040501. https://resolver.caltech.edu/CaltechAUTHORS:20110808-100520724
![]()
|
PDF
- Published Version
See Usage Policy. 129kB | |
![]() |
Plain Text
- Supplemental Material
See Usage Policy. 628B | |
![]()
|
PDF
- Supplemental Material
See Usage Policy. 110kB | |
![]() |
LaTeX
- Supplemental Material
See Usage Policy. 25kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20110808-100520724
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.
Item Type: | Article | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||||||
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. | ||||||||||
Group: | Institute for Quantum Information and Matter | ||||||||||
Funders: |
| ||||||||||
Issue or Number: | 4 | ||||||||||
Classification Code: | PACS: 03.67.Ac, 71.20.-b, 89.70.Eg | ||||||||||
DOI: | 10.1103/PhysRevLett.107.040501 | ||||||||||
Record Number: | CaltechAUTHORS:20110808-100520724 | ||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20110808-100520724 | ||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||
ID Code: | 24727 | ||||||||||
Collection: | CaltechAUTHORS | ||||||||||
Deposited By: | INVALID USER | ||||||||||
Deposited On: | 08 Aug 2011 17:47 | ||||||||||
Last Modified: | 09 Nov 2021 16:26 |
Repository Staff Only: item control page