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

Solutions to all three questions of the 11 June 2020 paper. Released Oxford examination archive, member 2019/T/a16608w1.pdf. The dated cover establishes 2020 despite the archive directory. All displayed state vectors are normalized unless described as unnormalized conditional vectors. We use column vectors, $|ij⟩=|i⟩\otimes |j⟩$, and the left tensor factor as the first wire. In a product of gates, the rightmost gate acts first. A global phase is physically irrelevant, but all relative signs and phases below are retained.

For the three given qutrit vectors, $⟨{\varphi }_0|=(⟨0|-i⟨2|)/\sqrt{2}$ and $⟨{\varphi }_2|=(⟨0|+i⟨2|)/\sqrt{2}$. Taking the complex conjugate in the bra is essential. Their squared norms are $1,1,1$, andThus they are an orthonormal set of three vectors in the three-dimensional inner product space ${\mathbb{C}}^3$. Such a set is linearly independent and spans the space, so it is an orthonormal basis.

For an orthonormal basis, choosing coefficients with magnitudes $\sqrt{p_j}$ gives the required Born rule probabilities. More generally, ${\sum }_j\sqrt{p_j}{e}^{i{\theta }_j}|{\varphi }_j⟩$ realizes the same distribution for arbitrary phases. The following are convenient examples of pure-state realization of a basis measurement distribution.

Choose $|\psi ⟩=|0⟩$. Since $|0⟩=(|{\varphi }_0⟩+|{\varphi }_2⟩)/\sqrt{2}$, the probability amplitudes in the measurement basis are $(1/\sqrt{2},0,1/\sqrt{2})$. Their squared moduli give $(1/2,0,1/2)$ by the Born rule.

Choose $|\psi ⟩=|{\varphi }_2⟩$. Its inner products with the three measurement vectors are $(0,0,1)$, so the Born rule gives certainty for the outcome labelled 2 and zero probability for the other two outcomes. This uses the measurement basis, rather than assuming that its label 2 means the initial state must be the computational vector $|2⟩$.

ChooseOrthonormality makes this a unit vector. Its probability amplitudes in the given measurement basis are $(1/\sqrt{2},1/\sqrt{2},0)$, so the required probabilities are $(1/2,1/2,0)$.

Swap the first two computational vectors and fix the third:This permutation matrix has orthonormal columns; equivalently, $U^{†}=U$ and $U^2=I$, proving unitarity. Its first column gives $U|0⟩=|1⟩=|{\varphi }_1⟩$, as required. A unitary must also specify what happens to the rest of the basis, which is why a single outer product alone would not suffice.

The map sends $|0⟩$ to $|0⟩$, $|1⟩$ to $|2⟩$, and $|2⟩$ to $\lambda |1⟩$. These output columns are mutually orthogonal, with squared norms $1,1,|\lambda {|}^2$. ConsequentlyandNecessity follows from preserving the norm of $|2⟩$; sufficiency follows because the three columns are then an orthonormal basis. Merely requiring $\lambda \ne 0$ would establish invertibility but not unitarity. This is the weighted permutation unitarity criterion.

Directly applying the Hadamard gate giveswhileHence the two states are interchanged up to the displayed global phases. Their relative factors $-i$ and $+i$ are retained. They are the two Pauli eigenstates of the Pauli Y gate, and the Hadamard interchange of Y eigenstates is consistent with $HYH=-Y$.

Compute the parity into the second wire, phase that wire with the T gate, then uncompute with the same controlled-NOT gate. The answer isFor computational bits $x,y$, the successive states are $|x,y⟩\mapsto |x,x\oplus y⟩\mapsto e^{i\pi (x\oplus y)/4}|x,x\oplus y⟩\mapsto e^{i\pi (x\oplus y)/4}|x,y⟩$. The parity $x\oplus y$ is one precisely on the two odd-parity inputs. Thus, in the ordered computational basis $00,01,10,11$, the matrix is exactly $\mathrm{diag}(1,e^{i\pi /4},e^{i\pi /4},1)$, with no omitted overall phase. This is a two-qubit parity phase gate.

