Past exam of the computer science course of the University of Oxford / 2019 / Quantum information (A16608W1)

Solutions to all three questions of the 15 June 2019 paper. Released Oxford examination archive, member 2018/T/a16608w1.pdf. The dated cover establishes 2019 despite that archive directory. Vectors are columns; the first tensor factor is the first wire; and the rightmost gate in an operator product acts first. Measurements use the printed outcome labels. Global phases are identified physically, with the approximation convention made explicit in Question 3(a). All five source pages and all 27 terminal parts are covered.

A basic measurement is specified by an orthonormal basis $\{|b_j⟩{\}}_{j=0}^{d-1}$, with outcome $j$ associated with the rank-one orthogonal projection $P_j=|b_j⟩⟨b_j|$. For a normalized pure state $|\psi ⟩$, the Born rule givesThe probabilities sum to one because ${\sum }_j{P}_j=I$. Conditional on an outcome with $p(j)>0$, the post-measurement state iswhich represents $|b_j⟩$ up to a global phase. An outcome of zero probability has no conditional state to normalize. For a density matrix $\rho$, the corresponding expressions are $p(j)=\mathrm{Tr}(P_j\rho )$ and $P_j\rho P_j/p(j)$. If the outcome is ignored, the nonselective projective measurement instead produces ${\sum }_j{P}_j\rho P_j$, generally a mixed state.^[ref]

The columns are $i|+⟩$ and $-i|-⟩$. Their norms are one and their inner product is zero, since $|+⟩,|-⟩$ are orthonormal. Thus $M_1$ is a unitary matrix. Equivalently,using the Hadamard gate and Pauli Z gate. The different column phases do not destroy orthonormality.

The Pauli Y gate satisfies $Y^{†}=Y$ and $Y^2=I$. With $c=\cos (\pi /6)=\sqrt{3}/2$ and $s=\sin (\pi /6)=1/2$, the given matrix is Hermitian, andTherefore $M_2$ is not a unitary matrix. Its eigenvalues are $c+s$ and $c-s$, neither of which has modulus one. An expression $\cos \theta I+i\sin \theta Y$ would behave differently, but the printed matrix has no such factor of $i$.

Set $A=U_A\otimes I_B$ and $B=I_A\otimes U_B$. They are self-adjoint operators and satisfy $A^2=B^2=I$, because the original factors are both self-adjoint and unitary. They also commute: each acts on a different tensor factor. HenceThe same calculation in the opposite order gives $M_3{M}_3^{†}=I$. Thus $M_3$ is a unitary matrix for every allowed pair of factors. Commutation cancels the cross terms, while their relative imaginary coefficient supplies the opposite signs. This is the commuting-involution unitary combination.

Let $p=|\alpha {|}^2$ and $1-p=|\beta {|}^2$. The first basic measurement has outcome probabilities $p$ and $1-p$, obtained by conjugating the amplitudes in the bras. Conditional on its first outcome, the next computational-basis measurement returns 0 with probability $p$; conditional on its second outcome, that probability is $1-p$. The law of total probability therefore givesConsequently the minimum is $1/2$, attained exactly when $|\alpha |=|\beta |=1/\sqrt{2}$. The relative complex phases do not affect this result. The alternatives after the first measurement form a classical mixture; their amplitudes must not be added coherently as if no measurement occurred.

Choose $|{\psi }_0⟩=|+⟩$ and its orthogonal companion $|{\psi }_1⟩=|-⟩$. Since $X|+⟩=|+⟩$, either branch of RandomFlip returns the same pure state. Alice therefore obtains label 0 with certainty, andThe alternative choice $|-⟩$ also works: its sign change under $X$ is only a global phase. The useful property is being a Pauli eigenstate of the Pauli X gate.

Use the preparation and measurement from part (i). RandomReset returns the density matrix ${\rho }_R=(|0⟩⟨0|+|1⟩⟨1|)/2=I/2$, a maximally mixed state. In the $|+⟩,|-⟩$ basis its two outcomes each have probability $1/2$. In contrast, RandomFlip always gives outcome 0.

Guess RandomFlip after 0 and RandomReset after 1. With the supplied equal priors,An outcome 1 identifies the reset action, but outcome 0 does not identify the flip action with certainty. For example, Bayes' theorem gives posterior probability $2/3$ for the flip action after 0. The total success rate already accounts for the reset runs that also produce 0.

