Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
The CNOT gate together with phase shift gates for all possible angles are not universal for quantum computing.
Are they also not universal for classical (reversible) computing?
Is it possible to characterize the set of classical Boolean functions that can be obtained using this set of gates?
Firstly, let us assume that we are restricted to measurements in the computational basis, i.e. outcomes of $|0\rangle$ or $|1\rangle$.
Next, since neither gates create any superposition (when applied to computational basis states) we can observe that without a Hadamard gate, our qubit state is always in a single computational basis state.
Hence, we can see that the computational power of our CNOT + phase gate set is not greater than that of just a simple CNOT, and so we can reduce the initial problem to simply considering the computational power of the classical CNOT.
So, in answer to the first question, a quick bit of googling reveals the answer is no, since the CNOT gate is not universal for classical computation, reversible or otherwise.
In answer to your second question, I guess the best answer I can give is simply that it is the same as the set produceable by circuits of CNOTs. I am not sure if this set of Boolean functions is well characterised or not, but perhaps this is worth posing in the CompSci stack exchange.
Just to add that phase shift has no meaning in classical (binary) computation as we work only with bits in state either 0 or 1.
CNOT is only another name for XOR operation which is not universal. In classical computation, universal sets of gates are for example:
