# Understanding the Gottesman-Knill Theorem

I come from a theoretical CS background, and I am trying to gain a better appreciation of the exact formal statement of the Gottesman-Knill theorem in terms that I am more familiar with. My question in this post clarified that the input need not be the "all-zero" state, but that in fact any computational basis state input works (and in fact any stabilizer state input works). My question here is concerned more with how to phrase the Gottesman-Knill theorem in terms of uniform families of Clifford circuits with computational basis state inputs. My formulation of what I think is the right statement is below, however I'm not sure if my quantification of the statement is right. In particular, is it that there exists a Turing machine such that for all inputs such and such is true, or is it that for all inputs, or perhaps for all Cliffords in the family, there exists a Turing machine such that such and such is true?

Claim: Let $$\Gamma_n$$ be a uniform family of polynomial size Clifford circuits. Then, there exists a classical probabilistic polynomial time Turing machine $$A$$ such that for all $$x \in \{0,1\}^*$$, the state $$\Gamma_{|x|}|x\rangle = \sum_{y \in \{0,1\}^{|x|}} \gamma_y(x) |y\rangle$$, for some amplitudes $$\gamma_y(x)$$, is exactly sampleable by $$A$$, i.e., $$\mathrm{Pr}[A(x) = y] = |\gamma_y(x)|^2$$.