So, it's well known that given magic states as inputs, one can perform any quantum computation using only Clifford gates, and it's also known that the running of Clifford gates on the zero-state can be computed efficiently classically.

My question is, are the Clifford gates alone, without magic states, Turing complete? How should we treat them from a classical computational point of view? Is the family of decision problems that can decide by Clifford circuits at polynomial depth, P-hard?



2 Answers 2


Clifford circuits alone are not universal for classical computation, at least not under common complexity-theoretic assumptions.

More precisely, Aaronson and Gottesman showed that deciding whether the first qubit is $|1\rangle$ with certainty after applying a Clifford circuit is $\oplus L$-complete (parity-L). It is conjectured that $\oplus L \neq P$, thus Clifford circuits would not be complete for $P$ (for more details on this see the Aaronson-Gottesman paper).

$\oplus L$ is the class of problems that can be decided by a nondeterministic, logarithmic-space Turing machine that accepts iff the number of accepting paths is odd. One can show that this is also the class of problems that can be reduced (in logarithmic space) to the simulation of CNOT circuits (i.e. linear reversible classical circuits).

Thus, the Aaronson-Gottesman result is a bit surprising since CNOT circuits are a proper subset of Clifford circuits, but the latter are in fact not more powerful than the former.


are the Clifford gates alone, without magic states, Turing complete?

A circuit has a fixed size, so it can't increment a number larger than that size. A Turing machine can increment an n-digit number, no matter how big n is. All circuits are vacuously not Turing complete.

You actually want to ask if Clifford circuits are universal. You want to know if, for every fixed size problem, there is a Clifford circuit that computes the correct answer for every instance of the problem of that size.

are the Clifford gates alone, without magic states, [Universal?]

They are if you allow classical feedback beyond Paulis with a single classical control.

If you can allow a doubly-classically-controlled Pauli gate, this is effectively a classical Toffoli gate, and Toffolis are universal for reversible computation. So you just ignore the Hadamards or whatever and do all the computation via the feedback. The same basic thing occurs if you're given a classically controlled CNOT gate, or classically controlled H gate or S gate, or any classically controlled non-Pauli gate.

If you ban classical feedback, then Clifford circuits aren't universal. For example, they can't compute the output of an AND gate. They can't multiply two integers.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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