Let $R=\mathrm{diag}(1,e^{i\pi /12})$. Since the Hadamard gate maps the standard basis to $|+⟩,|-⟩$, the given gate is $Q=HRH$. Because $H^2=I$,Next, use $HZH=X$ on the target wire of the Controlled-Z gate:The control-zero block remains the identity, and the control-one block becomes $HZH=X$, proving the identity with the stated control convention. We have therefore constructed each gate in the assumed universal quantum gate set $\{\mathrm{CNOT},H,T\}$ using only $CZ,Q,H$.

Replacing every gate of a circuit by its displayed finite construction reproduces that circuit exactly. Thus $\{CZ,Q,H\}$ is universal under the usual arbitrary-accuracy convention: it can perform every approximation obtainable from the given universal set. The claim concerns approximation of arbitrary unitary operators; it does not assert that finitely many circuits exactly represent an uncountable continuum of gates. This is universality transfer by exact gate synthesis.

The controlled-NOT gate is its own inverse, so ${\mathrm{CNOT}}^2=I$. Every remaining nontrivial gate acts on one wire. By the tensor product rule, any circuit on a product input stays a product state; in particular, starting at $|00⟩$ it cannot produce a Bell state.

This also prevents arbitrary approximation, not merely exact preparation. For normalized single-qubit vectors $|u⟩,|v⟩$,by the Cauchy-Schwarz inequality. Hence the quantum fidelity with $|{\Phi }^{+}⟩$ is bounded away from one for every reachable state. This gate set is not universal. The obstruction is preservation of product states, a special case of the existing product-state obstruction to SWAP universality.

Here $H^2=I$. Both remaining gates fix the all-zero computational vector: the T gate fixes $|0⟩$, and the controlled-NOT gate fixes $|00⟩$. Therefore every finite circuit, on any number of initially zero wires, leaves $|0\cdots 0⟩$ unchanged.

It cannot even approximate $|+⟩\otimes |0\cdots 0⟩$, whose squared overlap with that unchanged vector is $1/2$. Thus the gate set is not universal. The needed quantum superposition cannot be created from this input by basis permutations and diagonal phases alone.

Now $T^2=S=\mathrm{diag}(1,i)$. The gates $H,S$ and CNOT are Clifford gates: conjugating a Pauli matrix or a tensor product of them gives another signed Pauli tensor. On one wire,For CNOT the generator images are $X\otimes I\mapsto X\otimes X$, $I\otimes X\mapsto I\otimes X$, $Z\otimes I\mapsto Z\otimes I$, and $I\otimes Z\mapsto Z\otimes Z$. These identities can be checked on the four computational vectors and generate the preservation property for all Pauli tensors.^[ref]

For a fixed number $n$ of wires there are only finitely many possible images of the $2n$ generators $X_j,Z_j$ in the Pauli group. Their images determine a unitary up to global phase. To see this, if two unitary operators induce identical images, their quotient commutes with every $Z_j$, so is diagonal in the computational basis; commuting with every $X_j$ then forces all diagonal entries to be equal. The quotient is a scalar phase. Thus the generated gates form a finite set modulo global phase, which cannot be dense in the continuous space of all unitary operators. This is finiteness of the projective Clifford group.

A small visible consequence is that from $|0⟩$, one-qubit Clifford circuits reach only the six states $|0⟩,|1⟩,|+⟩,|-⟩,|+i⟩,|-i⟩$ up to global phase. For instance, $T|+⟩$ is outside this finite set. The fixed-$n$ Pauli argument also covers circuits using CNOT on several wires. Therefore $\{\mathrm{CNOT},H,T^2\}$ is not universal.

Write the product state as $|\Psi ⟩=|a⟩\otimes |b⟩$. The two partial inner products areBoth vectors therefore lie in the same one-dimensional vector subspace, possibly with one or both equal to zero. If $(c_1,c_2)\ne (0,0)$, choose ${\lambda }_1=c_2$ and ${\lambda }_2=c_1$; then ${\lambda }_1|{\psi }_1^{\prime }⟩={\lambda }_2|{\psi }_2^{\prime }⟩$, and the multipliers are not both zero. If both $c_j$ vanish, choose $({\lambda }_1,{\lambda }_2)=(1,0)$.

Thus the conditional vectors are linearly dependent, with a nontrivial pair of multipliers in every case. The printed existential condition does not explicitly exclude $(0,0)$, which would make it vacuous for arbitrary vectors; the argument establishes the stronger intended statement. These unnormalized vectors need not themselves be valid unit state vectors, and a zero vector corresponds to a measurement outcome of probability zero. This is the forward direction of the conditional-vector product-state criterion.

