betaFeedback

WorksComputer Science

MASQ: Measurement-Adaptive Sampling for Near-Clifford Quantum Error Correction Circuits

Abstract

Classical sampling of quantum error correction (QEC) circuits supports fault-tolerant protocol evaluation, but estimating rare logical failures requires many independent shots. Frame-active-state simulators isolate non-stabilizer information in a dense active-state vector, yet dense-state processing remains exponential in the active width. This paper presents MASQ, an exact measurement-adaptive sampler for near-Clifford QEC circuits based on selective materialization of non-Clifford rotations. At each measurement boundary, MASQ materializes only rotations in a measurement-relevant closure capturing direct and indirect non-commuting dependencies, deferring the rest to limit active-state expansion. Stabilizer-assisted elimination further removes rotations certified to be invisible to all future measurements. A circuit-dependent schedule is computed once and shared across shots, while adaptive caching of conditional Born probabilities and batched execution reduce repeated sampling work while preserving the measurement-record distribution. Across 19 QEC benchmarks, MASQ reduces peak active width by up to 40 active virtual qubits and achieves up to 8,098-fold CPU throughput speedup over Clifft on multi-round circuits.

Introduction

Quantum error correction (QEC) protects logical information by encoding it across physical qubits, enabling fault-tolerant quantum computing (FTQC) [1]–[3]. Because large-scale, repeated hardware evaluation remains challenging, classical simulation is widely used to assess protocol reliability [4]–[7]. Direct calculation of measurement probabilities or logical error rates (LERs) under a noise model can be costly as fault and outcome combinations grow with circuit size [8]–[10]. Sampling instead tracks one realization of noise and measurement outcomes per shot, using repeated shots to estimate LER statistically [11]–[13]. In the fault-tolerant regime, rare logical failures require many shots [6], [14]–[16], making shot-generation throughput critical.

Clifford circuits with Pauli noise and measurements admit compact stabilizer-tableau representations [17]. Stim [11] exploits this structure by preprocessing deterministic Clifford structure and propagating stochastic Pauli errors and measurement-result changes. However, FTQC requires non-Clifford resources such as TT gates, which arise in magic-state injection, distillation, and cultivation. These resources and coherent noise can generate non-stabilizer information that a single tableau or Pauli frame cannot represent, making exact near-Clifford sampling substantially more expensive [10].

Clifford-compatible or stochastic Pauli approximations retain efficient stabilizer sampling [7], [18] but can bias LER and threshold estimates by altering non-Clifford dynamics [19], [20]. Exact methods avoid this approximation error but remain

Frame–active-state hybrid methods isolate non-stabilizer degrees of freedom in a dense active vector while handling Clifford–Pauli structure through compact frames. Clifft [12] maintains a frame-factored state with 2k2^k amplitudes for kk active virtual qubits, and SymFT [13] reduces per-shot frame updates and bookkeeping through symbolic Clifford–Pauli factorization and offline stabilizer-coordinate planning. Nevertheless, dense-state processing remains O(2k)O(2^k), making peak active width kmax⁡k_{\max} a central bottleneck.

Our key observation is that not all unresolved non-Clifford information must be materialized to evaluate the current measurement. We propose MASQ (Measurement-Adaptive Sampling for QEC), an exact sampler for near-Clifford QEC circuits. MASQ keeps rotations pending, constructs a measurement-relevant closure at each boundary, and materializes only the rotations in that closure. The closure captures both direct measurement dependencies and earlier rotations connected through non-commuting dependencies, while other rotations remain pending for later measurements. MASQ further uses stabilizer-equivalent relations to eliminate measurement-invisible rotations whose effects can be moved beyond all future measurements. Together, they reduce avoidable active-state growth and exponential cost.

By retaining only measurement-relevant non-Clifford information at each boundary, MASQ exposes recurring probability-determining contexts that adaptive caching exploits to reuse conditional Born probabilities. These optimizations preserve conditional Born probabilities at every boundary and therefore the joint measurement-record distribution. Across 19 QEC benchmarks, MASQ reduces peak active width by up to 40 active virtual qubits and achieves CPU throughput gains up to 8,098× over Clifft and 1,267× over CPU SymFT on multi-round surface-code circuits, while completing circuits where existing exact simulators hit memory or compilation limits. A numerical correctness validation further confirms that MASQ reproduces baseline Born probabilities within 1.17×10−171.17 \times10^{-17} across 15 benchmarks with available baselines.

Background and Motivation

Frame-Factored State Representation

Frame-factored simulation separates Clifford–Pauli transformations from quantum information that must be tracked explicitly using dense amplitudes. At any point along a shot trajectory, an NN-qubit physical state ∣Ψ⟩|\Psi\rangle is represented as

∣Ψ⟩=UCPF(∣ϕ⟩A⊗∣0⟩D),(1)|\Psi\rangle= U_C P_F (|\phi\rangle_A \otimes|0\rangle_D), \tag*{(1)}

where UCU_C is the Clifford frame representing deterministic Clifford operations and PFP_F is the Pauli frame containing shot-dependent Pauli errors and corrections. The virtual qubits are partitioned into an active set AA and a dormant set DD, where A∩D=∅A \cap D = \varnothing and ∣A∣+∣D∣=N|A| + |D| = N. The active state ∣ϕ⟩A|\phi\rangle_A stores the remaining quantum information, whereas each dormant coordinate is fixed to ∣0⟩|0\rangle in the virtual basis.

Each dormant coordinate vv satisfies Zv∣0⟩v=∣0⟩vZ_v|0\rangle_v = |0\rangle_v. More generally, if a state ∣χ⟩|\chi\rangle satisfies S∣χ⟩=ϵ∣χ⟩S|\chi\rangle= \epsilon|\chi\rangle for a Hermitian Pauli operator SS and ϵ∈{+1,−1}\epsilon\in\{+1,-1\}, then ϵS\epsilon S is a stabilizer of ∣χ⟩|\chi\rangle [11]. The Pauli stabilizers of a state form a commuting group with independent generators, while information not captured by these relations is retained in the dense active state. For an active width k=∣A∣k = |A|, ∣ϕ⟩A|\phi\rangle_A contains 2k2^k complex amplitudes rather than the 2N2^N amplitudes of a full state vector.

