Source-linked AI summary
Stim: a fast stabilizer circuit simulator
Craig Gidney
TL;DR
Stim addresses the challenge of simulating very large stabilizer circuits quickly enough for interactive exploration and repeated sampling. It combines faster deterministic measurements, SIMD-based implementation, and Pauli-frame bulk sampling, producing a useful simulator despite not reaching its original tenth-of-a-second goal.
Problem
Stim targets the difficulty of interactively simulating surface-code circuits with tens of thousands of qubits and millions of operations.
Method
Stim combines linear-time deterministic measurements, SIMD-optimized stabilizer operations, and parallel Pauli-frame simulation after an initial sample.
Results
Stim is a useful fast stabilizer circuit simulator that can simulate a 15 thousand-qubit circuit with millions of gates in roughly ten seconds and then produce batches of hundreds of samples in a tenth of that time.
Takeaways & Limitations
Stim provides a general-purpose tool for exploring large stabilizer circuits without requiring hardcoded knowledge of specific circuit behavior.
Takeaways & Limitations
Stim does not address magic state injections and does not implement asymptotically efficient detector sampling.
Abstract
from arXiv · showhide
This paper presents ``Stim", a fast simulator for quantum stabilizer circuits. The paper explains how Stim works and compares it to existing tools. With no foreknowledge, Stim can analyze a distance 100 surface code circuit (20 thousand qubits, 8 million gates, 1 million measurements) in 15 seconds and then begin sampling full circuit shots at a rate of 1 kHz. Stim uses a stabilizer tableau representation, similar to Aaronson and Gottesman's CHP simulator, but with three main improvements. First, Stim improves the asymptotic complexity of deterministic measurement from quadratic to linear by tracking the {\em inverse} of the circuit's stabilizer tableau. Second, Stim improves the constant factors of the algorithm by using a cache-friendly data layout and 256 bit wide SIMD instructions. Third, Stim only uses expensive stabilizer tableau simulation to create an initial reference sample. Further samples are collected in bulk by using that sample as a reference for batches of Pauli frames propagating through the circuit.
1 Introduction
Stim targets fast, general-purpose simulation of huge stabilizer circuits, motivated by strict latency, memory-access, measurement, and sampling demands. It addresses these obstacles with faster deterministic measurements, SIMD-optimized computation, and bulk Pauli-frame sampling.
- Motivation: 0.1 seconds is the target latency for interactively exploring a surface-code circuit spanning 15 thousand qubits and millions of gates.The motivating example is a 15-to-1 surface-code T-state factory with millions of gates across 15 thousand qubits.
- Motivation: 200 clock cycles per gate is the budget for simulating a million-gate circuit on a 2 gigahertz computer.This leaves little room for overhead in each gate operation.
- Contribution: Stim’s first sample serves as a reference for hundreds or thousands of Pauli-frame simulations updated in parallel with SIMD instructions.This makes bulk-sampling timings almost identical to the time required to obtain the first sample.
- Obstacles: Θ(n^2) worst-case measurement time is inadequate for surface-code circuits containing many measurements.Earlier stabilizer simulators reduced measurement complexity from Θ(n^3) to Θ(n^2), but the paper argues the quadratic cost remains too high.
- Contribution: Stim can simulate a 15 thousand-qubit surface-code circuit with millions of gates in roughly ten seconds, then produce batches of hundreds of samples in a tenth of that time.The result falls short of the 0.1-second goal but supports substantially faster subsequent sampling.
- Contribution: Stim makes three key improvements: linear-time deterministic measurements, SIMD-optimized tight loops, and parallel Pauli-frame simulation for bulk sampling.These improvements target the measurement, constant-factor, and mega-sampling obstacles.
2 Key Concepts
Stim’s core representations encode Pauli products and Clifford operations using compact algebraic structures, with stabilizer tableaus tracking generator conjugations. Pauli frames then provide an external, linear-space mechanism for propagating corrections through stabilizer circuits.
- Pauli Products: A Pauli product applies one Pauli gate to each selected qubit and identity elsewhere, forming the Pauli group under multiplication.Stim represents Pauli products with the stim::PauliString class and can encode them using x and z bits.
- Stabilizer Tableaus: A stabilizer tableau represents a Clifford operation by storing how each generator Xq and Zq is conjugated.Valid tableaus preserve the commutation and anticommutation relations of the generators.
- Stabilizer Tableaus: 4n^2 + O(n) bits store an n-qubit stabilizer tableau, making the tableau Stim’s dominant space cost.There are 2n generator outputs, each containing n Pauli terms encoded with two bits per term.
- Tableau Operations: O(mc) time conjugates an n-qubit Pauli product by an m-qubit tableau when c qubits overlap, independent of n.The operation decomposes the product into tableau generators, conjugates them, and reassembles the result.
- Tableau Operations: O(Nm^2) time is required to append or prepend an m-qubit tableau into an N-qubit tableau.Stim implements these compositions with inplace scatter append and prepend methods, plus specialized methods for common gates.
- Pauli Frames: A Pauli frame augments a stabilizer simulator into a noisy stabilizer simulator without requiring access to the simulator’s internal implementation.Pauli frames are also central to tracking corrections in surface-code error correction.
3 Pauli Frame Simulation
Pauli frame simulation reuses one noiseless reference sample while propagating randomized Pauli corrections through the circuit. This makes bulk sampling inexpensive, but restricts the noise model to Pauli channels.
- Frame Propagation: O(n) bits store a Pauli frame, and O(1) time updates it per gate.Clifford gates conjugate the frame, noise multiplies Paulis into it, and collapsing operations randomize parts of it.
- Noise Assumption: Pauli frame simulation requires noise processes to be Pauli channels, such as dephasing and depolarization.Relaxation to the ground state and leakage outside the computational basis are not Pauli channels under this method.
- Simulation Procedure: A reference sample is collected once with noise disabled, then reused for additional simulation runs.Each subsequent run initializes and advances a separate Pauli frame through the target circuit.
- Measurement Updates: At a measurement, the reported result is the reference result XOR the frame’s X-or-Y indicator on the measured qubit.A random Z correction is then multiplied into the frame because measurement is a collapsing operation.
- Simulation Procedure: The frame-propagation procedure repeats until the requested number of circuit samples has been generated.Stim applies each action to multiple frames simultaneously using SIMD operations.
4 Stabilizer Tableau Simulation
Stim’s stabilizer tableau simulation resolves measurements by mapping current observables backward to the circuit start. Tracking the inverse tableau reduces deterministic-measurement cost from quadratic to linear and improves surface-code scaling.
- Measurement Resolution: A current measurement observable is conjugated backward through the inverse Clifford circuit to obtain its equivalent start-of-time observable.For example, a current Zq measurement can become a signed product such as −ZaZb or −XaXb.
- Measurement Resolution: Measurements whose start-of-time observables contain only Z terms are deterministic, while those containing X or Y terms are random.Deterministic results equal the observable’s sign; random measurements require tableau elimination before resolution.
- Inverse Tableau: O(n) worst-case time resolves a deterministic measurement when the tableau maps current observables backward to the start of time.Forward mapping instead requires finding a combination of stabilizers and has a higher deterministic-measurement cost.
- Tableau Construction: A stabilizer tableau is initialized and folded through the circuit, using inverse-gate prepending and measurement elimination to update the representation.The tableau tracks the inverse of the processed circuit, enabling start-of-time observable queries.
- Complexity: O(ng + nd + n^2r) is the simulation complexity, improving on O(ng + n^2d + n^2r) from previous work.Here, n is the qubit count, g the gate count, d deterministic measurements, and r random measurements; resets contribute implicitly to d and r.
- Surface-Code Scaling: Θ(d^6) replaces Θ(d^7) for a distance-d surface-code circuit run for d rounds when tracking the inverse rather than forward tableau.The remaining Θ(d^6) cost comes entirely from random measurements in the first and last rounds, while intermediate rounds cost Θ(d^5) together.
5 Software Engineering
Stim’s software engineering choices prioritize predictable memory access, dense representations, and vectorization across Pauli frames. The implementation also uses targeted sampling, threading, and comprehensive testing to improve performance and correctness.
- Data layout: Sequential memory access lets caching mechanisms prefetch data, while disorganized access can cause cache misses and order-of-magnitude slowdowns.The paper contrasts contiguous-memory layouts with layouts that make accesses difficult to predict.
- Data layout: The Pauli frame layout remains constrained because circuit gates affect unpredictable, tiny subsets of bits, creating difficult cache behavior even in organized circuits.This is described as a worst-case scenario for cache misses.
- Data layout and vectorization: Stim vectorizes across 1024 Pauli frames, packing corresponding bits from 256 frames into each 256-bit word for single-instruction gate application.For an S gate, one 256-bit XOR computes new z_q values for 256 frames simultaneously.
- Sparse vs Dense: Stim uses dense representations because maintaining sparse structure can resemble non-linear-scaling problems and sparse set operations carry large constant factors.The paper reports that ten nanoseconds can process ten thousand dense items but only ten sparse items, with sparsity needing to exceed 99.9% before the sparse representation becomes preferable for speed.
- Entropy: Stim samples low-probability noise using truncated and refinement probabilities, whose bitwise OR produces the desired intermediate probability.These optimizations, together with others, allow Bernoulli distributions to be sampled at gigahertz rates.
- Sampling Detection Events: Stim does not implement asymptotically efficient detector sampling; it samples measurements and combines them because sparse-representation constants dominate near 0.1% noise levels.The paper notes that detector sampling could turn non-local measurement effects into bounded-local detector effects, but Stim currently uses the measurement-based approach.
5.8 Profiling and Optimizing
Stim’s optimization process combines targeted microbenchmarks and profiling with cache-conscious, vectorized implementations and a minimal circuit interface. The design also provides multiple output formats for dense and sparse measurement data.
- Benchmarking: Stim’s benchmark framework repeatedly runs a task for 0.5 seconds and compares its inferred time to a reference time.The framework was intended for the author’s individual benchmarking purposes rather than team-wide comparisons.
- Benchmarking: Profiling with Linux’s perf tool identified disproportionate costs, including entropy generation during Bernoulli error sampling.The author used debug builds with frame pointers to locate performance regressions and bottlenecks.
- Data layout and vectorization: Stim hides 256-bit AVX, 128-bit SSE, and scalar implementations behind the portable simd_word abstraction.Compile-time defines select the implementation appropriate for the available architecture.
- Data layout and vectorization: simd_bits and simd_bit_table automate padding and iteration over vectorized one- and two-dimensional bit-packed data.The abstractions avoid requiring callers to depend on the size of simd_word.
- Input and output: Stim uses a minimal line-based circuit format in which each line specifies a gate and its targets.The format also supports comments, broadcasting, and REPEAT blocks that reduce file sizes.
- Input and output: Stim supports character, packed-byte, and sparse output formats for measurement results.Sparse formats focus on non-zero-bit indices and are useful when sampling detectors because non-zero bits are rarer.
6 Comparison
Stim was compared with four stabilizer simulators across five circuit benchmarks using timed simulations on a specified laptop setup. At larger sizes it generally led by large margins, while graphsim excelled on nested distillation circuits.
- Benchmark setup: Stim was compared against chp, Qiskit’s stabilizer simulator, Cirq’s CliffordSimulator, and graphsim.The comparison covered five tasks: surface code bulk sampling, surface code sampling, Bacon-Shor sampling, random circuits, and multilevel S-state distillation.
- Benchmark setup: The benchmarks ran on an Intel Core i7-8650U laptop with 16GB of RAM, using g++ 10.2.1 and -O3.Timing used steady clocks around key simulation methods, with startup and parsing excluded except for a separately labeled condition.
- Benchmark tasks: Stim scales comparatively well on surface-code memory circuits because deterministic measurements take worst-case linear rather than quadratic time.The Bacon-Shor benchmark lacks many deterministic measurements, and Stim’s apparent scaling resembles the other simulators there.
- Benchmark setup: Gate decompositions and glue code were required because the simulators did not share a common format or gate set.For example, chp’s lack of a Z gate was handled by substituting two S gates.
- Overall results: At larger sizes, Stim outperformed the other simulators by one or more orders of magnitude.When collecting thousands of samples, Stim outperformed the others by many orders of magnitude.
- Overall results: Graphsim was a notable exception on multilevel distillation because it simulated piecewise circuits piecewise.The benchmarks also contained structure that a simulator exploiting it could potentially use to outperform Stim.
7 Conclusion
The conclusion presents Stim as a useful fast stabilizer simulator despite missing the original tenth-of-a-second target. It identifies sparse representations, reuse across circuit variants, and user-provided structure as possible routes to further speedups.
- Conclusion: Stim was intended to simulate surface-code circuits with tens of thousands of qubits and millions of operations in 0.1 seconds, but that goal was not reached.The paper nevertheless presents Stim as useful software.
- Future work: Special-case speedups may come from recognizing repetitive topological structure and improving sparse-representation maintenance.The paper contrasts this with a person’s ability to focus on lattice surgeries and braids rather than low-level repetition.
- Future work: Caching work across small iterative circuit changes could avoid treating each simulation as a completely new circuit.The paper also suggests verifying and exploiting user-provided repeated pieces or measurement relationships.
- Implications: Faster simulation could enable brute-force or machine-learning searches over error-correction-circuit details to reduce undesirable error propagation.The paper frames this as a possible use of simulations that are ten or a hundred times faster.
A.2 (Python) Sample a noisy repetition code 1024 times
The example constructs a noisy repetition-code circuit in Stim, repeats its rounds, compiles a sampler, and prints 1024 sampled results.
- Circuit construction: The example sets distance 5, 20 rounds, and a 0.01 bit-flip error rate per round.It creates qubits indexed over range(2 * distance + 1).
- Circuit construction: The circuit applies X_ERROR, forward and reverse CNOT chains, and mid-circuit measurements before repeating the round block.The repeated block is multiplied by the chosen number of rounds.
- Sampling: The compiled sampler produces 1024 samples, which the example prints one sample at a time.Sampling is performed after circuit construction and repetition.
A.3 (Python) Interactive quantum teleportation
The example uses Stim to teleport a quantum state through an EPR pair, applying Alice’s measurement-dependent corrections to recover it on Bob’s qubit.
- Stim creates an EPR pair between qubits 1 and 9 using a Hadamard gate followed by a controlled-NOT.
- Alice prepares the state on qubit 0, performs the teleportation measurements, and records the two classical outcomes.
- Bob conditionally applies X and Z corrections to qubit 9 based on Alice’s measurement results.
- The example verifies successful reception by uncomputing the preparation on Bob’s qubit and asserting that the final measurement is false.
A.4 (Python) Algebraic manipulations
Stim’s Python interface supports inverse-tableau algebra, Pauli-string transformation, and deriving canonical stabilizers from an inverse tableau.
- A randomly generated ten-qubit tableau can be inverted, with multiplication by its inverse returning the ten-qubit identity tableau.
- The inverse operation also supports exponent arithmetic, demonstrated by canceling t^1000000 with two copies of t_inverse^500.
- Applying the inverse tableau to a product of selected X and Z outputs produces a specific Pauli string.
- An inverse tableau can initialize a TableauSimulator, which can then return canonical stabilizers that commute with one another.