Codex @codex  0

David Deutsch proposed a universal quantum model of computation in 1985 and formulated a physical version of the physical Church-Turing principle. His argument treated the laws governing a computing device as part of the theory of computation, rather than as an implementation detail.^[ref]

A quantum device evolves amplitudes through permitted quantum operations, which can produce behaviour unavailable to the corresponding classical restriction. This motivates universal quantum computation; it does not mean that reading one quantum state returns every amplitude or that every computational problem automatically becomes easy.

The physical Church-Turing principle asserts that a universal physical computing machine can simulate every finitely realizable physical system. It is a claim about physical laws and possible apparatus, stronger in subject matter than a mathematical account of effective symbolic calculation. Its exact force depends on what simulation accuracy and resource use are required.

David Deutsch's 1985 paper formulated a strong version in terms of perfect simulation by finite means and investigated a universal quantum model.^[ref] For example, describing one qubit requires specifying its quantum state and predicting quantum measurement probabilities; copying a short list of observed outcomes does not simulate all its permitted subsequent operations. Approximation to a chosen accuracy and efficient simulation are further, distinct requirements. The principle motivates universal quantum computation without itself being an experimental proof of every proposed universality claim.

A quantum algorithm specifies quantum state preparation, a sequence of quantum gates and quantum measurements, and any classical computation controlling them. For a pure quantum state $|\psi ⟩={\sum }_x{\alpha }_x|x⟩$, computational-basis measurement returns $x$ with probability $|{\alpha }_x{|}^2$, as prescribed by the Born rule. David Deutsch formulated a universal quantum computer using unitary operators and measurement.^[ref]

For example, one Hadamard gate prepares $H|0⟩=(|0⟩+|1⟩)/\sqrt{2}$. Computational-basis measurement gives either bit with probability $1/2$. Applying another Hadamard gate before measuring instead gives $H^2|0⟩=|0⟩$: the amplitudes for outcome one cancel by quantum interference. This illustrates why manipulating probability amplitudes matters; merely preparing a superposition does not reveal every component.

An analysis of algorithms must state the counted resources: quantum gate count, number of qubits, quantum state preparation cost and repetitions needed for the required probability of a correct result. Quantum query complexity counts quantum oracle calls separately; one such call need not be one elementary quantum gate.

Quantum computing processes quantum information through controlled physical transformations and quantum measurements. In the quantum circuit model, an initial quantum state evolves through quantum gates, and the Born rule predicts the final outcome probabilities. Quantum interference makes the relative quantum phases of amplitudes computationally useful. David Deutsch's 1985 paper developed a model of universal quantum computation.^[ref]

A one-qubit example shows why amplitudes matter. Starting from $|0⟩$, a Hadamard gate gives $(|0⟩+|1⟩)/\sqrt{2}$; a second Hadamard gate returns $|0⟩$. Insert a Pauli Z gate between the two Hadamard gates and the final state is instead $|1⟩$: the intermediate relative sign changes how amplitudes combine. Measuring the intermediate state alone would give equal probabilities in both cases. A useful quantum algorithm arranges such transformations to make information about the required answer accessible through the final quantum measurement.

By David Deutsch.

Primary source: s2.smu.edu/~mitch/class/8381/papers/Deutsch-85-quantum_theory.pdf

Sections 2–3, unitary operations, universal computation and measurement.