Prepare the uniform pure stateEvery permutation matrix fixes this vector, so RandomPermute returns $|s⟩$ with certainty. Choose an orthonormal basis with first vector $|{\psi }_0⟩=|s⟩$, for example the quantum Fourier transform basis. Under RandomReset, the returned state is $I/d$, which gives each of the $d$ measurement labels probability $1/d$.

Guess RandomPermute on label 0 and RandomReset on every other label. ThenThis is invariant-pure-state discrimination against a maximally mixed reset. It also agrees with the Holevo–Helstrom theorem: the eigenvalues of $|s⟩⟨s|-I/d$ are $1-1/d$ once and $-1/d$ with multiplicity $d-1$, giving optimal equal-prior success $1/2+\Vert {\rho }_P-{\rho }_R{\Vert }_1/4=1-1/(2d)$. This confirms optimal discrimination of these returned states, in addition to constructing the requested strategy.^[ref] For $d=1$, the actions coincide and the formula correctly gives random-guessing success $1/2$.

Put $\delta =\pi /(2n)$. Between successive measurement bases, the squared overlap is $c={\cos }^2\delta$ for retaining the same label and $s={\sin }^2\delta$ for changing label. The first step obeys the same rule if we regard the initial state as label 0 at angle zero. Thus the recorded labels form a Markov chain with transition matrix $\left(\begin{array}{cc}c& s\\ s& c\end{array}\right)$.

Let $q_k$ be the probability of label 0 after step $k$. Then $q_0=1$ andSince $c-s=\cos (\pi /n)$, iteration yieldsThis is the total final-outcome probability, including histories that change label an even number of times. The smaller quantity ${\cos }^{2n}(\pi /(2n))$ counts only the history with label 0 at every step and is not the requested total. For example, at $n=3$ the total is $9/16$, whereas the uninterrupted history has probability $27/64$. At $n=1$, the final basis is $\{|1⟩,|0⟩\}$ up to signs, so the total probability of label 0 is zero, as the formula also gives. This distinguishes nonselective measurement-guided Zeno transfer from postselection on one record.

At the last step, $|{\psi }_{0,n}⟩=|1⟩$ and $|{\psi }_{1,n}⟩=|0⟩$. Ignoring the recorded outcome, the final density matrix isFor large $n$, the Taylor expansion $\log \cos x=-x^2/2+O(x^4)$ givesThus $q_n\to 1$, and the final state tends to $|1⟩⟨1|$, or $|1⟩$ as a pure-state representative. In fact $1-q_n\sim {\pi }^2/(4n)$, and its trace distance from $|1⟩⟨1|$ is exactly $1-q_n$. With records retained, the final conditional state is $|1⟩$ with probability tending to one. These are compatible descriptions, not a coherent sum of the two outcome branches. This quantum Zeno effect guides a known preparation through slowly rotating measurement bases; it is not a unitary Pauli X gate acting coherently on an arbitrary unknown input.

A normalized bipartite pure state is entangled when it cannot be written as a product state $|a{⟩}_A\otimes |b{⟩}_B$. Equivalently, its Schmidt rank exceeds one. This definition concerns the specified partition into systems A and B; the mixed-state definition of separability requires a different convex-mixture condition.

A bipartite unitary operator is an entangling gate if it maps at least one product state to an entangled state. It need not entangle every product input. For example, the controlled-NOT gate entangles $|+⟩|0⟩$ but leaves $|00⟩$ as a product. A gate that preserves every product input is not entangling, even if it exchanges the two subsystems.

The joint Born rule uses the tensor product of the two outcome bras. Its amplitude isThe other source component vanishes on contraction with $⟨0|$ on A. ThereforeThis is a joint probability: $\mathrm{Pr}(A=0)=16/25$, while $\mathrm{Pr}(B={\theta }_0\mid A=0)={\cos }^2\theta$. Dropping the first factor would give only the conditional probability.

Here $⟨+y|=(⟨0|-i⟨1|)/\sqrt{2}$. Keeping that complex conjugation, the joint amplitude isHence $\mathrm{Pr}(A=+,B=+y)=0$. The cancellation is destructive quantum interference between the two source components, not the absence of either local outcome. Each local outcome individually has probability $1/2$, since each reduced density matrix is $I/2$. Omitting the conjugation in the second bra would turn the cancellation into reinforcement and give the wrong answer.

