Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 58 / 1

With the negative exponential convention of the specified quantum Fourier transform, the amplitude of computational outcome $k$ isIf $k=m$, every summand is one. Otherwise this finite geometric series has ratio $q\ne 1$ with $q^N=1$, so it equals $(1-q^N)/(1-q)=0$. ThusThe Born rule gives outcome $m$ with probability one when performing a quantum measurement in the computational basis. Recover the promised phase as ${\varphi }_m=2\pi m/N$ modulo $2\pi$. Using the opposite Fourier sign would instead return the label $-m\mathrm{mod}N$, so the sign convention matters.

Use most-significant-bit-first ordering, so $l={\sum }_{j=1}^n{b}_j{2}^{n-j}$ and $|l⟩=|b_1⟩\otimes \cdots \otimes |b_n⟩$. Then the coefficient factors as $e^{i{\varphi }_{m}l}={\prod }_j{e}^{i{\varphi }_m{b}_j{2}^{n-j}}$. Expanding a tensor product over all bit strings proves the product decomposition of a Fourier phase state:Each factor is a normalized one-qubit state. The whole register is therefore a product state, hence a separable state; no claim that arbitrary outputs of the Fourier transform are separable is needed. Reversing the bit convention reverses the order of these factors.

The PDF circuit has its upper wire controlling both CNOT gates. Its successive states areThe first arrow is the upper Hadamard gate; the middle phase arises because both ones receive a phase. The second CNOT disentangles and resets the lower wire. Hence the output isThis implements doubled logical phase using two parallel phase gates, rather than two serial applications on one qubit.

Write the promised phase as $\varphi =2\pi m/8$. Prepare three logical qubits in $|+⟩$ and attach zero ancillas in three blocks of sizes four, two and one. A block of size $r$ is prepared by fanout CNOT gates asApply one copy of $U_{\varphi }$ to every physical qubit in every block, all in the same time step. Undo each fanout. The logical block output is $(|0⟩+e^{ir\varphi }|1⟩)/\sqrt{2}$ and every ancillary wire returns to zero. This is parallel phase multiplication by coherent fanout; its intermediate entanglement copies basis labels, and does not clone an arbitrary quantum state.

For block weights $4,2,1$, the three logical wires now containApply the specified negative-sign quantum Fourier transform and measure. Part (a) gives label $m$ deterministically. Thus seven parallel phase-gate applications, on three logical wires and four ancillas, identify the phase in one oracle time step. Preparation, uncomputation and the Fourier transform cost no time under the stated model; using serial powers would not meet the time requirement.