Because the active state is expressed in the virtual basis defined by UCU_C, physical Pauli axes must first be mapped into this basis. For physical rotation and measurement axes QphysQ_{\mathrm{phys}} and MphysM_{\mathrm{phys}}, respectively, the corresponding virtual axes are

Q=UC†QphysUC,M=UC†MphysUC.(2)Q = U_C^\dagger Q_{\mathrm{phys}} U_C,\qquad M = U_C^\dagger M_{\mathrm{phys}} U_C. \tag*{(2)}

Since UCU_C is Clifford, the mapped axes remain signed Pauli operators [34]. A deterministic Clifford gate CC is absorbed into the Clifford frame as UC←CUCU_C \leftarrow C U_C, whereas a physical Pauli operation EE is mapped to the virtual basis and accumulated as PF←(UC†EUC)PFP_F \leftarrow(U_C^\dagger E U_C)P_F. Neither update directly modifies ∣ϕ⟩A|\phi\rangle_A or changes the active width kk.

A nonidentity virtual Pauli string can be mapped to a single virtual coordinate through Pauli localization [35]:

VQV†=ησv,σv∈{Xv,Yv,Zv},η∈{−1,+1}.(3)V Q V^\dagger= \eta\sigma_v,\qquad\sigma_v \in\{X_v,Y_v,Z_v\},\quad\eta\in\{-1,+1\}. \tag*{(3)}

The same localization applies to a measurement axis MM. Here, VV is a change of virtual coordinates rather than an additional physical gate, and the corresponding representation is updated consistently so that the physical state in Eq. (1) remains unchanged. Below, QQ and MM denote the signed Pauli axes in the current virtual coordinates.

Non-Clifford Rotations and Pauli Measurements

Unlike Clifford and Pauli operations, a non-Clifford rotation can introduce non-stabilizer information that cannot be absorbed into either frame. A rotation about a Hermitian Pauli axis QQ is defined as

RQ(θ)=e−iθQ/2.(4)R_Q(\theta) = e^{-i\theta Q/2}. \tag*{(4)}

Its interaction with the Pauli frame follows

RQ(θ)PF=PFRQ((−1)ω(Q,PF)θ),(5)R_Q(\theta)P_F = P_F R_Q\left((-1)^{\omega(Q,P_F)}\theta\right), \tag*{(5)}

where ω(⋅,⋅)∈{0,1}\omega(\cdot,\cdot) \in\{0,1\} is the commutation parity, with 0 and 1 denoting commutation and anticommutation, respectively. If the localized coordinate vv is already active, the rotation updates the existing 2k2^k amplitudes without changing kk. If vv is dormant and the rotation introduces non-stabilizer information, the simulator promotes it to the active set as A←A∪{v}A \leftarrow A \cup\{v\}, D←D∖{v}D \leftarrow D \setminus\{v\}, and k←k+1k \leftarrow k+1, doubling the dense active-state size from 2k2^k to 2k+12^{k+1}.

Pauli measurements can conversely reduce the active width. Let b~∈{0,1}\tilde b \in\{0,1\} denote the measurement outcome in the virtual-state representation, with projector Πb~(M)=[I+(−1)b~M]/2\Pi_{\tilde b}(M) = [I + (-1)^{\tilde b}M]/2 for a virtual measurement axis MM. When the localized measurement acts on an active coordinate, its Born probability is pb~=∥Πb~(M)∣ϕ⟩A∥2p_{\tilde b} = \|\Pi_{\tilde b}(M)|\phi\rangle_A\|^2, where identity factors outside AA are omitted. The simulator samples b~\tilde b from {p0,p1}\{p_0,p_1\} and updates the active state as ∣ϕ⟩A←Πb~(M)∣ϕ⟩A/pb~|\phi\rangle_A \leftarrow\Pi_{\tilde b}(M)|\phi\rangle_A/\sqrt{p_{\tilde b}}. The recorded physical outcome is b=b~⊕ω(M,PF)b = \tilde b \oplus\omega(M,P_F), where PFP_F is evaluated immediately before measurement, so an anticommuting Pauli frame reverses the sampled virtual outcome.

After an active coordinate is measured, it can be returned to the dormant set once the post-measurement Pauli eigenstate is factored out and the frame representation is updated to restore the dormant-state convention ∣0⟩v|0\rangle_v. The simulator then moves vv from AA to DD and decreases kk by one, halving the dense active-state size from 2k2^k to 2k−12^{k-1}.

If a localized measurement instead acts on a dormant coordinate, the outcome is determined or sampled from its stabilizer relation and the resulting state change can be represented through Clifford–Pauli frame updates without dense-state projection or an increase in kk. Consequently, Clifford and Pauli operations leave the active width unchanged, whereas non-Clifford rotations and measurements can introduce and remove active degrees of freedom, respectively.

Active-Width Bottleneck and Measurement Relevance

The exponential component of frame-factored simulation is governed by the active width kk rather than directly by the total physical-qubit count NN. Let kmax⁡k_{\max} denote the maximum active width during circuit execution. The dense active state requires O(2kmax⁡)O(2^{k_{\max}}) peak memory, while a non-Clifford rotation, Born probability evaluation, or projection on a width-kk active state requires O(2k)O(2^k) dense-state work. Total execution time additionally depends on the number of such operations and on frame-management and localization overheads.

When kmax⁡≪Nk_{\max} \ll N, frame-factored simulation confines the exponential state representation to a much smaller subspace than the full 2N2^N state vector. Its cost nevertheless remains exponentially sensitive to active-state growth, particularly when non-Clifford rotations accumulate before measurements remove their associated active degrees of freedom. For example, Clifft reduces kmax⁡k_{\max} through equivalence-preserving Heisenberg IR (HIR) reordering that pushes commuting non-Clifford operations later and measurements earlier [12]. Even with this optimization, its coherent-noise QEC evaluation reports kmax⁡k_{\max} values from 5 to 24, over which sampling throughput decreases by several orders of magnitude. These results highlight that active-state growth remains a central scalability bottleneck.

