Quantum algorithm
= Quantum algorithm
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\rangle=\sum_x\alpha_x|x\rangle$, <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>.<Quantum theory, the Church-Turing principle and the universal quantum computer by David Deutsch>[sections 2–3]{ref}
For example, one <Hadamard gate> prepares $H|0\rangle=(|0\rangle+|1\rangle)/\sqrt2$. <Computational-basis measurement> gives either <bit> with <probability> $1/2$. Applying another <Hadamard gate> before measuring instead gives $H^2|0\rangle=|0\rangle$: 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>.