Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.35498

Fast and accurate rare-event simulation by Markov chain Monte Carlo for general quantum codes

Junichi Haruna, Kotaro Murakami

quant-phSubmitted Oct 26, 2026• Announced Oct 27, 2026• 0 citations
arXivHTMLPDF

Abstract

The splitting method estimates logical error rates of quantum error-correcting codes deep in the rare-event regime, where direct Monte Carlo sampling is prohibitively expensive. It relies on a Markov chain Monte Carlo (MCMC) sampler of faulty configurations, usually driven by one-bit-flip proposals. However, one-bit flips have been reported to be trapped on some codes, which biases the estimate. To address this issue, we propose a new kernel that combines locally balanced one-bit-flip proposals with a cluster-exchange move. We benchmark both kernels and direct Monte Carlo on twelve codes under code-capacity bit-flip noise in two ways, by comparing the mean fault weight with an MCMC-independent reference and by measuring the computation time to reach a fixed accuracy. In the first, our kernel agrees with the reference on every code, including those where one-bit flips are trapped. In the second, it is faster than one-bit flips wherever they are trapped, by orders of magnitude on some codes. Furthermore, at the lowest error rate, it is faster than direct Monte Carlo on every code, by more than four orders of magnitude on some.

AI Summary

Rare-event splitting estimates logical error rates using MCMC samples conditioned on decoder failure, but single-bit-flip chains can become trapped and bias the estimate. This paper tests whether richer proposals alleviate trapping across quantum codes. It combines locally balanced single-bit flips with weight-preserving exchanges of occupied and unoccupied qubits; the default exchanges two errors with probability $0.3$ per step. Benchmarks cover twelve surface, toric, asymmetric toric, concatenated Steane, hypergraph-product, and bivariate-bicycle codes under code-capacity bit-flip noise. Accuracy is assessed through the conditional mean fault weight against MCMC-independent weight-stratified sampling or direct Monte Carlo. Single-bit flips show substantial initialization-dependent or persistent bias on asymmetric toric and two bicycle codes. The combined kernel reproduces reference means after sufficient sampling, although some cases require longer runs than the initial benchmark. At $p=10^{-5}$, it reaches $2\%$ mean-weight accuracy faster than direct Monte Carlo on every tested code, with speedups exceeding $10^4$ on some. Against single-bit flips, speedups reach lower bounds of $530$–$1{,}400$ on selected trapping codes; without trapping, it is typically $2$–$5$ times slower. These are mean-weight benchmarks, not end-to-end logical-error-rate measurements; projected splitting costs rely on additional assumptions. Ergodicity is unproven, and matching one observable does not establish unbiased sampling. Splitting also requires a fixed failure set across ladder levels, which the tested error-rate-dependent BP-OSD decoders need not provide. A limited depolarizing-noise test reduces bias but does not pass convergence checks; circuit-level effectiveness remains untested.

Some signs of AI-generated textAI use disclosedStrong assumptionsMissing comparison
They assisted with drafting the manuscript and with writing the simulation and analysis code.

Error found: The measured mean-fault-weight speedups do not establish end-to-end logical-error-rate speedups, especially for BP+OSD ladders whose changing failure sets violate the fixed-set assumption of the stated splitting identity.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
23 pages, 3 figures, 8 tables

Related papers

Improved Methods for Determining Quantum Error Correcting Code Performance and Fault Tolerance

Michael Mullan, Matthew Weippert, Winton Brown

One of the central challenges in quantum error correction is determining the performance of a code in the low-error regimes needed to implement utility-scale computations. While performance at these error rates is not amenable to direct Monte Carlo simulation, it can be extrapolated from simulations at higher logical error rates, assuming the logical error rate scales predictably with increasing distance or decreasing physical error rate. However, the expected scaling depends sensitively on the minimum weight of uncorrectable error patterns. In many cases, the minimum weight is unknown since it depends not only on the theoretical code distance, but also on details of the implementation. Markov chain Monte Carlo (MCMC) methods, as adapted to quantum error correction by Bravyi and Vargo, provide a way to estimate logical failure rates in these low-error regimes via simulation. While offering significant gains over Monte Carlo, the described Metropolis algorithm makes small changes to the current logical failure patterns which results in slow convergence. In this paper, we argue that typical failure patterns include a large number of easily correctable errors that coexist alongside a malignant core. This observation motivates two new approaches to better evaluate code performance. First, we describe a pruning algorithm designed to obviate these correctable errors and focus on the problematic low-weight core. Second, we develop a novel family of Metropolis-Hastings algorithms, referred to as subregion MCMC. This technique is parameterized by the fraction of the error pattern that is resampled at each step, effectively interpolating between Monte Carlo and single step MCMC. We show that a judicious choice of this parameter results in far faster convergence than prior work.

