Measuring 4-local qubit observables could probabilistically solve PSPACE

    Authors

    P. Wocjan; D. Janzing;T. Decker

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    Quantum Inform. Comput.

    Keywords

    complexity of quantum measurements; measurement accuracy; algorithmic; measurements; BQP; PSPACE; QUANTUM ALGORITHMS; COMPUTATION; COMPLEXITY; COMPUTER; SPACE; Computer Science, Theory & Methods; Physics, Particles & Fields; Physics, Mathematical

    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 the operator A. Moreover. every decision problem that can be solved by a deterministic quantum algorithm 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 not equal 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.

    Journal Title

    Quantum Information & Computation

    Volume

    8

    Issue/Number

    8-9

    Publication Date

    1-1-2008

    Document Type

    Article

    Language

    English

    First Page

    741

    Last Page

    755

    WOS Identifier

    WOS:000258699300005

    ISSN

    1533-7146

    Share

    COinS