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

Simple item page
dc.creatorWocjan, Pawel
dc.creatorJanzing, Dominik
dc.creatorDecker, Thomas
dc.creatorBeth, Thomas
dc.date2003-08-01
dc.date.accessioned2026-07-07T06:07:31Z
dc.date.available2026-07-07T06:07:31Z
dc.descriptionWe 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.
dc.description18 pages, 3 figures
dc.identifierhttps://arxiv.org/abs/quant-ph/0308011
dc.identifierhttp://arxiv.org/abs/quant-ph/0308011
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/91321
dc.subjectQuantum Physics
dc.titleMeasuring 4-local n-qubit observables could probabilistically solve PSPACE
dc.typetext

Files

Collections

arXiv