In this work we proceed with the investigation of the power of an abstract model of computation that considers Turing machines coupled with physical oracles. A physical oracle is an experiment controlled by the Turing machine with the purpose of measuring some quantity or parameter, possibly suitable to boost the power of the Turing machine. We consider one of the three known types of measurement experiments — the two-sided case. Researches on the computational power under bounded resources of the two other types — threshold and vanishing — have been considered and are settle by other authors up to some hard open problems. Herein we address the unfinished case of the two-sided oracle, establishing the corresponding upper bounds. We consider three types of communication between the Turing machine and the oracle (infinite precision, unbounded precision and fixed precision), that simulate the error propagation common to physical experiments. These three types of precision introduce variants of the two-sided oracle machines. We fix the upper bounds for the three cases. In the context of the infinite precision protocol of two-sided machines, we then address the question of knowing if a number, a physical parameter, is measurable or not. This problem was first put out by the physicists Geroch and Hartle without a formal framework to reason upon definition. We characterize the measurable and the non measurable numbers and we analyze some of their properties.
In this work we proceed with the investigation of the power of an abstract model of computation that considers Turing machines coupled with physical oracles. A physical oracle is an experiment controlled by the Turing machine with the purpose of measuring some quantity or parameter, possibly suitable to boost the power of the Turing machine. We consider one of the three known types of measurement experiments — the two-sided case. Researches on the computational power under bounded resources of the two other types — threshold and vanishing — have been considered and are settle by other authors up to some hard open problems. Herein we address the unfinished case of the two-sided oracle, establishing the corresponding upper bounds. We consider three types of communication between the Turing machine and the oracle (infinite precision, unbounded precision and fixed precision), that simulate the error propagation common to physical experiments. These three types of precision introduce variants of the two-sided oracle machines. We fix the upper bounds for the three cases. In the context of the infinite precision protocol of two-sided machines, we then address the question of knowing if a number, a physical parameter, is measurable or not. This problem was first put out by the physicists Geroch and Hartle without a formal framework to reason upon definition. We characterize the measurable and the non measurable numbers and we analyze some of their properties.
Consider the classical model of a Turing machine with an oracle. The classical oracle is a one step external consultation device. The oracle may contain either non-computable information, or computable information provided just to speed up the computations of the Turing machine. In this talk we will consider the abstract experimenter (e.g. the experimental physicist) as a Turing machine and the abstract experiment of measuring a physical quantity (using a specified physical apparatus) as an oracle to the Turing machine. The algorithm running in the machine abstracts the experimental method of measurement (encoding the recursive structure of experimental actions) chosen by the experimenter. It is standard to consider that to measure a real number 4 µ, e.g. the value of a physical quantity, the experimenter (now the Turing machine) should proceed by approximations. Thus, besides the value of µ, we will consider dyadic rational approximations (denoted by finite binary strings), and a procedure to measure µ proved to be universal.
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 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.
Quantum measurement is universal for quantum computation. This universality allows alternative schemes to the traditional three-step organisation of quantum computation: initial state preparation, unitary transformation, measurement. In order to formalize these other forms of computation, while pointing out the role and the necessity of classical control in measurement-based computation, and for establishing a new upper bound of the minimal resources needed to quantum universality, a formal model is introduced by means of Measurement-based Quantum Turing Machines.
We present results on quantum Turing machines and on prover-verifier interactions. \n \n \nIn our work on quantum Turing machines, we continue the line of research opened by Yao (1993), who proved that quantum Turing machines and quantum circuits are polynomially equivalent computational models: t ≥ n steps of a quantum Turing machine running on an input of length n can be simulated by a uniformly generated family of quantum circuits with size quadratic in t, and a polynomial-time uniformly generated family of quantum circuits can be simulated by a quantum Turing machine running in polynomial time. We then first revisit the simulation of quantum Turing machines with uniformly generated quantum circuits, and present a variation on the simulation method employed by Yao together with an analysis of it. This analysis reveals that the simulation of quantum Turing machines can be performed by quantum circuits having depth linear in t, rather than quadratic depth, and can be extended easily to many variants of quantum Turing machines, such as ones having multi-dimensional tapes. Our analysis is based on an extension of a method of Arrighi, Nesme, and Werner (2011) that allows for the localization of causal unitary evolutions, involving abstract lemmas that might be of independent interest. \n \n \nWe also consider the more complex extension of our variant to the circuit simulation of multi-tape quantum Turing machines, where our variant provides a circuit with O(t^k) size and O(t^{k-1}) depth for the simulation of t steps of a machine with k tapes. This can be contrasted with the O(t^{k}) depth corresponding to the generalization of Yao's simulation by Nishimura and Ozawa (2002). Our usage of abstract techniques regarding the localization of causal unitary evolutions allows again for a simplification of the algebraic manipulation aspects of the construction. We also discuss the further extension to the case of oracle quantum Turing machines. \n \n \nIn our work on prover-verifier interactions, we first consider a protocol under the name of perfect/conclusive quantum state exclusion. This means to be able to discard with certainty at least one out of n possible quantum state preparations by performing a measurement of the resulting state. When all the preparations correspond to pure states and there are no more of them than their common dimension, it is an open problem whether POVMs give any additional power for this task with respect to projective measurements. This is the case even for the simple case of three states in three dimensions, which is discussed by Caves, Fuchs and Schack (2002) as unsuccessfully tackled. In our work, we give an analytical proof that in this case POVMs do indeed not give any additional power with respect to projective measurements. We also discuss possible generalizations of our work, including an application of Quadratically Constrained Quadratic Programming that might be of special interest. \n \n \nWe additionally consider the problem of quantum hedging, a particular kind of quantum correlation that arises between parallel instances of prover-verifier interactions. M. and Watrous (2012) studied a protocol that exhibited a perfect form of quantum hedging, where the risk for the prover of losing a first game can completely offset the corresponding risk for a second game. We take a step towards a better understanding of this hedging phenomenon by giving a characterization of the prover's optimal behavior for a natural generalization of this protocol. Furthermore, we discuss how the usage of the logarithmic utility principle to analyze prover-verifier interactions could justify further study of quantum hedging.
Quantum measurement is universal for quantum computation. This universality allows alternative schemes to the traditional three-step organisation of quantum computation: initial state preparation, unitary transformation, measurement. In order to formalize these other forms of computation, while pointing out the role and the necessity of classical control in measurement-based computation, and for establishing a new upper bound of the minimal resources needed to quantum universality, a formal model is introduced by means of Measurement-based Quantum Turing Machines.