PaperlayerView exact revision on arXiv

Source-linked AI summary

Clifft: Fast Exact Simulation of Near-Clifford Quantum Circuits

Bradley A. Chase, Farrokh Labib

arXiv:2604.27058v2quant-ph

TL;DR

Exact simulation of fault-tolerant non-Clifford circuits is constrained by tradeoffs in qubit-count scaling, non-Clifford operations, and per-shot overhead. Clifft factors the state into offline and online frames plus a dynamic active state vector, then uses it for exact end-to-end MSC simulation. Escape-stage failures suppress the T-gate versus S-proxy discrepancy at low decoder-gap thresholds, while higher thresholds approach the larger cultivation-stage discrepancy.

  • Problem

    Exact simulation of fault-tolerant circuits is limited by tradeoffs among dense state-vector scaling with qubit count, stabilizer-rank scaling with non-Clifford operations, and sparse-simulator tracking overhead.

    Source: §1 · p. 1

  • Method

    Clifft separates an offline Clifford frame, an online Pauli frame, and a dynamically sized active state vector to confine dense evolution to the active non-Clifford subspace.

    Source: §1 · pp. 2–3

  • Results

    Escape-stage failures suppress the true T-gate versus S-proxy discrepancy at low decoder-gap thresholds, while at higher thresholds end-to-end behavior approaches the larger discrepancy observed in cultivation stages alone.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Clifft supports exact end-to-end MSC simulation through the escape stage over hundreds of billions of shots on commodity CPUs.

    Source: §1 · p. 3, §5 · p. 17

    The current greedy localization and scheduling heuristics may leave room to reduce peak active dimension or time spent at large active dimension.

    Source: §5 · p. 17

Abstract

from arXiv · show

Exact classical simulation of fault-tolerant quantum circuits remains limited by a tradeoff between exponential state vector scaling, exponential $T$-count scaling in stabilizer-rank approaches, and per-shot tracking overhead in sparse generalized stabilizer simulators. In this work, we introduce Clifft, an open-source simulator that shifts the dominant exponential cost from the total qubit count to a dynamic active subspace by factoring the quantum state into an offline Clifford frame, an online Pauli frame, and a dynamically sized active state vector. This architecture resolves deterministic Clifford coordinate transformations ahead of time, generalizing Stim's compile-once, sample-many execution model to circuits with non-Clifford operations. Consequently, exponential simulation costs are determined by the peak active virtual dimension, which expands during non-Clifford operations and contracts during measurements. Clifft remains within a constant factor of standard tools in the pure-Clifford and non-Clifford limits, while delivering up to orders-of-magnitude throughput gains over GPU-accelerated near-Clifford simulators on low-magic fault-tolerant benchmarks. Executing on commodity CPUs and exposing a Stim-like API, Clifft enables, to our knowledge, the first exact end-to-end simulation of magic state cultivation including the escape stage, over hundreds of billions of shots. These simulations show that escape-stage failures suppress the discrepancy between the true $T$-gate circuit and its $S$-proxy at low decoder-gap thresholds, while at high thresholds the full-protocol behavior approaches the larger discrepancy observed in the cultivation stages alone.

1 Introduction

Fault-tolerant protocols need exact, high-throughput simulation of non-Clifford circuits, but existing approaches trade scalability across qubit count, non-Clifford operations, and per-shot tracking. Clifft moves dense evolution to a dynamically sized active subspace and applies it to end-to-end Magic State Cultivation (MSC) simulation.

1 Introduction

  • Existing simulators address different parts of the problem: dense state vectors scale exponentially with qubit count, while low-magic methods and sparse simulators face other practical tradeoffs.Methods exploiting specialized algebraic structure generally do not cover the non-Clifford gates and feed-forward measurements central to fault-tolerant magic-state protocols.Source: §1 · pp. 1–2
  • MSC is a demanding near-Clifford benchmark: its dominant operations are Clifford, but evaluating its correctness and performance requires exact non-Clifford simulation at millions-to-trillions-of-shots scale.The original MSC study relied on an S-gate proxy for large-scale evaluation because exact simulation of the full noisy circuit was not available at useful scale.Source: §1 · p. 2
  • Prior MSC simulation studies omitted the final escape stage, while SyQMA targets analytic small-to-moderate QEC studies rather than high-throughput end-to-end sampling.Earlier tools had made progress on cultivation, but system size and shot count remained practical limits.Source: §1 · p. 2
  • Clifft factors the state into an offline Clifford frame, an online Pauli frame, and a dense active state vector, so exponential costs depend on active virtual dimension rather than total qubit count.Its compiler resolves Clifford transformations ahead of time, leaving lightweight Pauli tracking and localized non-Clifford operations for runtime.Source: §1 · pp. 2–3
  • Clifft is competitive across pure-Clifford, near-Clifford, and non-Clifford regimes, with its clearest advantage on low-magic fault-tolerant circuits.It remains within an order of magnitude of Stim in the pure-Clifford limit and close to leading CPU state-vector simulations in the dense limit.Source: §1 · p. 3
  • At low decoder-gap thresholds, escape-stage failures suppress the discrepancy between the true T-gate circuit and its S-proxy; at high thresholds, full-protocol behavior approaches the larger cultivation-stage discrepancy.The simulations include MSC's escape stage and cover hundreds of billions of shots.Source: §1 · p. 3

