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:2002.05180 · IEEE Transactions on Information Theory

Beyond Single-Shot Fault-Tolerant Quantum Error Correction

Nicolas Delfosse, Ben W. Reichardt, Krysta M. Svore

Published Oct 16, 2021• 36 citations
arXivHTMLPDF

Abstract

Extensive quantum error correction is necessary in order to perform a useful computation on a noisy quantum computer. Moreover, quantum error correction must be implemented based on imperfect parity check measurements that may return incorrect outcomes or inject additional faults into the qubits. To achieve fault-tolerant error correction, Shor proposed to repeat the sequence of parity check measurements until the same outcome is observed sufficiently many times. Then, one can use this information to perform error correction. A basic implementation of this fault tolerance strategy requires$\Omega (r d^{2})$parity check measurements for a distance-$d$code defined by$r$parity checks. For some specific highly structured quantum codes, Bombin has shown that single-shot fault-tolerant quantum error correction is possible using only$r$measurements. In this work, we consider a phenomenological noise model for parity check measurements assuming that each bit of a codeword and the measurement outcome suffer from independent bit flips with some error rate$p$. For this model, we demonstrate that fault-tolerant quantum error correction can be achieved using$O(d \log (d))$measurements for any code with distance$d \geq \Omega (n^\alpha)$for some constant$\alpha > 0$. Moreover, we prove the existence of a sub-single-shot fault-tolerant quantum error correction scheme using fewer than$r$measurements. In some cases, the number of parity check measurements required for fault-tolerant quantum error correction is exponentially smaller than the number of parity checks defining the code. The short measurement sequences constructed generally have high weight and our phenomenological noise model is not realistic in this regime. Our error correction strategy could find applications to small codes and LDPC codes if one can manage to keep the weight of the measured parity checks low.

DOI
10.1109/tit.2021.3120685

Related papers

Short Shor-style syndrome sequences

Nicolas Delfosse, Ben W. Reichardt

We optimize fault-tolerant quantum error correction to reduce the number of syndrome bit measurements. Speeding up error correction will also speed up an encoded quantum computation, and should reduce its effective error rate. We give both code-specific and general methods, using a variety of techniques and in a variety of settings. We design new quantum error-correcting codes specifically for efficient error correction, e.g., allowing single-shot error correction. For codes with multiple logical qubits, we give methods for combining error correction with partial logical measurements. There are tradeoffs in choosing a code and error-correction technique. While to date most work has concentrated on optimizing the syndrome-extraction procedure, we show that there are also substantial benefits to optimizing how the measured syndromes are chosen and used. As an example, we design single-shot measurement sequences for fault-tolerant quantum error correction with the 16-qubit extended Hamming code. Our scheme uses 10 syndrome bit measurements, compared to 40 measurements with the Shor scheme. We design single-shot logical measurements as well: any logical Z measurement can be made together with fault-tolerant error correction using only 11 measurements. For comparison, using the Shor scheme a basic implementation of such a non-destructive logical measurement uses 63 measurements. We also offer ten open problems, the solutions of which could lead to substantial improvements of fault-tolerant error correction.

arXiv:2008.05051•Aug 12, 2020•37 citations

New methods in quantum error correction and fault-tolerant quantum computing

Christopher Chamberland

