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

Include all fixed resource states and all measurement records in an environment, so the entire physical protocol has an linear isometry $U$ from the unknown input to a larger pure output. If every recipient receives a perfect copy, its reduced density matrix is the pure projector $|\psi ⟩⟨\psi |$. A pure marginal forces factorization: write a joint vector in a basis beginning with $|\psi ⟩$; its squared components along every orthogonal basis vector vanish because their marginal probabilities are zero. Applying this successively to all recipients giveswhere $|R⟩$ is the fixed initial resource and $|E_{\psi }⟩$ may depend on the input. This includes Alice's discarded systems and every possible outcome record.

Choose two distinct nonorthogonal pure states, for example $|0⟩$ and $|+⟩=(|0⟩+|1⟩)/\sqrt{2}$, and write their overlap as $s$. Preservation of the inner product by the linear isometry requiresNormalized environment vectors have overlap of absolute value at most one. Thus $0<|s|<1$ would imply $|s|\le |s{|}^N$, impossible for $N>1$. Hence perfect transmission of a copy to every recipient is impossible for $N>1$. This proves the no-cloning theorem obstruction even though Alice keeps no copy herself.

Write $N=2k+1$ and abbreviate the Dicke states by $|D_j^n⟩=|{\Psi }_j^n⟩$. Alice's shared resource has decompositionFollow the actual circuit order: a controlled-NOT gate from the input to $q_0$, a Hadamard gate on the input and a Pauli X gate on $q_0$, followed by computational basis measurements. Just before measurement, the joint vector isThe Dicke states in each branch are orthogonal, so each branch has squared norm $1/4$. Conditioning on outcome $00$ and normalizing therefore gives the state of the other $N$ parties:This is the encoding used in Dicke-resource telecloning. The extra Pauli X gate on Alice's resource qubit is essential to the displayed ordering of the amplitudes.

The state in part (b) is symmetric in the receiving qubits. Single out Bob using the Dicke state recursion. For $k\ge 1$, the two vectors areDistinct excitation counts give orthogonal states of the other recipients. Taking their partial trace, the only surviving off-diagonal term comes from the common rest vector $|D_k^{N-1}⟩$. The one-qubit reduction of Dicke-state superpositions is consequentlyPut $p=|\alpha {|}^2$ and $q=|\beta {|}^2$, so $p+q=1$. The overlap with the input isFor $N=1$ there is no system to trace out, and the same matrix is $|\psi ⟩⟨\psi |$, with overlap one. For every $N>1$ the overlap is below one, even at its maximum $p=q=1/2$, so these are imperfect copies.

Define $E|0⟩=|D_k^N⟩$ and $E|1⟩=|D_{k+1}^N⟩$. From the branch calculation in part (b), outcome $R_0=0,R_1=1$ leavesThus the effective input teleported was $X|\psi ⟩=\beta |0⟩+\alpha |1⟩$. A Pauli X gate flips every bit and hence maps a Dicke state with $j$ excitations to one with $N-j$ excitations. Since $N-k=k+1$, applying $X$ at every receiving party interchanges the two logical basis states and restores $E|\psi ⟩$. ThereforeIn particular Bob's uncorrected reduced density matrix is $X\rho X$, and his correction returns it to the matrix in part (c). The remaining branches can likewise be corrected: $Z^{\otimes N}$ implements logical $Z$ up to the common global phase $(-1{)}^k$, while $X^{\otimes N}$ implements logical $X$. Thus the outcome dependence can be removed by local Pauli gates even though the resulting copies remain imperfect.

Put $L=2^N$ and define $\theta =\arcsin \sqrt{M/L}$. The normalized good and bad vectors have disjoint computational basis supports, so they are orthogonal. Counting the terms in the uniform quantum superposition givesSince $V_0=I-2|0^N⟩⟨0^N|$, the Hadamard transform gives $-H^{\otimes N}{V}_0{H}^{\otimes N}=2|\varphi ⟩⟨\varphi |-I$, the Grover diffusion operator. On the ordered orthonormal basis $(|{\Psi }_g⟩,|{\Psi }_b⟩)$, the two reflection operators have matricesTheir product isThis is a plane rotation through angle $-2\theta$ in the displayed coordinate convention, with the invariant good-bad plane preserved by both operators. In particular its action sends $(\sin a,\cos a)$ to $(\sin (a+2\theta ),\cos (a+2\theta ))$. Induction therefore gives the Grover rotation angle formula