2 Frame-Factored State Representation

Clifft factors the state into an offline Clifford frame, a virtual Pauli frame, and a dynamically sized active state vector, so dense evolution is confined to a small active virtual subspace. Heisenberg mapping and Pauli localization express active operations on virtual axes, which can expand or leave the active set.

2 Frame-Factored State Representation

  • Exact simulation cost scales exponentially with active dimension k rather than physical qubit count N.The representation maps operations into a virtual basis and uses Pauli localization to restrict the dense state vector to a small active subspace.Source: §2 · pp. 3–4

2.1 Circuit Model and the Heisenberg Picture

  • Clifford unitaries are passive coordinate updates, while non-Clifford Pauli rotations, Pauli measurements, stochastic Pauli noise, and conditional Pauli corrections are active operations.More general non-Clifford unitaries can be decomposed into Pauli rotations before evaluation.Source: §2.1 · p. 4

2.2 The Frame-Factored State

  • The state is factored into a deterministic Clifford frame, a virtual Pauli frame, and an active state vector over active qubits, with dormant virtual qubits fixed to |0⟩.The active vector stores amplitudes for the active subspace; its maximum dimension bounds the dominant exponential cost.Source: §2.2 · p. 5

2.3 Virtual Operations and Pauli Localization

  • Pauli localization uses virtual Clifford gates to map a multi-qubit generator to one virtual axis, absorbing the inverse transformation into the offline frame and updating the Pauli frame.For any non-identity virtual Pauli, at most 2N virtual Clifford gates suffice; localization sequences are preferred when they preserve dormant |0⟩ states.Source: §2.3 · pp. 5–6

2.4 Active Operation Updates

  • A localized rotation on a dormant axis either contributes only a scalar phase or promotes that qubit and expands the active vector from dimension 2^k to 2^(k+1).Rotations on an already active axis update its tensor factor without changing k.Source: §2.4 · p. 6

Projective Pauli measurements.

Measurements shift their outcome according to the virtual Pauli frame and can contract the active subspace. The Clifford frame and active-set schedule are fixed before sampling, leaving per-shot work in frame tracking and active-array operations, with dominant exponential cost set by peak active dimension.

Projective Pauli measurements.

  • An active-axis measurement applies the Pauli-frame-shifted projector, disentangles the measured axis, and returns it to the dormant set, reducing k by one.For a dormant axis, the state vector is unchanged; the outcome is deterministic up to the frame shift or uniformly random with a deterministic basis update.Source: Projective Pauli measurements · p. 6

2.5 Coordinate-Amplitude Decoupling

  • The Clifford frame and active-set geometry are independent of stochastic errors, measurement outcomes, and active-state amplitudes, so kmax can be determined before sampling.Runtime sampling then performs Pauli-frame updates, active-array operations, and measurement/noise sampling over a fixed compiled schedule.Source: §2.5 · p. 7

2.6 Asymptotic Complexity

  • Deterministic Clifford transformations and Pauli localization are compiled once per circuit before repeated sampling.The pipeline resolves Clifford-coordinate evolution, optimization, localization, and active-space planning ahead of time.Source: §2.6 · pp. 7–8, Figure 2 · p. 8
  • Per-shot cost is independent of passive Clifford-gate count C and combines O((T + M + E)N) bookkeeping with active-state traversals scaling with 2^kmax.In the near-Clifford regimes studied, active-array traversals typically dominate while full-N dependence is confined to lightweight updates.Source: §2.6 · p. 8

3 Clifft Compilation and Execution

