Cambridge University Press eBooks

Turing in Quantumland

Harry Buhrman

Published May 1, 2014• 0 citations

Abstract

. We revisit the notion of a quantum Turing-machine , whose design is based on the laws of quantum mechanics. It turns out that such a machine is not more powerful, in the sense of computability, than the machine originally constructed by Turing. Quantum Turing-machines do not violate the Church–Turing thesis. The benefit of quantum computing lies in efficiency . Quantum computers appear to be more efficient, in time, than classical Turing-machines, however its exact additional computational power is unclear, as this question ties in with deep open problems in complexity theory. We will sketch where BQP, the quantum analogue of the complexity class P, resides in the realm of complexity classes. §1. Introduction . A decade before Turing developed his theory of computing, physicists struggled with the advent of quantum mechanics. During the famous 5th Solvay Conference in 1927 it was clear that a new era of physics had surfaced. Its strange features like superposition and entanglement still lead to heated discussions and much confusion. However strange and counter-intuitive, the theory has never been refuted by experiments that are performed daily and in great numbers throughout laboratories around the world. Time after time the predictions of quantum mechanics are in full agreement with experiment. Shortly after the advent of quantum mechanics, Church, Turing and Post developed the notion of computability [Chu36, Tur36, Pos36]. Less than 10 years later these formal ideas would be put to practice resulting in the ENIAC, the first general purpose machine.

DOI: 10.1017/cbo9781107338579.004

Related papers

Quantum computation

Sanjeev Arora, Boaz Barak

Turning to quantum mechanics … secret, secret, close the doors! we always have had a great deal of difficulty in understanding the world view that quantum mechanics represents. … It has not yet become obvious to me that there's no real problem. I cannot define the real problem, therefore I suspect there's no real problem, but I'm not sure there's no real problem. So that's why I like to investigate things. – Richard Feynman, 1964 The only difference between a probabilistic classical world and the equations of the quantum world is that somehow or other it appears as if the probabilities would have to go negative. – Richard Feynman, in “Simulating Physics with Computers,” 1982 Our first result is the existence of an efficient universal quantum Turning machine in Deutsch's model. … We give the first formal evidence that quantum Turning machines violate the modern complexity theoretic formulation of the Church Turning thesis. We show the existence of a problem relative to an oracle that can be solved in polynomial time on a quantum Turning machine but require super polynomial time on a bounded error probabilistic Turning machine. – E. Bernstein and U. Vazirani, “Quantum Complexity Theory,” 1997 Quantum computing is a new computational model that may be physically realizable and may provide an exponential advantage over “classical” computational models such as probabilistic and deterministic Turing machines.

Cambridge University Press eBooksApr 20, 20090 citations

Computational Power of the Quantum Turing Automata

Sina Jafarpour, Mohammad Ghodsi, Keyvan Sadri +1 more

Lots of efforts in the last decades have been done to prove or disprove whether the set of polynomially bounded problems is equal to the set of polynomially verifiable problems. This paper will present an overview of the current beliefs of quantum complexity theorists and discussion detail the impacts these beliefs may have on the future of the field. We introduce a new form of Turing machine based on the concepts of quantum mechanics and investigate the domain of this novel definition for computation. The main object is to show the domain of these computation machines and the new definition of algorithms using these automata. In section one we give a brief fundamental overview of classical complexity theory, Turing machine and all the fundamental concepts required for the next chapters. In section two we describe various classes of classical complexity automata. In next chapter we introduce quantum complexity featuring quantum Turing machines and discuss its relationship to classical complexity. Section four presents a relationship between quantum complexity classes based on the quantum Turing machines and quantum oracles, and their relationship with corresponding classical complexity classes. And section five presents a discussion on the practical phenomena in problem solving using quantum computers. Finally in section five we speculate briefly on the direction we believe the field to be headed, and what might reasonably be expected in the future

Apr 1, 20070 citations

Guest Column

Carlo Mereghetti, Beatrice Palano

Quantum computing is a prolific research area, halfway between physics and computer science [27, 29, 52]. Most likely, its origins may be dated back to 70's, when some works on quantum information began to appear (see, e.g., [34, 37]). In early 80's, R.P. Feynman suggested that the computational power of quantum mechanical processes might be beyond that of traditional computation models [25]. Almost at the same time, P. Benioff already proved that such processes are at least as powerful as Turing machines [9]. In 1985, D. Deutsch [22] proposed the notion of a quantum Turing machine as a physically realizable model for a quantum computer. From the point of view of structural complexity, E. Bernstein and U. Vazirani introduced in [20] the class BQP of problems solvable in polynomial time on quantum Turing machines, focusing attention on relations with the corresponding deterministic and probabilistic classes P and BPP, respectively. Several works in the literature explored classical issues in complexity theory from the quantum paradigm perspective (see, e.g., [7, 60, 61]).

ACM SIGACT NewsOct 17, 20214 citations

Quantum Computation

Cristopher Moore, Stephan Mertens

Abstract According to the Church-Turing Thesis, a Turing machine, and thus the programming languages and computers in existence, can simulate any reasonable computing device. However, there are physical devices that are exponentially more efficient than a Turing machine, and hence would prove exponentially difficult to simulate using such a machine. This chapter explores the concept of quantum computers and their potential not only to simulate quantum physics exponentially faster than classical computers but also to solve other problems exponentially faster. It considers algorithms that break cryptosystems, find needles in haystacks, and predict who can win a game. It first describes particles, waves, and amplitudes in quantum computation before turning to states and operators. It then examines how interference lets a quantum computer learn some things about a function, how quantum computers can solve factoring in polynomial time, the link between factoring and modern cryptography, graph isomorphism and the hidden subgroup problem, and quantum walks and scattering.

Aug 11, 20110 citations

Critique of fault-tolerant quantum information processing

Robert Alicki

Introduction The idea of fault-tolerant quantum computation presents a bold challenge to the rather well established principles called the strong Church–Turing thesis and the Bohr correspondence principle. One of the variations of the strong Church–Turing thesis (SCTT), which is not due to Church or Turing, but rather gradually developed in the field of computational complexity theory, is the following [BV97]: Any “reasonable” model of computation can be efficiently simulated on a probabilistic Turing machine. This can be expressed even less formally but more practically as: No computer can be more efficient than a digital one equipped with a random number generator. Here, a computer A is “more efficient” than a computer B if A can solve, in polynomial time, a problem that cannot be solved in a polynomial time by computer B. On the other hand the Bohr correspondence principle (BCP) demands that: Classical physics and quantum physics give the same answer when the systems become large. A more rigorous form of the BCP is the following: For large systems the experimental data are consistent with classical probabilistic models . Here, by a classical probabilistic model we mean a model in which all observables are described by real functions, and all states by probability distributions on a certain set (“phase-space”).

arXiv:1310.8457Cambridge University Press eBooksSep 5, 20134 citations

Quantum Computation and the Church–Turing Hypothesis

Christopher G. Timpson

Some of the philosophical questions raised by the theory of quantum computation are discussed. First it is considered whether the possibility of exponential speed-up in quantum computation provides an argument for a more substantive notion of quantum information than so far allowed. It is concluded that this is not so. Then some questions regarding the status of the Church-Turing hypothesis in the light of quantum computation are considered. In particular, Deutsch’s claim that a physical principle, the Turing Principle, underlies the Church-Turing hypothesis is rebutted. Finally, the question of whether the Church-Turing hypothesis might serve as a constraint on the laws of physics is briefly considered.

Oxford University Press eBooksApr 25, 20130 citations