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

Take the Hadamard gate to be $H=2^{-1/2}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$ and the phase gate to be $P(\varphi )=\mathrm{diag}(1,e^{i\varphi })$. This fixes the sign convention for the interference phase.

For the coherent quantum circuit, the successive quantum states areThe Born rule therefore gives the concise answer

With the stated quantum decoherence after the phase gate, the joint pure state before the last Hadamard gate isAfter that Hadamard gate, its environment coefficient at output zero is $(|e_0⟩+e^{i\varphi }|e_1⟩)/2$. Squaring its norm sums over every unobserved environment outcome, soThe Cauchy-Schwarz inequality gives $0\le v\le 1$. In this single-qubit interference with conditional environment states, $v$ is the interference visibility: orthogonal environment states erase the fringe, while a unit-modulus overlap shifts its phase without reducing visibility. The plus sign in $\varphi +\alpha$ follows from the specified overlap $⟨e_0|e_1⟩$, rather than its complex conjugate.

If the same quantum decoherence occurs before the phase gate, the joint pure state is first $(|0⟩|e_0⟩+|1⟩|e_1⟩)/\sqrt{2}$. The phase gate then produces exactly the same state used above. Equivalently, the controlled environment interaction commutes with the diagonal phase gate. The probability is unchanged.

For the Deutsch algorithm, use the reversible Boolean quantum oracleThe algebraic oracle map printed in the source has its arguments misplaced: taken literally, it sends two distinct answer inputs to the same output for constant $f$, so it cannot be a unitary operator. The corrected map above agrees with the diagram's input-control, answer-target arrangement. Put the answer qubit in $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$. Since the Pauli X gate satisfies $X|-⟩=-|-⟩$, quantum phase kickback givesWrite $b=f(0)\oplus f(1)$. Up to the irrelevant global phase $(-1{)}^{f(0)}$, the input qubit acquires relative phase $(-1{)}^b$, so its ideal final computational-basis measurement returns $b$: zero for a constant function and one for a balanced function.

Let the specified quantum decoherence occur in the interference portion between the two Hadamard gates. It commutes with the oracle's effective diagonal phase on the input, so the same analysis applies whether it occurs just before or just after the query. The two likelihoods areThus the diagram's usual zero-for-constant decision rule hasThis is the reliability for either promised class separately, with no prior needed. For equally likely classes, if $v\cos \alpha$ is known to be negative, reversing the interpretation gives $(1+|v\cos \alpha |)/2$. A known environment phase can instead be compensated by the phase gate $P(-\alpha )$ before the final Hadamard gate, giving success probability $(1+v)/2$. In particular, $v=0$ gives no information and $v=1$ permits certainty after phase compensation. These refinements distinguish a shifted fringe from lost quantum coherence; with the unmodified diagram a phase shift alone can reverse the apparent answer. Quantum decoherence after the final Hadamard gate leaves its computational populations unchanged, so that different placement would not spoil the measured answer.

The Walsh-Hadamard transform is the tensor product of one Hadamard gate on each qubit. Indeed,The network therefore consists of $n$ parallel Hadamard gates, with no interaction between wires. Applied to an all-zero quantum register, it produces the uniform quantum superposition of all $2^n$ input strings. This lets a Boolean quantum oracle act coherently on all those inputs; a subsequent operation can turn their relative phases into useful interference. It does not permit reading all oracle values from a single measurement in quantum mechanics.

For the supplied linear-phase input, the amplitude on output $y$ isEach factor is obtained by summing over the independent bit $x_j$. This directly proves the relevant orthogonality of the binary Fourier phases, and yields the output state $|a⟩$ exactly.

For exact classical identification, query the Boolean function at the $n$ standard unit vectors: $f(e_j)=a_j$. Hence $n$ oracle calls suffice. They are also necessary in the worst case, even with adaptive queries: every answer supplies one binary linear equation in the unknown string. With fewer than $n$ queries, their coefficient matrix has matrix rank at most the number of queries, so its null space contains a nonzero string $h$. The strings $a$ and $a\oplus h$ give identical answers along that adaptive transcript and cannot both be identified correctly. Equivalently, a depth-$t$ binary decision tree has at most $2^t$ leaves and must distinguish $2^n$ possibilities. Thus the exact classical query count is $n$. This concerns exact recovery, rather than allowing an arbitrary error probability.

