CHAPTER 16

Classical simulation and the cost of representation

Learning goals. Estimate exact memory costs, identify efficient special cases, and choose a simulator matched to the circuit and required answer.

16.1 State-vector memory

A generic n-qubit pure state has $2^n$ complex amplitudes. At 16 bytes per complex double, raw storage is

$$M_\mathrm{vector}=16\,2^n\ \text{bytes}.$$

This excludes temporary arrays, circuit metadata, and application overhead. A single-qubit gate updates pairs of amplitudes in O($2^n$) work. A circuit with G such gates has naive cost O($G2^n$). A dense general $2^n\times2^n$ matrix should not be constructed when local gate updates suffice.

Each added qubit doubles memory. A generic density matrix contains $4^n$ complex entries, using $16\,4^n$ bytes. At n=15, that is 16 GiB. Hermiticity reduces independent real parameters but does not remove exponential scaling.

These numbers do not prove that every n-qubit circuit is difficult. They describe a dense representation. A product state needs only n small vectors, and many entangled states have compact alternative representations.

16.2 Stabilizer simulation

The Clifford gates map Pauli strings to Pauli strings under conjugation. H exchanges X and Z, S maps X to Y, and CNOT has simple propagation rules. A stabilizer state can be stored by n commuting independent Pauli generators rather than $2^n$ amplitudes.

A stabilizer tableau has O(n²) binary entries, and Clifford gates and Pauli measurements admit efficient updates. This is the basis of Gottesman–Knill simulation. It can handle highly entangled states such as GHZ states; entanglement alone is therefore insufficient to imply exponential classical cost [33, 30].

Non-Clifford gates such as T generally break closure of the stabilizer representation. Specialized simulators express a state as combinations of stabilizer states or use related decompositions, with cost depending strongly on non-Clifford resources. A million Clifford operations can be easier to simulate than far fewer appropriately arranged non-Clifford gates.

Stim is an important specialized stabilizer-circuit simulator and detector-error-model tool [32]. Its speed comes from targeting a restricted but useful circuit family. It is not a generic state-vector simulator for arbitrary rotations.

16.3 Tensor networks and entanglement structure

A tensor network factors a large coefficient array into smaller tensors joined by summed indices. For a one-dimensional chain, a matrix product state has amplitudes

$$a_{x_0\cdots x_{n-1}} =A^{[0]x_0}A^{[1]x_1}\cdots A^{[n-1]x_{n-1}}.$$

The internal matrix dimensions are bond dimensions. A bond dimension χ bounds Schmidt rank across that cut; entanglement entropy is at most $\log_2\chi$. Low-entanglement dynamics can be represented efficiently. Generic strongly entangling dynamics may force χ to grow exponentially [31].

Truncating small Schmidt coefficients gives an approximate method. Its reliability depends on accumulated truncation error and the requested observables. A visually smooth expectation curve does not establish small global state error.

For more general tensor networks, contraction order and graph structure determine cost. A circuit’s depth, geometry, and chosen output can substantially change simulation difficulty. Computing one amplitude, one local expectation, or samples from an approximate distribution are different tasks.

16.4 Trajectories, density matrices, and sampling

A density-matrix simulator exactly averages a specified noise channel but pays $4^n$ storage. A quantum-trajectory method samples Kraus outcomes and evolves pure states, trading memory for Monte Carlo variance. A single trajectory is a conditioned pure state, not the ensemble density operator.

For an observable, average trajectory estimates and include both trajectory randomness and measurement sampling if the workflow has both. Choosing a convenient Kraus decomposition can affect numerical efficiency without changing the channel average.

Sparse state vectors help while only a few basis amplitudes are nonzero, but Hadamard-rich circuits can quickly destroy sparsity. Distributed simulation spreads arrays across machines at the cost of communication. GPU acceleration changes constants and capacity, not the exponential asymptotic storage law.

16.5 A practical simulator selection process

Ask what output is needed. A circuit with Clifford gates and Pauli noise favors a stabilizer tool. A small arbitrary ideal circuit favors a state vector. A small open system favors a density matrix. A larger structured low-entanglement circuit may favor tensor methods. A noisy observable calculation may favor trajectories.

Then check assumptions. Does the tool support mid-circuit measurement, classical conditions, leakage, non-Pauli noise, qudits, and the intended ordering? Does its noise convention match the paper? An unsupported operation should be rejected or explicitly approximated, never silently reinterpreted.

The browser workbench intentionally limits the generic circuit to eight qubits and 40 operations for responsive teaching. Other laboratories use exact specialized formulas for larger small registers. These user-interface limits are not a statement about the maximum classical simulator capacity.

16.6 Why classical baselines keep moving

A quantum benchmark may motivate improved classical contraction, approximation, or sampling methods. A published comparison is dated evidence about a specified task, not a permanent mathematical lower bound. Claimed quantum advantage should report accuracy, hardware time, preprocessing, classical resources, and whether the baseline was later improved.

Worst-case complexity statements and empirical benchmark records are both useful, but they answer different questions. Chapter 24 keeps them separate when describing current experiments.

16.7 Exercises