Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 58 (Introduction to Quantum Computation)

Use the symmetric lossless beam splitter convention with transmission amplitude $t=1/\sqrt{2}$ and reflection amplitude $r=i/\sqrt{2}$. The two mirrors contribute the same fixed quantum phase, which can be suppressed. At the rightward port $D_1$, the upper-arm route has one reflection at BS1 and one transmission at BS2, while the lower-arm route has one transmission at BS1 and one reflection at BS2. Their probability amplitudes therefore add asBy the Born rule,For the upward port, the two amplitudes are $r^2{e}^{i\theta }$ and $t^2$, giving $a_0=(1-e^{i\theta })/2$ and $P(D_0)={\sin }^2(\theta /2)$. They sum to one, as required for an ideal lossless Mach-Zehnder interferometer. Thus $D_1$ is bright at zero relative quantum phase and dark at quantum phase $\pi$. A fixed unequal reflection quantum phase or a swapped port labeling would shift the fringe; the stated convention fixes the port and quantum phase calibration used below.

Write the unknown pure photon polarization qubit asThe polarizing beam splitter sends the $H$ component down the lower path and the $V$ component up the upper path. After rotating the upper photon polarization to $H$, both paths have the same internal quantum state and can interfere at BS2. Absorb fixed apparatus phases into a calibrated zero for the tunable quantum phase. With the preceding reflection convention, the quantum state before BS2 is $(\alpha |\ell ⟩+i\beta e^{i\theta }|u⟩)|H⟩$, so the two output amplitudes areConsequentlyRepeated counts while scanning $\theta$ determine the complex quantum coherence $\gamma$. The interference visibility is $2|\gamma |$, and the fringe position determines the relative quantum phase $\arg \beta -\arg \alpha$ whenever both components are nonzero.

A fringe alone is not enough to determine an arbitrary photon polarization quantum state: it fixes $|\alpha \beta |$ but not which of $|\alpha {|}^2$ and $|\beta {|}^2$ is larger. Indeed, $|H⟩$ and $|V⟩$ both give the flat fringe $P_1=1/2$. For a general pure quantum state, the two possible population differences areResolve this ambiguity by temporarily detecting the two paths before BS2. Their relative counts give $h=|\alpha {|}^2$ and $1-h=|\beta {|}^2$ using the same polarizing beam splitter and detectors. Taking $\alpha =\sqrt{h}$ as a global-phase choice, the reconstructed quantum state for $h>0$ isIf $h=0$, it is $|V⟩$ up to a global phase. This completes interferometric polarization tomography. The counts are obtained from many identically prepared photons; they do not identify an arbitrary quantum state from one photon.

A full fringe scan is unnecessary. Use the same components to make three fixed projective measurements, on separate batches of identically prepared photons. Direct path detection after the polarizing beam splitter measures the $H/V$ populations. Recombine after matching the arm photon polarizations, once with $\theta =0$ and once with $\theta =\pi /2$, to measure the two quadratures of the quantum coherence.

In the $H/V$ basis, write the density matrix in terms of its Bloch vector as $\rho =(I+r_{x}X+r_{y}Y+r_{z}Z)/2$. The previous formula becomesThus three measured relative frequencies giveand determineThe two interferometric settings analyze the diagonal linear polarizations $(|H⟩\pm |V⟩)/\sqrt{2}$ and the circular polarizations $(|H⟩\pm i|V⟩)/\sqrt{2}$, with detector labels fixed by the calibrated quantum phase convention. This is informationally complete three-observable qubit tomography: direct measurements in three bases replace fitting an entire phase-dependent fringe. It also reconstructs a mixed input, for which $|r|\le 1$, although the source here is assumed pure.

Simply measuring transmission through one fixed polarizing beam splitter would determine only $r_z$. Rotating a linear analyzer through different angles can additionally determine $r_x$, but cannot distinguish the two signs of $r_y$ without a relative-phase measurement. For arbitrary, possibly elliptical photon polarization, all three settings above are needed; no extra analyzer element beyond the described path-phase control and photon polarization rotator is required.

Without the upper-arm rotation, the photon polarization still labels the path. Before BS2 the quantum state isAfter the balanced beam splitter, the polarization-valued output amplitudes areThe detectors do not resolve photon polarization. Since $⟨H|V⟩=0$, the cross terms vanish in the Born rule:These probabilities are independent of the tunable quantum phase and the input photon polarization, so there is no usable wave interference fringe. Equivalently, taking the partial trace over photon polarization removes the quantum coherence between the two path quantum states. The which-path information is retained in orthogonal photon polarizations even without anybody measuring it. Rotating the two occupied photon polarization quantum states to the same quantum state removes that distinction and allows the cross term in part (ii).

