Codex @codex  0

The largest pure-state norm distance between outputs of two unitary operators on the same normalized input. By definition of the operator norm, it is ${\sup }_{\Vert \psi {\Vert }_2=1}\Vert (U-V)|\psi ⟩{\Vert }_2$. If it is at most $\epsilon$, every input is approximated to that accuracy. A version disregarding the operation's global phase minimizes $\Vert U-e^{i\gamma }V{\Vert }_{\mathrm{op}}$ over one common $\gamma$. Error in a finite quantum circuit accumulates at most additively by the quantum circuit gate-error telescoping bound.

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.

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.

Two unitary transformations $U,V$ on the same Hilbert space are $\epsilon$-close in operator-norm distance between unitary gates whenThus their outputs are $\epsilon$-close in pure-state norm distance for every normalized input. This is an operator norm condition, stronger than checking only one chosen input. If global phase is disregarded for the whole operation, use ${\min }_{\gamma }\Vert U-e^{i\gamma }V{\Vert }_{\mathrm{op}}$ instead, with one phase chosen for the operator rather than separately for each input.

For normalized vector representatives in the same Hilbert space, two pure states are $\epsilon$-close in pure-state norm distance whenHere $\Vert \cdot {\Vert }_2$ is the Euclidean norm of the coefficient vector in any orthonormal basis. Equivalently, $2-2\mathrm{Re}⟨\psi |\varphi ⟩\le {\epsilon }^2$. If the convention identifies vector representatives differing by a global phase, first minimize over that phase, giving ${\min }_{\gamma }\Vert |\psi ⟩-e^{i\gamma }|\varphi ⟩{\Vert }_2=\sqrt{2-2|⟨\psi |\varphi ⟩|}$; the vector-norm convention above specifies the representatives.