This paper investigates the relative power of space-bounded quantum and classical (probabilistic) computational models. The following relationships are proved. 1. Any probabilistic Turing machine (PTM) which runs in space s and which halts absolutely (i.e. halts with certainty after a finite number of steps) can be simulated in space O(s) by a quantum Turing machine (QTM). If the PTM operates with bounded error, then the QTM may be taken to operate with bounded error as well, although the QTM may not halt absolutely in this case. In the unbounded error case, the QTM may be taken to halt absolutely. 2. Any QTM running in space s can be simulated by an unbounded error PTM running in space O(s). No assumptions on the probability of error or Turing time for the QTM are required, but it is assumed that all transition amplitudes of the quantum machine are rational. It follows that unbounded error, space O(s) bounded quantum Turing machines and probabilistic Turing machines are equivalent in power. This implies that any space s QTM can be simulated deterministically in space O(s/sup 2/), and further that any (unbounded-error) QTM running in log-space can be simulated in NC/sup 2/ We also consider quantum analogues of nondeterministic and one-sided error probabilistic space-bounded classes, and prove some simple relationships regarding these classes.
In this thesis, we introduce a new quantum Turing machine (QTM) model that supports general quantum operators, together with its pushdown, counter, and finite automaton variants, and examine the computational power of classical and quantum machines using small space bounds in many different cases. The main contributions are summarized below. Firstly, we consider QTMs in the unbounded error setting: (i) in some cases of sublogarithmic space bounds, the class of languages recognized by QTMs is shown to be strictly larger than that of classical ones; (ii) in constant space bounds, the same result can still be obtained for restricted QTMs; (iii) the complete characterization of the class of languages recognized by realtime constant space nondeterministic QTMs is given. Secondly, we consider constant space-bounded QTMs in the bounded error setting: (i) we introduce a new type of quantum and probabilistic finite automata (QFAs and PFAs, respectively,) with a special two-way input head which is not allowed to be stationary or move to the left but has the capability to reset itself to its starting position; (ii) the computational power of this type of quantum machine is shown to be superior to that of the probabilistic machine; (iii) based on these models, two-way PFAs and two-way classical-head QFAs are shown to be more succinct than two-way nondeterministic finite automata and their one-way variants; (iv) we also introduce PFAs and QFAs with postselection with their bounded error language classes, and give many characterizations of them. Thirdly, the computational power of realtime QFAs augmented with a write-only memory is investigated by showing many simulation results for different kinds of counter automata. Finally, some lower bounds of realtime classical Turing machines in order to recognize a nonregular language are shown to be tight.
In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing machine in Deutsch's model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97--117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specified. We prove that
O(logT) 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 machines violate the modern (complexity theoretic) formulation of the Church--Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class $\BPP$. The class $\BQP$ of languages that are efficiently decidable (with small error-probability) on a quantum Turing machine satisfies $\BPP \subseteq \BQP \subseteq \Ptime^{\SP}$. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.
Abstract. In this paper we study quantum computation from a complexity theoretic viewpoint. Our rst result is the existence of an ecient universal quantum Turing machine in Deutsch’s model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97{117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specied. We prove that O(log T) bits of precision suce to support a T step computation. This justies 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 rst formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church{Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class BPP. The class BQP of languages that are eciently decidable (with small error-probability) on a quantum Turing machine satises BPP ⊆ BQP ⊆ P]P. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.
The rapid evolution of computers in the half century since their invention has resulted in dramatically smaller and faster computers. However, from a computational point of view, all these computers look alike; for example, they are built out of simple logic gates. A fundamental thesis of computer science---the modern form of the Church--Turing thesis---asserts that this is inevitable in a deep sense. Any computer can be simulated with at most a polynomial factor slowdown by a probabilistic Turing machine. Quantum computation poses the first credible challenge to this thesis. It goes back to a suggestion by Feynman [4], who pointed out that there appears to be no efficient way of simulating a quantum mechanical system on a computer, and suggested that, perhaps, a computer based on quantum physical principles might be able to carry out the simulation efficiently. Two formal models for quantum computers---the quantum Turing machine [2] and quantum computational networks [3]---were defined by Deutsch. The first three papers in this issue describe efficient quantum algorithms for computational tasks that we do not know how to solve classically. In "Quantum Complexity Theory," Bernstein and Vazirani give the first formal evidence that quantum computers violate the modern form of the Church--Turing thesis. They show that a certain problem---the recursive Fourier sampling problem---can be solved in polynomial time on a quantum Turing machine, but relative to an oracle, requires superpolynomial time on a classical probabilistic Turing machine. Simon, in the paper "On the Power of Quantum Computation" introduces a fundamental projection technique and uses it to design an efficient quantum algorithm to determine whether a certain type of function is 2-1 or 1-1. He further shows that, relative to an oracle, this problem requires exponential time on a classical probabilistic Turing machine. In the paper "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer," Shor gives remarkable polynomial time quantum algorithms for two of the most famous problems in computer science: factoring and discrete log. Since the computational hardness of these problems is the basis of several famous cryptosystems, Shor's paper very dramatically underlines the power of quantum computers. To understand the computational power of quantum computers, it is helpful to consider a quantum mechanical system of n particles, each of which can be in one of two states, labeled
∣0⟩ and
∣1⟩. If this were a classical system, then its instantaneous state could be described by n bits. However, in quantum physics, the system is allowed to be in a linear superposition of configurations, and indeed the instantaneous state of the system is described by a unit vector in the 2n dimensional vector space, whose basis vectors correspond to all the2n classical configurations. Therefore, to describe the instantaneous state of the system, we must specify 2n complex numbers. Nature must update 2n complex numbers at each instant to evolve the system in time. This is an extraordinary amount of effort, since even for n = 200, 2n is larger than estimates of the number of elementary particles in the visible universe. Nonetheless, there are limits to the power of quantum computers. In "Strengths and Weaknesses of Quantum Computing," Bennett, Bernstein, Brassard, and Vazirani show that, relative to a random oracle, with probability 1, the class NP cannot be solved on a quantum Turing machine in time o(2n/2). This bound is tight, since recent work of Grover [5] has shown how to accept any language in NP in time O(2n/2) on a quantum Turing machine. Quantum computers are necessarily time reversible. Indeed, Bennett's work [1] on reversible computation inspired early work on quantum computation that preceded Feynman's paper [4]. The reversibility requirement makes it quite complex to implement even basic computational primitives such as looping or composition. In "Quantum Complexity Theory," Bernstein and Vazirani show how to implement quantum programming primitives and give a construction for an efficient universal quantum Turing machine. The structure of the universal quantum Turing machine is quite simple: it consists of a deterministic Turing machine with a single "quantum coin flip." In "Quantum Computability," Adleman, DeMarrais, and Huang greatly simplify this further by showing that a very simple type of coin flip is sufficient---a rotation by an angle
θ such that
sinθ=3/5. Making quantum computers robust against noise and decoherence is an important and challenging problem. In "Stabilization of Quantum Computations by Symmetrization," Barenco, Berthiaume, Deutsch, Ekert, Jozsa, and Macchiavello show how to use the quantum watchdog effect to stabilize a quantum computation against noise. Their method is based on running several copies of the quantum computer in parallel and projecting its state into the symmetric subspace at frequent intervals. They show that the quantum watchdog effect results in the suppression of errors that lie outside the symmetric subspace. Quantum computation touches upon the foundations of both computer science and quantum physics. It is not unlikely that the issues raised by quantum computation will stimulate further research into the foundations of quantum physics. I wish to express my gratitude to several people who made this special section possible. Oded Goldreich acted as editor for two of the papers in the issue and dealt with them with his characteristic efficiency and judgment. The editorial staff at SIAM, most notably Lisa Dougherty, Beth Gallagher, Deidre Wunderlich, and Sam Young, were extremely helpful, patient, and resourceful. Finally, I would like to thank a number of referees whose careful and timely reviews were critical to putting together this issue. Umesh Vazirani
The two-way finite automaton with quantum and classical states (2QCFA), defined by Ambainis and Watrous, is a model of quantum computation whose quantum part is extremely limited; however, as they showed, 2QCFA are surprisingly powerful: a 2QCFA with only a single-qubit can recognize the language
Lpal={w∈{a,b}∗:w is a palindrome} with bounded error in expected time
2O(n), on inputs of length
n. We prove that their result essentially cannot be improved upon: a 2QCFA (of any size) cannot recognize
Lpal with bounded error in expected time
2o(n). To our knowledge, this is the first example of a language that can be recognized with bounded error by a 2QCFA in exponential time but not in subexponential time. Moreover, we prove that a quantum Turing machine (QTM) running in space
o(logn) and expected time
2n1−Ω(1) cannot recognize
Lpal with bounded error; again, this is the first lower bound of its kind. Far more generally, we establish a lower bound on the running time of any 2QCFA or
o(logn)-space QTM that recognizes any language
L in terms of a natural "hardness measure" of
L. This allows us to exhibit a large family of languages for which we have asymptotically matching lower and upper bounds on the running time of any such 2QCFA or QTM recognizer.