Measuring the state from part (a) in the computational basis succeeds with probability $p_n={\sin }^2((2n+1)\theta )$. In the sparse-solution regime $0<M\le 2^{N-1}$, one has $0<\theta \le \pi /4$. The first success interval with $p_n\ge 1/2$ is $\pi /4\le (2n+1)\theta \le 3\pi /4$. Entering it requires $n\ge \pi /(8\theta )-1/2$, so the first half-probability Grover iterate isFor this integer, the angle is at least $\pi /4$ and less than $\pi /4+2\theta \le 3\pi /4$, so the rounding cannot skip the required interval. Every smaller nonnegative integer has angle below $\pi /4$ and hence success below $1/2$, proving minimality. For $M\ll 2^N$, the leading size is $n_{\min }\sim (\pi /8)\sqrt{2^N/M}$. If $M\ge 2^{N-1}$, the initial measurement already succeeds with probability at least one half and the smallest count is zero; if $M=0$ no search can succeed.

For the known bit string $y$, define the Pauli gate product $T_y={⨂}_{j=0}^{N-1}{Z}_j^{y_j}$. Its diagonal action is $T_y|x⟩=(-1{)}^{x\cdot y}|x⟩$, where the binary inner product is taken modulo two. The Hadamard transform produces $|{\varphi }_y⟩=H^{\otimes N}|y⟩=T_y|\varphi ⟩$. Thus the required vectors for Grover search with a nonzero reflection label areThey remain orthonormal and $|{\varphi }_y⟩=\sin \theta |{\tilde{\Psi }}_g⟩+\cos \theta |{\tilde{\Psi }}_b⟩$. The new iterate is $G_y=(2|{\varphi }_y⟩⟨{\varphi }_y|-I)U_f$. Since $T_y$ commutes with the diagonal marked-state phase oracle and $T_y^2=I$,Consequently its matrix on the signed basis is exactly the rotation matrix in part (a), proving the claimed equivalence of the two evolutions.

Initialize the register inThis can be prepared by Pauli X gates on the one-bits of $y$, starting from $|0^N⟩$, followed by Hadamard gates on all qubits. Alternatively, prepare the original uniform state and apply Pauli Z gates at those same bit positions. The conjugation calculation givesThe final diagonal sign operator changes no computational basis outcome probabilities. Thus the success probability and the iteration count in part (b) are unchanged. No final correction is needed when the objective is to measure a marked string.

The Pauli matrices obey $X|0⟩=|1⟩$, $X|1⟩=|0⟩$, $Y|0⟩=i|1⟩$, and $Y|1⟩=-i|0⟩$. Thus $X\otimes X$ and $Y\otimes Y$ contribute opposite amplitudes on $|00⟩,|11⟩$ and equal amplitudes on $|01⟩,|10⟩$. For the XY exchange interaction $E=(X\otimes X+Y\otimes Y)/2$,Equivalently $E=|01⟩⟨10|+|10⟩⟨01|$. It transfers an excitation across a link without creating or destroying excitations, so a sum of such links preserves the single-excitation subspace.

In the single-excitation subspace, part (a) turns each coupling into a hopping coefficient between adjacent sites. With $|\tilde{n}⟩$ denoting the excitation at site $N+n$, the two central links giveFor $N\ge 2$ the links from these neighbors to the next sites have strength $J_1$. Applying the Hamiltonian operator a second time yieldsThe central coefficient is $2(J_0/\sqrt{2}{)}^2=J_0^2$. On the comparison path, direct multiplication givesThus the two calculations match under $|0⟩\mapsto |\tilde{0}⟩$ and $|j⟩\mapsto (|\widetilde{-j}⟩+|\tilde{j}⟩)/\sqrt{2}$ for $j=1,2$. If $N=1$, the terms involving $J_1$ and distance two are absent on both sides.

