Quantum Information, 2 Volume Set, 2nd Edition

6 Quantum Algorithms

Julia Kempe

LIAFA ‐ case 7014, Cedex 13, 75205 Paris, France

6.1 Introduction

The idea to use quantum mechanics for algorithmic tasks may be traced back to Feynman (1,2). The application he had in mind was the simulation of quantum mechanical systems by a universal quantum system, the quantum computer. Feynman argued that quantum mechanical systems are well equipped to simulate other quantum mechanical systems; hence a universal quantum machine might be able to efficiently do such simulations. Another approach to this question was taken by Deutsch (3), who tried to reconcile quantum mechanics and the Church–Turing principle, which (roughly speaking) states that any computable function can be calculated by what ...