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 (7)

• Quantum fingerprinting
• A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors
• Simulation of topological field theories by quantum computers
• Quantum search by measurement
• Consistency of Local Density Matrices is QMA-complete
• Measuring 4-local n-qubit observables could probabilistically solve PSPACE
• Quantum algorithm for finding periodicities in the spectrum of a black-box Hamiltonian or unitary transformation

Cited by in corpus (14)

• Universal computation by quantum walk
• Quantum phase estimation of multiple eigenvalues for small-scale (noisy) experiments
• The BQP-hardness of approximating the Jones Polynomial
• Interactive Proofs For Quantum Computations
• Heisenberg-limited quantum phase estimation of multiple eigenvalues with few control qubits
• The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings
• BQP-complete Problems Concerning Mixing Properties of Classical Random Walks on Sparse Graphs
• A single-shot measurement of the energy of product states in a translation invariant spin chain can replace any quantum computation
• A BQP-complete problem related to the Ising model partition function via a new connection between quantum circuits and graphs
• Normalizer Circuits and Quantum Computation
• Estimating diagonal entries of powers of sparse symmetric matrices is BQP-complete
• A Cutting-plane Method for Semidefinite Programming with Potential Applications on Noisy Quantum Devices
• How much is a quantum controller controlled by the controlled system?
• Two remarks on the local Hamiltonian problem