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

Write $C_U=|0⟩⟨0|\otimes I+|1⟩⟨1|\otimes U$ for the controlled unitary gate. For a normalized eigenvector $|u⟩$, the first Hadamard gate and quantum phase kickback giveThe final Hadamard gate therefore produces the unentangled outputThe auxiliary system is unchanged, while its eigenphase becomes accessible through interference of the control qubit. The special unitary group assumption is not needed for this calculation; unitarity and the normalized eigenvector suffice.

Apply the Born rule to the two amplitudes in the introductory calculation. In the computational basis, the probabilities areThe other basis printed in this question is $(|0⟩\pm i|1⟩)/\sqrt{2}$, the Pauli Y gate eigenbasis. It is not the real Hadamard basis. Write the output amplitudes as $a=(1+e^{i\varphi })/2$ and $b=(1-e^{i\varphi })/2$. The plus-outcome amplitude is $(a-ib)/\sqrt{2}$ and the minus-outcome amplitude is $(a+ib)/\sqrt{2}$. Since $\mathrm{Im}(\overline{a}b)=-\sin \varphi /2$, the Born rule givesIn particular, at $\varphi =\pi /2$ the output is the minus eigenstate, which checks the sign of the imaginary quadrature.

Use separate fresh runs for each measurement basis. If ${\hat{P}}_j$ denotes the empirical outcome frequency, thenThe two differences estimate $\cos \varphi$ and $\sin \varphi$, resolving the ambiguity that would remain from the first basis alone. Each Bernoulli frequency converges by the strong law of large numbers, with standard error of order the inverse square root of the number of runs. One may project the noisy estimate onto the unit circle if a phase estimate is desired, but that projection is not necessary for consistency.

The mixed-state expression in the PDF contains a mismatched bra in its second term. A probability mixture of the stated orthonormal eigenvectors must be interpreted as $\rho ={\sum }_k{p}_k|u_k⟩⟨u_k|$. Taken literally with a different bra, it need not be Hermitian or positive and is not generally a density operator.

Let $m={\sum }_k{p}_k{e}^{i{\varphi }_k}=\mathrm{Tr}(\rho U)$. A quantum channel and its measurement probabilities are linear in the density operator, so averaging the pure-state results givesTherefore the same frequency estimator yieldsMore generally, after the controlled operation and before the final Hadamard gate, the reduced control density operator isThis follows by a partial trace of the control blocks $\rho$, $\rho U^{†}$, $U\rho$ and $U\rho U^{†}$. It proves the mixed-state Hadamard-test quadratures for any auxiliary density operator, even one not diagonal in the eigenbasis. Conjugation by the final Hadamard gate maps $X$ to $Z$ and $Y$ to $-Y$, explaining the imaginary-part sign.

Prepare the auxiliary system in the maximally mixed state $\rho =I/N$. Then $\mathrm{Tr}(\rho U)=\mathrm{Tr}U/N$, so the two measurement bases giveThere is no need to know the eigenvectors of $U$. Choose a uniformly random member of any known orthonormal basis on each run; discarding the classical preparation label produces $I/N$. Alternatively, discard one half of a maximally entangled pair of $N$-level systems. This is trace estimation by a maximally mixed Hadamard test.

The circuit directly estimates the normalized trace. To demand fixed absolute accuracy $\epsilon$ in the unnormalized trace requires normalized accuracy $\epsilon /N$; straightforward independent frequency sampling consequently uses order $N^2/{\epsilon }^2$ runs at fixed confidence. Thus the construction should not be confused with a dimension-independent guarantee for arbitrary absolute trace precision.

Apply one Hadamard gate independently to each qubit. These gates act in parallel, so the quantum circuit implements $H^{\otimes n}$ with $n$ gates and depth one.

For a computational basis state, factorization givesThe exponent is the dot product over the finite field ${\mathbb{F}}_2$, because multiplying the separate signs adds their exponents modulo two. This is the Walsh-Hadamard transform, equivalently the quantum Fourier transform on the finite Abelian group $({\mathbb{Z}}_2{)}^n$.

