arXiv:quant-ph/0407008 · Mathematical Structures in Computer Science

Classically controlled quantum computation

Simon Perdrix, Philippe Jorrand

Published Jul 24, 2006• 26 citations

Abstract

It is reasonable to assume that quantum computations take place under the control of the classical world. For modelling this standard situation, we introduce a Classically controlled Quantum Turing Machine (CQTM), which is a Turing machine with a quantum tape for acting on quantum data, and a classical transition function for formalised classical control. In a CQTM, unitary transformations and quantum measurements are allowed. We show that any classical Turing machine can be simulated by a CQTM without loss of efficiency. Furthermore, we show that any -tape CQTM can be simulated by a 2-tape CQTM with a quadratic loss of efficiency. In order to compare CQTMs with existing models of quantum computation, we prove that any uniform family of quantum circuits (Yao 1993) is efficiently approximated by a CQTM. Moreover, we prove that any semi-uniform family of quantum circuits (Nishimura and Ozawa 2002), and any measurement calculus pattern (Danos et al. 2004) are efficiently simulated by a CQTM. Finally, we introduce a Measurement-based Quantum Turing Machine (MQTM), which is a restriction of CQTMs in which only projective measurements are allowed. We prove that any CQTM is efficiently simulated by a MQTM. In order to appreciate the similarity between programming classical Turing machines and programming CQTMs, some examples of CQTMs are given.

DOI: 10.1017/s096012950600538x

Related papers

Classically-controlled Quantum Computation

Simon Perdrix, Philippe Jorrand

It is reasonable to assume that quantum computations take place under the control of the classical world. For modelling this standard situation, we introduce a Classically-controlled Quantum Turing Machine (CQTM) which is a Turing machine with a quantum tape for acting on quantum data, and a classical transition function for a formalized classical control. In CQTM, unitary transformations and quantum measurements are allowed. We show that any classical Turing machine is simulated by a CQTM without loss of efficiency. Furthermore, we show that any k -tape CQTM is simulated by a 2-tape CQTM with a quadratic loss of efficiency. The gap between classical and quantum computations which was already pointed out in the framework of measurement-based quantum computation (see [S. Perdrix, Ph. Jorrand, Measurement-Based Quantum Turing Machines and their Universality, arXiv, quant-ph/0404146 , 2004]) is confirmed in the general case of classically-controlled quantum computation. In order to appreciate the similarity between programming classical Turing machines and programming CQTM, some examples of CQTM will be given in the full version of the paper. Proofs of lemmas and theorems are omitted in this extended abstract.

Electronic Notes in Theoretical Computer ScienceFeb 24, 200612 citations

Construction of a universal quantum computer

Antonio A. Lagana, Max A. Lohe, Lorenz von Smekal

We construct a universal quantum computer following Deutsch's original proposal of a universal quantum Turing machine (UQTM). Like Deutsch's UQTM, our machine can emulate any classical Turing machine and can execute any algorithm that can be implemented in the quantum gate array framework but under the control of a quantum program, and hence is universal. We present the architecture of the machine, which consists of a memory tape and a processor and describe the observables that comprise the registers of the processor and the instruction set, which includes a set of operations that can approximate any unitary operation to any desired accuracy and hence is quantum computationally universal. We present the unitary evolution operators that act on the machine to achieve universal computation and discuss each of them in detail and specify and discuss explicit program halting and concatenation schemes. We define and describe a set of primitive programs in order to demonstrate the universal nature of the machine. These primitive programs facilitate the implementation of more complex algorithms and we demonstrate their use by presenting a program that computes the NAND function, thereby also showing that the machine can compute any classically computable function.

Physical Review AMay 18, 20099 citations

Quantum Turing Machines and Quantum Prover-Verifier Interactions

Abel Molina

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.

Jul 31, 20200 citations

Towards Observable Quantum Turing Machines: Fundamentals, Computational Power, and Universality

Simon Perdrix

We study the observation of quantum Turing machines by allowing interactions between a quantum machine and its environment during the computation, whereas a quantum Turing machine --original model introduced by Deutsch-- remains isolated. We show that the introduction of observations leads to a weakening of the well formedness conditions of quantum Turing machines such that any (reversible or not) classical Turing machine is a special instance of a quantum machine. Moreover, observation of quantum Turing machines provides a formal solution to the halting process problem: the impossibility to know whether a given quantum Turing machine has actually reached its halting state. It also provides a more realistic abstract architecture of a quantum computer while most of the physical proposals of quantum computers are based on an hybrid classical-quantum architecture. However, we show that a natural formalisation of an observable quantum Turing machines leads to an over-powerful model solving undecidable problems. As a consequence, we introduce a restricted version of observable quantum Turing machines and we show that, under this restriction, any observable quantum Turing machine can be efficiently simulated by a quantum Turing machine. Finally, we discuss the potential application of the observable quantum Turing machine in the quest of a universal quantum Turing machine while recent papers have pointed out that a classical control is a key feature of a universal quantum machine.

Jan 1, 20110 citations

Universality of quantum Turing machines with deterministic control

Paulo Mateus, Amı́lcar Sernadas, André Souto

A simple notion of quantum Turing machine with deterministic, classical control is proposed and shown to be powerful enough to compute any unitary transformation that is computable by a finitely generated quantum circuit. An efficient universal machine with the s-m-n property is presented. The BQP class is recovered. A robust notion of plain Kolmogorov complexity of quantum states is proposed and compared with those previously reported in the literature.

Journal of Logic and ComputationFeb 26, 20159 citations

Quantum Turing Machines: Computations and Measurements

Stefano Guerrini, Simone Martini, Andrea Masini

Contrary to the classical case, the relation between quantum programming languages and quantum Turing Machines (QTM) has not been fully investigated. In particular, there are features of QTMs that have not been exploited, a notable example being the intrinsic infinite nature of any quantum computation. In this paper, we propose a definition of QTM, which extends and unifies the notions of Deutsch and Bernstein & Vazirani. In particular, we allow both arbitrary quantum input, and meaningful superpositions of computations, where some of them are “terminated” with an “output”, while others are not. For some infinite computations an “output” is obtained as a limit of finite portions of the computation. We propose a natural and robust observation protocol for our QTMs, which does not modify the probability of the possible outcomes of the machines. Finally, we use QTMs to define a class of quantum computable functions—any such function is a mapping from a general quantum state to a probability distribution of natural numbers. We expect that our class of functions, when restricted to classical input-output, will not be different from the set of the recursive functions.

arXiv:1703.07748Applied SciencesAug 11, 20209 citations