3.4 Exact packet simulation and polynomial collapse
On this page · Permalink · Source line 243
3.4.1 Gatewise invariance
On this page · Permalink · Source line 246
Let \(P\) be an orthogonal projector and suppose the initial state obeys \(P{\lvert \psi_0\rangle}={\lvert \psi_0\rangle}\). If every gate satisfies
then \(G_j\) maps \(P{\mathcal H}\) into itself. For a general linear map, this equation asserts only invariance of the selected subspace. For the finite-dimensional unitary gates considered here, invariance also implies invariance of the orthogonal complement, so it is equivalent to commutation with \(P\).
Theorem 3.6: Invariant-basis simulation
Let \(U=G_m\cdots G_1\) and assume Equation (3.3) for every gate. If \(P{\lvert \psi_0\rangle}={\lvert \psi_0\rangle}\), then
In any basis of \(P{\mathcal H}\), the restricted circuit gives exactly the same amplitudes after embedding.
Proof
Inductively, if \(P{\lvert \psi_{j-1}\rangle}={\lvert \psi_{j-1}\rangle}\), then
so the next state remains in \(P{\mathcal H}\). Iterating proves the identity.
3.4.2 Polynomial packet-simulation theorem
On this page · Permalink · Source line 277
Theorem 3.7: Polynomial packet-simulation theorem
Let \(\{C_x\}\) be a polynomial-time uniform family of quantum circuits. Suppose there is an efficiently computable packet representation such that:
the initial state lies in the represented packet and its coordinates are computable in polynomial time;
every gate preserves the representation;
the representation size is at most \({\operatorname{poly}}(|x|)\);
each gate update is computable to polynomial precision in polynomial time;
the final acceptance probability is computable from the representation in polynomial time.
Then the language decided by the circuit family belongs to \(P\).
Proof
The simulator stores a polynomial-size classical description of the evolving state. It performs polynomially many polynomial-time gate updates and evaluates the final measurement to inverse-polynomial precision. Choosing an error smaller than the amplified promise gap yields a deterministic polynomial-time decision algorithm.
Proved statement
The theorem is a genuine quantum-to-classical complexity collapse for the declared subclass. It does not assume that a full \(2^n\) state vector is ever constructed.
3.4.3 Dimension-only corollary
On this page · Permalink · Source line 301
A convenient special case uses an explicit basis of a packet of dimension \(D_n\).
Corollary 3.8: Polynomial-dimensional invariant packet
If \(D_n\le{\operatorname{poly}}(n)\), the packet basis is efficiently indexed, every gate has a polynomial-time sparse or structured action in that basis, and the measurement is efficiently evaluable, then the circuit family is classically polynomial-time simulable.
3.4.4 A broader compressed representation
On this page · Permalink · Source line 308
The state description need not be a vector of packet amplitudes. Let \(\mathcal R_n\) be a polynomial-size classical representation class with an embedding into the packet Hilbert space. If initialization, gate updates, and measurement stay within \(\mathcal R_n\) and are efficient, the same proof applies. This observation will later combine packet labels with stabilizer, Gaussian, or tensor-network coordinates.