For deterministic classical responses, denote the two possible local answers by $x_0,x_1$, $y_0,y_1$ and $z_0,z_1$. Certainty in the GHZ game would requireTaking the exclusive or of all four equations gives zero on the left, since every answer occurs twice, but one on the right. This contradiction rules out deterministic certainty. Pre-shared randomness cannot cure it: conditioning on the random seed fixes a deterministic response table, and none succeeds on every allowed input. Thus noncommunicating classical players cannot win with certainty. No uniform distribution on the referee's questions is needed for this worst-case claim.

For the quantum strategy, share the GHZ state and measure the Pauli X gate observable when the local question is 0, or the Pauli Y gate observable when it is 1. Return bit 0 for measurement eigenvalue $+1$ and bit 1 for eigenvalue $-1$. The four relevant operator identities areFor the first identity, the three bit flips exchange $|000⟩$ and $|111⟩$. For each remaining identity, the two Y actions contribute $i^2=-1$ on $|000⟩$ and $(-i{)}^2=-1$ on $|111⟩$, so they exchange the terms with a minus sign. Local measurements on separate systems commute, and the product of their observed eigenvalues is therefore fixed by the displayed joint eigenvalue. That product equals $(-1{)}^{x+y+z}$, giving exactly the required output parity for each promised input. Hence the quantum strategy wins with certainty without communication. This is the GHZ theorem in nonlocal-game form; it does not let a player control another player's individual outcome.

Consider one normalized measurement vector $|u⟩=a|0⟩+b|1⟩$ on C. The unnormalized partial inner product on AB isIts tensor-product coefficient matrix and determinant areThe two-qubit product-state determinant criterion therefore says that this branch is entangled whenever $a\ne 0$. Its probability is $(|b{|}^2+2|a{|}^2)/3>0$, so such a branch is physically possible and can be normalized without changing whether its determinant vanishes.

For an orthonormal basis $\{|u_0⟩,|u_1⟩\}$, completeness gives $|⟨0|u_0⟩{|}^2+|⟨0|u_1⟩{|}^2=1$. At least one vector has $a\ne 0$. Hence at least one nonzero-probability outcome leaves AB entangled, proving conditional entanglement of the three-qubit W state. Some bases give two entangled branches; the computational basis gives one entangled and one product branch. The claim is not that every outcome must entangle AB.

Suppose $|W⟩=(U_A\otimes U_B\otimes U_C)|GHZ⟩$. Measure C in the orthonormal basis $\{U_C|0⟩,U_C|1⟩\}$. Its two AB conditional vectors would be proportional torespectively. Both are product states, because measuring the original GHZ state's C factor in the computational basis selects $|00⟩$ or $|11⟩$. This contradicts part (i), which applies to every basic measurement basis of the W state's C factor. Therefore no local unitary transformation maps GHZ to W.

An additional invariant makes the distinction visible without measurement records. Across the partition AB versus C, the GHZ reduced density matrix on C has eigenvalues $1/2,1/2$, whereas the W state's are $2/3,1/3$. By local-unitary invariance of reduced-state spectra, these spectra cannot be changed by local unitaries. This supplies the same impossibility and emphasizes that the proposed transformation is a product of unitaries, not arbitrary postselected local processing.

For every nontrivial dimension $d\ge 2$, no such pure state exists. The literal claim needs this qualification: for $d=1$, the only measurement outcome is necessarily the same for both parties. The contradiction below requires allowing all complex orthonormal bases, as quantum theory does.

If equal outcomes were certain in the computational basis, all amplitudes with different labels would vanish, so the normalized joint state would have the formChoose distinct labels $j,k$ and replace their computational vectors in both local bases by $|+{⟩}_{jk}=(|j⟩+|k⟩)/\sqrt{2}$ and $|-{⟩}_{jk}=(|j⟩-|k⟩)/\sqrt{2}$, leaving all other vectors fixed. The joint amplitude for the different outcomes $+,-$ is $(c_j-c_k)/2$. Certainty of equal outcomes would force $c_j=c_k$.