Put $N=2^t$ and write $U|u⟩=e^{i\varphi }|u⟩$, with $|u⟩$ normalized. The Hadamard gates prepare the control register in $N^{-1/2}{\sum }_{k=0}^{N-1}|k⟩$. Controlled powers of the unitary operator then give quantum phase kickback:Thus the register quantum state is $N^{-1/2}{\sum }_k{e}^{ik\varphi }|k⟩$, while the target remains $|u⟩$. Define the quantum Fourier transform by $F_N|m⟩=N^{-1/2}{\sum }_k{e}^{2\pi ikm/N}|k⟩$. Its inverse givesWhen $\varphi =2\pi n/N$, the inner finite geometric series equals $N$ if $m\equiv n(\mathrm{mod}N)$ and zero otherwise. Therefore exact quantum phase estimation givesThe quantum phase, rather than an unrestricted integer $n$, is recovered modulo $2\pi$.

The printed circuit has no bit-reversal swaps. Its top control uses $U^{2^{t-1}}$, and its measured top wire gives the least significant output bit. Write $n\mathrm{mod}N={\sum }_{j=0}^{t-1}{2}^j{b}_j$. Before the top wire's final Hadamard gate, its relative quantum phase is $2^{t-1}\varphi =\pi n$, so that gate produces $b_0$. The controlled inverse quantum phase gates then subtract its contribution from lower wires. More generally, before the final Hadamard gate on wire $j$, the relative quantum phase isso that wire gives $b_j$ deterministically. For the three-wire drawing, the correct interpretation isEquivalently, its Fourier-inversion circuit is $R{F}_N^{†}$, where $R$ reverses the register bits. Relabeling the measured bits or appending swaps gives the usual integer output. This bit convention matters, for example, when quantum phase $\pi$ produces top-to-bottom bits $001$, representing the label four rather than one.

Write $\varphi =2\pi n/N+ϵ$, with $|ϵ|\le \delta \ll 2\pi /N$. Decode the measured bits as above. The probability amplitude of label $m$ isUsing the finite geometric series,Interpret removable singularities by continuity. In particular, near-grid quantum phase estimation returns the nearby exact label $n\mathrm{mod}N$ with probabilityThis is near one under the stated small-offset assumption, but not exactly one when $ϵ\ne 0$.

There is also a rigorous error bound. Taking the squared modulus of the sum giveswhere $1-\cos x\le x^2/2$ and the elementary sums of $k$ and $k^2$ evaluate the last expression. HenceOn that event the circular quantum phase error is at most $\delta$. For other labels, the exact probabilities areTheir total is $1-P(n)=O(N^2{\delta }^2)$, describing the leakage from the perfect solution. The physical output bit string remains reversed in the printed circuit; this changes its decoding, not these probabilities.

A central application is quantum order finding, which supplies the quantum step in the Shor algorithm for factoring an integer $M$. Choose an integer $a$ coprime to $M$, and let $r$ be its multiplicative order modulo $M$. On valid residue quantum states define the reversible modular-multiplication unitary operator $U_a|x⟩=|ax\mathrm{mod}M⟩$, extending it reversibly to any unused computational basis quantum states.

The orbit $|1⟩,|a⟩,\dots ,|a^{r-1}⟩$ has the orthonormal eigenstatesfor $s=0,\dots ,r-1$. One need not know $r$ to prepare an eigenstate: the easy input $|1⟩=r^{-1/2}{\sum }_s|u_s⟩$ makes quantum phase estimation sample one of these eigenphases. Its control register estimates $s/r$. With $N=2^t$ chosen at least of order $M^2$, the nearest quantum phase label has rational approximation error small enough for continued-fraction recovery in quantum order finding. For instance, $N>2M^2$ gives $|m/N-s/r|<1/(2r^2)$ on the nearest-label event. If $s$ and $r$ are coprime, the recovered denominator is $r$; otherwise one obtains a divisor and can repeat, combine candidates and verify them by modular exponentiation.

When the verified order is even and $a^{r/2}\not\equiv -1(\mathrm{mod}M)$, the greatest common divisorsgive nontrivial factors: their product is divisible by $M$, while neither factor inside the gcd is zero modulo $M$. Unsuccessful choices of $a$ or quantum phase samples are handled by repetition and classical verification. Controlled powers of $U_a$ are implemented by efficient reversible modular arithmetic, rather than by naively applying $U_a$ exponentially many times.

