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:

  • $\{\text{NAND}\}$
  • $\{\text{NOR}\}$
  • $\{\text{AND},\text{OR},\text{NOT}\}$
  • $\begingroup$ {XNOR} is also universal. $\endgroup$ – mbomb007 May 13 '20 at 17:25
  • $\begingroup$ @mbomb007: Could you please provide a proof of that? So far, I though that XNOR is not universal gate. $\endgroup$ – Martin Vesely May 15 '20 at 6:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.