Measuring 4-local n-qubit observables could probabilistically solve PSPACE

Abstract

We consider a hypothetical apparatus that implements measurements for arbitrary 4-local quantum observables A on n qubits. The apparatus implements the ``measurement algorithm'' after receiving a classical description of A. We show that a few precise measurements, applied to a basis state would provide a probabilistic solution of PSPACE problems. The error probability decreases exponentially with the number of runs if the measurement accuracy is of the order of the spectral gaps of A. Moreover, every decision problem which can be solved on a quantum computer in T time steps can be encoded into a 4-local observable such that the solution requires only measurements of accuracy O(1/T). Provided that BQP<>PSPACE, our result shows that efficient algorithms for precise measurements of general 4-local observables cannot exist. We conjecture that the class of physically existing interactions is large enough to allow the conclusion that precise energy measurements for general many-particle systems require control algorithms with high complexity.

18 pages, 3 figures

References in corpus (3)

• Quantum Algorithms Revisited
• 3-Local Hamiltonian is QMA-complete
• The 2-local Hamiltonian problem encompasses NP

Cited by in corpus (7)

• Several natural BQP-Complete problems
• Szegedy Walk Unitaries for Quantum Maps
• The Jones polynomial: quantum algorithms and applications in quantum complexity theory
• A single-shot measurement of the energy of product states in a translation invariant spin chain can replace any quantum computation
• Is there a physically universal cellular automaton or Hamiltonian?
• Estimating diagonal entries of powers of sparse symmetric matrices is BQP-complete
• Estimating mixing properties of local Hamiltonian dynamics and continuous quantum random walks is PSPACE-hard