= Solution
Both the <controlled-NOT gate> and <Pauli X gate> permute <computational basis> <vectors>. Any finite composition remains a <permutation matrix>, and so sends $|0\cdots0\rangle$ to another <computational basis> <vector>. It cannot prepare a superposition such as $|+\rangle\otimes|0\cdots0\rangle$.
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-\sqrt2}>0$. Hence \b[$\{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.
Back to article page
