Computational difficulty of computing the density of states.

Area of Science:

• Quantum computing
• Computational complexity theory
• Statistical mechanics

Background:

• Local Hamiltonians are fundamental in quantum mechanics and condensed matter physics.
• Calculating ground state properties and density of states is crucial for understanding material behavior.
• The computational complexity of these problems for quantum systems is not fully understood.

Purpose of the Study:

• To determine the exact computational difficulty of computing ground state degeneracy and density of states for local Hamiltonians.
• To establish the relationship between the complexity of these quantum problems and their classical counterparts.

Main Methods:

• Introduced a new complexity class, #BQP (the counting version of quantum Merlin Arthur).
• Analyzed the computational hardness of ground state degeneracy and density of states within this framework.
• Compared the complexity of #BQP with the classical complexity class #P.

Main Results:

• The computational difficulty of computing ground state degeneracy and density of states for local Hamiltonians is precisely characterized by #BQP.
• #BQP is shown to be no harder than #P.
• This implies that computing these properties for classical Hamiltonians is computationally equivalent in difficulty to doing so for quantum Hamiltonians.

Conclusions:

• The study precisely quantifies the computational complexity of key problems in quantum many-body physics.
• Establishes a direct link between quantum and classical computational hardness for these problems.
• Suggests that quantum computation does not offer a general advantage for computing ground state degeneracy and density of states of local Hamiltonians.