One often reads that the key reason why classical computers (probabilistic or deterministic) are unable to simulate quantum algorithms such as Simon's or Shor's efficiently is that a classical computer needs $2^n$ complex numbers to represent an $n$ qubit state of a quantum computer. While it is true that the dimensionality of the Hilbert space spanned by an $n$ qubit computational basis is $2^n$, it seems to me that the subspaces reachable by many quantum algorithms that employ fixed sequence of unitary gates are substantially smaller.
Let $n$ be the number of qubits in a quantum computer. Consider an algorithm that starts from some simple initial state (say the 0 for all qubits) and employs a sequence of $kn$ unitary gates ($k$ being some factor), each involving no more than 1 or 2 qubits. One may ask: What is the size of the Hilbert subspace reachable by this algorithm from the initial state? A 2 qubit gate should not need more than 16 complex numbers for its representation and $kn$ such gates in a fixed sequence will not need more than $16kn$ such numbers (in reality the factor will be smaller). The fact that the sequence of gates is a fixed one is important in this argument to avoid branching. Many algorithms including Shor's, Grover's, Simon's are based on fixed gate sequences like this. If the number of gates scales as a polynomial of $n$, the "size" of the Hilbert subspace reachable from the initial state should scale as polynomial of $n$ as well. Therefore, I do not see why we would need $2^n$ complex numbers as would be needed to describe the entire Hilbert space. Can someone help explain why? If my thinking is correct, wouldn't this logic be a generalization of Gottesman-Knill theorem and wouldn't it also imply that there exists "classical", possibly probabilistic computing, algorithms capable of equalling Simon's and Shor's in efficiency? What am I missing?