Now use the complex pair $|+i{⟩}_{jk}=(|j⟩+i|k⟩)/\sqrt{2}$ and $|-i{⟩}_{jk}=(|j⟩-i|k⟩)/\sqrt{2}$ in the same way on both systems. The amplitude for different outcomes $+i,-i$ is $(c_j+c_k)/2$, because the conjugated bra factors on the $|kk⟩$ term multiply to $(-i)(i)=1$. Thus equal outcomes would also force $c_j=-c_k$. Combining the two requirements gives $c_j=c_k=0$. Every label belongs to such a pair when $d\ge 2$, forcing the zero vector and contradicting normalization. This proves impossibility of universal identical-basis perfect correlations.

The maximally entangled state $d^{-1/2}{\sum }_j|jj⟩$ is not a counterexample: it correlates matching labels when one party uses a basis and the other its coordinatewise complex conjugate basis. Requiring the two complex bases to be identical is different. This distinction also follows from conjugate-state steering from a maximally entangled pair; restricting attention to real bases would miss the contradiction.

For normalized vector representatives in the same Hilbert space, the vector-norm convention is $\Vert |\psi ⟩-|\varphi ⟩{\Vert }_2\le \epsilon$. Since physical pure states identify global phases, a phase-insensitive version isThe equality follows by choosing the phase to make the overlap real and nonnegative. This states an explicit pure-state norm distance convention; fidelity-based or trace-distance conventions use different numerical error parameters. We use the phase-insensitive convention for the universality claim below.

Under fixed phase representatives, two unitary operators on the same space are $\epsilon$-close when $\Vert U-V{\Vert }_{\mathrm{op}}\le \epsilon$, where the operator norm isThus every input vector is approximated uniformly, not merely one selected input. Under the phase-insensitive convention, replace this bound by ${\min }_{\theta }\Vert U-e^{i\theta }V{\Vert }_{\mathrm{op}}\le \epsilon$. The minimization uses one phase for the whole operator, not a separately chosen phase inside the supremum for each input. This is operator-norm distance between unitary gates with the stated global-phase identification.

A finite universal quantum gate set can approximate every unitary on any fixed finite number of qubits to any prescribed positive accuracy, using a finite circuit of its gates on allowed wires. Explicitly, for every target $U$ and $\epsilon >0$ there is such a circuit $C$ withThe global-phase convention is the one just specified. Universality means arbitrary approximation, not exact representation of an uncountable family by finitely described circuits. Products of approximate gates can be controlled using the quantum circuit gate-error telescoping bound.

Both the controlled-NOT gate and Pauli X gate permute computational basis vectors. Any finite composition remains a permutation matrix, and so sends $|0\cdots 0⟩$ to another computational basis vector. It cannot prepare a superposition such as $|+⟩\otimes |0\cdots 0⟩$.

This also rules out approximation: the squared overlap of that target with any computational basis vector is at most $1/2$, so even after optimizing global phase the pure-state norm distance is at least $\sqrt{2-\sqrt{2}}>0$. Hence $\{CNOT,X\}$ is not universal. Basis permutations can create entanglement on some superposed inputs, but this gate set cannot create the required superposition from the specified basis input.

Squaring the diagonal gate givesThus the T gate is available up to a global phase. Reading the supplied W columns in order $00,01,10,11$, it sends $|01⟩$ to $|11⟩$, $|11⟩$ to $|01⟩$, and fixes the other two vectors: it is CNOT with the second wire controlling the first. Conjugating both wires by the Hadamard gate reverses that orientation:For instance, write $W=I\otimes |0⟩⟨0|+X\otimes |1⟩⟨1|$. Conjugation uses $HXH=Z$ and $H|0⟩=|+⟩$, $H|1⟩=|-⟩$, yielding $I\otimes |+⟩⟨+|+Z\otimes |-⟩⟨-|$. Expanding the first-wire Z eigenspaces gives $|0⟩⟨0|\otimes I+|1⟩⟨1|\otimes X$, as required.

We have H directly and finite constructions of CNOT and T up to physically irrelevant global phase. By universality transfer by exact gate synthesis, the assumed universality of $\{CNOT,H,T\}$ proves that $\{V,H,W\}$ is universal under the phase-insensitive convention. There is no assertion of arbitrary strict operator-norm phases: on a fixed register these generators have only a finite set of possible determinants, which would obstruct density in the entire unitary group if global phase were treated as an observable target.

