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