CaltechAUTHORS
  A Caltech Library Service

Computational Difficulty of Computing the Density of States

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

[img]
Preview
PDF - Published Version
See Usage Policy.

129kB
[img] Plain Text - Supplemental Material
See Usage Policy.

628B
[img]
Preview
PDF - Supplemental Material
See Usage Policy.

110kB
[img] 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:
URLURL TypeDescription
http://dx.doi.org/10.1103/PhysRevLett.107.040501DOIUNSPECIFIED
http://prl.aps.org/abstract/PRL/v107/i4/e040501PublisherUNSPECIFIED
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:
Funding AgencyGrant Number
Industry CanadaUNSPECIFIED
Gordon and Betty Moore FoundationUNSPECIFIED
NSFPHY-0803371
Ontario MRIUNSPECIFIED
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