Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 67 / 4 / b / Solution

The quantum circuit has one control wire per binary digit and one target quantum register. Every control starts in $|0⟩$, receives a Hadamard gate, controls the corresponding power $U^{2^j}$, and then enters the collective inverse quantum Fourier transform. Only the control register is measured; the target stays in $|\psi ⟩$.

The omitted intermediate wires continue the pattern $j=0,1,\dots ,m-1$. The inverse quantum Fourier transform black box is defined on the integer basis $|k⟩$ with $k={\sum }_j{2}^j{k}_j$, so the displayed ordering introduces no hidden bit reversal. The measured bits satisfyEach controlled power box represents $2^j$ sequential controlled-$U$ uses when only that primitive is available.