### Abstract

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. Classical computers Quantum computers quantum circuit models Quantum computers quantum Turing machines Quantum computers universal

Original language | English (US) |
---|---|

Title of host publication | Quantum Information, Computation and Cryptography |

Subtitle of host publication | An Introductory Survey of Theory, Technology and Experiments |

Editors | Fabio Benatti |

Pages | 309-342 |

Number of pages | 34 |

DOIs | |

State | Published - 2010 |

### Publication series

Name | Lecture Notes in Physics |
---|---|

Volume | 808 |

ISSN (Print) | 0075-8450 |

### ASJC Scopus subject areas

- Physics and Astronomy (miscellaneous)

## Fingerprint Dive into the research topics of 'Quantum algorithms'. Together they form a unique fingerprint.

## Cite this

*Quantum Information, Computation and Cryptography: An Introductory Survey of Theory, Technology and Experiments*(pp. 309-342). (Lecture Notes in Physics; Vol. 808). https://doi.org/10.1007/978-3-642-11914-9_10