The quantum network in the lower panel starts its data quantum register in $|0{⟩}^{\otimes n}$ and its answer ancilla qubit in $|-⟩$, which can be prepared as $H|1⟩$. Apply Hadamard gates to the data wires, make one Boolean quantum oracle call, then apply Hadamard gates again to all data wires. Quantum phase kickback producesA computational-basis measurement of the data wires gives all bits of $a$ with certainty. This is Bernstein-Vazirani phase kickback: one quantum query, $2n$ data Hadamard gates, and one answer-state preparation suffice. The answer ancilla qubit stays separate from the data at the output.

Use the Hilbert-Schmidt inner product normalized by the dimension: $(A,B)=\frac{1}{2}\mathrm{Tr}(A^{†}B)$. The identity and the three Pauli matrices are Hermitian, each has square $I$, and each nonidentity Pauli matrix has zero trace. For distinct nonidentity indices, the Pauli matrix multiplication law gives ${\sigma }_j{\sigma }_k=i{\sum }_l{\epsilon }_{jkl}{\sigma }_l$, which is traceless. ThereforeThere are four such orthonormal operators, and the complex vector space of two-by-two matrices has dimension four. Hence they form an orthonormal basis. Taking the inner product of any $E$ with each basis element proves, for arbitrary complex $E$ and not just Hermitian ones,For example, if $E=\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)$, its four coefficients are $(a+d)/2$, $(b+c)/2$, $i(b-c)/2$, and $(a-d)/2$, respectively.

For the joint error, regard the two prescribed basis outputs as the columns of an environment-valued linear map. Its coefficient array in the usual output-row, input-column convention isThe source's other array is arranged as a column of the images of basis kets; it must not be mistaken for this coefficient array acting on an amplitude column. Applying the just-proved Pauli matrix expansion componentwise in any environment orthonormal basis gives the Pauli decomposition of a qubit-environment isometry:To check the potentially delicate sign of the Pauli Y gate coefficient, use $Y|0⟩=i|1⟩$ and $Y|1⟩=-i|0⟩$. The four terms then giveLinearity proves the expansion for every input pure state. The environment coefficient vectors need not be normalized or mutually orthogonal. Consequently this expansion includes coherent combinations of Pauli errors, rather than asserting that every quantum channel is a probabilistic Pauli channel.

For the recovery probability, use the usual independent-use interpretation of the given phase-flip channel: each of the three transmitted qubits has a Pauli Z gate error independently with probability $q$. The phase-flip repetition code uses logical codewords $|+++⟩$ and $|---⟩$. The decoding Hadamard gates convert physical phase flips to bit flips because $HZH=X$. We can then analyze the two decoding controlled-NOT gates and the final Toffoli gate directly, rather than assuming a recovery rule.

Let $b_1,b_2,b_3$ be the error bits after this basis conversion. For a logical basis input $t\in \{0,1\}$, the three data bits before inverse encoding are $t\oplus b_1,t\oplus b_2,t\oplus b_3$. The two controlled-NOT gates produceThe Toffoli gate flips the first wire when both of the last two bits are one. Its residual error isThe last two wires carry an error syndrome independent of $t$. Thus this transformation preserves the amplitudes of an arbitrary superposition: zero or one phase error returns the original unknown qubit, while two or three phase errors leave the logical Pauli X gate applied to it. The probability of universally successful recovery is thereforeEquivalently, the decoded quantum channel is $\rho \mapsto (1-p_L)\rho +p_{L}X\rho X$, with logical failure of the three-qubit phase-flip repetition code $p_L=3q^2-2q^3$. For $0<q<1/2$, the failure probability is below $q$, since $q-p_L=q(1-q)(1-2q)>0$. A special input that is a Pauli X eigenstate is unchanged even by the residual logical error; this does not make the code correct that error on an unknown input. Its squared quantum fidelity with a particular pure input is $1-p_L+p_L|⟨\chi |X|\chi ⟩{|}^2$. If the errors on different channel uses are correlated, the marginal probability $q$ alone is insufficient: the general universal success probability is the probability of at most one error.

