Title

Measuring 4-Local Qubit Observables Could Probabilistically Solve Pspace

Keywords

Algorithmic measurements; BQP; Complexity of quantum measurements; Measurement accuracy; PSPACE

Abstract

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=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. © Rinton Press.

Publication Date

9-1-2008

Publication Title

Quantum Information and Computation

Volume

8

Issue

8-9

Number of Pages

741-755

Document Type

Article

Personal Identifier

scopus

Socpus ID

65649145036 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/65649145036

This document is currently not available here.

Share

COinS