Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2019/quantum-information/3/b/i/solution

Both the controlled-NOT gate and Pauli X gate permute computational basis vectors. Any finite composition remains a permutation matrix, and so sends to another computational basis vector. It cannot prepare a superposition such as .
This also rules out approximation: the squared overlap of that target with any computational basis vector is at most , so even after optimizing global phase the pure-state norm distance is at least . Hence 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.

New to topics? Read the docs here!