We introduce quantum alternation as a generalization of quantum nondeterminism. We define q-alternating Turing machine (qATM) by augmenting alternating Turing machine with constant-size quantum memory. We show that one-way constant-space qATMs (1AQFAs) are Turing equivalent. Then, we introduce strong version of qATM by requiring to halt in every computation path and we show that strong qATMs can simulate deterministic spacewith exponentially less space. This leads to shifting the deterministic space hierarchy exactly by one level. We also focus on realtime versions of 1AQFAs (rtAQFAs) and obtain many results: rtAQFAs can recognize a PSPACE-complete problem; they cannot be simulated by sublinear deterministic Turing machines; for any level of polynomial hierarchy, say k , there exists a complete language that can be recognized by rtAFAs with only ( k +1) alternations; and polynomial hierarchy lies in its log-space q-alternation counterpart.
We introduce quantum alternation as a generalization of quantum nondeterminism. We define q-alternating Turing machine (qATM) by augmenting alternating Turing machine with constant-size quantum memory. We show that one-way constant-space qATMs (1AQFAs) are Turing equivalent. Then, we introduce strong version of qATM by requiring to halt in every computation path and we show that strong qATMs can simulate deterministic spacewith exponentially less space. This leads to shifting the deterministic space hierarchy exactly by one level. We also focus on realtime versions of 1AQFAs (rtAQFAs) and obtain many results: rtAQFAs can recognize a PSPACE-complete problem; they cannot be simulated by sublinear deterministic Turing machines; for any level of polynomial hierarchy, say k , there exists a complete language that can be recognized by rtAFAs with only ( k +1) alternations; and polynomial hierarchy lies in its log-space q-alternation counterpart.
In this paper, we introduce a new public quantum interactive proof system and the first quantum alternating Turing machine: qAM proof system and qATM, respectively. Both are obtained from their classical counterparts (Arthur-Merlin proof system and alternating Turing machine, respectively,) by augmenting them with a fixed-size quantum register. We focus on space-bounded computation, and obtain the following surprising results: Both of them with constant-space are Turing-equivalent. More specifically, we show that for any Turing-recognizable language, there exists a constant-space weak-qAM system, (the nonmembers do not need to be rejected with high probability), and we show that any Turing-recognizable language can be recognized by a constant-space qATM even with one-way input head. For strong proof systems, where the nonmembers must be rejected with high probability, we show that the known space-bounded classical private protocols can also be simulated by our public qAM system with the same space bound. Besides, we introduce a strong version of qATM: The qATM that must halt in every computation path. Then, we show that strong qATMs (similar to private ATMs) can simulate deterministic space with exponentially less space. This leads to shifting the deterministic space hierarchy exactly by one-level. The method behind the main results is a new public protocol cleverly using its fixed-size quantum register. Interestingly, the quantum part of this public protocol cannot be simulated by any space-bounded classical protocol in some cases.
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 dissertation, we investigate the computational power of quantum Turing machines operating in bounded space. First, we consider space-bounds that are space-constructible and at least logarithmic in the input size. For such space-bounds, it is shown that quantum Turing machines and probabilistic Turing machines are equivalent in power in the unbounded-error setting, in the sense that each model may simulate the other with at most a constant factor increase in space. From this, it follows that any quantum Turing machine computation can be simulated deterministically with at most a quadratic increase in space, and can be simulated deterministically in time at most exponential in the space-bound. Several other facts regarding quantum complexity classes defined in terms of such space-bounds are also proved. Second, we consider the power of quantum Turing machines restricted to constant space. In this case, we first prove that quantum Turing machines having one-sided error and running in linear time are strictly more powerful than probabilistic Turing machines having either one-sided error or having two-sided bounded error and running in polynomial time. Second, we prove that exact (i.e., accepting with probability 0 or 1) constant-space quantum Turing machines upon which no restrictions on running time are placed can recognize languages that cannot be recognized by any bounded-error constant-space probabilistic Turing machine. ii Acknowledgements I would like to take this opportunity to express my gratitude to a number of people. First, I would like to thank my advisor Eric Bach for all that he has taught me, regarding both theoretical computer science and how to be a researcher in general. His advice and support are greatly appreciated. I would also like to thank Anne Condon for her great advice and for many helpful discussions during my years as a graduate student. This dissertation has benefitted greatly from comments and suggestions by Anne and Eric as well.
In automata theory, quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to QFAs augmented with counters or stacks. In this paper, we focus on such generalizations of QFAs where the input head operates in one-way or realtime mode, and present some new results regarding their superiority over their classical counterparts. Our first result is about the nondeterministic acceptance mode: Each quantum model architecturally intermediate between realtime finite state automaton and one-way pushdown automaton (one-way finite automaton, realtime and one-way finite automata with one-counter, and realtime pushdown automaton) is superior to its classical counterpart. The second and third results are about bounded error language recognition: for any k > 0, QFAs with k blind counters outperform their deterministic counterparts; and, a one-way QFA with a single head recognizes an infinite family of languages, which can be recognized by one-way probabilistic finite automata with at least two heads. Lastly, we compare the nondeterminictic and deterministic acceptance modes for classical finite automata with k blind counter(s), and we show that for any k > 0, the nondeterministic models outperform the deterministic ones.
We show that there exists a universal quantum Turing machine (UQTM) that can simulate every other QTM until the other QTM has halted and then halt itself with probability one. This extends work by Bernstein and Vazirani who have shown that there is a UQTM that can simulate every other QTM for an arbitrary, but preassigned number of time steps. As a corollary to this result, we give a rigorous proof that quantum Kolmogorov complexity as defined by Berthiaume is invariant, i.e., depends on the choice of the UQTM only up to an additive constant. Our proof is based on a new mathematical framework for QTMs, including a thorough analysis of their halting behavior. We introduce the notion of mutually orthogonal halting spaces and show that the information encoded in an input qubit string can always be effectively decomposed into a classical and a quantum part.
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.