Write both the input and output integer labels in most-significant-bit-first order, $x={\sum }_{j=1}^n{x}_j{2}^{n-j}$ and $y={\sum }_{j=1}^n{y}_j{2}^{n-j}$. Factoring the Fourier phase over the bits of $y$ gives the product decomposition of a Fourier phase state:Here $0.x_l\cdots x_n$ denotes the binary fraction ${\sum }_{r=l}^n{x}_r/2^{r-l+1}$; the integer part of $x/2^j$ does not affect the phase.

Build a dyadic quantum Fourier transform circuit as follows. Process wires $j=1,\dots ,n$ in that order. First apply a Hadamard gate to wire $j$. Then, for each $l=j+1,\dots ,n$, apply the controlled phase gate $R_{l-j+1}$ with control wire $l$ and target wire $j$. On a computational-basis state, every unprocessed control is still the bit $x_l$, so wire $j$ becomesOnce a wire has been processed it is not touched by later stages. Reversing the order of the output wires gives exactly the Fourier product above. Agreement on every computational-basis state proves agreement as linear operators on all superpositions, even though the intermediate operation on a general input can create entanglement.

There are $n$ Hadamard gates and $n(n-1)/2$ controlled phase gates. Output reversal may be treated as wire relabelling. If it must instead be implemented physically while using only the requested gate family, use $\lfloor n/2\rfloor$ swap operators. Each swap is three controlled-NOT gates, andThus the swaps use only Hadamard gates and Controlled-Z gates, which are controlled $R_1$ gates. An exact physical network haselementary gates from the stated family. This implements the positive-exponent Fourier transform with the correct output order in quadratic size. Omitting the output reversal without relabelling the wires would produce the reversed-order transform instead.

For the perturbation bound, the operator norm in the source is equivalently $\Vert A\Vert ={\sup }_{\Vert \psi \Vert =1}\Vert A\psi \Vert$. It satisfies the triangle inequality, is unchanged by left or right multiplication by a unitary operator, and a unitary operator has norm one. The exact telescoping identity isIt follows by replacing one factor at a time; alternatively all intermediate products cancel in the sum. Taking the operator norm and using unitary invariance gives the quantum circuit gate-error telescoping boundThe original PDF assumes strict $\Vert U_j-V_j\Vert <ϵ$, so its strict conclusion is justified. If the hypothesis were weakened to a non-strict inequality, the conclusion would likewise be $\le mϵ$. The TeX aid misreads this hypothesis; the PDF resolves it.

Apply the non-strict version to each approximate unitary gate in the Fourier network. Extending a gate by the identity on other wires leaves its operator norm error unchanged. Including the physical swap decompositions, all gates are of the required type and can obey the stated accuracy. HenceWith exact output relabelling rather than physical swaps the numerator is just $n(n+1)/2$. The proof retains gate phases and makes no assumption of cancellation between coherent errors.

For every normalized input the output-state norm error is at most this same bound. If $M$ is any positive operator satisfying $0\le M\le I$, the change in its measurement in quantum mechanics outcome probability is at most $2\delta$, where $\delta =\Vert U_n-{\mathrm{QFT}}_{2^n}\Vert$: expand the difference of the two expectations into two terms, each bounded by $\delta$ using the Cauchy-Schwarz inequality. Thus inverse-polynomial gate accuracy gives an inverse-polynomial total error, rather than requiring exponential precision in the number of qubits. For the phase gates this corresponds to specifying angles with $O(\log n)$ bits of precision, since $|e^{i\theta }-e^{i{\theta }^{\prime }}|\le |\theta -{\theta }^{\prime }|$. This is a robustness statement for unitary gate approximations; it does not by itself correct quantum decoherence, correlated stochastic faults, or limitations of hardware connectivity.