Quantum computers have the potential to solve several interesting problems in polynomial \ntime for which no polynomial time classical algorithms have been found. However, \none of the major challenges in building quantum devices is that quantum systems are very \nsensitive to noise arising from undesired interactions with the environment. Noise can lead \nto errors which can corrupt the results of the computation. Quantum error correction is \none way to mitigate the effects of noise arising in quantum devices. \nWith a plethora of quantum error correcting codes that can be used in various settings, \none of the main challenges of quantum error correction is understanding how well various \ncodes perform under more realistic noise models that can be observed in experiments. \nThis thesis proposes a new decoding algorithm which can optimize threshold values of \nerror correcting codes under different noise models. The algorithm can be applied to \nany Markovian noise model. Further, it is shown that for certain noise models, logical \nClifford corrections can further improve a code's threshold value if the code obeys certain \nsymmetries. \n \nSince gates and measurements cannot in general be performed with perfect precision, \nthe operations required to perform quantum error correction can introduce more errors \ninto the system thus negating the benefits of error correction. Fault-tolerant quantum \ncomputing is a way to perform quantum error correction with imperfect operations while \nretaining the ability to suppress errors as long as the noise is below a code's threshold. \nOne of the main challenges in performing fault-tolerant error correction is the high resource \nrequirements that are needed to obtain very low logical noise rates. With the use of \nflag qubits, this thesis develops new fault-tolerant error correction protocols that are applicable \nto arbitrary distance codes. Various code families are shown to satisfy the requirements \nof flag fault-tolerant error correction. We also provide circuits using a constant number of \nqubits for these codes. It is shown that the proposed flag fault-tolerant method uses fewer \nqubits than previous fault-tolerant error correction protocols. \n \nIt is often the case that the noise afflicting a quantum device cannot be fully characterized. \nFurther, even with some knowledge of the noise, it can be very challenging to use \nanalytic decoding methods to improve the performance of a fault-tolerant scheme. This \nthesis presents decoding schemes using several state of the art machine learning techniques \nwith a focus on fault-tolerant quantum error correction in regimes that are relevant to near \nterm experiments. It is shown that even in low noise rate regimes and with no knowledge \nof the noise, noise can be further suppressed for small distance codes. Limitations of machine \nlearning decoders as well as the classical resources required to perform active error \ncorrection are discussed. \n \nIn many cases, gate times can be much shorter than typical measurement times of \nquantum states. Further, classical decoding of the syndrome information used in quantum \nerror correction to compute recovery operators can also be much slower than gate times. \nFor these reasons, schemes where error correction can be implemented in a frame (known \nas the Pauli frame) have been developed to avoid active error correction. In this thesis, we \ngeneralize previous Pauli frame schemes and show how Clifford frame error correction can \nbe implemented with minimal overhead. Clifford frame error correction is necessary if the \nlogical component of recovery operators were chosen from the Clifford group, but could \nalso be used in randomized benchmarking schemes.

•Oct 22, 2018•0 citations

Fault-Tolerant Quantum Computation with Adversarial Errors

Nikolas P. Breuckmann, Louis Golowich, Umesh Vazirani

