QUANTUM COMPLEXITY THEORY

In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universa l quantum Turing machine in Deutsch's model of a quantum Turing machin e (QTM) [Proc. Roy Sec. London Ser. A, 400 (1985), pp. 97-117]. This c onstruction is substantially more complicated than the corresponding c onstruction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straigh tforward in the context of quantum Turing machines. We establish how t hese familiar primitives can be implemented and introduce some new, pu rely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynom ially bounded dimension. We also consider the precision to which the t ransition amplitudes of a quantum Turing machine need to be specified. We prove that O(log T) bits of precision suffice to support a T step computation. This justifies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the first formal evidence that quantum Turing mac hines violate the modern (complexity theoretic) formulation of the Chu rch-Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing mach ine, but requires superpolynomial time on a bounded-error probabilisti c Turing machine, and thus not in the class BPP. The class BQP of lang uages that are efficiently decidable (with small error-probability) on a quantum Turing machine satisfies BPP subset of or equal to BQP subs et of or equal to P-#P. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful tha n classical probabilistic Turing machines (in the unrelativized settin g) unless there is a major breakthrough in complexity theory.