Past exam of the computer science course of the University of Oxford / 2020 / Quantum information / 1

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.