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 ⟩={\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.

Approximate quantum counting estimates the number $k$ of satisfying assignments of a Boolean function, using a quantum oracle and quantum measurement. Controlled repetitions of a Grover search algorithm iteration let quantum interference reveal the count. For one input bit, a Hadamard test can give Pauli Z gate expectation value $1-k$: with the complemented phase oracle $U_f=\mathrm{diag}(2f(0)-1,2f(1)-1)$ and $G=-X{U}_f$, use $⟨+|X=⟨+|$ to obtain $⟨+|G|+⟩=-[(2f(0)-1)+(2f(1)-1)]/2=1-k$. Repeated preparations estimate this expectation value; one binary measurement result does not distinguish all three counts $0,1,2$.

The Bernstein-Vazirani algorithm identifies the coefficient string of a linear Boolean function with one Boolean quantum oracle call. It contrasts with the $n$ calls required by the classical query complexity of linear Boolean function identification. Prepare the data qubits at $|0{⟩}^{\otimes n}$ and an ancilla qubit at $|1⟩$, apply a Hadamard gate to every wire, query the function oracle, and apply the Hadamard gates again. The full output is $|a⟩|1⟩$.

The mechanism is Bernstein-Vazirani phase kickback. The Pauli X gate has eigenvector $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$ with eigenvalue $-1$. Thus the target flips become relative quantum phases on the data, givingThe final Hadamard transform maps this product to $|a⟩$, so computational-basis measurement recovers every coefficient with certainty. The ancilla preparation for the Bernstein-Vazirani algorithm ensures the required minus sign, and the Hadamard-conjugated linear oracle gives an exact quantum circuit interpretation. One query is optimal for $n\ge 1$, since without a query the output cannot depend on the unknown string.

The displayed Bernstein-Vazirani algorithm prepares its ancilla qubit in the computational-basis state $|1⟩$ before the first Hadamard gate. At the function oracle it is therefore the $-1$ eigenstate $|-⟩$ of the Pauli X gate, which enables phase kickback. Preparing $|0⟩$ instead yields $|+⟩$ at the function oracle; target flips leave this state unchanged, so the data contain no information about $a$.

The Hadamard-conjugated linear oracle makes the more general statement transparent. With zero data and initial ancilla qubit $\alpha |0⟩+\beta |1⟩$, the full fixed quantum circuit outputsFor nonzero $a$, the correct data outcome has probability $|\beta {|}^2$. To obtain exact identification for all $a$, this preparation must have $\alpha =0$, so it is $|1⟩$ up to global phase. This is a condition on the prescribed preparation circuit: any alternative quantum state preparation that supplies $|-⟩$ at the function oracle is equivalent.

Let $U_a|x⟩|b⟩=|x⟩|b\oplus (a\cdot x)⟩$ be the Boolean quantum oracle for a linear Boolean function, and put $W=H^{\otimes (n+1)}$. The CNOT gates $C_{j\to y}^{a_j}$ implement $U_a$, where the data wires control the ancilla qubit. CNOT control reversal in the Hadamard basis and $W^2=I$ imply the exact unitary operator identityHere $\oplus$ on strings is bitwise exclusive or. To conjugate a product, insert $W^2=I$ between its factors; each factor reverses its control and target, and the unused Hadamard gates cancel. The global phase is exactly $1$. In particular, the identity holds on arbitrary quantum superpositions, not only on the initialized inputs of the Bernstein-Vazirani algorithm.