Factor the coefficients:Therefore the first state is a product state, not entangled. Both factors have unit norm, so this factorization also checks normalization.

Taking partial inner products with $⟨0|$ and $⟨1|$ on the first wire gives $(|0⟩+|1⟩)/2$ and $(-|0⟩+|1⟩)/2$. They are nonzero and orthogonal, hence linearly independent. This contradicts the necessary product-state property proved in part (a), so the second state is entangled.

Equivalently, its tensor-product coefficient matrix is $C=\frac{1}{2}\left(\begin{array}{cc}1& 1\\ -1& 1\end{array}\right)$, with $\det C=1/2\ne 0$. The two-qubit product-state determinant criterion gives the same conclusion. In fact $C{C}^{†}=I/2$, so its Schmidt coefficients are both $1/\sqrt{2}$: it is maximally entangled.

The corresponding conditional vectors are $|0⟩/\sqrt{2}$ and $|+⟩/\sqrt{2}$. The second has a nonzero $|1⟩$ component while the first does not, so they are linearly independent. Therefore the third state is also entangled. Orthogonality of these two conditional vectors is not required for this conclusion.

For an independent matrix check, expanding the second factor givesThe original expression is normalized because its two first-wire factors are orthogonal: its squared norm is $(1+1)/2=1$, despite the overlap between $|0⟩$ and $|+⟩$ on the second wire.

Measure the first qutrit in the computational basis and the second in the orthonormal basis $\{|{\varphi }_0⟩,|{\varphi }_1⟩,|{\varphi }_2⟩\}$ from Question 1(a), with those labels as outcomes. For first-party outcome 0, the unnormalized conditional vector of the second party is $|0⟩/\sqrt{3}$, so this outcome occurs with probability $1/3$ and leaves the normalized state $|0⟩$.

The second-party Born rule probabilities are then $|⟨{\varphi }_0|0⟩{|}^2=1/2$, $|⟨{\varphi }_1|0⟩{|}^2=0$, and $|⟨{\varphi }_2|0⟩{|}^2=1/2$. HenceThe relevant joint probabilities are $1/6,0,1/6$, each divided by $\mathrm{Pr}(A=0)=1/3$. This distinguishes the conditional statement from an unconditional outcome probability. More generally, conjugate-state steering from a maximally entangled pair explains how the first local measurement determines the second party's conditional vector; the basis choice here makes that vector especially simple.

Fix the two subsystem dimensions. For reflexivity, $|\Psi ⟩=(I_d\otimes I_{d^{\prime }})|\Psi ⟩$, and both identity operators are unitary.

For symmetry, if $|\Psi ⟩=(U\otimes V)|\Phi ⟩$, apply the inverse local unitary transformation:The conjugate transposes of unitary operators are unitary, so the reverse relation holds.

For transitivity, if additionally $|\Phi ⟩=(R\otimes S)|\Theta ⟩$, the tensor product multiplication rule givesBoth products are unitary, for example $(UR{)}^{†}(UR)=R^{†}{U}^{†}UR=I$. Thus local-unitary equivalence is reflexive, symmetric and transitive, and hence is an equivalence relation.

Use $S=\mathrm{diag}(1,i)=T^2$ and the Pauli X gate. Starting with the Bell state $|{\Phi }^{+}⟩$, the exact constructions areFor the first, $I\otimes X$ changes the two terms to $|01⟩$ and $|10⟩$, and $S\otimes I$ multiplies just the second term by $i$. For the second,All factors are single-party unitary operators, proving both claimed local-unitary equivalences. The equations hold as vectors, without even an additional global phase.

Extend the normalized vector $|\varphi ⟩$ to an orthonormal basis $\{|f_j⟩{\}}_{j=1}^d$ with $|f_1⟩=|\varphi ⟩$, and extend $|\psi ⟩$ to an orthonormal basis $\{|e_j⟩{\}}_{j=1}^d$ with $|e_1⟩=|\psi ⟩$. The Gram-Schmidt process provides such extensions. DefineThen $U^{†}U={\sum }_j|f_j⟩⟨f_j|=I$ and $U{U}^{†}=I$, so $U$ is unitary and $U|\varphi ⟩=|\psi ⟩$. Construct $V$ on the second subsystem in the same way, sending $|{\varphi }^{\prime }⟩$ to $|{\psi }^{\prime }⟩$. ConsequentlyThus any two normalized product states on the same pair of subsystem spaces are local-unitary equivalent. The dimension and normalization requirements matter because a unitary preserves both its domain and vector norms.

