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

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.

Denote the normalized initial field by $|F⟩$, and its shifted packets byHere the photon-number kets are orthogonal Fock states. Counting shared number labels givesAfter the interaction, linearity gives the joint stateTake the partial trace over the field. Put $d=|\alpha {|}^2-|\beta {|}^2$ and $c=\alpha {\beta }^{\ast }+{\alpha }^{\ast }\beta$. In the ordered qubit basis $(|0⟩,|1⟩)$, the reduced density matrix isFor example, its upper off-diagonal entry is half the overlap of the field accompanying $|1⟩$ with the field accompanying $|0⟩$, fixing the conjugation order. The trace is one, and positivity follows because this is the partial trace of a normalized pure state. For $k\ge 2$, $s_k=1-2/k$; at $k=1$ it is zero, not the continuation $-1$. This is the photon-number reference for a Hadamard gate channel, not an actual coherent-state packet.

The desired output is $|{\psi }_d⟩=((\alpha +\beta )|0⟩+(\alpha -\beta )|1⟩)/\sqrt{2}$. To evaluate its squared quantum fidelity, write the input Bloch vector as $(x,y,z)$, with $x=c$, $y=2\mathrm{Im}({\alpha }^{\ast }\beta )$ and $z=d$. The desired vector after the Hadamard is $(z,-y,x)$. From part (a), the actual vector isFor $k\ge 2$ this simplifies to $(1-1/k)(z,-y,x)-(x/k,0,0)$. The pure state overlap is one half of one plus the dot product with the desired unit vector, soSince $x^2+y^2+z^2=1$, $|xz|\le 1/2$. Therefore the infidelity is uniformly bounded by $3/(4k)$, and the entanglement effect on the implemented gate is negligible for large $k$, uniformly over all initial pure states. The shifted field packets then have overlaps tending to one, so they retain negligible information about the qubit transitions. A large fixed photon number without this broad number coherence would not suffice.

The printed overlap silently requires $k\ge 2$. If the allowed packet has $k=1$, the exact result instead isFor instance, $\alpha =\cos (\pi /8)$ and $\beta =\sin (\pi /8)$ give actual overlap $3/8$, whereas substituting $k=1$ into the printed expression gives $1/4$. This boundary correction follows directly from the two-shift overlap above.

Use the rotation-invariant distribution over pure initial states, namely the uniform pure-qubit average with area element $\sin \theta d\theta d\phi /(4\pi )$. Reflection symmetry gives $\mathbb{E}[xz]=0$, and rotational symmetry together with $x^2+y^2+z^2=1$ gives $\mathbb{E}[y^2]=1/3$. Averaging the squared quantum fidelity from part (b) therefore yieldsIf the single-number packet $k=1$ is included, its corrected average isUniform polar angle without the sine weight would not be the Haar-uniform average over all pure qubit states.

For a pure qubit $a|0⟩+b|1⟩$, the Bloch vector is $(2\mathrm{Re}(a^{\ast }b),2\mathrm{Im}(a^{\ast }b),|a{|}^2-|b{|}^2)$. Substitution givesBoth lie on the unit Bloch sphere, at the same azimuth and opposite heights. They are reflections across its equatorial plane, not antipodal vectors. Choose $\theta =\pi /3$ and $\phi =\pi /4$, so their coordinates are $(\sqrt{6}/4,\sqrt{6}/4,\pm 1/2)$. The following original sketch shows those vectors and their common meridian:

Represent the pure states by density matrices ${\rho }_u=(I+u\cdot \sigma )/2$ and ${\rho }_v=(I+v\cdot \sigma )/2$. The Pauli matrices obey $\mathrm{Tr}{\sigma }_i=0$ and $\mathrm{Tr}({\sigma }_i{\sigma }_j)=2{\delta }_{ij}$. ConsequentlyOn the other hand, ${\rho }_u=|u⟩⟨u|$ and ${\rho }_v=|v⟩⟨v|$ make that trace equal to $⟨u|v⟩⟨v|u⟩$. Thus the pure-qubit overlap identity isFor mixed states the trace formula still holds, but its left side is then a Hilbert–Schmidt overlap rather than this squared pure-state overlap.