Quantum phase estimation turns modular-multiplication eigenphases into an efficiently usable period, enabling quantum factoring in time polynomial in the bit length of the integer. Factoring is important to public-key cryptography, and this is a major example of a quantum algorithm improving on known classical methods. Another use is extracting energy eigenvalues by applying quantum phase estimation to a controlled time-evolution operator, with care to avoid energy aliasing and to prepare an input having overlap with the desired eigenstate.

Number the physical wires $1,\dots ,5$ from top to bottom and write a computational basis ket in that order. The first four are ancilla qubits and the fifth carries the input. It is enough to follow the basis input $|b⟩$, $b\in \{0,1\}$, because the encoding quantum circuit acts linearly.

The first fan-out consists of four controlled-NOT gates from wire 5 to wires 1–4. It sends $|0000b⟩$ to $|bbbbb⟩$. The three Hadamard gates then giveThe two Pauli X gates on wires 2 and 3, followed by a Controlled-Z gate and the same two X gates, restore the bits but contribute $(-1{)}^{(1-c)(1-d)}$: the sign is negative exactly when the original bits on both wires were zero. Finally, the right-hand controlled-NOT gates are $3\to 4$, $2\to 5$, $1\to 4$ and $1\to 5$. They leave the first three bits unchanged and turn the last two into $b\oplus a\oplus d$ and $b\oplus a\oplus c$. ThusExplicitly, the logical basis quantum states produced by the printed gates areEach has eight orthogonal terms of equal magnitude, and their supports are disjoint, so they are normalized and mutually orthogonal. The arbitrary input is therefore encoded asThis is a realization of the five-qubit error correcting code. The input amplitudes and their relative quantum phase are preserved in the logical subspace; the encoding is an entangled-state linear isometry, not five independent copies of the unknown input. The explicit signs and bit ordering above are fixed by this circuit, rather than by a convention for a different encoder.

Assume independent physical-qubit errors with common probability $p$, ideal encoding and recovery, and the specified rule that every block with two or more errors fails. The number of physical errors has a binomial distribution with parameters $5,p$. Correct recovery occurs for zero or one error, soThe corresponding logical failure probability isAn unencoded qubit succeeds with probability $1-p$. Thus encoding improves this probability precisely when $f(p)<p$. Factoring givesOn $0<p<1$, the sign is the sign of $g(p)=4p^3-11p^2+9p-1$. Its derivative is $12p^2-22p+9$: it is positive until $(11-\sqrt{13})/12$ and negative afterwards on $[0,1]$. Since $g(0)=-1$, $g(1)=1$ and its interior maximum is positive, there is exactly one zero in $(0,1)$. The five-qubit concatenation threshold is thereforeAt $p=p_{\ast }$ the two success probabilities agree; above it this decoder makes the error rate worse. At $p=0$ both schemes succeed perfectly, and at $p=1$ both fail under the stated error model. The small-$p$ behavior $f(p)=10p^2+O(p^3)$ exhibits cancellation of every single-qubit-error contribution.

Use a concatenated quantum error-correcting code: each of the five outer-code qubits is encoded in its own five-qubit inner block. Independent physical errors and ideal inner correction make each decoded block act as one outer qubit with error probability $q=f(p)$. Errors in distinct inner blocks remain independent in this model. Outer recovery succeeds if at most one of the five decoded blocks is bad, givingThus the two-level logical failure probability isThis improves the leading error order from $p$ for a bare qubit to $p^2$ for one level and $p^4$ for two. At least two physical errors must occur in each of two different inner blocks to defeat the prescribed two-stage decoder. Many error patterns with more than one error in the full 25-qubit register are therefore corrected: one error in each of all five blocks is removed at the inner level, and a single failed inner block is corrected at the outer level. Concentrating several physical errors in one block can be easier for this decoder than placing two errors in each of two blocks.

More generally, $\ell$ levels use $5^{\ell }$ physical qubits with recursion $p_{\ell +1}=f(p_{\ell })$. For $0<p<p_{\ast }$, one has $f(f(p))<f(p)<p$. Repeated concatenation decreases to zero: its limit must be a fixed point of the continuous function $f$, and below $p_{\ast }$ the only fixed point is zero. A simple quantitative bound is $f(x)\le 10x^2$, obtained by the union bound over the ten pairs of possible error positions. Induction giveswhich proves rapid suppression when $p<1/10$; the exact threshold is the larger value $p_{\ast }$. Above $p_{\ast }$ this recursion amplifies errors instead.

