David Deutsch’s paper, “Quantum theory, the Church-Turing principle and the universal quantum computer,” presents several key arguments and concepts central to the field of quantum computing:

  1. Church-Turing Principle: Deutsch extends the classical Church-Turing hypothesis, which states that any function naturally regarded as computable can be computed by a Turing machine. He formulates a physical principle asserting that “every finitely realizable physical system can be perfectly simulated by a universal model computing machine operating by finite means.”
  2. Limitations of Classical Computers: Classical deterministic computing machines compute functions deterministically, while stochastic (probabilistic) classical machines provide outputs based on probability distributions. However, these classical models do not fully adhere to the Church-Turing principle when considering the continuous nature of classical systems versus the discrete nature of Turing machines.
  3. Quantum Computers: Deutsch introduces the concept of quantum computers as a generalization of classical Turing machines. Quantum computers can potentially simulate any physical system perfectly, adhering to the strong form of the Church-Turing principle. Unlike classical machines, quantum computers leverage quantum superposition and entanglement, allowing them to perform certain tasks more efficiently through quantum parallelism.
  4. Quantum Parallelism: One of the remarkable properties of quantum computers is their ability to perform many calculations simultaneously due to quantum parallelism. This is achieved by preparing the quantum system in a superposition of states and then evolving it according to quantum dynamics, allowing for the simultaneous exploration of multiple computational paths.
  5. Implications for Physics: The paper explores the deeper connections between quantum computation and physical theories. Quantum complexity theory, for instance, provides a more physically realistic definition of complexity and knowledge within a physical system compared to classical complexity theory.
  6. Universal Quantum Computer: Deutsch describes a universal quantum computer capable of simulating any physical system, arguing that quantum mechanics, unlike classical mechanics, is compatible with the Church-Turing principle in its strongest form. This universal quantum computer would have properties that are not reproducible by any classical Turing machine, though it would not compute non-recursive functions.
  7. Experimental Validation: While the principles underlying the theory of quantum computers are grounded in physical assertions, their empirical validation follows the same criteria as other physical principles, relying on the consistency with experimentally corroborated theories and observations.

In summary, Deutsch’s work lays the foundational theoretical framework for quantum computing, highlighting the limitations of classical computing and the potential of quantum computers to transform our understanding of computation and its relationship with physical systems