Clifft compiles deterministic Clifford-coordinate changes ahead of time, then executes a fixed schedule over a frame-factored state. Its pipeline optimizes virtual-basis operations and specializes them to runtime work on the active state.

3.1 Compilation Pipeline

  • SVM bytecode specializes optimized HIR to the frame-factored runtime, distinguishing frame updates, active-state work, dormant and active measurements, and noise sampling.Bytecode optimization fuses active-state expansion with a T update and coalesces adjacent noise instructions to reduce traversals and dispatch overhead.Source: Figure 4 · p. 9, §3.1 · p. 10

3 Clifft Compilation and Execution

  • The compiler turns physical circuits into optimized SVM bytecode through four stages, separating HIR construction and optimization from runtime-state specialization.Each shot then follows a fixed schedule of Pauli-frame updates, stochastic sampling, classical control, and localized active-state operations.Source: §3 · p. 8, §3.1 · p. 9

3.1 Compilation Pipeline

  • HIR represents active operations in a shared virtual basis while passive Clifford effects persist in transformed generators; optimization can reorder operations to reduce peak active dimension.The HIR optimizations are not specific to the SVM and could target other back ends.Source: §3.1 · pp. 9–10

3.2 Sampling with the Schrödinger Virtual Machine

  • The SVM reuses fixed per-shot storage and targets active-array traversal with SIMD kernels and fused operations, while sparse-noise sampling jumps directly to realized faults.For rare logical errors, it also supports fault-count-conditioned, importance-weighted batches; rejected shots can terminate early through post-selection instructions.Source: §3.2 · pp. 10–11

3.3 Validation

  • Clifft validates its simulation through interface contracts, structured reversible and stress-test circuits, and cross-checks against dense state-vector simulation and Stim.The cross-checks cover small-circuit states, noisy-QEC statistics, and deterministic-fault detector trajectories.Source: §3.3 · p. 11

4 Benchmarks and Results

Clifft is benchmarked across Clifford, near-Clifford, and dense circuits, then used for end-to-end magic state cultivation. The results show threshold-dependent T/S discrepancies in the full protocol and strongest simulation performance on low-magic circuits.

4.1 Benchmarks

  • In the pure-Clifford limit, Stim retains a roughly 10× throughput advantage because Clifft maintains its frame-factored representation even when kmax = 0.Stim also benefits from SIMD parallelism across many shots.Source: §4.1 · p. 12
  • On tested fixed-noise cultivation instances, Clifft has a roughly 370× throughput advantage over Tsim at d=3; Tsim did not compile the d=5 circuit within two minutes, while Clifft sustains 314k shots/s.The d=3 and d=5 cultivation circuits have peak active dimensions kmax = 4 and kmax = 10, respectively.Source: §4.1 · p. 12
  • As kmax grows from 5 to 24, Clifft’s throughput decreases by several orders of magnitude as the active state vector exceeds CPU cache size.Tsim did not compile within the time budget for larger repeated-round coherent-noise instances.Source: §4.1 · pp. 12–13
  • Clifft’s clearest advantage is on low-magic circuits with large physical qubit counts and modest active dimension; in the dense limit, it tracks leading CPU state-vector simulators within a small constant factor.The dense Quantum Volume benchmark reaches kmax = N and reports this behavior up to N = 28.Source: §4.1 · p. 13, Figure 5 · p. 14

4.2.1 Inject and Cultivate Stage

  • At d=5 and p = 5 × 10−4, the inject-and-cultivate T/S error ratio reaches approximately 30×, exceeding the roughly 15× ratio found by prior works.The statistical bands widen at lower noise rates, though the data suggest the discrepancy increases over the studied range.Source: §4.2.1 · p. 15, Figure 6 · p. 15
  • Clifft reaches comparable low-rate d=5 cultivation estimates in approximately 12 machine-hours, versus approximately 388 machine-hours for SOFT.The comparison uses one 16-core CPU instance for Clifft and a 16-H800 GPU cluster for SOFT.Source: §4.2.1 · p. 15, Table 2 · p. 16

4.2.2 End-to-End Cultivation Including the Escape Stage

  • 390 billion T-gate shots were collected at d=5 and 3 billion at d=3 for direct end-to-end simulations without importance sampling.The deep decoder-gap tail at d=5 remained shot-starved, with widening 95% credible intervals.Source: §4.2.2 · p. 16
  • At low decoder-gap thresholds, escape-stage failures make the end-to-end T/S curves overlap; at higher thresholds, the ratio approaches the larger inject-and-cultivate discrepancy.The cultivation-stage discrepancy predicts high-confidence end-to-end behavior, while the escape decoder controls how quickly that regime is reached.Source: §4.2.2 · p. 16, Figure 7 · p. 17

