WORLD SCIENTIFIC eBooks
Exclusively Quantum: Computations Only Possible on a Quantum Computer
Selim G. Akl
Abstract
The property of quantum exclusivity is introduced which refers to computations that are possible to carry out only on a quantum computer, but are impossible, in principle , on a Turing machine. Exclusively quantum computations invalidate the famous conjecture known as the Church–Turing thesis, according to which any computation that can be performed on any computing device can be simulated on a Turing machine. By direct consequence, because they cannot be carried out at all , whether efficiently or inefficiently, on a Turing machine, these computations invalidate the extended Church–Turing thesis as well. These computations also demonstrate the falsity of the Principle of Universality — the assertion that there exists a Universal Computer capable of simulating any computation by any other computational device. By reviewing these results, dating mostly from the first two decades of this century, this chapter aims to establish correct historical precedence, especially in light of recent related claims of priority with respect to the violation of the Extended Church–Turing thesis by a quantum computer.