We prove a fault-tolerance theorem for quantum computation against adversarial noise. For every quantum circuit on $\bar{N}$ logical qudits of depth $\bar{T}$, we construct a fault-tolerant circuit on $N=\text{poly}(\bar{N})$ physical qudits of depth $\bar{T}\cdot\bar{N}^{o(1)}$, which is robust against an adversary who may arbitrarily choose and corrupt an almost-linear number $N^{1-o(1)}$ of physical qudits at each time step. This robustness significantly improves upon prior fault-tolerance theorems, which assumed corruptions were either local and stochastic, or else only act on a polynomially vanishing fraction of qudits. Our fault-tolerance scheme addresses a key bottleneck towards constructing quantum PCPs via the circuit-to-Hamiltonian mapping of Anshu, Breuckmann, and Nguyen (STOC'24). More fundamentally, our result demonstrates that fault-tolerant quantum computation remains possible under noise models that are global, worst-case, and non-Markovian over the full duration of the computation, directly countering concerns that correlated noise could fundamentally undermine quantum fault tolerance. Our construction is based on a new family of subsystem product codes we develop, which have large dimension and distance along with low-weight parity-checks, and which support transversal non-Clifford gates. We show how to perform single-shot fault-tolerant error correction on these codes using a Floquet-like procedure based on the local testability of classical tensor codes. We then obtain a universal fault-tolerance scheme using repeated code switching in a hypercubic qudit architecture. Finally, we recursively compose our scheme with itself to reduce an initially exponential qudit dimension down to a constant.

quant-pharXiv:2608.16857•Aug 18, 2026•0 citations

Practical fault-tolerant quantum computing

Naomi Nickerson

Quantum computing has the potential to transform information technology by offering algorithms for certain tasks, such as quantum simulation, that are vastly more efficient than what is possible with any classical device. But experimentally implementing practical quantum information processing is a very difficult task. Here we study two important, and closely related, aspects of this challenge: architectures for quantum computing, and quantum error correction Exquisite quantum control has now been achieved in small ion traps, in nitrogen-vacancy centres and in superconducting qubit clusters, but the challenge remains of how to scale these systems to build practical quantum devices. In Part I of this thesis we analyse one approach to building a scalable quantum computer by networking together many simple processor cells, thus avoiding the need to create a single complex structure. The difficulty is that realistic quantum links are very error prone. Here we describe a method by which even these error-prone cells can perform quantum error correction. Groups of cells generate and purify shared resource states, which then enable stabilization of topologically encoded data. Given a realistically noisy network (10% error rate) we find that our protocol can succeed provided that all intra-cell error rates are below 0.8%. Furthermore, we show that with some adjustments, the protocols we employ can be made robust also against high levels of loss in the network interconnects. We go on to analyse the potential running speed of such a device. Using levels of fidelity that are either already achievable in experimental systems, or will be in the near-future, we find that employing a surface code approach in a highly noisy and lossy network architecture can result in kilohertz computer clock speeds. In Part II we consider the question of quantum error correction beyond the surface code. We consider several families of topological codes, and determine the minimum requirements to demonstrate proof-of-principle error suppression in each type of code. A particularly promising code is the gauge color code, which admits a universal transversal gate set. Furthermore, a recent result of Bombin shows the gauge color code supports an error-correction protocol that achieves tolerance to noisy measurements without the need for repeated measurements, so called single-shot error correction. Here, we demonstrate the promise of single-shot error correction by designing a decoder and investigating its performance. We simulate fault-tolerant error correction with the gauge color code, and estimate a sustainable error rate, i.e. the threshold for the long time limit, of ~0.31% for a phenomenological noise model using a simple decoding algorithm.

•Dec 1, 2015•4 citations

Performance Limits of Fault-Tolerant Quantum Error Correction Schemes

Lorenzo Valentini, Diego Forlivesi, Marco Chiani

Quantum error correction (QEC) is essential for realizing scalable quantum computation. However, when evaluating its benefits, most analyses assume idealized components, overlooking the imperfections inherent in realistic fault-tolerant (FT) implementations. In this paper, we investigate the performance of QEC schemes taking into account that quantum gates and measurements are themselves error-prone. We derive bounds for the failure probability of Shor-style FT-QEC schemes using limited structural information, such as the number of flag qubits and quantum gates. Our analysis separates and quantifies two key contributors to the failure rate: decoding errors and residual errors arising from circuit-level faults. The derived bounds highlight fundamental limitations in Shor-style FT-QEC performance and quantify how circuit imperfections degrade error correction capabilities, under the assumption of depolarizing noise.

quant-pharXiv:2605.24501•IEEE Journal on Selected Areas in Communications•May 26, 2026•0 citations

Simplified circuit-level decoding using Knill error correction

Ewan Murphy, Subhayan Sahu, Michael Vasmer

Quantum error correction will likely be essential for building a large-scale quantum computer, but it comes with significant requirements at the level of classical control software. In particular, a quantum error-correcting code must be supplemented with a fast and accurate classical decoding algorithm. Standard techniques for measuring the parity-check operators of a quantum error-correcting code involve repeated measurements, which both increases the amount of data that needs to be processed by the decoder, and changes the nature of the decoding problem. Knill error correction is a technique that replaces repeated syndrome measurements with a single round of measurements, but requires an auxiliary logical Bell state. Here, we provide a theoretical and numerical investigation into Knill error correction from the perspective of decoding. We give a self-contained description of the protocol, prove its fault tolerance under locally decaying (circuit-level) noise, and numerically benchmark its performance for quantum low-density parity-check codes. We show analytically and numerically that the time-constrained decoding problem for Knill error correction can be solved using the same decoder used for the simpler code-capacity noise model, illustrating that Knill error correction may alleviate the stringent requirements on classical control required for building a large-scale quantum computer.

quant-pharXiv:2603.05320•Mar 6, 2026•1 citation
Extensive quantum error correction is necessary in order to perform a useful computation on a noisy quantum computer. Moreover, quantum error correction must be implemented based on imperfect parity check measurements that may return incorrect outcomes or inject additional faults into the qubits. To achieve fault-tolerant error correction, Shor proposed to repeat the sequence of parity check measurements until the same outcome is observed sufficiently many times. Then, one can use this information to perform error correction. A basic implementation of this fault tolerance strategy requiresΩ(rd2)\Omega (r d^{2})Ω(rd2)parity check measurements for a distance-dddcode defined byrrrparity checks. For some specific highly structured quantum codes, Bombin has shown that single-shot fault-tolerant quantum error correction is possible using onlyrrrmeasurements. In this work, we consider a phenomenological noise model for parity check measurements assuming that each bit of a codeword and the measurement outcome suffer from independent bit flips with some error rateppp. For this model, we demonstrate that fault-tolerant quantum error correction can be achieved usingO(dlog⁡(d))O(d \log (d))O(dlog(d))measurements for any code with distanced≥Ω(nα)d \geq \Omega (n^\alpha)d≥Ω(nα)for some constantα>0\alpha > 0α>0. Moreover, we prove the existence of a sub-single-shot fault-tolerant quantum error correction scheme using fewer thanrrrmeasurements. In some cases, the number of parity check measurements required for fault-tolerant quantum error correction is exponentially smaller than the number of parity checks defining the code. The short measurement sequences constructed generally have high weight and our phenomenological noise model is not realistic in this regime. Our error correction strategy could find applications to small codes and LDPC codes if one can manage to keep the weight of the measured parity checks low.
We optimize fault-tolerant quantum error correction to reduce the number of syndrome bit measurements. Speeding up error correction will also speed up an encoded quantum computation, and should reduce its effective error rate. We give both code-specific and general methods, using a variety of techniques and in a variety of settings. We design new quantum error-correcting codes specifically for efficient error correction, e.g., allowing single-shot error correction. For codes with multiple logical qubits, we give methods for combining error correction with partial logical measurements. There are tradeoffs in choosing a code and error-correction technique. While to date most work has concentrated on optimizing the syndrome-extraction procedure, we show that there are also substantial benefits to optimizing how the measured syndromes are chosen and used. As an example, we design single-shot measurement sequences for fault-tolerant quantum error correction with the 16-qubit extended Hamming code. Our scheme uses 10 syndrome bit measurements, compared to 40 measurements with the Shor scheme. We design single-shot logical measurements as well: any logical Z measurement can be made together with fault-tolerant error correction using only 11 measurements. For comparison, using the Shor scheme a basic implementation of such a non-destructive logical measurement uses 63 measurements. We also offer ten open problems, the solutions of which could lead to substantial improvements of fault-tolerant error correction.
Quantum computers have the potential to solve several interesting problems in polynomial \ntime for which no polynomial time classical algorithms have been found. However, \none of the major challenges in building quantum devices is that quantum systems are very \nsensitive to noise arising from undesired interactions with the environment. Noise can lead \nto errors which can corrupt the results of the computation. Quantum error correction is \none way to mitigate the effects of noise arising in quantum devices. \nWith a plethora of quantum error correcting codes that can be used in various settings, \none of the main challenges of quantum error correction is understanding how well various \ncodes perform under more realistic noise models that can be observed in experiments. \nThis thesis proposes a new decoding algorithm which can optimize threshold values of \nerror correcting codes under different noise models. The algorithm can be applied to \nany Markovian noise model. Further, it is shown that for certain noise models, logical \nClifford corrections can further improve a code's threshold value if the code obeys certain \nsymmetries. \n \nSince gates and measurements cannot in general be performed with perfect precision, \nthe operations required to perform quantum error correction can introduce more errors \ninto the system thus negating the benefits of error correction. Fault-tolerant quantum \ncomputing is a way to perform quantum error correction with imperfect operations while \nretaining the ability to suppress errors as long as the noise is below a code's threshold. \nOne of the main challenges in performing fault-tolerant error correction is the high resource \nrequirements that are needed to obtain very low logical noise rates. With the use of \nflag qubits, this thesis develops new fault-tolerant error correction protocols that are applicable \nto arbitrary distance codes. Various code families are shown to satisfy the requirements \nof flag fault-tolerant error correction. We also provide circuits using a constant number of \nqubits for these codes. It is shown that the proposed flag fault-tolerant method uses fewer \nqubits than previous fault-tolerant error correction protocols. \n \nIt is often the case that the noise afflicting a quantum device cannot be fully characterized. \nFurther, even with some knowledge of the noise, it can be very challenging to use \nanalytic decoding methods to improve the performance of a fault-tolerant scheme. This \nthesis presents decoding schemes using several state of the art machine learning techniques \nwith a focus on fault-tolerant quantum error correction in regimes that are relevant to near \nterm experiments. It is shown that even in low noise rate regimes and with no knowledge \nof the noise, noise can be further suppressed for small distance codes. Limitations of machine \nlearning decoders as well as the classical resources required to perform active error \ncorrection are discussed. \n \nIn many cases, gate times can be much shorter than typical measurement times of \nquantum states. Further, classical decoding of the syndrome information used in quantum \nerror correction to compute recovery operators can also be much slower than gate times. \nFor these reasons, schemes where error correction can be implemented in a frame (known \nas the Pauli frame) have been developed to avoid active error correction. In this thesis, we \ngeneralize previous Pauli frame schemes and show how Clifford frame error correction can \nbe implemented with minimal overhead. Clifford frame error correction is necessary if the \nlogical component of recovery operators were chosen from the Clifford group, but could \nalso be used in randomized benchmarking schemes.
We prove a fault-tolerance theorem for quantum computation against adversarial noise. For every quantum circuit on Nˉ\bar{N}Nˉ logical qudits of depth Tˉ\bar{T}Tˉ, we construct a fault-tolerant circuit on N=poly(Nˉ)N=\text{poly}(\bar{N})N=poly(Nˉ) physical qudits of depth Tˉ⋅Nˉo(1)\bar{T}\cdot\bar{N}^{o(1)}Tˉ⋅Nˉo(1), which is robust against an adversary who may arbitrarily choose and corrupt an almost-linear number N1−o(1)N^{1-o(1)}N1−o(1) of physical qudits at each time step. This robustness significantly improves upon prior fault-tolerance theorems, which assumed corruptions were either local and stochastic, or else only act on a polynomially vanishing fraction of qudits. Our fault-tolerance scheme addresses a key bottleneck towards constructing quantum PCPs via the circuit-to-Hamiltonian mapping of Anshu, Breuckmann, and Nguyen (STOC'24). More fundamentally, our result demonstrates that fault-tolerant quantum computation remains possible under noise models that are global, worst-case, and non-Markovian over the full duration of the computation, directly countering concerns that correlated noise could fundamentally undermine quantum fault tolerance. Our construction is based on a new family of subsystem product codes we develop, which have large dimension and distance along with low-weight parity-checks, and which support transversal non-Clifford gates. We show how to perform single-shot fault-tolerant error correction on these codes using a Floquet-like procedure based on the local testability of classical tensor codes. We then obtain a universal fault-tolerance scheme using repeated code switching in a hypercubic qudit architecture. Finally, we recursively compose our scheme with itself to reduce an initially exponential qudit dimension down to a constant.
Quantum computing has the potential to transform information technology by offering algorithms for certain tasks, such as quantum simulation, that are vastly more efficient than what is possible with any classical device. But experimentally implementing practical quantum information processing is a very difficult task. Here we study two important, and closely related, aspects of this challenge: architectures for quantum computing, and quantum error correction Exquisite quantum control has now been achieved in small ion traps, in nitrogen-vacancy centres and in superconducting qubit clusters, but the challenge remains of how to scale these systems to build practical quantum devices. In Part I of this thesis we analyse one approach to building a scalable quantum computer by networking together many simple processor cells, thus avoiding the need to create a single complex structure. The difficulty is that realistic quantum links are very error prone. Here we describe a method by which even these error-prone cells can perform quantum error correction. Groups of cells generate and purify shared resource states, which then enable stabilization of topologically encoded data. Given a realistically noisy network (10% error rate) we find that our protocol can succeed provided that all intra-cell error rates are below 0.8%. Furthermore, we show that with some adjustments, the protocols we employ can be made robust also against high levels of loss in the network interconnects. We go on to analyse the potential running speed of such a device. Using levels of fidelity that are either already achievable in experimental systems, or will be in the near-future, we find that employing a surface code approach in a highly noisy and lossy network architecture can result in kilohertz computer clock speeds. In Part II we consider the question of quantum error correction beyond the surface code. We consider several families of topological codes, and determine the minimum requirements to demonstrate proof-of-principle error suppression in each type of code. A particularly promising code is the gauge color code, which admits a universal transversal gate set. Furthermore, a recent result of Bombin shows the gauge color code supports an error-correction protocol that achieves tolerance to noisy measurements without the need for repeated measurements, so called single-shot error correction. Here, we demonstrate the promise of single-shot error correction by designing a decoder and investigating its performance. We simulate fault-tolerant error correction with the gauge color code, and estimate a sustainable error rate, i.e. the threshold for the long time limit, of ~0.31% for a phenomenological noise model using a simple decoding algorithm.
Quantum error correction (QEC) is essential for realizing scalable quantum computation. However, when evaluating its benefits, most analyses assume idealized components, overlooking the imperfections inherent in realistic fault-tolerant (FT) implementations. In this paper, we investigate the performance of QEC schemes taking into account that quantum gates and measurements are themselves error-prone. We derive bounds for the failure probability of Shor-style FT-QEC schemes using limited structural information, such as the number of flag qubits and quantum gates. Our analysis separates and quantifies two key contributors to the failure rate: decoding errors and residual errors arising from circuit-level faults. The derived bounds highlight fundamental limitations in Shor-style FT-QEC performance and quantify how circuit imperfections degrade error correction capabilities, under the assumption of depolarizing noise.
Quantum error correction will likely be essential for building a large-scale quantum computer, but it comes with significant requirements at the level of classical control software. In particular, a quantum error-correcting code must be supplemented with a fast and accurate classical decoding algorithm. Standard techniques for measuring the parity-check operators of a quantum error-correcting code involve repeated measurements, which both increases the amount of data that needs to be processed by the decoder, and changes the nature of the decoding problem. Knill error correction is a technique that replaces repeated syndrome measurements with a single round of measurements, but requires an auxiliary logical Bell state. Here, we provide a theoretical and numerical investigation into Knill error correction from the perspective of decoding. We give a self-contained description of the protocol, prove its fault tolerance under locally decaying (circuit-level) noise, and numerically benchmark its performance for quantum low-density parity-check codes. We show analytically and numerically that the time-constrained decoding problem for Knill error correction can be solved using the same decoder used for the simpler code-capacity noise model, illustrating that Knill error correction may alleviate the stringent requirements on classical control required for building a large-scale quantum computer.