5 Conclusion

Clifft combines frame factoring with an active state vector to simulate near-Clifford circuits exactly. It performs well on low-magic fault-tolerant circuits and supports end-to-end magic state cultivation simulations through the escape stage.

5 Conclusion

  • Clifft factors the state into offline Clifford and online Pauli frames plus an active state vector, confining sample-time dense evolution to active dimension k.The architecture shifts deterministic Clifford-coordinate tracking to compile time while retaining exact treatment of noise, mid-circuit measurement, and classical control.Source: §5 · p. 17
  • Clifft enabled exact end-to-end magic state cultivation simulation through the escape stage, over hundreds of billions of shots on commodity CPUs.The full-protocol simulations show the T-gate versus S-proxy discrepancy becoming visible once decoder-gap post-selection suppresses escape-stage-dominated failures.Source: §5 · p. 17
  • Clifft remained competitive in the dense-state limit, degraded gracefully in the pure-Clifford limit, and showed its clearest advantage on low-magic circuits with modest kmax despite large physical size.The simulations find the full-protocol T-gate versus S-proxy discrepancy persists and becomes visible when decoder-gap post-selection suppresses escape-stage-dominated failures.Source: §5 · p. 17
  • Better scheduling and localization heuristics may reduce kmax, while broader gate support would expand Clifft's target protocols.The passage also identifies coherent-noise approximation and system improvements such as memory layout, dispatch overhead, GPU execution, and vectorization as future directions.Source: §5 · p. 17
  • HIR exposes non-Clifford structure and supports circuit specialization in Clifft, with potential use in Clifford+T optimization, compiler-tool integration, and new backends.The authors characterize frame-factored exact simulation as a middle ground between pure stabilizer simulation and dense state-vector methods.Source: §5 · p. 17

A Constructive Proof of Pauli Localization

The constructive proof gives an O(N) sequence of two-qubit gates that localizes a multi-qubit virtual Pauli operator to one virtual qubit. It handles operators with X support and pure Z strings using different pivot-based gate sequences.

A Constructive Proof of Pauli Localization

  • For nonzero X support, choose a pivot with x_v = 1 and apply CNOT gates from that pivot to each other qubit with X support.This removes those X-support components while updating the Z-support vector.Source: A Constructive Proof of Pauli… · p. 20
  • After that CNOT sequence, CZ gates from the pivot to each remaining Z-supported qubit eliminate off-pivot Z support, leaving X_v or Y_v.If the result is Y_v, a virtual phase gate can convert it to the desired single-qubit form.Source: A Constructive Proof of Pauli… · p. 21
  • For a pure Z string, choose a pivot with z_v = 1 and apply CNOT gates from each other Z-supported qubit into the pivot, leaving Z_v.Source: A Constructive Proof of Pauli… · p. 21
  • The greedy localization sequence uses at most O(N) two-qubit gates and isolates the operator without spreading support to previously cleared qubits.Each gate monotonically erases generator support on the qubit being cleared.Source: A Constructive Proof of Pauli… · pp. 20–21

B Active Operations in the Frame-Factored Representation

This section describes how active operations are evaluated in the frame-factored representation.

B Active Operations in the Frame-Factored Representation

B.1 Pauli Rotations

A physical non-Clifford rotation is mapped into the virtual frame, localized to one qubit, and evaluated against the active state vector. Depending on whether that qubit is dormant or already active, the operation can leave the active dimension unchanged, expand it, or rotate an existing active component.

B.1 Pauli Rotations

  • A physical rotation exp(−iθPq) maps its generator to a multi-qubit virtual string, which the localization sequence reduces to a single-qubit Pauli.For a T gate, Pq = Zq and θ = π/8.Source: §B.1 · p. 21
  • If localization yields X or Y, a virtual basis change is appended to make the rotation act around the Z axis, with α absorbed into θ when needed.Source: §B.1 · p. 21
  • Commuting the localized rotation past the virtual Pauli frame extracts a deterministic sign set by whether that frame anticommutes with Z_v.The sign bit c is 1 for anticommutation and 0 otherwise.Source: §B.1 · p. 21
  • When v is dormant and the generator is Z_v, the rotation contributes only a global scalar, leaving the active vector and dimension unchanged.Source: §B.1 · p. 21
  • When a dormant qubit requires a Hadamard, it joins the active set in |+⟩, increasing k by one; an already active qubit instead receives the diagonal phase directly.Source: §B.1 · p. 21

