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. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1103/PhysRevLett.107.040501 | PHYSICAL REVIEW LETTERS |
Keywords | DocType | Volume |
quantum algorithm,computational complexity,electron density,band structure,complexity class,ground state,density of state | Journal | 107 |
Issue | ISSN | Citations |
4 | 0031-9007 | 2 |
PageRank | References | Authors |
0.37 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Brielin Brown | 1 | 4 | 0.83 |
Steven T. Flammia | 2 | 5 | 1.19 |
Norbert Schuch | 3 | 21 | 2.35 |