In particular, the all-zero input becomes the uniform coherent superposition $2^{-n/2}{\sum }_y|y⟩$. It is a useful initial operation because an oracle can then act on all amplitudes in one call, and subsequent interference can reveal a global property. Measurement alone does not read all function values: the later interference step is what turns the preparation into an algorithmic advantage.

The first Hadamard transform prepares a uniform superposition in the first register while the second stays zero. The Boolean quantum oracle, now with an $n$-bit output register and bitwise addition, therefore givesThis state is normalized because distinct $x$ labels are orthogonal, even when their oracle outputs coincide. Addition in the oracle is bitwise exclusive-or, making the oracle reversible; replacing the first register by $f(x)$ would not define a unitary gate for a two-to-one function.

For the later recovery steps we use the intended nonzero hidden-period promise $s\ne 0$. Then two-to-one behavior and $f(x+s)=f(x)$ force each fibre to be exactly $\{x,x+s\}$. The printed allowance $s\in \{0,1{\}}^n$ does not explicitly exclude zero. If zero were allowed without a nonzero-period promise, the displayed identity would hold trivially for every function and would not specify Simon's problem. That distinction is addressed again in the query count.

Only strings $k$ in the image of $f$ can be observed. Choose one preimage $x_k$ of an observed string. Under the nonzero-period promise its two preimages are $x_k$ and $x_k+s$. The Born rule gives probability $2/2^n$ to this second-register outcome, and conditional normalization leaves the first-register coset stateThe relative plus sign is retained: measuring the output register reveals which fibre was sampled but does not reveal which member of the fibre was present. Measuring its bits successively gives the same projection onto the observed full string as measuring the whole register at once.

Apply the Hadamard transform to the conditional coset state. The amplitude of a first-register output $z$ isWhen $s\cdot z=1$ over ${\mathbb{F}}_2$, the two terms cancel exactly. When $s\cdot z=0$, their squared modulus is $2^{-(n-1)}$. ThusThere are $2^{n-1}$ orthogonal outputs, so these probabilities sum to one. The distribution is independent of the particular observed fibre. It is the Single-sample distribution in Simon's algorithm: each run gives a uniform random equation restricting the hidden period to the orthogonal complement over the binary field.

Each independent run uses one oracle call and gives a uniformly sampled equation $z\cdot s=0$. Collect $n-1$ linearly independent equations and use Gaussian elimination over ${\mathbb{F}}_2$. Their solution space has dimension one and consists of $\{0,s\}$, so the promised nonzero solution identifies $s$ uniquely.

To quantify the expected query count for Simon sampling, write $d=n-1$. If the existing equations have rank $k<d$, their span contains $2^k$ of the $2^d$ possible samples. A fresh equation raises the rank with probability $1-2^{k-d}$. The mean waiting time is the corresponding geometric distribution mean, givingThe last sum is less than $2$: its first term is $1$ and its remaining terms are bounded by ${\sum }_{j=2}^{\infty }{2}^{1-j}=1$. Hence the expected number of quantum queries is $O(n)$. For a fixed high-confidence budget, use $m=d+c$ samples. Failure to span means that a nonzero linear functional on the $d$-dimensional sampling space annihilates every sample. Each such functional has probability $2^{-m}$, so the union bound gives failure probability at most $(2^d-1)2^{-m}<2^{-c}$. Thus $O(n+\log (1/\delta ))$ queries suffice for failure probability at most $\delta$. For $n=1$, the nonzero string is known already and no samples are needed.

Classically, a collision between distinct queried arguments immediately yields $s=x+y$. Random queries produce this collision after order $2^{n/2}$ calls, by the birthday problem. Conversely, choose the nonzero period uniformly and label the fibres randomly. Before a collision, $q$ queries can exclude at most $\left(\genfrac{}{}{0ex}{}{q}{2}\right)$ periods, their pairwise argument differences; every remaining period has the same no-collision transcript distribution. When $q=o(2^{n/2})$, those exclusions occupy a vanishing fraction of the candidate periods, and neither collision discovery nor guessing a remaining period has a constant success probability. More quantitatively, conditioned on no previous collision, the next query tests at most $q$ of at least $2^n-1-\left(\genfrac{}{}{0ex}{}{q}{2}\right)$ remaining periods; summing these conditional probabilities proves the same square-root lower bound. Therefore the optimal bounded-error classical query count is $\Theta (2^{n/2})$, exponentially larger in $n$ than the quantum count.

