Deutsch: constant or balanced?
★★☆For the function \(f(0)=1,\ f(1)=1\), we run Deutsch’s circuit. What is measured on the first qubit?
Appendix · beyond the lecture notes
With the amplitudes, interference and Hadamard gate of chapter 1, we can grasp the principle of two famous algorithms, with no extra formalism.
A register of \(n\) qubits carries \(2^n\) amplitudes. A quantum algorithm does not “try all cases at once”: it makes these amplitudes interfere so that wrong answers cancel and the right one remains. The final measurement does the rest. This works only for certain problems.
A black box computes \(f:\{0,1\}\to\{0,1\}\) through \(U_f\ket{x}\ket{y} = \ket{x}\ket{y\oplus f(x)}\). We want to know whether \(f\) is constant (\(f(0)=f(1)\)) or balanced (\(f(0)\ne f(1)\)). Classically two calls are needed; quantum mechanically, one.
Circuit: start from \(\ket0\ket1\), apply \(H\otimes H\), then \(U_f\), then \(H\) on the first qubit, and measure the first qubit.
The value of \(f\) goes into a phase \((-1)^{f(x)}\) (“phase kickback”), and the second \(H\) turns it into a probability: we read \(0\) if \(f\) is constant, \(1\) if balanced.
For the function \(f(0)=1,\ f(1)=1\), we run Deutsch’s circuit. What is measured on the first qubit?
We look for one marked item among \(N\). We start from the uniform state \(\ket s = H^{\otimes n}\ket0\) (all amplitudes equal to \(1/\sqrt N\)), then repeat two steps: the oracle flips the sign of the marked item’s amplitude; the diffusion \(2\ket s\bra s - \mathbb 1\) sends every amplitude to the other side of the mean. For \(N=4\) one iteration is enough: the oracle gives \((\tfrac12,\tfrac12,\tfrac12,-\tfrac12)\), with mean \(\tfrac14\), and inversion about the mean gives \((0,0,0,1)\).
For large \(N\), about \(\tfrac\pi4\sqrt N\) iterations are needed: a quadratic gain over classical search (about \(N/2\) tries on average), not an exponential one.
We look for one item among \(N=64\) with Grover’s algorithm. The success probability after \(k\) iterations is \(\sin^2\!\big((2k+1)\theta\big)\) with \(\sin\theta = 1/\sqrt N\). Which integer \(k \le 10\) (first maximum) gives the best probability?