This motivates reducing active-state work beyond commutation-based scheduling when only exact measurement statistics, rather than the full quantum state, must be preserved [36], [37]. MASQ combines measurement-relevant closures at measurement boundaries with stabilizer-assisted elimination, which uses state-dependent equivalent axes to certify rotations as invisible to all future measurements. The resulting probability-determining contexts enable adaptive reuse of conditional Born probabilities across noisy shots.

Illustrative materialization schedules for frame-factored simulation

Figure 1. Illustrative materialization schedules for frame-factored simulation. (a) An eager execution without commutation-based scheduling. (b) MASQ materializes only rotations in each measurement-relevant closure and eliminates those certified to be invisible to future measurements, reducing the peak active width from kmax⁡=3k_{\max}=3 to rmax⁡=2r_{\max}=2 in this example.

MASQ: Proposed Method

Fig. 1 illustrates the materialization behavior of MASQ relative to an eager frame-factored execution without commutation-based scheduling. In the eager execution, non-Clifford rotations are materialized as encountered, whereas MASQ keeps rotations pending and materializes only those required at each measurement boundary in their original circuit order. Rotations irrelevant to the current measurement remain pending, while those certified to be invisible to all future measurements are eliminated. The following analysis establishes when these transformations preserve the conditional Born probabilities and the measurement-record distribution.

Measurement-Adaptive Active-State Reduction

Let mm denote the number of measurements, MnM_n the virtual Pauli axis of the nnth measurement, and GnG_n the gate segment between Mn−1M_{n-1} and MnM_n, with G1G_1 starting at circuit initialization. As defined in Section II-B, b~n\tilde{b}_n denotes the virtual outcome used for active-state projection, whereas bnb_n denotes the recorded physical measurement bit. A shot produces the measurement record b=(b1,…,bm)\mathbf{b}=(b_1,\ldots,b_m) by sequentially sampling conditional Born probabilities. All commutation tests below are performed with the corresponding rotation and measurement axes expressed in the same virtual coordinates.

Commutation-Based Rotation Deferral. Consider a pending rotation RQ(ϑ)R_Q(\vartheta), where ϑ\vartheta denotes its effective angle including the shot-dependent Pauli-frame sign. If ω(Q,Mn)=0\omega(Q,M_n)=0, the rotation commutes with either measurement projector:

Πb~(Mn)RQ(ϑ)=RQ(ϑ)Πb~(Mn).(6)\Pi_{\tilde{b}}(M_n)R_Q(\vartheta)=R_Q(\vartheta)\Pi_{\tilde{b}}(M_n). \tag*{(6)}

For a normalized virtual state ∣ψ⟩|\psi\rangle, the Born probability of outcome b~\tilde{b} is therefore

Pr⁡(b~)=⟨ψ∣RQ†(ϑ)Πb~(Mn)RQ(ϑ)∣ψ⟩=⟨ψ∣Πb~(Mn)∣ψ⟩.(7)\Pr(\tilde{b})=\langle\psi|R_Q^\dagger(\vartheta)\Pi_{\tilde{b}}(M_n)R_Q(\vartheta)|\psi\rangle=\langle\psi|\Pi_{\tilde{b}}(M_n)|\psi\rangle. \tag*{(7)}

Thus, when considered in isolation, a rotation commuting with MnM_n can be moved beyond the measurement without changing its conditional Born probabilities [36], provided that its effect remains pending afterward. Pauli-frame propagation can change the effective angle sign according to Eq. (5), but does not change the Pauli commutation relations used for dependency analysis.

Measurement-Relevant Closure. Commutation with MnM_n alone is insufficient when multiple rotations are pending because an earlier rotation can affect the measurement indirectly through a later non-commuting rotation. Let Ln\mathcal{L}_n denote the ordered set of rotation indices pending immediately before MnM_n, where the indices preserve their original circuit order. MASQ first identifies the rotations that directly anticommute with the measurement:

Cn(0):={a∈Ln:ω(Qa,Mn)=1}.(8)\mathcal{C}_n^{(0)}:=\{a\in\mathcal{L}_n:\omega(Q_a,M_n)=1\}. \tag*{(8)}

It then recursively adds an earlier rotation whenever it anticommutes with an already selected later rotation:

Cn(s+1)=Cn(s)∪{a∈Ln:∃c∈Cn(s), a<c, ω(Qa,Qc)=1}.(9)\mathcal{C}_n^{(s+1)}=\mathcal{C}_n^{(s)}\cup\{a\in\mathcal{L}_n:\exists c\in\mathcal{C}_n^{(s)},\ a<c,\ \omega(Q_a,Q_c)=1\}. \tag*{(9)}

The fixed point Cn=Cn(s∗)\mathcal{C}_n=\mathcal{C}_n^{(s^*)} is the measurement-relevant closure of MnM_n. Rotations in Cn\mathcal{C}_n are materialized before MnM_n in their original circuit order, while the remaining set Dn=Ln∖Cn\mathcal{D}_n=\mathcal{L}_n\setminus\mathcal{C}_n remains pending for subsequent boundaries. The procedure therefore assigns each retained rotation to the first measurement boundary at which it becomes required under the closure rule.

Preservation of Measurement Statistics. Let WXW_{\mathcal{X}} denote the product of effective rotations in X\mathcal{X} in circuit order. By construction, any deferred rotation preceding a selected one commutes with it; otherwise, Eq. (9) would include it in Cn\mathcal{C}_n, so the pending sequence can be reordered using only commuting swaps as WLn=WDnWCnW_{\mathcal{L}_n}=W_{\mathcal{D}_n}W_{\mathcal{C}_n}. Every rotation in Dn\mathcal{D}_n also commutes with MnM_n, since any directly anticommuting rotation belongs to Cn(0)\mathcal{C}_n^{(0)}. For either virtual outcome b~\tilde{b},

Πb~(Mn)WLn∣ϕ⟩=WDnΠb~(Mn)WCn∣ϕ⟩.(10)\Pi_{\tilde{b}}(M_n)W_{\mathcal{L}_n}|\phi\rangle=W_{\mathcal{D}_n}\Pi_{\tilde{b}}(M_n)W_{\mathcal{C}_n}|\phi\rangle. \tag*{(10)}

