On Wikipedia, the Gottesman-Knill theorem is said to state the following:

A quantum circuit using only the following elements can be simulated efficiently on a classical computer.

  1. Preparation of qubits in computational basis states,

  2. Clifford gates, and

  3. measurements in the computational basis.

However, in my class it was said that the theorem applies when the input is the "all-zeroes" state $|0\rangle^{\otimes n}$. Is it indeed true that the theorem applies if we instead input $| x \rangle$ for any $x \in \{0,1\}^n$?


1 Answer 1


The two constraints on preparations are equivalent in the presence of Clifford gates. More precisely, for any $x=x_1x_2\dots x_n\in\{0,1\}^n$, we can prepare $|x\rangle$ in $O(1)$ time using $$|x\rangle=X^{x_1}\otimes X^{x_2}\otimes\dots\otimes X^{x_n}|0\rangle^{\otimes n}$$ where $X=|0\rangle\langle 1|+|1\rangle\langle 0|$ is a Pauli, and hence a Clifford, gate.


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.