This comparison presumes a hidden nonzero period. Under a literal interpretation asking merely for some $s$ satisfying the printed identity, returning $s=0$ requires no queries at all, quantum or classical. Nonzero $s$ is the necessary intended promise, not a consequence of two-to-one behavior alone.

Let $c=⟨R_0|R_1⟩$. The joint state after the environment interaction is $\alpha |0⟩|R_0⟩+\beta |1⟩|R_1⟩$. Taking its partial trace over the environment gives the exact reduced density operatorThe conjugate in the upper off-diagonal entry follows from tracing $|R_0⟩⟨R_1|$. Normalization of the environment states and the Cauchy-Schwarz inequality imply $|c|\le 1$.

For comparison, a phase-flip channel sends $\rho$ to $(1-p)\rho +pZ\rho Z$, multiplying its off-diagonal entries by the real number $1-2p$. Consequently the claimed representation is valid, for a general input, provided the environment overlap is real, withThis is a genuine probability between zero and one. The environment maps printed in the question do not themselves imply that $c$ is real. For example, choose $|R_1⟩=i|R_0⟩$, so $c=i$, and take $\alpha =\beta =1/\sqrt{2}$. The qubit becomes $(|0⟩+i|1⟩)/\sqrt{2}$, whose imaginary off-diagonal entries cannot come from any probabilistic mixture of $\rho$ and $Z\rho Z$. These environment maps are a valid isometry and can be extended to a unitary interaction, so this is an actual counterexample to the unrestricted premise.

The general complex environment overlap in qubit dephasing has an exact corrected description. Write $c=r{e}^{i\phi }$, $0\le r\le 1$, and let $D_{\phi }=\mathrm{diag}(1,e^{i\phi })$. ThenAt $r=0$, choose any phase. The dephasing channel includes both random phase errors and, when the overlap is complex, a coherent diagonal rotation. The subsequent probability formulas use the intended real-overlap phase-flip model.

Subtract the two density operators. The difference is Hermitian with zero diagonal and off-diagonal entry $\alpha \overline{\beta }(1-\overline{c})$. A matrix $\left(\begin{array}{cc}0& a\\ \overline{a}& 0\end{array}\right)$ has eigenvalues $\pm |a|$, because its square is $|a{|}^{2}I$. Its two singular values are therefore both $|a|$. By the definition of the trace norm,For the intended real-overlap phase-flip channel, $1-c=2p$, givingThis vanishes for a computational basis state, since a phase flip then changes only an unobservable global phase. Its largest value at fixed $p$ is $p$, attained when $|\alpha |=|\beta |=1/\sqrt{2}$. The general formula remains correct even when the probabilistic premise of part 1 fails.

Assume the three physical phase-flip channels act independently, with the same probability $p$ on each qubit, and encoding, recovery and decoding are ideal. Zero or one physical error is corrected. HenceThe probability of an uncorrectable two- or three-site error is $p_L=3p^2(1-p)+p^3=3p^2-2p^3$.

One must also choose the logical convention consistently with the output phase error specified here. The usual phase-flip repetition code with codewords $|+++⟩$ and $|---⟩$ has residual operator $Z_1{Z}_2{Z}_3$ after two or three physical errors: their error syndrome equals that of the complementary zero- or one-error pattern. This operator exchanges those codewords, so plain inverse encoding would give logical $X$, not $Z$.

To obtain the stated logical phase-flip convention, use the logical Hadamard convention for a phase-flip repetition code. Put a logical Hadamard gate before that encoding and after its decoding. The encoded state iswhere the plus and minus states in these codewords are the real Hadamard basis states. The uncorrectable exchange is now conjugated to $HXH=Z$. With that convention the decoded density operator and its trace distance are exactlyFor $0<p<1/2$, $p-p_L=p(1-p)(1-2p)>0$, so coding reduces the trace distance. The displayed recovery probability means success of correction as a quantum operation on an arbitrary unknown input. If the particular input is a $Z$ eigenstate, even the logical phase-error branch represents the same physical state, and the probability of recovering that particular state is one.