Because WDnW_{\mathcal{D}_n} is unitary, both sides of Eq. (10) have the same squared norm. Materializing only WCnW_{\mathcal{C}_n} therefore produces exactly the same conditional Born probabilities at MnM_n as immediate materialization of all pending rotations. After projection, WDnW_{\mathcal{D}_n} remains the pending operator relating the MASQ state to the fully materialized state, preserving the same invariant at subsequent boundaries.

Stabilizer-Assisted Elimination. Some rotations may remain unnecessary at every measurement boundary, and MASQ identifies them using stabilizer-equivalent representations that allow their effects to propagate beyond future measurements. For S∣ψ⟩=ϵ∣ψ⟩S|\psi\rangle=\epsilon|\psi\rangle with ϵ∈{+1,−1}\epsilon\in\{+1,-1\} and ω(S,Q)=0\omega(S,Q)=0, defining Q′=QSQ'=QS gives Q′∣ψ⟩=ϵQ∣ψ⟩Q'|\psi\rangle=\epsilon Q|\psi\rangle and, using Eq. (4), RQ′(ϵϑ)∣ψ⟩=RQ(ϑ)∣ψ⟩R_{Q'}(\epsilon\vartheta)|\psi\rangle=R_Q(\vartheta)|\psi\rangle [37].

For a subsequent rotation or measurement with Pauli axis OO, the equivalent axis satisfies ω(Q′,O)=ω(Q,O)+ω(S,O)\omega(Q',O)=\omega(Q,O)+\omega(S,O) (mod 2). Thus, if QQ anticommutes with OO, a currently valid stabilizer SS satisfying ω(Q,S)=0\omega(Q,S)=0 and ω(S,O)=1\omega(S,O)=1 makes Q′=QSQ' = QS commute with OO, allowing the equivalent rotation to propagate beyond that operation. MASQ applies this test sequentially through the remaining circuit while updating the valid stabilizer relations as the state evolves. If the candidate propagates beyond all remaining measurements, it is removed as measurement-invisible; otherwise, it is retained for measurement-relevant closure. Shot-dependent noise and measurement outcomes alter only the eigenvalue signs of these relations, whereas elimination depends only on commutation parity and preserves the subsequent measurement-outcome distribution, although the unmeasured final state may differ.

Stabilizer-equivalent axes are used only to certify elimination and do not replace the original axes of rotations retained in the runtime schedule, avoiding reliance on state-dependent equivalences that may no longer hold after projection.

Together, closure-based deferral and stabilizer-assisted elimination preserve the conditional virtual-outcome distribution at every measurement boundary. The corresponding physical measurement record is obtained as

bn=b~n⊕ω(Mn,PF,n),(11)b_n = \tilde{b}_n \oplus\omega(M_n,P_{F,n}), \tag*{(11)}

where PF,nP_{F,n} is the Pauli frame immediately before MnM_n. MASQ therefore preserves P(bn∣b1,…,bn−1)P(b_n \mid b_1,\ldots,b_{n-1}) for every physical-noise realization and measurement prefix. Thus, by the chain rule, P(b)=∏n=1mP(bn∣b1,…,bn−1)P(\mathbf{b}) = \prod_{n=1}^{m} P(b_n \mid b_1,\ldots,b_{n-1}) is identical to that of baseline exact simulation, preserving the complete measurement-record distribution.

With rmax⁡r_{\max} denoting MASQ’s peak active width, reducing the peak from kmax⁡k_{\max} to rmax⁡r_{\max} decreases the peak dense-state size by a factor of 2kmax⁡−rmax⁡2^{k_{\max}-r_{\max}}.

Algorithm Implementation

MASQ consists of compile-time rotation scheduling, schedule-driven shot sampling, and adaptive boundary caching. Algorithm 1 removes measurement-invisible rotations, determines the measurement boundary of each retained rotation, and generates a shared Rotation_Plan. The same plan is reused across all shots, while shot-dependent Pauli-frame effects are handled during runtime sampling.

Compile-Time Rotation Scheduling. The first phase of COMPILE_SCHEDULE performs stabilizer-assisted elimination. The compiler maintains independent Pauli eigenstate relations in a tableau TT and tests each candidate rotation using the relations valid at its circuit position. When the transported candidate axis PP anticommutes with a subsequent Pauli axis OO, the compiler searches for a valid stabilizer S∈⟨T⟩S \in\langle T\rangle satisfying ω(P,S)=0\omega(P,S)=0 and ω(S,O)=1\omega(S,O)=1. If no such relation exists, the rotation is retained. Because removing measurement-invisible rotations can restore discarded Pauli relations, the stabilizer tables are recomputed after each pass, and the procedure repeats until convergence.

The second phase constructs the measurement-relevant closures of the remaining rotations. Indices without an assigned boundary are maintained in the pending list L\mathcal{L}. After the rotations of segment GnG_n are appended to L\mathcal{L}, the compiler computes Cn\mathcal{C}_n according to Eq. (9), assigns its rotations to MnM_n in circuit order, and carries the remaining indices to the next boundary. The resulting Rotation_Plan stores {Gn,Mn,Cn}n=1m\{G_n,M_n,\mathcal{C}_n\}_{n=1}^{m} together with the axes, angles, and circuit identities of the retained rotations.

Algorithm 1 MASQ compilation and sampling

Figure 1 (PDF p. 4).

Schedule-Driven Shot Sampling. Each shot begins with the identity Pauli frame and the initial frame-factored state. Within each segment GnG_n, shot-dependent Pauli errors and feed-forward corrections are accumulated in FF, while non-Clifford rotations remain pending. MASQ fixes each effective angle ϑa\vartheta_a at the rotation’s original circuit position using Eq. (5) and preserves it until materialization. Immediately before MnM_n, only the rotations assigned to Cn\mathcal{C}_n are materialized in their original circuit order. MASQ then computes the virtual Born probabilities (p0,p1)(p_0,p_1) and samples b~n\tilde{b}_n. The recorded physical bit is obtained from Eq. (11), after which the active state is projected onto b~n\tilde{b}_n, and eligible measured coordinates are returned to the dormant representation. Repeating this procedure over all boundaries generates the measurement record b(i)\mathbf{b}^{(i)}.

Adaptive Boundary Caching

By restricting each boundary to the non-Clifford information required for its Born probabilities, MASQ defines compact probability-determining contexts that can recur across shots. Adaptive caching reuses the corresponding conditional Born probabilities when such contexts recur.

For shot ii, Γn(i)\Gamma_n^{(i)} represents the effective angle sign history of rotations materialized through boundary nn, with signs fixed at their original positions. MASQ constructs the cache key as

Key⁡n(i)=(n,Γn(i),b~1(i),…,b~n−1(i)).(12)\operatorname{Key}_n^{(i)} = \left(n,\Gamma_n^{(i)},\tilde{b}_1^{(i)},\ldots,\tilde{b}_{n-1}^{(i)}\right). \tag*{(12)}

For a fixed Rotation_Plan, identical keys represent the same sequence of materialized rotations and prior virtual

Algorithm 2  Adaptive boundary caching
function ADAPTIVE_SAMPLE_SHOTS(Rotation_Plan, Nshot)
    Run Nprobe uncached probe shots; measure τbase and initialize Cache
    for i = Nprobe + 1 to Nshot do
        F ← I; initialize sign context Γ and virtual-outcome history
        for n = 1 to m do
            Process Gn to update F and Γ; construct Key(i)n using Eq. (12)
            if Key(i)n ∈ Cache then
                Draw and append b̃n(i) from Cache[Key(i)n]
                bn(i) ← b̃n(i) ⊕ ω(Mn, F)
            else
                Reconstruct and complete shot i using the sampled prefix
                if size(Cache) < capacity(Cache) then update Cache
                break
        Update μ, τhit, τmiss, and D(i)
        if (i − Nprobe) % Ncheck = 0 and μτmiss + (1 − μ)τhit > τbase
        then
            if Cache is full then run remaining shots uncached; break
            Fit D(j) ≈ λjβ; N̂miss ← λ(Nshot − iβ)
            if N̂miss(τmiss − τhit) > (Nshot − i)(τbase − τhit) then
                Run the remaining shots using uncached SAMPLE_SHOTS
                break
    return b(1), …, b(Nshot)

projections, yielding the same conditional Born probabilities at MnM_n. The Cache maps each key to (p0,p1)(p_0,p_1).

On a cache hit, MASQ skips active-state reconstruction, non-Clifford rotation application, and Born probability evaluation and directly samples b~n\tilde{b}_n from the cached probabilities. The physical outcome bnb_n is then obtained from the current Pauli frame using (11). On a cache miss, MASQ evaluates the shot through the uncached sampling path, adds the newly computed boundary probabilities to the Cache, and completes the measurement record. At capacity, further cache growth cannot reduce misses, so MASQ switches to uncached sampling when (13) is violated. Because caching only reuses an already determined conditional probability distribution and each outcome is sampled independently from that distribution, caching does not alter the shot distribution.

Algorithm 2 summarizes adaptive caching, which begins with NprobeN_{\rm probe} uncached probe shots to measure τbase\tau_{\rm base} and initialize the Cache; these shots are retained in the final measurement records. During subsequent execution, τhit\tau_{\rm hit} and τmiss\tau_{\rm miss} denote the mean times of all-hit and miss-containing shots, respectively, while μ\mu denotes the observed miss ratio. Caching is currently beneficial when

μτmiss+(1−μ)τhit≤τbase.(13)\mu\tau_{\rm miss} + (1-\mu)\tau_{\rm hit} \le\tau_{\rm base}. \tag*{(13)}

Before capacity is reached, MASQ does not immediately disable caching when (13) is violated because future misses may decrease as the Cache grows. Let D(j)D(j) denote the number of distinct boundary keys observed after jj shots. MASQ fits D(j)≈λjβD(j)\approx\lambda j^\beta for 1≤j≤i1\le j\le i using least squares in the log domain and estimates the remaining miss-containing shots as N^miss=λ(Nshotβ−iβ)\hat{N}_{\rm miss}=\lambda(N_{\rm shot}^{\beta}-i^\beta). Caching is disabled when

N^miss(τmiss−τhit)>(Nshot−i)(τbase−τhit),(14)\hat{N}_{\rm miss}(\tau_{\rm miss}-\tau_{\rm hit})>(N_{\rm shot}-i)(\tau_{\rm base}-\tau_{\rm hit}), \tag*{(14)}

where the two sides estimate the future miss overhead and the maximum remaining cache-hit saving, respectively. Once disabled, remaining shots use uncached sampling.

Complexity. The compile-time cost of MASQ is dominated by stabilizer-assisted elimination and measurement-relevant closure construction. For NN virtual qubits, RR non-Clifford rotations, mm measurements, and LL circuit operations, these require O(R2LN2)O(R^2LN^2) and O(mR2)O(mR^2) time in the worst case, respectively. The resulting compile-time complexity is O(R2LN2+mR2)O(R^2LN^2+mR^2) with O(N2+R2+L+m)O(N^2+R^2+L+m) space, and this one-time cost is shared across all shots. Uncached sampling requires O(L+(R+m)2rmax⁡)O(L+(R+m)2^{r_{\max}}) time per shot and O(2rmax⁡)O(2^{r_{\max}}) dense-state memory. Caching avoids dense-state operations on a hit but does not increase the worst-case runtime of O(Nshot[L+(R+m)2rmax⁡])O(N_{\rm shot}[L+(R+m)2^{r_{\max}}]); with at most Dmax⁡D_{\max} cached contexts and SkeyS_{\rm key} storage per key, the total runtime space is O(2rmax⁡+N+L+R+m+Dmax⁡Skey)O(2^{r_{\max}}+N+L+R+m+D_{\max}S_{\rm key}).

Experimental Evaluation

Experimental Setup

We evaluate MASQ against the exact near-Clifford samplers Clifft [12], Tsim [31], and SymFT [13], with Stim [11] additionally evaluated on the pure-Clifford benchmark. Clifft is evaluated with its default HIR optimization pipeline, including active-width squeezing. The suite comprises 19 QEC circuits based on Clifft’s benchmarks: surface-code memories with coherent RZR_Z errors [32] (d=3,5,7,9d=3,5,7,9) or RXR_X errors (d=3,5d=3,5), magic-state distillation [38], magic-state cultivation [39] (d=3,5d=3,5), and a pure-Clifford surface-code memory (d=7d=7). We extend the original suite with multi-round RZR_Z circuits at d=7d=7 and a d=9d=9 circuit to evaluate larger instances. Coherent variants use RZ/RX(0.02)R_Z/R_X(0.02) at the corresponding noise locations.

CPU experiments use 16 physical cores of an Intel Xeon Gold 6246R with 614 GiB host memory; Tsim and SymFT are additionally evaluated on an RTX A6000. MASQ uses Nprobe=512N_{\rm probe}=512 shots, 64 shots per word for batched execution, and Ncheck=2048N_{\rm check}=2048 shots throughout. Every simulator is subject to a 600 s compilation limit per circuit, and sampling throughput and compilation time are reported separately. For runs reaching saturation, capacity, or halt after NwarmN_{\rm warm} shots, throughput is measured over the next NwarmN_{\rm warm} shots. The Cache is implemented as a per-core hash table capped at 2 GiB to bound memory overhead in multi-core execution. Thus, the reported points are averaged across cores.

Experimental Results

Shot-Sampling Throughput

Table I compares all CPU and GPU configurations at a Pauli error rate of 10−310^{-3}. MASQ samples all 19 circuits and achieves the highest throughput on 15, whereas Clifft and SymFT each encounter OOM on four circuits and Tsim exceeds the compilation limit on 12. Of these 12 DNC cases, 11 are coherent-error surface codes, consistent with Tsim’s exponential dependence on the number of non-Clifford gates [31]. For surface RZR_Z at d=5d=5, r=3r=3, MASQ reaches 7.45×1047.45\times10^4 shots/s, outperforming Clifft and CPU SymFT by 8,098× and 1,267×, respectively. For distillation, MASQ reaches 3.97×1073.97\times10^7 shots/s, corresponding to 7.65× and 3.68× speedups. The gains extend to coherent RXR_X errors: at r=1r=1, MASQ achieves 2.31×1072.31\times10^7 shots/s, 122× faster than Clifft and 384× faster than CPU SymFT. For pure Clifford, MASQ reaches 3.52×1073.52\times10^7 shots/s, 2.32× over Stim.

CircuitVariantddrrQubitsTsim [31]SymFT [13]Clifft [12]Tsim [31]SymFT [13]Stim [11]MASQ (Caching)kmax⁡k_{\max}rmax⁡r_{\max}tcompilet_{\mathrm{compile}}Max. ∣ΔP∣|\Delta P|Max. ∣Δlog⁡P∣|\Delta\log P|
SurfaceRZR_Z error911881.59×1071.59 \times10^{7}OOM*OOM2.66×1082.66 \times10^{8}OOM–1.16×1081.16 \times10^{8} (Halted)40017.99––
74DNCOOMOOMDNCOOM–3.02×10−13.02 \times10^{-1} (Halted)452532.84––
73118DNCOOMOOMDNCOOM–5.52×10−15.52 \times10^{-1} (Halted)452524.72––
72DNCOOMOOMDNCOOM–3.073.07 (Halted)452516.39––
712.75×1072.75 \times10^{7}2.58×10−12.58 \times10^{-1}1.734.65×1084.65 \times10^{8}5.53–1.96×1081.96 \times10^{8} (Halted)2403.900.00e+000.00\mathrm{e}+000.00e+000.00\mathrm{e}+00
5764DNC3.193.08DNC1.95×1011.95 \times10^{1}–1.98×1041.98 \times10^{4} (Halted)22139.723.73×10−253.73 \times10^{-25}2.06×10−132.06 \times10^{-13}
55DNC5.134.58DNC2.94×1012.94 \times10^{1}–3.14×1043.14 \times10^{4} (Halted)22136.979.10×10−249.10 \times10^{-24}2.49×10−132.49 \times10^{-13}
53DNC1.05×1011.05 \times10^{1}9.20DNC5.88×1015.88 \times10^{1}–7.45×1047.45 \times10^{4} (Halted)22134.229.31×10−239.31 \times10^{-23}7.46×10−147.46 \times10^{-14}
519.90×1079.90 \times10^{7}9.17×1049.17 \times10^{4}1.61×1051.61 \times10^{5}1.01×1091.01 \times10^{9}3.06×1053.06 \times10^{5}–2.72×1082.72 \times10^{8} (Halted)1200.670.00e+000.00\mathrm{e}+000.00e+000.00\mathrm{e}+00
3726DNC1.52×1061.52 \times10^{6}1.33×1061.33 \times10^{6}DNC2.53×1062.53 \times10^{6}–4.88×1064.88 \times10^{6} (2.24×1082.24 \times10^{8})750.791.95×10−181.95 \times10^{-18}2.13×10−142.13 \times10^{-14}
35DNC2.04×1062.04 \times10^{6}1.93×1061.93 \times10^{6}DNC3.24×1063.24 \times10^{6}–1.18×1071.18 \times10^{7} (1.46×1071.46 \times10^{7})750.563.25×10−183.25 \times10^{-18}1.07×10−141.07 \times10^{-14}
33DNC2.92×1062.92 \times10^{6}3.19×1063.19 \times10^{6}DNC5.85×1065.85 \times10^{6}–3.10×1073.10 \times10^{7} (7.01×1067.01 \times10^{6})750.353.47×10−183.47 \times10^{-18}7.11×10−157.11 \times10^{-15}
312.27×1082.27 \times10^{8}5.32×1065.32 \times10^{6}1.95×1071.95 \times10^{7}3.33×1093.33 \times10^{9}3.50×1073.50 \times10^{7}–8.00×1088.00 \times10^{8} (Halted)400.080.00e+000.00\mathrm{e}+000.00e+000.00\mathrm{e}+00
SurfaceRXR_X error3326DNC2.92×1042.92 \times10^{4}6.46×1046.46 \times10^{4}DNC1.75×1041.75 \times10^{4}–5.10×1065.10 \times10^{6} (6.09×1066.09 \times10^{6})14120.389.11×10−189.11 \times10^{-18}1.07×10−141.07 \times10^{-14}
31DNC8.85×1048.85 \times10^{4}1.90×1051.90 \times10^{5}DNC6.02×1046.02 \times10^{4}–2.31×1072.31 \times10^{7} (9.79×1069.79 \times10^{6})14110.101.17×10−171.17 \times10^{-17}7.11×10−157.11 \times10^{-15}
Cultivation–5–42DNC2.21×1052.21 \times10^{5}6.85×1056.85 \times10^{5}DNC5.24×1055.24 \times10^{5}–1.83×1061.83 \times10^{6} (1.60×1071.60 \times10^{7})†10100.141.55×10−251.55 \times10^{-25}2.57×10−142.57 \times10^{-14}
Cultivation–3–151.89×1041.89 \times10^{4}4.39×1064.39 \times10^{6}9.44×1069.44 \times10^{6}1.37×1021.37 \times10^{2}2.93×1072.93 \times10^{7}–4.57×1074.57 \times10^{7} (1.83×1061.83 \times10^{6})440.021.76×10−181.76 \times10^{-18}6.66×10−166.66 \times10^{-16}
Distillation–5–856.85×1056.85 \times10^{5}2.47×1062.47 \times10^{6}5.19×1065.19 \times10^{6}5.71×1045.71 \times10^{4}1.08×1071.08 \times10^{7}–3.97×1073.97 \times10^{7} (2.10×1052.10 \times10^{5})540.044.29×10−284.29 \times10^{-28}7.11×10−157.11 \times10^{-15}
SurfaceClifford771181.30×1061.30 \times10^{6}5.95×1055.95 \times10^{5}2.60×1062.60 \times10^{6}1.40×1071.40 \times10^{7}5.75×1065.75 \times10^{6}1.52×1071.52 \times10^{7}3.52×1073.52 \times10^{7} (Halted)000.090.00e+000.00\mathrm{e}+000.00e+000.00\mathrm{e}+00

Table I. Shot-sampling throughput (shots/s) and MASQ characteristics across 19 QEC circuits at a Pauli error rate of 10−310^{-3}. dd and rr denote code distance and measurement rounds; kmax⁡k_{\max} and rmax⁡r_{\max} denote the peak active widths for Clifft after HIR reordering and MASQ, respectively; tcompilet_{\mathrm{compile}} is the MASQ compilation time (s). Accuracy reports maximum absolute errors in Born probability and log probability, ∣ΔP∣|\Delta P| and ∣Δlog⁡P∣|\Delta\log P|, against the baseline. Parentheses report caching status or saturation/capacity point, when applicable.

CPU Tsim remains fastest on all single-round RZR_Z circuits, outperforming MASQ by 2.29–4.16×. For the executable d=3,5,7d=3,5,7 cases, Tsim exceeds Clifft by 171× to 2.69×1082.69\times10^8, whereas its advantage over MASQ remains only 2.37–4.16×. At d=9d=9, MASQ also completes sampling within 2.29× of

Tsim despite Clifft and SymFT encountering OOM. These MASQ runs have rmax⁡=0r_{\max} = 0, making the remaining gap consistent with residual frame and per-shot control overhead once dense-state processing is eliminated. Figure 2 examines throughput across the Pauli error rate for two representative d=3d = 3 cases where Tsim successfully compiles. In Figure 2(a), CPU Tsim leads at low error rates for the single-round surface RZR_Z circuit (d=3d = 3, r=1r = 1), but the curves cross at p=0.011p = 0.011 and approximately 3.9×1083.9 \times10^{8} shots/s as Tsim throughput decreases more sharply, with MASQ leading at higher error rates even within this Tsim-compatible subset. In Figure 2(b), for d=3d = 3 cultivation with caching enabled, MASQ maintains the highest throughput throughout the sweep, with its advantage widening at lower error rates, consistent with greater reuse of cached measurement contexts.

Throughput versus Pauli error rate

Figure 2. Throughput versus Pauli error rate for (a) surface RZR_Z (d=3d = 3, r=1r = 1) and (b) cultivation (d=3d = 3); MASQ caching is halted in (a) and active in (b).

  1. Active-State Reduction: MASQ reduces the peak active width in most near-Clifford benchmarks, with particularly large reductions on multi-round RZR_Z circuits: 22 →\to 13 at d=5d = 5 and 45 →\to 25 at d=7d = 7. Figure 3 illustrates the d=5d = 5, r=5r = 5 case, where Clifft directly reaches 2222^{22} amplitudes while MASQ limits the peak to 2132^{13}, reducing the peak dense-state size by 512×512 \times. MASQ’s one-time compilation takes at most 32.84 s across the evaluated circuits, and the resulting schedule is shared across all shots to amortize this cost.

Figure 3. Active-state size throughout the surface-code memory circuit with coherent RZR_Z errors (d=5d = 5, r=5r = 5). MASQ reduces the peak amplitude count from 2222^{22} to 2132^{13}.

  1. Adaptive Caching Performance: Table I shows that caching remains enabled for the d=3d = 3 multi-round RZR_Z circuits, both RXR_X variants, and the magic-state circuits, but is disabled elsewhere. Reported saturation/capacity points range from 2.10×1052.10 \times10^{5} to 2.24×1082.24 \times10^{8} shots, motivating runtime cache control rather than a uniform caching policy. Notably, d=3d = 3 cultivation has kmax⁡=rmax⁡=4k_{\max} = r_{\max} = 4, so its throughput improvement is achieved without reducing the peak active width.

Correctness Validation. Table I reports the maximum absolute and log Born-probability errors, ∣ΔP∣|\Delta P| and ∣Δlog⁡P∣|\Delta\log P|, between MASQ and Clifft over ample sampled shots. Comparisons match noise realizations and measurement outcomes, including cached execution where applicable. Across 15 circuits, the maximum ∣ΔP∣|\Delta P| is 1.17×10−171.17 \times10^{-17} for RXR_X (d=3d = 3, r=1r = 1), with double-precision roundoff, where ∣Δlog⁡P∣=7.11×10−15|\Delta\log P| = 7.11 \times10^{-15}.

Conclusion

This paper presented MASQ, an exact measurement-adaptive sampler that reduces the active-state bottleneck in near-Clifford QEC simulation through selective materialization of non-Clifford rotations. Measurement-relevant clouters defer rotations unnecessary for the current measurement, while stabilizer-assisted elimination removes rotations invisible to all future measurements; adaptive caching further reduces repeated work across shots. Across 19 QEC benchmarks, MASQ reduces peak active width by up to 40 active virtual qubits and achieves up to 8,098×\times CPU throughput speedup over Clifft on multi-round circuits, while completing circuits for which existing exact simulators hit memory or compilation limits. These results demonstrate that measurement-adaptive control of non-stabilizer information can substantially improve the practical scalability of exact QEC sampling while preserving the measurement-record distribution exactly.

References

  1. [1]L. Schmid, T. Peham, L. Berent, M. Müller, and R. Wille, “Deterministic fault-tolerant state preparation for near-term quantum error correction: Automatic synthesis using Boolean satisfiability,” in 2025 Design, Automation & Test in Europe Conference (DATE). IEEE, 2025, pp. 1–7.arxiv.org/abs/2501.05527
  2. [3]L. Lao and C. G. Almudever, “Fault-tolerant quantum error correction on near-term quantum processors using flag and bridge qubits,” Physical Review A, vol. 101, no. 3, p. 032333, 2020.DOI
  3. [4]K. Zhang, D. Gao, Z. Yang et al., “Optimal compilation of syndrome extraction circuits for general quantum LDPC codes,” in 2026 Design, Automation & Test in Europe Conference (DATE). IEEE, 2026, pp. 1–7.
  4. [6]Google Quantum AI and Collaborators, “Quantum error correction below the surface code threshold,” Nature, vol. 638, no. 8052, pp. 920–926, 2025.
  5. [7]J. Bausch, A. W. Senior, F. J. Heras et al., “Learning high-accuracy error decoding for quantum processors,” Nature, vol. 635, no. 8040, pp. 834–840, 2024.DOI
  6. [8]A. Cicero, M. A. Maleki, M. W. Azhar, A. F. Kockum, and P. Trancoso, “Simulation of quantum computers: Review and acceleration opportunities,” ACM Transactions on Quantum Computing, vol. 7, no. 1, pp. 1–35, 2025.DOI
  7. [10]K. Chen, L. Yu, W. Fang et al., “Verifying Fault-Tolerance of Quantum Error Correction Codes,” in Computer Aided Verification (CAV), ser. Lecture Notes in Computer Science, vol. 15934. Springer, 2025, pp. 3–27.arxiv.org/abs/2501.14380
  8. [11]C. Gidney, “Stim: a fast stabilizer circuit simulator,” Quantum, vol. 5, p. 497, 2021.DOI
  9. [12]B. A. Chase and F. Labib, “Cliff: Fast exact simulation of near-clifford quantum circuits,” arXiv preprint arXiv:2604.27058, 2026.arxiv.org/abs/2604.27058
  10. [13]W. Fang, H. Lou, and R. Li, “SymFT: Universal Fault-Tolerant Quantum Circuit Simulation via Symbolic Clifford–Pauli Frames and Stabilizer Coordinates,” arXiv preprint arXiv:2607.28600, 2026.arxiv.org/abs/2607.28600
  11. [14]S. Heuben, D. Winter, M. Rispler, and M. Müller, “Dynamical subset sampling of quantum error-correcting protocols,” Physical Review Research, vol. 6, no. 1, p. 013177, 2024.
  12. [16]F. Garcia-Herrero, J. Valls, L. Vergara-Picazo, and V. Torres, “Diversity Methods for Improving Convergence and Accuracy of Quantum Error Correction Decoders Through Hardware Emulation,” Quantum, vol. 10, p. 2071, 2026.DOI
  13. [17]S. Aaronson and D. Gottesman, “Improved simulation of stabilizer circuits,” Physical Review A—Atomic, Molecular, and Optical Physics, vol. 70, no. 5, p. 052328, 2004.DOI
  14. [18]S. Singh, F. Gu, S. De Boe et al., “Modular architectures and entanglement schemes for error-corrected distributed quantum computation,” npj Quantum Information, vol. 12, no. 1, p. 3, 2026.
  15. [19]S. R. Garner, N. M. Myers, M. Wang et al., “Simulation of thermal-relaxation noise for quantum error correction,” Physical Review Research, vol. 8, no. 2, p. 023134, 2026.DOI
  16. [20]Z. Schwartzman-Nowik, L. Shirizly, and H. Landa, “Modeling error correction with Lindblad dynamics and approximate channels,” Physical Review A, vol. 111, no. 2, p. 022613, 2025.
  17. [31]R. Haenel, X. Luo, and C. Zhao, “TSim: Fast universal simulator for quantum error correction,” arXiv preprint arXiv:2604.01059, 2026.arxiv.org/abs/2604.01059
  18. [32]T. Tuloup and T. Ayral, “Computing logical error thresholds with the Pauli Frame Sparse Representation,” arXiv preprint arXiv:2603.14670, 2026.arxiv.org/abs/2603.14670
  19. [34]D. Gottsman, “The Heisenberg Representation of Quantum Computers,” arXiv preprint quant-ph/9807006, 1998.arxiv.org/abs/quant-ph/9807006
  20. [35]G. Li, A. Wu, Y. Shi et al., “Paulihdral: A Generalized Block-Wise Compiler Optimization Framework for Quantum Simulation Kernels,” in Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2022, pp. 554–569.arxiv.org/abs/2109.03371
  21. [36]J. Paykin, A. T. Schmitz, M. Ibrahim, X.-C. Wu, and A. Y. Matsuura, “PCOAST: A Pauli-Based Quantum Circuit Optimization Framework,” in 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), vol. 01, 2023, pp. 715–726.arxiv.org/abs/2305.10966
  22. [37]A. T. Schmitz, M. Ibrahim, N. P. D. Sawaya et al., “Optimization at the Interface of Unitary and Non-unitary Quantum Operations in PCOAST,” arXiv preprint arXiv:2305.09843, 2023.arxiv.org/abs/2305.09843
  23. [38]P. Sales Rodriguez, J. M. Robinson, P. N. Jepsen et al., “Experimental demonstration of logical magic state distillation,” Nature, vol. 645, no. 8081, p. 620–625, 2025.
  24. [39]C. Gidney, N. Shutty, and C. Jones, “Magic state cultivation: growing T states as cheap as CNOT gates,” arXiv preprint arXiv:2409.17959, 2024.

Paper details

vlnc:W_3ktx63zp
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 6

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents