A Caltech Library Service

Quantum Algorithms

Kempe, J. and Vidick, T. (2010) Quantum Algorithms. In: Quantum Information, Computation and Cryptography: An Introductory Survey of Theory, Technology and Experiments. Lecture Notes in Physics. No.808. Springer , Berlin, pp. 309-342. ISBN 978-3-642-11913-2.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


The idea to put computing machines on a physical footing and to use the laws of physics as the basis of a computer already dates back several decades. In the 1980s, Feynman [24,25] was the first to consider quantum mechanics from a computational point of view by observing that the simulation of quantum mechanical systems on a classical computer seemed to require an increase in complexity exponential in the size of the system. He asked whether this exponential overhead was inevitable, and if it was possible to design a universal quantum computer, which could simulate any quantum system without the exponential overhead. In 1985 Deutsch [17] defined the model of the quantum Turing machine, generalizing the classical Turing machine to follow the laws of quantum mechanics. Yao later showed that it was equivalent to the quantum circuit model, also defined by Deutsch.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Vidick, T.0000-0002-6405-365X
Additional Information:© 2010 Springer-VerlagBerlin Heidelberg. First Online: 23 April 2010.
Subject Keywords:Quantum Algorithm; Quantum Circuit; Quantum Walk; Toffoli Gate; Hadamard Gate
Series Name:Lecture Notes in Physics
Issue or Number:808
Record Number:CaltechAUTHORS:20200804-153453452
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:104740
Deposited By: Tony Diaz
Deposited On:05 Aug 2020 19:08
Last Modified:16 Nov 2021 18:34

Repository Staff Only: item control page