Define orthonormal symmetric vectorsThe symmetric-arm reduction of an exchange Hamiltonian here has two arms. To verify it directly, the link between radial distances $j$ and $j+1$ has strength $J_j$ on either side, while the two central links have strength $J_0/\sqrt{2}$. The calculation of part (a) therefore givesIn particular this subspace is invariant and contains the initial vector. Define the linear isometry $F|j⟩=|s_j⟩$. The displayed matrix entries prove $H_{e}F=F{H}_T$, or $F^{†}{H}_{e}F=H_T$. Induction gives $H_e^{m}F=F{H}_T^m$ for every nonnegative integer $m$; hence the convergent exponential series proves $e^{-i{H}_{e}t}F=F{e}^{-i{H}_{T}t}$. This establishes the mapping for the entire evolution, rather than just its first two powers. The supplied endpoint transfer also forces every $J_j$ to be nonzero, since a broken link would disconnect the two endpoints. Successive powers applied to $|s_0⟩$ then generate all $|s_j⟩$, so this is exactly the cyclic subspace governing the initial state.

Using the stated perfect quantum state transfer identity at time $\pi /2$,The two terms have the excitation at sites $0$ and $2N$, respectively, and all intermediate qubits are zero in both terms. The full state thus factors into a Bell state at the endpoints and the vacuum on the interior. Its partial trace isThe coherent cross terms survive the trace because the interior vectors coincide. We have used the transfer phase convention supplied in the question; a common transfer phase would leave this density operator unchanged.

Replace the two arms by three identical arms of length $N$ attached to one central qubit. Label the hub $c$ and the sites on arm $a$ by $(a,j)$, $a=1,2,3$, $j=1,\dots ,N$. Use XY exchange interactions with coupling $J_0/\sqrt{3}$ on each hub-to-first-site link, and coupling $J_j$ on each arm link $(a,j)$ to $(a,j+1)$. Initially excite only the hub: this is the product state $|1{⟩}_c$ with every arm qubit in $|0⟩$.

In the symmetric single-excitation subspace, define $|s_0⟩=|c⟩$ and $|s_j⟩=3^{-1/2}{\sum }_{a=1}^3|a,j⟩$. The hub coupling isand the reverse coupling has the same coefficient. All other radial links have coefficients $J_j$, just as in part (c). Thus the symmetric-arm reduction of an exchange Hamiltonian is again exactly $H_T$. At time $\pi /2$ its evolution isEvery nontip qubit is zero, so tracing them out leaves the three tips in the pure W stateThe essential change is the additional identical arm and the normalization of each hub coupling by $\sqrt{3}$ instead of $\sqrt{2}$.

Label the control qubits by binary weight: the bit $x_n$ contributes $2^n$ to $x={\sum }_{n=0}^{N-1}{2}^n{x}_n$. For each $n$, use that qubit as the control of the supplied controlled-$V^{2^n}$, with the same target eigenstate $|v_j⟩$. The controlled unitary gate acts bysince $V^{2^n}|v_j⟩=e^{i{2}^n{\varphi }_j}|v_j⟩$. The target remains unchanged after every application. Multiplying these factors givesThe ordering of the tensor factors is chosen to match the binary place values. Discarding the unchanged target leaves the required phase register. This uses quantum phase kickback in the phase accumulation step of quantum phase estimation.

Set $L=2^N$. Applying the inverse quantum Fourier transform to the register in part (a) gives probability amplitude at label $m$ equal toChoose $m$ nearest to $\eta =L{\varphi }_j/(2\pi )$, with $m$ reduced modulo $L$ at the phase boundary. Then the difference can be represented with $|\delta |\le \pi /L$. For $\delta \ne 0$, sum the finite geometric series to obtainLet $z=L|\delta |/2\le \pi /2$. On $[0,\pi /2]$, concavity of sine gives $\sin z\ge 2z/\pi$, the line through its endpoint values. Also $|\sin (\delta /2)|\le |\delta |/2$. Thereforeand the Born rule proves the nearest-integer success bound for quantum phase estimation:If $\delta =0$, every summand is one and the probability is exactly one. If the scaled phase is halfway between two integers, either nearest label separately satisfies the displayed bound. Interpreting the measured integer as $m/L$ gives the closest available $N$-bit phase estimate modulo one.