Under the prescribed computational-basis measurement and decision rule, the first state is correctly declared when outcome zero occurs, with probability ${\cos }^2(\theta /2)$. The second is correctly declared on outcome one, with the same probability. Averaging the two equal priors givesOne can also verify optimality directly: the two density matrices differ by $\cos \theta {\sigma }_z$. Since $\cos \theta >0$, choosing the positive eigenspace as the decision for the first state maximizes the trace contribution to success. This is the equal-prior discrimination of qubit states construction along the vertical axis.

Continue with equal prior probabilities as in part (c). The two Bloch vectors areTheir density-matrix difference is $\Delta =\sin \theta \cos \phi {\sigma }_x$. If a binary measurement effect $E$ declares the first state, its success isDiagonalize $\Delta$. Because $0\le E\le I$, the trace is maximized by taking $E$ to be its positive-eigenvalue projector. Thus perform a Pauli measurement of ${\sigma }_x$, equivalently measure in $(|0⟩\pm |1⟩)/\sqrt{2}$. If $\cos \phi >0$, identify the first state on the positive outcome and the second on the negative; reverse the labels if $\cos \phi <0$. The optimum isFor $\cos \phi =0$ the states coincide, so the best probability is $1/2$. This explicit positive-eigenspace optimization proves the Helstrom measurement for two pure states result in the present case, rather than only quoting its name.

Use the optimal three-to-one qubit random access code. For Alice's bits $(b_1,b_2,b_3)$, put $s_j=(-1{)}^{b_j}$ and send the pure state with Bloch vectorThese are the eight vertices of a cube inscribed in the Bloch sphere. If an explicit ket is wanted, choose $\cos {\theta }_b=s_3/\sqrt{3}$ and $e^{i{\phi }_b}=(s_1+i{s}_2)/\sqrt{2}$, and prepare $\cos ({\theta }_b/2)|0⟩+e^{i{\phi }_b}\sin ({\theta }_b/2)|1⟩$.

Bob wanting bit $j$ performs a Pauli measurement of ${\sigma }_x,{\sigma }_y,{\sigma }_z$ respectively, reporting zero for eigenvalue $+1$ and one for $-1$. Its success for every input and every requested bit isOnly one chosen bit is extracted; the protocol does not recover all three simultaneously and uses no shared entanglement.

To prove that no one-qubit protocol gives a greater guaranteed probability, allow Alice arbitrary mixed encoding vectors $|r_b|\le 1$ and Bob any binary positive operator-valued measure. Write his decision difference as $D_j=E_{j,0}-E_{j,1}=t_{j}I+v_j\cdot \sigma$. Its eigenvalues lie in $[-1,1]$, implying $|v_j|\le 1-|t_j|\le 1$. On input $b$, success for bit $j$ is $[1+s_j(t_j+v_j\cdot r_b)]/2$. Average over all eight strings and three choices. The terms in $t_j$ cancel, leavingThe Cauchy-Schwarz inequality and cancellation of cross terms over all sign choices giveHence $p_{\mathrm{avg}}\le p_{\ast }$. Any worst-case guarantee is no greater than this average; the cube protocol attains it uniformly, proving optimality both for guaranteed success and for the uniform-input average. Biased prior information about the bits would define a different optimization problem.

The best classical strategy avoids previously failed inputs: inspect a uniformly random permutation. Assume $1\le m\le N$ and let $K$ be the first marked position. For $K=k$, the first $k-1$ guesses must all fail and the next must succeed. ThusThe empty product covers $k=1$. The binomial form follows by choosing the $m$ marked positions uniformly: put one at $k$ and the remaining $m-1$ after it. This is the first marked item in a random permutation distribution.

