Turing in Quantumland

. 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.