The complexity boundary
On this page · Permalink · Source line 1800
6.1 Compressed packet simulation
On this page · Permalink · Source line 1801
6.1.1 Beyond packet dimension
On this page · Permalink · Source line 1805
The small-packet theorem stores one amplitude per packet-basis state. This is not the only classical representation. A state in an exponentially large packet may lie on a polynomially parameterized manifold. Stabilizer states, Gaussian states, matrix-product states of bounded bond dimension, and low-rank operator states are standard examples of compact internal encodings.
Let \(\mathcal R_n\) be a class of classical descriptions, and let
associate a quantum state with each description.
Theorem 6.1: Compressed-packet simulation
A polynomial-time uniform quantum circuit family lies in \(P\) if there is a polynomial-size classical representation satisfying:
the initial state has an efficiently constructible description \(r_0\in\mathcal R_n\);
every gate induces a polynomial-time update \(r\mapsto T_j(r)\) with
\[ \operatorname{decode}(T_j(r)) = G_j\operatorname{decode}(r); \]all intermediate description sizes remain polynomial;
the acceptance probability is computable from the final description in polynomial time.
Proof
Iterate the polynomial-time classical updates on the polynomial-size descriptions and evaluate the final measurement. The algorithm never reconstructs the full state vector.
6.1.2 Two-axis complexity
On this page · Permalink · Source line 1835
The records suggest the pair
where \(D_{\rm packet}\) measures active packet size or count and \(\chi_{\rm internal}\) measures the representation cost inside the packet. Efficient simulation may follow from either coordinate:
fixed weight has polynomial \(D_{\rm packet}\) and can use explicit amplitudes;
stabilizer states may have exponential support but polynomial \(\chi_{\rm internal}\);
Gaussian states may occupy large number sectors but have polynomial covariance descriptions;
half-filled generic states may have both coordinates exponential.
6.1.3 Hybrid transfer graphs
On this page · Permalink · Source line 1855
Suppose packets are nodes of a sparse graph and each node carries an internal representation. A gate may update a node internally or transfer a compact component to neighboring nodes. The simulation cost depends on
This model combines symmetry selection rules with compact state classes.
6.1.4 Closure is the decisive condition
On this page · Permalink · Source line 1864
A compact representation may be destroyed by one gate. Clifford tableaux fail under generic non-Clifford rotations. Gaussian covariance matrices fail under generic non-Gaussian operations. Low-bond tensor networks may acquire exponential bond dimension. The theorem therefore requires closure or a proved polynomial growth bound, not merely a compact initial state.
Principle 6.2: Representation growth audit
The correct complexity variable is the maximum representation size reached along the computation, not the size of the initial or final state alone.