quant-pharXiv:2607.27153•Jul 30, 2026•1 citation

Fail fast: techniques to probe rare events in quantum error correction

Michael E. Beverland, Malcolm Carroll, Andrew W. Cross +1 more

The ultimate goal of quantum error correction is to create logical qubits with very low error rates (e.g. 1e-12) and assemble them into large-scale quantum computers capable of performing many (e.g. billions) of logical gates on many (e.g. thousands) of logical qubits. However, it is necessarily difficult to directly assess the performance of such high-quality logical qubits using standard Monte Carlo sampling because logical failure events become very rare. Building on existing approaches to this problem, we develop three complementary techniques to characterize the rare-event regime for general quantum low-density parity-check (qLDPC) codes under circuit noise. (I) We propose a well-motivated, low-parameter ansatz for the failure spectrum (the fraction of fault sets of each size that fail) that empirically fits all the QEC systems we studied and predicts logical error rates at all physical error rates. (II) We find min-weight logical operators of syndrome measurement circuits and exactly compute the number of min-weight failing configurations. (III) We generalize the splitting method to qLDPC codes using multi-seeded Metropolis sampling to improve convergence for systems with many inequivalent logical operators. We apply these tools to distance-6, -12, and -18 bivariate bicycle codes under circuit noise, observing strong low-error-rate performance with the recently proposed Relay decoder but also considerable scope for further improvement.

quant-pharXiv:2511.15177•Nov 20, 2025•32 citations

Fast Accurate Quantum Monte Carlo without Metropolis Adjustment

Reuben Cohn-Gordon, Gabriel Pescia, Sumner N. Hearth +3 more

In quantum systems, physical quantities of interest can be expressed as expectation values of a probability distribution, which allows their estimation by Markov Chain Monte Carlo (MCMC) methods. This approach, an instance of Quantum Monte Carlo (QMC), plays a central role in obtaining predictions of system properties relevant to condensed matter and high energy physics. The use of Hamiltonian dynamics to design a Markov kernel, known as Hybrid or Hamiltonian Monte Carlo (HMC), is widespread in quantum applications. In this context, it is standard to use an HMC kernel that is ``adjusted'' with the Metropolis-Hastings (MH) criterion, so that estimates of expectations converge to their true value in the limit of infinite sample size. However, recent work in computational statistics suggests that an \emph{unadjusted} HMC kernel can be significantly more efficient, while safely maintaining an asymptotic bias which is small relative to the error arising from the variance of the finite sample size. We adapt this approach to the QMC setting, focusing on a challenging and high-dimensional \emph{spin-fermion} model of a quantum phase transition. We find that unadjusted methods outperform adjusted HMC in terms of effective sample size per gradient call, while retaining accurate results.

arXiv:2611.10187•Nov 6, 2026•0 citations

Experimental Realization of the Markov Chain Monte Carlo Algorithm on a Quantum Computer

Baptiste Claudon, Sergi Ramos-Calderer, Jean-Philip Piquemal

Quantum algorithms present a quadratically improved complexity over classical ones for certain sampling tasks. For instance, the Quantum Amplitude Estimation (QAE) algorithm promises to speed up the estimation of the mean of certain functions, given access to the quantum state corresponding to the probability distribution to be sampled from. Classically, samples are often obtained by simulating a Markov chain. In this work, we experimentally use encodings of Markov chains to prepare quantum states and run a quantum Markov Chain Monte Carlo (qMCMC) algorithm on Quantinuum System Model H2 and Quantinuum Helios quantum computers. We first demonstrate that it is possible to obtain accurate results by operating directly on the physical qubits. Crucially, to pave the way toward fault-tolerant execution, we also implement these algorithms using logical qubits protected by the Iceberg Quantum Error Detection (QED) code. By applying multiple rounds of mid-circuit QED during a random walk, we successfully catch and filter out hardware errors. These experiments demonstrate the feasibility of qMCMC on quantum hardware, bringing us closer to realizing quadratic quantum speedups with broad applications ranging from molecular modeling to machine learning and finance.

