Quantum Complexity Class

Definition 29 (BQP)

#BQP

Theorem 10

computing the density of states of a local n-spin Hamiltonian \(H = \sum_i H_i\) with few-body terms \(H_i\), \(|| H_i || \le 1\), up to accuracy 1/poly(n), is a problem which is complete for #BQP