Rare Event Simulation of Quantum Error-Correcting Circuits

Technical Summary: Rare Event Simulation of Quantum Error-Correcting Circuits

Problem Statement
Assessing the logical failure rates of Quantum Error-Correcting (QEC) circuits is critical for determining the viability of fault-tolerant quantum computing, particularly in the "teraquop" regime where physical error rates must reach $10^{-12}$. Standard Monte Carlo (MC) simulations, the de facto approach for studying circuit failure rates, become computationally infeasible as physical error rates ($p$) decrease. In low-$p$ regimes, the number of independent runs required to observe even a single logical failure grows exponentially. For strictly fault-tolerant circuits, the logical failure rate scales as $p = \Omega(p^{\lceil d/2 \rceil})$, where $d$ is the code distance. Consequently, estimating failure rates in the $10^{-20}$ regime via standard MC would require on the order of $10^{20}$ samples, a task beyond current classical computing capabilities. Existing rare event simulation techniques, such as those by Bravyi and Vargo [6], were limited to code capacity and phenomenological noise models and could not be directly applied to the more realistic circuit noise model, where errors propagate through specific gate sequences and syndrome extraction circuits.

Methodology
The authors propose a practical approach to access logical failure rates in low physical failure rate regimes by extending the "splitting method" (a Metropolis-Hastings algorithm) to the circuit noise model. The core methodology involves:

1. Splitting Technique: Instead of simulating the entire circuit at a low target failure rate $p_t$, the method estimates the ratio of failure rates between a sequence of intermediate physical failure rates $p_1, p_2, \dots, p_t$. The initial rate $p_1$ is chosen high enough for standard MC to be efficient, while subsequent rates are lowered incrementally. The total failure rate is reconstructed by multiplying these ratios.
2. Adaptation to Circuit Noise: Unlike previous works that operated on decoder graphs (edges), this work modifies the state space of the Markov Chain Monte Carlo (MCMC) to consist of sets of physical (gate, fault) pairs. The Metropolis routine is redesigned to select and toggle specific gate-fault tuples rather than edges in a decoding graph. This ensures the simulation respects the physical constraints of the circuit, such as error propagation through CNOT or CPHASE gates during syndrome extraction.
3. Reversible Markov Chain (RIMC): The authors define a transition protocol that satisfies the detailed balance equation. The routine selects a (gate, fault) tuple uniformly at random and proposes a state change (adding, removing, or altering a fault). Acceptance probabilities are calculated based on the specific failure probabilities of the gates and the conditional probabilities of the faults, ensuring the chain converges to the correct stationary distribution of failing events.
4. Extensions: The framework is extended to handle leakage (by including leakage paths in the state tuples) and post-selection (by allowing multi-gate alterations in the proposal step to maintain ergodicity in circuits with conditional state preparation).
5. Optimization: To mitigate the high computational cost of decoding, the authors implement a caching scheme that stores decoding outcomes for specific sets of gate faults, significantly reducing redundant decoder calls.

Key Contributions

• First Full Prescription for Circuit Noise: The authors claim to be the first to develop a complete prescription for rare event simulation using the splitting technique specifically for the circuit-based noise model. Previous applications were restricted to simpler noise models.
• Access to Ultra-Low Failure Rates: The method enables the estimation of logical failure rates down to the $10^{-20}$ regime, far beyond the reach of standard Monte Carlo simulations (which typically stall around $10^{-6}$).
• Validation: The results generated by the rare event simulation are confirmed to agree with standard Monte Carlo simulations in the "accessible regime" where both methods are feasible, providing empirical validation of the technique's correctness.
• Efficiency: The approach utilizes a caching mechanism that drastically reduces the number of calls to the decoder (e.g., Minimum Weight Perfect Matching), making the simulation of large code distances computationally tractable.

Results
The study focuses on the rotated surface code under a symmetric circuit noise model.

• Agreement with Monte Carlo: In the regime where physical error rates are between $10^{-4}$ and $10^{-3}$, the rare event simulation results align with unbiased negative binomial estimators from standard Monte Carlo runs.
• Scalability: The simulation successfully projects logical failure rates into the $10^{-20}$ range for the tested code distances.
• Decoder Efficiency: The use of caching significantly reduces the cumulative number of decoder calls required compared to a straightforward approach, demonstrating that the method is not only theoretically sound but practically efficient.
• Convergence: The authors provide empirical evidence of convergence using multiple independent Markov chains. Specifically, Figure 10 shows the mean and standard deviation of estimates from 20 independent runs for a distance 7 rotated surface code, demonstrating that the mean and standard deviation of estimates stabilize after a sufficient number of jumps and burn-in periods.

Significance and Claims
The paper asserts that this work provides a necessary tool for the quantum computing community to assess the performance of QEC designs in the teraquop regime without relying on unverified extrapolations. By bridging the gap between simple noise models and realistic circuit noise, the authors enable researchers to study the logical failure rates of large, fault-tolerant circuits under conditions that mirror future hardware requirements. The authors remain modest regarding statistical confidence intervals, noting that a rigorous quantification of confidence for the rare event estimates is left for future work. They also identify future directions, including the study of qubit leakage effects and circuits with dynamic sizes imposed by post-selections, acknowledging that the current study did not include the Pauli+ noise model or leakage in the primary results.