Independence is an extra noise assumption needed for the numerical probability. If all three physical qubits flip together with probability $p$, each marginal still has the given phase-flip channel, but the logical failure probability is $p$, not $3p^2-2p^3$. More generally, for a classical joint phase-error distribution with a random number $K$ of flips, $P_{\mathrm{rec}}=\mathrm{Pr}(K\le 1)$ and $p_L=\mathrm{Pr}(K\ge 2)$; the same decoded mixture holds in the stated logical convention. Thus marginal error probabilities alone do not determine the requested recovery probability. A complex environment overlap likewise requires the coherent rotation to be retained or separately compensated before this stochastic phase-error analysis applies.

For independent attempts, measuring after each application of $A$ produces a success with probability $p$. Recognize the answer with the verifier and restart on failure. The number $T$ of attempts has a geometric distribution, with $\mathrm{Pr}(T=k)=(1-p{)}^{k-1}p$. Summing the tail probabilities givesThis counts applications of $A$; it presumes $p>0$ and a fresh preparation for each attempt. If $p=0$, neither repetition nor the amplification construction can create a good component from this input.

Let ${\Pi }_g$ project onto the good-output subspace and let $|g⟩=|{\Psi }_g⟩$, $|b⟩=|{\Psi }_b⟩$. They are orthonormal because their supporting computational basis strings are disjoint. The verification unitary operator is $V=I-2{\Pi }_g$, so $V|g⟩=-|g⟩$ and $V|b⟩=|b⟩$.

Also $V_0=I-2|0⟩⟨0|$. Since $A|0⟩=|\Psi ⟩$, conjugating gives $A{V}_0{A}^{†}=I-2|\Psi ⟩⟨\Psi |$. ThusBoth reflections preserve the span of $|g⟩$ and $|b⟩$: $V$ is diagonal there, and the other reflection only adds a multiple of $|\Psi ⟩$, already in that span. Direct substitution of $|\Psi ⟩=\sqrt{p}|g⟩+\sqrt{1-p}|b⟩$ yieldsThe minus sign in the first image follows from applying $V$ before the state reflection. In the ordered basis $(|b⟩,|g⟩)$ the matrix isThis exhibits the invariant plane without assumptions about the action of $A$ on the other input basis vectors.

Choose $0<\theta <\pi /2$ with $\sin \theta =\sqrt{p}$. Then $1-2p=\cos 2\theta$ and $2\sqrt{p(1-p)}=\sin 2\theta$. The matrix found in part 2 is a rotation by $2\theta$ in the ordered good-bad plane, with the bad coordinate listed first. The initial coordinate vector is $(\cos \theta ,\sin \theta {)}^T$.

After $r$ rotations its angle from the bad axis is $(2r+1)\theta$. Equivalently, multiplication of the displayed matrix and the addition formulas for sine and cosine prove the assertion by induction from $r=0$. HenceThe Born rule therefore gives good-output probability ${\sin }^2((2r+1)\theta )$. This is the geometric mechanism of amplitude amplification: each coherent iteration rotates the already existing good amplitude toward the good axis.

For known $p$, use nearest-integer stopping for amplitude amplification. SetWriting $x=\pi /(4\theta )$, the difference between $r+1/2$ and $x$ has absolute value at most $1/2$. Thus $|(2r+1)\theta -\pi /2|\le \theta$. The Born rule and part 3 giveCount the initial $A$ once and the $A^{†}$ and $A$ occurring inside each of the $r$ amplification iterates. The number of applications of either preparation unitary is thereforeThe counts separately are $r+1$ applications of $A$ and $r$ applications of $A^{†}$, in addition to $r$ applications each of $V$ and $V_0$. This is a quadratic improvement over the $1/p$ mean number of unamplified trials. At an exact rounding tie either nearest iterate meets the probability bound. Knowledge of $p$ is used in selecting the stopping time; repeatedly applying $Q$ without a suitable stopping rule can rotate the state past the good axis and reduce success again. The fact that answers lie in NP supplies verification, but by itself gives no claim that $1/\sqrt{p}$ is polynomial in input length.