quant-pharXiv:2603.08395•Mar 10, 2026•1 citation

Rare Event Simulation of Quantum Error-Correcting Circuits

Carolyn Mayer, Anand Ganti, Uzoma Onunkwo +3 more

We describe a practical approach for accessing the logical failure rates of quantum error-correcting (QEC) circuits under low physical (component) failure rate regimes. Standard Monte Carlo is often the de facto approach for studying the failure rates of quantum circuits. However, in the study of fault-tolerant error-correcting circuits, the ability to extend this approach to low physical failure rates is limited. In particular, the use of Monte Carlo to access circuits that are relatively large or have high correcting power becomes more difficult as we lower the input failure rates of the individual components (gates) in the circuit. For these reasons, many simulations studying the circuit model go no lower than end-to-end logical failure rates in the 10 − 6 regime.In this report, we outline an approach that borrows from earlier work by Bravyi and Vargo \cite{bv13} to the more complex circuit noise model. Earlier works studied both the capacity and phenomenological noise models \cite{bv13,Beverland2019,bonilla2021xzzx}, but the work is insufficient for generating similar simulations in the circuit-noise model. To the best of our knowledge, our team is the first to develop a full prescription of the rare event simulation by splitting technique for the circuit-based noise model. We have also generated promising results that are confirmed by standard Monte Carlo simulation under an accessible regime. This work shows that we can access noise in the circuit-model prescription of quantum error-correcting code to failure rates below 10 − 20 regime.

arXiv:2509.13678•Quantum•Oct 15, 2026•18 citations

Efficient Markov chain Monte Carlo algorithm for the surface code

Adrian Hutter, James R. Wootton, Daniel Loss

Minimum-weight perfect matching (MWPM) has been the primary classical algorithm for error correction in the surface code, since it is of low runtime complexity and achieves relatively low logical error rates [Phys. Rev. Lett. 108, 180501 (2012)]. A Markov chain Monte Carlo (MCMC) algorithm [Phys. Rev. Lett. 109, 160503 (2012)] is able to achieve lower logical error rates and higher thresholds than MWPM, but requires a classical runtime complexity, which is super-polynomial in $L$, the linear size of the code. In this work we present an MCMC algorithm that achieves significantly lower logical error rates than MWPM at the cost of a runtime complexity increased by a factor $O({L}^{2})$. This advantage is due to taking correlations between bit- and phase-flip errors (as they appear, for example, in depolarizing noise) as well as entropic factors (i.e., the numbers of likely error paths in different equivalence classes) into account. For depolarizing noise with error rate $p$, we present an efficient algorithm for which the logical error rate is suppressed as $O({(p/3)}^{L/2})$ for $p\ensuremath{\rightarrow}0$---an exponential improvement over all previously existing efficient algorithms. Our algorithm allows for tradeoffs between runtime and achieved logical error rates as well as for parallelization, and can be also used for correction in the case of imperfect stabilizer measurements.