B.2 Projective Pauli Measurements

Physical measurements are converted to virtual-basis projectors, with the Pauli frame shifting the measurement branch. Dormant qubits stay outside the active state vector, while active qubits are measured and demoted.

B.2 Projective Pauli Measurements

  • The Pauli frame shifts the projector branch by p, which is 1 when the virtual observable anticommutes with the frame and 0 otherwise.The physical outcome is therefore deterministically inverted when p = 1.Source: §B.2 · p. 22
  • For a dormant qubit measured in Z, the virtual outcome is deterministic and no state-vector update is needed; an X measurement is random and leaves the qubit dormant after a frame update.For the X case, a virtual Hadamard is absorbed into the Clifford and Pauli frames to restore the dormant |0⟩ convention.Source: §B.2 · p. 22
  • For an active qubit, the shifted projector acts on its tensor factor, disentangles it, and demotes it to the dormant set, reducing active dimension by one.Z measurements mask amplitudes, while X measurements fold amplitudes across the measured axis.Source: §B.2 · p. 22

B.3 Conditional Pauli Operations

Conditional Pauli operations are handled through discrete frame updates rather than amplitude changes. The physical Pauli is mapped into the virtual basis and combined with the existing frame.

B.3 Conditional Pauli Operations

  • Feed-forward corrections and stochastic noise bypass Pauli localization because they do not perturb amplitudes.A classical boolean c represents either a deterministic measurement outcome or a sampled error event.Source: §B.3 · p. 22
  • The physical Pauli E is mapped to a virtual Pauli string, and its conditional product with the existing frame becomes a new phase-free frame plus a scalar phase.Closure of the N-qubit Pauli group enables this discrete frame update.Source: §B.3 · p. 22

C Measuring the T state fidelity on the surface code

The section estimates escaped logical T-state fidelity from a decoder-corrected logical Y expectation. Its conservativeness relies on an expected logical-error hierarchy under the studied surface-code noise and decoder.

C Measuring the T state fidelity on the surface code

  • A Clifft-native expectation-value probe measures logical YL after decoder correction because the relevant basis is not available as a standard transversal measurement.The resulting estimate applies in the regime studied in the section.Source: C Measuring the T state fidelity on… · p. 23
  • The reported infidelity is a conservative upper bound on true infidelity when the stated inequality holds.That inequality is expected for the surface-code escape stage under the symmetric circuit-level noise and decoder used here.Source: C Measuring the T state fidelity on… · p. 23
  • Residual logical errors are modeled as an effective logical Pauli channel after syndrome extraction and decoding.Logical errors that anticommute with the measured observable attenuate its expectation value.Source: C Measuring the T state fidelity on… · p. 23
  • The decoder-corrected logical Y expectation gives a conservative estimate of escaped T-state fidelity because logical Y errors are expected to be much rarer than X and Z errors.For the studied d = 15 surface code under uniform circuit-level depolarizing noise at p = 0.003, the experiments confirm P(YL) ≪ P(XL), P(ZL).Source: C Measuring the T state fidelity on… · p. 23

D Bayesian Credible Intervals for Rate Ratios

The appendix estimates uncertainty in the ratio of two event rates with Bayesian credible intervals. These ratio intervals apply to the lower panels of Figures 6 and 7, not the separate absolute-rate bands.

D Bayesian Credible Intervals for Rate Ratios

  • The ratio of two event probabilities is estimated by sampling independent Beta posteriors and taking elementwise ratios.The event counts use binomial likelihoods with Jeffreys priors.Source: D Bayesian Credible Intervals for Rate… · p. 24
  • The median ratio sample is the point estimate, and the 2.5th and 97.5th percentiles define the 95% Bayesian credible interval.Under the model and prior, the posterior probability that the true ratio lies in the interval is 95%.Source: D Bayesian Credible Intervals for Rate… · p. 24
  • The described ratio intervals cover only the lower panels of Figures 6 and 7; upper-panel absolute error-rate bands use a separate rare-event visualization convention.The separate convention is implemented in Stim/Sinter.Source: D Bayesian Credible Intervals for Rate… · p. 24

Related papers

Loading 2604.27058v2…