The requested range is part of its support, but omits the last possible value $k=N-m+1$. All $N-m$ bad inputs can be encountered first, after which success is certain. The same formula includes that nonzero terminal probability; summing through this last value gives one. If $m=0$, the search never succeeds. If sampling were instead with replacement, its inferior repeated-guess strategy would have the geometric law $(1-m/N{)}^{k-1}m/N$ with no such finite endpoint.

With one marked input, after $r$ distinct failed guesses it is uniformly distributed among the $N-r$ untested inputs. Therefore the conditional chance of success on the next guess is $1/(N-r)$. One further failure raises it byor by a multiplicative factor $(N-r)/(N-r-1)$. There is a different unconditional statement: the marked position is uniform, so $\mathbb{P}(K=k)=1/N$ and $\mathbb{P}(K\le k)=k/N$. Thus each additional distinct guess increases cumulative success by $1/N$, even though the conditional next-guess probability increases after each failure. These distinguish the two possible meanings of a probability boost.

At this stage $A$ is an arbitrary unitary operator; do not yet assume it prepares the displayed uniform state from zero. Put $|a⟩=A|0⟩$, $p=e^{i\varphi }$ and $t=e^{i\theta }$. The phase on the zero basis state can be written using a rank-one orthogonal projection as $S_0^{\varphi }=I+(p-1)|0⟩⟨0|$, henceThe marked-state phase sends $|{\psi }_1⟩$ to $t|{\psi }_1⟩$ and leaves $|{\psi }_0⟩$ unchanged. ThereforeandThis is the complete general action. Unless $|a⟩$ lies in their span, that two-dimensional space need not be invariant. The PDF uses $S_f^{\theta }$ in $Q$; the TeX conversion's replacement by $S_0^{\theta }$ is a transcription error and would describe a different operation.

Now $|a⟩=|\psi ⟩$. Suppose $0<m<N$, and normalize the orthogonal good and bad components:Their disjoint computational supports make $(|g⟩,|b⟩)$ an orthonormal basis. For $s=\sin \chi ,c=\cos \chi$, the two-dimensional matrix for phase amplitude amplification isTo obtain its first column, the marked phase first multiplies $|g⟩$ by $t$, then $I+(p-1)|\psi ⟩⟨\psi |$ adds its projection onto $|\psi ⟩$; the second column is obtained similarly without $t$. This also proves unitarity: the rank-one phase has eigenvalues $p,1$ on this plane, and the marked phase has eigenvalues $t,1$, all of unit modulus. Their negative product is unitary for any real phases.

Using the unnormalized pair $(|{\psi }_1⟩,|{\psi }_0⟩)$ instead would produce a differently scaled matrix, which is not in general unitary in the ordinary Euclidean metric. At $m=0$ or $m=N$ one component vanishes and the relevant search space is one-dimensional.

For $p=t=-1$, the preceding matrix becomesMultiplying it by $(\sin \chi ,\cos \chi {)}^T$ gives $(\sin 3\chi ,\cos 3\chi {)}^T$. The sine and cosine addition identities then prove by induction thatFor $0<\chi \le \pi /4$, the first angle reaching the interval $[\pi /4,3\pi /4]$ gives success at least one half. Its smallest integer iteration count isThe ceiling advances the angle by less than $2\chi$, so the chosen angle remains in that success interval. This is the first half-success time in Grover search. If near-certain rather than half success is desired, choose the nearest integer to $\pi /(4\chi )-1/2$; its success is at least ${\cos }^2\chi$ and the count is asymptotic to $(\pi /4)\sqrt{N/m}$. Both exhibit the quadratic query improvement of amplitude amplification. Success oscillates, so further iterations past the first maximum are not automatically beneficial. The count presumes positive known $m$ (or known $\chi$); if no marked item exists, no number of iterations can produce one.