arXiv:1302.2669•Physical Review A•Feb 18, 2014•88 citations
The splitting method estimates logical error rates of quantum error-correcting codes deep in the rare-event regime, where direct Monte Carlo sampling is prohibitively expensive. It relies on a Markov chain Monte Carlo (MCMC) sampler of faulty configurations, usually driven by one-bit-flip proposals. However, one-bit flips have been reported to be trapped on some codes, which biases the estimate. To address this issue, we propose a new kernel that combines locally balanced one-bit-flip proposals with a cluster-exchange move. We benchmark both kernels and direct Monte Carlo on twelve codes under code-capacity bit-flip noise in two ways, by comparing the mean fault weight with an MCMC-independent reference and by measuring the computation time to reach a fixed accuracy. In the first, our kernel agrees with the reference on every code, including those where one-bit flips are trapped. In the second, it is faster than one-bit flips wherever they are trapped, by orders of magnitude on some codes. Furthermore, at the lowest error rate, it is faster than direct Monte Carlo on every code, by more than four orders of magnitude on some.
Rare-event splitting estimates logical error rates using MCMC samples conditioned on decoder failure, but single-bit-flip chains can become trapped and bias the estimate. This paper tests whether richer proposals alleviate trapping across quantum codes. It combines locally balanced single-bit flips with weight-preserving exchanges of occupied and unoccupied qubits; the default exchanges two errors with probability 0.30.30.3 per step.
Benchmarks cover twelve surface, toric, asymmetric toric, concatenated Steane, hypergraph-product, and bivariate-bicycle codes under code-capacity bit-flip noise. Accuracy is assessed through the conditional mean fault weight against MCMC-independent weight-stratified sampling or direct Monte Carlo. Single-bit flips show substantial initialization-dependent or persistent bias on asymmetric toric and two bicycle codes. The combined kernel reproduces reference means after sufficient sampling, although some cases require longer runs than the initial benchmark. At p=10−5p=10^{-5}p=10−5, it reaches 2%2\%2% mean-weight accuracy faster than direct Monte Carlo on every tested code, with speedups exceeding 10410^4104 on some. Against single-bit flips, speedups reach lower bounds of 530530530–1,4001{,}4001,400 on selected trapping codes; without trapping, it is typically 222–555 times slower.
These are mean-weight benchmarks, not end-to-end logical-error-rate measurements; projected splitting costs rely on additional assumptions. Ergodicity is unproven, and matching one observable does not establish unbiased sampling. Splitting also requires a fixed failure set across ladder levels, which the tested error-rate-dependent BP-OSD decoders need not provide. A limited depolarizing-noise test reduces bias but does not pass convergence checks; circuit-level effectiveness remains untested.
One of the central challenges in quantum error correction is determining the performance of a code in the low-error regimes needed to implement utility-scale computations. While performance at these error rates is not amenable to direct Monte Carlo simulation, it can be extrapolated from simulations at higher logical error rates, assuming the logical error rate scales predictably with increasing distance or decreasing physical error rate. However, the expected scaling depends sensitively on the minimum weight of uncorrectable error patterns. In many cases, the minimum weight is unknown since it depends not only on the theoretical code distance, but also on details of the implementation. Markov chain Monte Carlo (MCMC) methods, as adapted to quantum error correction by Bravyi and Vargo, provide a way to estimate logical failure rates in these low-error regimes via simulation. While offering significant gains over Monte Carlo, the described Metropolis algorithm makes small changes to the current logical failure patterns which results in slow convergence. In this paper, we argue that typical failure patterns include a large number of easily correctable errors that coexist alongside a malignant core. This observation motivates two new approaches to better evaluate code performance. First, we describe a pruning algorithm designed to obviate these correctable errors and focus on the problematic low-weight core. Second, we develop a novel family of Metropolis-Hastings algorithms, referred to as subregion MCMC. This technique is parameterized by the fraction of the error pattern that is resampled at each step, effectively interpolating between Monte Carlo and single step MCMC. We show that a judicious choice of this parameter results in far faster convergence than prior work.
The ultimate goal of quantum error correction is to create logical qubits with very low error rates (e.g. 1e-12) and assemble them into large-scale quantum computers capable of performing many (e.g. billions) of logical gates on many (e.g. thousands) of logical qubits. However, it is necessarily difficult to directly assess the performance of such high-quality logical qubits using standard Monte Carlo sampling because logical failure events become very rare. Building on existing approaches to this problem, we develop three complementary techniques to characterize the rare-event regime for general quantum low-density parity-check (qLDPC) codes under circuit noise. (I) We propose a well-motivated, low-parameter ansatz for the failure spectrum (the fraction of fault sets of each size that fail) that empirically fits all the QEC systems we studied and predicts logical error rates at all physical error rates. (II) We find min-weight logical operators of syndrome measurement circuits and exactly compute the number of min-weight failing configurations. (III) We generalize the splitting method to qLDPC codes using multi-seeded Metropolis sampling to improve convergence for systems with many inequivalent logical operators. We apply these tools to distance-6, -12, and -18 bivariate bicycle codes under circuit noise, observing strong low-error-rate performance with the recently proposed Relay decoder but also considerable scope for further improvement.
In quantum systems, physical quantities of interest can be expressed as expectation values of a probability distribution, which allows their estimation by Markov Chain Monte Carlo (MCMC) methods. This approach, an instance of Quantum Monte Carlo (QMC), plays a central role in obtaining predictions of system properties relevant to condensed matter and high energy physics. The use of Hamiltonian dynamics to design a Markov kernel, known as Hybrid or Hamiltonian Monte Carlo (HMC), is widespread in quantum applications. In this context, it is standard to use an HMC kernel that is ``adjusted'' with the Metropolis-Hastings (MH) criterion, so that estimates of expectations converge to their true value in the limit of infinite sample size. However, recent work in computational statistics suggests that an \emph{unadjusted} HMC kernel can be significantly more efficient, while safely maintaining an asymptotic bias which is small relative to the error arising from the variance of the finite sample size. We adapt this approach to the QMC setting, focusing on a challenging and high-dimensional \emph{spin-fermion} model of a quantum phase transition. We find that unadjusted methods outperform adjusted HMC in terms of effective sample size per gradient call, while retaining accurate results.
Quantum algorithms present a quadratically improved complexity over classical ones for certain sampling tasks. For instance, the Quantum Amplitude Estimation (QAE) algorithm promises to speed up the estimation of the mean of certain functions, given access to the quantum state corresponding to the probability distribution to be sampled from. Classically, samples are often obtained by simulating a Markov chain. In this work, we experimentally use encodings of Markov chains to prepare quantum states and run a quantum Markov Chain Monte Carlo (qMCMC) algorithm on Quantinuum System Model H2 and Quantinuum Helios quantum computers. We first demonstrate that it is possible to obtain accurate results by operating directly on the physical qubits. Crucially, to pave the way toward fault-tolerant execution, we also implement these algorithms using logical qubits protected by the Iceberg Quantum Error Detection (QED) code. By applying multiple rounds of mid-circuit QED during a random walk, we successfully catch and filter out hardware errors. These experiments demonstrate the feasibility of qMCMC on quantum hardware, bringing us closer to realizing quadratic quantum speedups with broad applications ranging from molecular modeling to machine learning and finance.
We describe a practical approach for accessing the logical failure rates of quantum error-correcting (QEC) circuits under low physical (component) failure rate regimes. Standard Monte Carlo is often the de facto approach for studying the failure rates of quantum circuits. However, in the study of fault-tolerant error-correcting circuits, the ability to extend this approach to low physical failure rates is limited. In particular, the use of Monte Carlo to access circuits that are relatively large or have high correcting power becomes more difficult as we lower the input failure rates of the individual components (gates) in the circuit. For these reasons, many simulations studying the circuit model go no lower than end-to-end logical failure rates in the 10 − 6 regime.In this report, we outline an approach that borrows from earlier work by Bravyi and Vargo \cite{bv13} to the more complex circuit noise model. Earlier works studied both the capacity and phenomenological noise models \cite{bv13,Beverland2019,bonilla2021xzzx}, but the work is insufficient for generating similar simulations in the circuit-noise model. To the best of our knowledge, our team is the first to develop a full prescription of the rare event simulation by splitting technique for the circuit-based noise model. We have also generated promising results that are confirmed by standard Monte Carlo simulation under an accessible regime. This work shows that we can access noise in the circuit-model prescription of quantum error-correcting code to failure rates below 10 − 20 regime.
Minimum-weight perfect matching (MWPM) has been the primary classical algorithm for error correction in the surface code, since it is of low runtime complexity and achieves relatively low logical error rates [Phys. Rev. Lett. 108, 180501 (2012)]. A Markov chain Monte Carlo (MCMC) algorithm [Phys. Rev. Lett. 109, 160503 (2012)] is able to achieve lower logical error rates and higher thresholds than MWPM, but requires a classical runtime complexity, which is super-polynomial in LLL, the linear size of the code. In this work we present an MCMC algorithm that achieves significantly lower logical error rates than MWPM at the cost of a runtime complexity increased by a factor O(L2)O({L}^{2})O(L2). This advantage is due to taking correlations between bit- and phase-flip errors (as they appear, for example, in depolarizing noise) as well as entropic factors (i.e., the numbers of likely error paths in different equivalence classes) into account. For depolarizing noise with error rate ppp, we present an efficient algorithm for which the logical error rate is suppressed as O((p/3)L/2)O({(p/3)}^{L/2})O((p/3)L/2) for $p\ensuremath{\rightarrow}0$---an exponential improvement over all previously existing efficient algorithms. Our algorithm allows for tradeoffs between runtime and achieved logical error rates as well as for parallelization, and can be also used for correction in the case of imperfect stabilizer measurements.