Does Gottesman-Knill theorem apply with any computational basis input?

Question

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$?

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.