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. http://resolver.caltech.edu/CaltechAUTHORS:20110808-100520724

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

126Kb
[img] Plain Text - Supplemental Material
See Usage Policy.

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

108Kb
[img] LaTeX - Supplemental Material
See Usage Policy.

24Kb

Use this Persistent URL to link to this item: http://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, IQIM
Funders:
Funding AgencyGrant Number
Industry Canada UNSPECIFIED
Gordon and Betty Moore Foundation UNSPECIFIED
NSFPHY-0803371
Ontario MRI UNSPECIFIED
Classification Code:PACS: 03.67.Ac, 71.20.-b, 89.70.Eg
Record Number:CaltechAUTHORS:20110808-100520724
Persistent URL:http://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: Jason Perez
Deposited On:08 Aug 2011 17:47
Last Modified:26 Dec 2012 13:27

Repository Staff Only: item control page