Several natural BQP-Complete problems

Abstract

A central problem in quantum computing is to identify computational tasks which can be solved substantially faster on a quantum computer than on any classical computer. By studying the hardest such tasks, known as BQP-complete problems, we deepen our understanding of the power and limitations of quantum computers. We present several BQP-complete problems, including Local Hamiltonian Eigenvalue Sampling and Phase Estimation Sampling. Different than the previous known BQP-complete problems (the Quadratically Signed Weight Enumerator problem [KL01] and the Approximation of Jones Polynomials [FKW02, FLW02, AJL06]), our problems are of a basic linear algebra nature and are closely related to the well-known quantum algorithm and quantum complexity theories.

13 pages, 4 figures

References in corpus (2)

• Consistency of Local Density Matrices is QMA-complete
• Measuring 4-local n-qubit observables could probabilistically solve PSPACE

Cited by in corpus (8)

• Universal computation by quantum walk
• Interactive Proofs For Quantum Computations
• A single-shot measurement of the energy of product states in a translation invariant spin chain can replace any quantum computation
• BQP-complete Problems Concerning Mixing Properties of Classical Random Walks on Sparse Graphs
• A BQP-complete problem related to the Ising model partition function via a new connection between quantum circuits and graphs
• Estimating diagonal entries of powers of sparse symmetric matrices is BQP-complete
• How much is a quantum controller controlled by the controlled system?
• Two remarks on the local Hamiltonian problem