Choose an orthonormal eigenbasis of $V$, with eigenphases ${\varphi }_0,{\varphi }_1$, counting multiplicity. The maximally mixed state is basis independent, soLinearity means that the experiment is the equal mixture of the two eigenstate experiments. After the inverse quantum Fourier transform, the joint state is $\frac{1}{2}{\sum }_{j=0}^1|{\chi }_j⟩⟨{\chi }_j|\otimes |v_j⟩⟨v_j|$, where $|{\chi }_j⟩={\sum }_m{a}_m({\varphi }_j)|m⟩$ andThus the exact output distribution for quantum phase estimation with a maximally mixed target isFor a nonzero phase mismatch, the squared probability amplitude is ${\sin }^2[L(\varphi -2\pi m/L)/2]/\{L^2{\sin }^2[(\varphi -2\pi m/L)/2]\}$, with value one at an exact match. If both eigenphases are exactly representable on the $L$-point grid, their two labels occur with probability $1/2$ each; coincident labels have their probabilities added. For general eigenphases there can be nonzero probabilities at other labels, so it would not be exact to list only the two best approximations with probability $1/2$ each. Each eigenphase is sampled with spectral weight $1/2$, and its nearest-label event has conditional probability at least $4/{\pi }^2$. In particular a nearest label for one eigenphase has unconditional probability at least $2/{\pi }^2$, with additional contributions possible from the other phase.

With access to the uncontrolled physical gate, use single-qubit process tomography. Prepare the positive eigenstate of each of $X,Y,Z$, apply $V$, and on independent copies measure each of $X,Y,Z$. Arbitrary single-qubit rotation gates let one prepare these inputs and rotate each measurement into the computational basis. The nine measured means areThey determine the real rotation matrix $R$ of the Bloch vector, and hence the action of $V$ on every qubit state. To see precisely what this identifies, suppose another unitary $U$ has the same action. Then $V^{†}U$ commutes with every Pauli matrix. Commuting with $Z$ makes it diagonal; commuting with $X$ makes its diagonal entries equal. Therefore $U=e^{i\gamma }V$.

Consequently tomography determines $V$, and its eigenvalues, up to a common phase. More explicitly, write a representative as $V=e^{i\gamma }(\cos aI-i\sin a\mathbf{n}\cdot \mathbf{\sigma })$. Its eigenvalues are $e^{i(\gamma -a)}$ and $e^{i(\gamma +a)}$, and its Bloch vector action is rotation through $2a$ about $\mathbf{n}$. The measured rotation identifies the unordered relative eigenphase information; for example $\mathrm{Tr}R=1+2\cos (2a)$. Once a representative with a specified overall phase is supplied, diagonalizing that representative gives the corresponding two eigenvalues.

The common phase itself cannot be recovered with the stated uncontrolled access. Indeed, $(e^{i\gamma }V)\rho (e^{i\gamma }V{)}^{†}=V\rho V^{†}$ for every input, including inputs entangled with ancillas. Replacing $V$ by $e^{i\gamma }V$ therefore leaves every such preparation-and-measurement experiment unchanged, whereas it multiplies both eigenvalues by $e^{i\gamma }$. For example, $I$ and $e^{i\gamma }I$ are indistinguishable physical gates under these operations. This proves that the request for absolute eigenvalue phases needs an additional phase reference or controlled-gate assumption: the global phase of an uncontrolled quantum gate is unobservable. The controlled powers in the earlier parts supply that extra resource, since $\mathrm{diag}(I,e^{i\gamma }V)$ changes a relative phase between the two control branches.

The practical advantages are that no unknown eigenstate preparation, controlled powers, entangling gates or inverse quantum Fourier transform are needed: a fixed set of single-qubit preparations and measurements suffices. The disadvantages are statistical estimation and the phase ambiguity just proved. Estimating the bounded Pauli measurement means to additive accuracy $ϵ$ at fixed confidence requires order ${ϵ}^{-2}$ independent repetitions, giving the usual sampling cost for this direct procedure. The earlier quantum phase estimation circuit uses $N$ phase qubits and high controlled powers to resolve scale $2^{-N}$ in one coherent experiment with a constant success bound; constructing those powers from controlled uses of $V$ costs $2^N-1$ gate calls, so its exponential-looking precision is not obtained with only $N$ uses of $V$. Repetitions can raise confidence. Finally, full process tomography grows exponentially with the number of system qubits, whereas the eigenstate-based phase procedure can estimate a selected eigenphase without reconstructing the entire operator.