Citation: Deutsch, David. "Quantum theory, the Church-Turing principle and the universal quantum computer." Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 400.1818 (1985): 97-117.
Web: https://royalsocietypublishing.org/doi/10.1098/rspa.1985.0070
Tags: Philosophical, Universal-scheme
This is the paper in which quantum computing came into its own as a subject. David Deutsch discusses the Church-Turing thesis, and argues that it has necessarily physical implications. Namely, it asserts limitations on what experiments could ever be performed. Deutsch argues that a correct physical version of the Church-Turing thesis requires a universal quantum computer.
This "universal quantum computer" is not made using circuits. It is allowed to be acted on by an arbitrary unitary which preserves local entanglement, and this unitary is applied repeatedly. That is, the state of the machine at time t is U^t applied to the state at time 0. It is shown that this is universal, in the sense that it can simulate any classical computation and also includes new quantum computations. The circuit model for quantum computation was introduced the same year, but by Feynman:
> Feynman, Richard P. "Quantum mechanical computers." Found. Phys. 16.6 (1986): 507-532.
This paper is very stepped in what I would call natural philosophy. Deutsch's paper is also special because he includes a new algorithm which demonstrates the power of quantum parallelism for speeding up computations.
A nice observation from this paper is this: "Turing machines, on the other hand, undergo irreversible changes during computations, and indeed it was, until recently, widely held that irreversibility is an essential feature of computation".The paper he is referring to is this one:
> Bennett, Charles H. "Logical reversibility of computation." IBM journal of Research and Development 17.6 (1973): 525-532.