By the spectral theorem, the nonscalar unitary V has orthonormal eigenvectors $|v_0⟩,|v_1⟩$ with distinct eigenvalues ${\lambda }_0\ne {\lambda }_1$. Choose $|b⟩=(|v_0⟩+|v_1⟩)/\sqrt{2}$. Then $V|b⟩=({\lambda }_0|v_0⟩+{\lambda }_1|v_1⟩)/\sqrt{2}$ is not proportional to $|b⟩$.

On the product input $|+⟩\otimes |b⟩$, the controlled unitary gate producesIts two conditional target vectors are linearly independent, so the conditional-vector product-state criterion proves that the output is entangled. Equivalently, in the control computational basis and target eigenbasis its coefficient matrix is $\frac{1}{2}\left(\begin{array}{cc}1& 1\\ {\lambda }_0& {\lambda }_1\end{array}\right)$, whose determinant is $({\lambda }_1-{\lambda }_0)/4\ne 0$. Thus U is an entangling gate. The excluded scalar case would only apply a phase gate to the control and could not entangle the factors; this is the controlled-unitary entangling criterion.

Let $N_0,N_1$ be the two output counts. Choose a known preparation unitary F with $F|0⟩=N^{-1/2}{\sum }_x|x⟩=:|s⟩$. The Deutsch-Jozsa algorithm applies the supplied phase oracle $O_f|x⟩=(-1{)}^{f(x)}|x⟩$ and then $F^{†}$, declaring constant exactly for outcome 0. Its amplitude on that outcome isThis is the Deutsch-Jozsa test with an arbitrary uniform-state unitary. For $N=2^m$, the usual preparation is $F=H^{\otimes m}$; the argument itself needs only a uniform preparation on the stated N-dimensional space.

For an actually constant-up-to-k function, the two counts are $k$ and $N-k$, so the outcome-0 probability is $(1-2k/N{)}^2$. The error is returning the other label. ThereforeHere the possible count k is nonnegative, and the supplied bound implies $0\le k/N\le 1/8$. The error is consequently at most $7/16$; at $k=0$ it vanishes. This is the error conditional on the stated constant-up-to-k case, not an average over unspecified prior probabilities. For comparison, the printed balanced-up-to-k definition has count difference $\pm k$, so its outcome-0 probability would be $(k/N{)}^2$, not the expression for the constant-up-to-k case. No change to that promise definition is made.

One Grover iteration returns a marked label with certainty. Prepare $|s⟩=N^{-1/2}{\sum }_x|x⟩$; apply the supplied phase oracle to negate amplitudes on the $N/4$ marked inputs; apply the Grover diffusion operator $D=2|s⟩⟨s|-I$; and measure in the computational basis. If F prepares $|s⟩$ from $|0⟩$, the reflection is $D=F(2|0⟩⟨0|-I)F^{†}$, requiring no further oracle query.

After the oracle the amplitudes are $1/\sqrt{N}$ on the $3N/4$ unmarked labels and $-1/\sqrt{N}$ on the marked labels. Their average isThe reflection performs inversion about the mean, $a_x\mapsto 2\mu -a_x$. It therefore sends every unmarked amplitude to zero and every marked amplitude to $2/\sqrt{N}$. The resulting normalized state isEach marked label has Born rule probability $4/N$, every unmarked label has probability zero, and the marked probabilities sum to $(N/4)(4/N)=1$. This is one-step exact Grover search with a quarter of the inputs marked, using one reduced-oracle query. The positive integer N must be divisible by four; a qubit implementation may take $N=2^m$, but the stated reflection proof does not assume that register convention.

Use the Bernstein-Vazirani algorithm: initialize n qubits in $|0^n⟩$, apply $H^{\otimes n}$, query the supplied phase oracle once, apply $H^{\otimes n}$ again, and measure all n computational bits. Immediately after the query the state iswhere the dot product in the exponent is taken modulo two. The Walsh-Hadamard transform gives amplitudeEvery factor is one if $y_j=a_j$ and zero otherwise. Thus the final state is exactly $|a⟩$, and the measurement outputs a with certainty after one oracle query. This is the character cancellation behind Bernstein-Vazirani phase kickback; because access here is already to the reduced phase oracle, no extra target ancilla or conversion from a bit-flip oracle is required.