Past exam of the computer science course of the University of Oxford / 2019 / Quantum information / 3 / b

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.