A Sparse and Truncated State Vector Simulator for Peaked Circuits

The Core Claim

Classical simulators typically track all possible quantum states—exponentially many as circuits grow—making simulation intractable beyond ~30 qubits. This paper argues that for peaked circuits (quantum circuits engineered to output a sharp probability distribution with one or few dominant outcomes), you can simulate them classically by tracking only the most probable states. Using sparse storage and vectorized operations, this approach runs on ordinary hardware where dense simulation would fail.

Why Peaked Circuits Are Special

Peaked circuits are deliberately designed so that measurement yields the same output bit string with high probability. Think of a quantum program that confidently returns one answer. Because the output distribution has a sharp peak rather than uniform randomness, most of the 2^n possible quantum states contribute negligibly to the final answer. The key insight is that you don't need to store or process the ~1 million states for a 20-qubit system if only, say, 10,000 of them matter.

The authors exploit this by keeping only nonzero amplitudes (the quantum "weights" for relevant states) in memory, discarding states below some threshold. A dense simulator would allocate a fixed array of 2^n slots regardless; a sparse one stores only occupied entries, like a hash table versus a full array.

How It Works in Practice

The implementation tracks state vectors as sparse data structures—essentially a map from bit strings to their complex amplitudes. As quantum gates are applied, the simulator updates only the amplitudes that exist and creates new ones if needed. Crucially, the authors vectorize operations: instead of applying a gate to one state at a time (slow), they batch operations on many states together, letting modern CPUs or accelerators (GPUs) process them in parallel.

The method is approximate: you choose a truncation threshold, discarding states whose total probability falls below it. This trades perfect accuracy for dramatic speedup. For a circuit where the true answer dominates with 95% probability, truncating to capture 99% of remaining mass still predicts the output reliably while simulating far fewer states than the exponential worst case.

Why It Matters

Peaked circuits appear in real quantum algorithms—variational circuits for optimization, quantum machine learning heuristics, and specific combinatorial solvers all aim for sharp outputs. Classical simulation of these circuits matters for two reasons: it provides a baseline to test whether real quantum hardware actually outperforms classical approaches, and it offers a way to verify small quantum programs before deployment.

The paper is pragmatic: rather than proving complexity-theoretic results, it documents an open-source tool and measures its real-world performance—how many states can be simulated, how sparse representation scales, where hardware acceleration helps. This gives practitioners concrete guidance on whether sparse simulation is viable for their circuit.

The main limitation is obvious: the method works only for peaked circuits. For circuits with uniform or flat output distributions, sparse storage buys little; you'd still track most of 2^n states. But within its domain, this approach extends classical simulation into regimes previously unreachable on laptops.