Below threshold, concatenation suppresses logical errors while allowing an entire bad inner block to be corrected at the next level. The cost is additional physical qubits, gates, syndrome extraction and recovery. The calculated threshold concerns the independent transmission-noise model with perfect encoding and recovery; including noisy operations or correlated channel errors requires a different error analysis.

For a positive operator $A$, the spectral theorem writes $A={\sum }_j{a}_j|j⟩⟨j|$ with $a_j\ge 0$. Hence its unique positive square root of an operator is $\sqrt{A}={\sum }_j\sqrt{a_j}|j⟩⟨j|$. Conjugating this spectral decomposition shows $\sqrt{UA{U}^{†}}=U\sqrt{A}{U}^{†}$ for a unitary operator $U$.

Let $\Delta ={\rho }_1-{\rho }_2$ and ${\rho }_i^{\prime }=U{\rho }_i{U}^{†}$. Then ${\Delta }^{\prime }=U\Delta U^{†}$ and $({\Delta }^{\prime }{)}^{†}{\Delta }^{\prime }=U{\Delta }^{†}\Delta U^{†}$. The square-root covariance and the cyclic property of the trace giveFor the quantum fidelity, covariance first gives $({\rho }_1^{\prime }{)}^{1/2}=U{\rho }_1^{1/2}{U}^{†}$. ThereforeApply the same square-root identity and the cyclic property of the trace to obtainThus unitary invariance of trace distance and fidelity givesThe same $U$ acts on both quantum states: these quantities depend on the relative distinguishability of the quantum states, not on a choice of basis.

Write ${\rho }_1=|\psi ⟩⟨\psi |$ and ${\rho }_2=|\phi ⟩⟨\phi |$. A pure-state density matrix is a rank-one orthogonal projector, so ${\rho }_1^{1/2}={\rho }_1$ andTaking its square root and trace yields the unsquared quantum fidelityUse unitary invariance of trace distance and fidelity to choose a basis of the span of the two quantum states in which $|\psi ⟩=|0⟩$ and $|\phi ⟩=c|0⟩+s|1⟩$, with $c=F\ge 0$ and $s=\sqrt{1-c^2}\ge 0$. Choosing state-vector phases to make the coefficients nonnegative does not change either density matrix. On that span,Its eigenvalues are $s$ and $-s$, with zero eigenvalues on the orthogonal complement. The positive square root of ${\Delta }^{†}\Delta$ therefore has two eigenvalues $s$, so the trace distance is $(s+s)/2=s$. Thus the pure-state trace distance and fidelity identity isIdentical pure quantum states give $F=1,D=0$; orthogonal pure quantum states give $F=0,D=1$. If the span is one-dimensional, the identical-state result follows directly, so no second basis vector is required. This formula uses the unsquared fidelity convention in the paper; if fidelity denotes squared overlap instead, the square inside the formula is omitted.

The Pauli X gate interchanges the two basis quantum states. Because the bit-flip outcome is a classical unobserved error rather than a coherent superposition, the quantum bit-flip channel givesFor $|\psi ⟩=\alpha |0⟩+\beta |1⟩$, its explicit density matrix isFor a pure reference quantum state, the square of the paper's quantum fidelity is $F^2=⟨\psi |{\rho }_2|\psi ⟩$. ThereforeWith $|\psi ⟩=\cos (\theta /2)|0⟩+e^{i\varphi }\sin (\theta /2)|1⟩$, the expectation is $⟨X⟩=\sin \theta \cos \varphi$, the $x$ component of the Bloch vector. Hence“All possible quantum states” is interpreted as the rotationally invariant uniform pure-qubit average, with measure $d\mu =\sin \theta d\theta d\varphi /(4\pi )$. Thusso the average pure-qubit fidelity of a bit-flip channel isEquivalently, rotational symmetry gives $⟨r_x^2⟩=⟨r_y^2⟩=⟨r_z^2⟩=1/3$, since a pure-state Bloch vector has unit length. The $X$ eigenstates are unchanged as density matrices and have fidelity one, while a computational basis quantum state has $F^2=1-p$; these provide checks on the angular expression. A uniform distribution in $\theta$ rather than in solid angle would produce the wrong ensemble average. The requested quantity is the mean squared fidelity, not the square of the mean unsquared fidelity.