A local unitary transformation preserves a product factorization:The output is therefore another product state. If an entangled state could be locally mapped to a product state, applying the inverse $U^{†}\otimes V^{†}$ would make the original entangled state a product as well, a contradiction. Hence a product state and an entangled state are never local-unitary equivalent.

In terms of a tensor-product coefficient matrix, $C$ changes to $UC{V}^T$, with an ordinary transpose on the second factor. Both multiplying matrices are invertible, so the matrix rank, equivalently the Schmidt rank, is unchanged. This supplies an algebraic form of the same argument: a nonzero pure state is a product state exactly when that rank is one.

Throughout this question let $|A_0⟩={\sum }_{f(x)=0}|x⟩$, $|A_1⟩={\sum }_{f(x)=1}|x⟩$, and $|J⟩={\sum }_{x=0}^{N-1}|x⟩=\sqrt{N}|e_0⟩$. These subset sums are unnormalized: $⟨A_j|A_j⟩=S_j$ and $⟨A_0|A_1⟩=0$. The promise implies that $N>0$ is divisible by four. No power-of-two assumption is needed for the abstract $N$-dimensional calculation.

Substitute the promised cardinalities:The marked and unmarked subsets also exhaust the computational basis, so $S_0+S_1=N$; this will ensure that the uniform initial state has unit norm.

By orthonormality of the computational basis,There is one nonzero term, the term with $y=x$. In particular, the uniform coefficient is unchanged when passing from the ket to its bra because it is real.

Summing part (i) over the $S_0$ unmarked indices gives $⟨e_0|A_0⟩=S_0/\sqrt{N}$. The Grover diffusion operator therefore acts asThis is an identity for an unnormalized subset sum; it does not require replacing its norm by one.

For the marked subset, $⟨e_0|A_1⟩=S_1/\sqrt{N}$ by the same summation of the individual inner products. ConsequentlyThe cardinality is $S_1$ here. Its sign will reverse when this expression is used for the oracle's negative marked component.

The phase oracle multiplies an unmarked basis vector by $+1$ and a marked one by $-1$. Thus the state after the oracle isIts squared norm is $(S_0+S_1)/N=1$. All computational outcomes would still have probability $1/N$ if measured at this point: the oracle has changed the relative phase, not the magnitudes of the amplitudes. The following reflection converts that phase information into a changed probability distribution through quantum interference.

Apply parts (b)(ii) and (b)(iii), keeping the oracle's minus sign:The middle equality uses part (a), and the last uses $|J⟩=|A_0⟩+|A_1⟩$. The final squared norm is $4S_1/N=1$, providing a normalization check.

The sign convention matters: here $W=2|e_0⟩⟨e_0|-I$ fixes $|e_0⟩$ and negates its orthogonal complement. Its action on amplitudes is inversion about the mean. The negative of this reflection would change the final vector by an overall global phase, but mixing those conventions midway would give incorrect intermediate signs.^[ref]

The algorithm returns a uniformly random marked input with certainty. The Born rule applied to the final state gives, for each individual basis label $y$,Summing over the $S_1=N/4$ marked inputs gives $\mathrm{Pr}(f(Y)=1)=1$. The outcome is a marked input label, not merely the bit indicating whether some marked input exists. There is one use of the supplied phase oracle, together with the specified preparation, reflection and measurement.

The exact success relies on the marked fraction $r=S_1/N=1/4$. More generally, the mean amplitude immediately after the oracle is $(1-2r)/\sqrt{N}$. Inversion about the mean sends an unmarked amplitude to $(1-4r)/\sqrt{N}$ and a marked amplitude to $(3-4r)/\sqrt{N}$. Thus a single iteration has marked success probability $r(3-4r{)}^2$. At $r=1/4$ the unmarked amplitudes vanish and the marked amplitudes become $2/\sqrt{N}$, giving the one-step exact Grover search with a quarter of the inputs marked. No claim of one-query certainty for an arbitrary marked fraction is needed.