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:quant-ph/9708021 · Fortschritte der Physik

Space, Time, Parallelism and Noise Requirements for Reliable Quantum Computing

Andrew M. Steane

Published Jun 1, 1998• 100 citations
arXivHTMLPDF

Abstract

Quantum error correction methods use processing power to combat noise. The noise level which can be tolerated in a fault-tolerant method is therefore a function of the computational resources available, especially the size of computer and degree of parallelism. I present an analysis of error correction with block codes, made fault-tolerant through the use of prepared ancilla blocks. The preparation and verification of the ancillas is described in detail. It is shown that the ancillas need only be verified against a small set of errors. This, combined with previously known advantages, makes this ’︁ancilla factory‚ the best method to apply error correction, whether in concatenated or block coding. I then consider the resources required to achieve 2 · 1010 computational steps reliably in a computer of 2150 logical qubits, finding that the simplest [[n, 1, d]] block codes can tolerate more noise with smaller overheads than the 7L-bit concatenated code. The scaling is such that block codes remain the better choice for all computations one is likely to contemplate.

DOI
10.1002/(sici)1521-3978(199806)46:4/5<443::aid-prop443>3.0.co;2-8

Related papers

Towards efficient fault-tolerant quantum computation

Yi-Cong Zheng

The threshold theorem indicates that if errors are all local and their rates are below a certain threshold, it is possible to implement large scale quantum computation with arbitrarily small error based on active quantum error correction (QEC). However, most fault-tolerant quantum computation (FTQC) schemes require enormous overhead to achieve this rate by increasing either the concatenation levels for concatenated codes or the distance (hence the size) for topological codes. As a result, a logical qubit is usually encoded in more than thousands of physical qubits, even when the error rate is below the threshold. In this thesis, we try to reduce the resource overhead of FTQC. We first study a quantum computation scheme using clouds of atoms trapped on atomic chips. It suggests that this scheme is robust to noise to some extent and has potential to be scalable. Secondly, we propose a FTQC scheme of encoding many logical qubits into large code blocks. The error performance of such scheme is numerically studied. Preparation of various ancilla states necessary for computation is also explored. Thirdly, we explore the idea of introducing energy gap to suppress thermal noise on each qubit. We show that fault-tolerant holonomic quantum computation (HQC) can be implemented in stabilizer codes with the existence of such energy protection. Especially, we studied fault-tolerant HQC in surface codes in detail. This scheme opens the possibility for self-correcting quantum computation in 2D lattice.

•Aug 6, 2015•0 citations

Fault-tolerant ancilla preparation and noise threshold lower bounds for the 23-qubit Golay code

Adam Paetznick, Ben W. Reichardt

In fault-tolerant quantum computing schemes, the overhead is often dominated by the cost of preparing codewords reliably. This cost generally increases quadratically with the block size of the underlying quantum error-correcting code. In consequence, large codes that are otherwise very efficient have found limited fault-tolerance applications. Fault-tolerant preparation circuits therefore are an important target for optimization. We study the Golay code, a $23$-qubit quantum error-correcting code that protects the logical qubit to a distance of seven. In simulations, even using a na{\"i}ve ancilla preparation procedure, the Golay code is competitive with other codes both in terms of overhead and the tolerable noise threshold. We provide two simplified circuits for fault-tolerant preparation of Golay code-encoded ancillas. The new circuits minimize error propagation, reducing the overhead by roughly a factor of four compared to standard encoding circuits. By adapting the malignant set counting technique to depolarizing noise, we further prove a threshold above $\threshOverlap$ noise per gate.

arXiv:1106.2190•Quantum Information and Computation•Nov 1, 2012•76 citations

Lower overhead fault-tolerant building blocks for noisy quantum computers

Prithviraj Prabhu

Quantum computation holds the promise of solving certain complex problems exponentially faster than classical computers. However, the high prevalent noise in current quantum devices impedes the accurate execution of even basic algorithms. This can be remedied by protecting quantum information with a quantum error-correcting code, where the logical information of an algorithmic qubit is spread across multiple physical qubits. Individual quantum errors are then located and corrected by the fault-tolerant measurement of multi-qubit stabilizer operators (parity checks). Unfortunately, error correction and fault tolerance both impose large demands on the qubit overhead: hundreds to thousands of physical qubits per logical qubit. We reduce the spacetime cost of fault tolerance by redesigning key building blocks of an error-corrected quantum computer. First, we develop a combinatorial proof with flag fault tolerance that exponentially reduces the extra qubits needed to measure a stabilizer of any size, while tolerating one fault. We leverage these proofs to then design state preparation circuits for the Steane and Golay codes with 100% yield. Next, we improve error correction on a planar layout by showing that a distance-four code encoding six logical qubits protects information as well as the distance-five surface code, using one-tenth as many physical qubits. Finally, we optimize the time overhead of logical gates in surface code quantum computers by protecting measurement results with a classical code, cutting computation time by a factor of two to six. Our hardware-agnostic optimizations of fault tolerance overheads thus suggest new routes to advance the timeline of error-free quantum computing.

quant-pharXiv:2605.12385•May 13, 2026•0 citations

Efficient preparation of large-block-code ancilla states for fault-tolerant quantum computation

Yi-Cong Zheng, Ching–Yi Lai, Todd A. Brun

Fault-tolerant quantum computation (FTQC) schemes that use multiqubit large block codes can potentially reduce the resource overhead to a great extent. A major obstacle is the requirement for a large number of clean ancilla states of different types without correlated errors inside each block. These ancilla states are usually logical stabilizer states of the data-code blocks, which are generally difficult to prepare if the code size is large. Previously, we have proposed an ancilla distillation protocol for Calderbank-Shor-Steane (CSS) codes by classical error-correcting codes. It was assumed that the quantum gates in the distillation circuit were perfect; however, in reality, noisy quantum gates may introduce correlated errors that are not treatable by the protocol. In this paper, we show that additional postselection by another classical error-detecting code can be applied to remove almost all correlated errors. Consequently, the revised protocol is fully fault tolerant and capable of preparing a large set of stabilizer states sufficient for FTQC using large block codes. At the same time, the yield rate can be boosted from $O({t}^{\ensuremath{-}2})$ to $O(1)$ in practice for an $[[n,k,d=2t+1]]$ CSS code. Ancilla preparation for the [[23,1,7]] quantum Golay code is numerically studied in detail through Monte Carlo simulation. The results support the validity of the protocol when the gate failure rate is reasonably low. To the best of our knowledge, this approach is one of the first attempts to prepare general large block stabilizer states free of correlated errors for FTQC in a fault-tolerant and efficient manner.

arXiv:1710.00389•Physical Review A•Mar 21, 2018•14 citations

Overhead and noise threshold of fault-tolerant quantum error correction

Andrew M. Steane

Fault-tolerant quantum error correction (QEC) networks are studied by a combination of numerical and approximate analytical treatments. The probability of failure of the recovery operation is calculated for a variety of Calderbank-Shor-Steane codes, including large block codes and concatenated codes. Recent insights into the syndrome extraction process, which render the whole process more efficient and more noise tolerant, are incorporated. The average number of recoveries that can be completed without failure is thus estimated as a function of various parameters. The main parameters are the gate $\ensuremath{\gamma}$ and memory $\ensuremath{\epsilon}$ failure rates, the physical scale-up of the computer size, and the time ${t}_{m}$ required for measurements and classical processing. The achievable computation size is given as a surface in parameter space. This indicates the noise threshold as well as other information. It is found that concatenated codes based on the $[[23,1,7]]$ Golay code give higher thresholds than those based on the $[[7,1,3]]$ Hamming code under most conditions. The threshold gate noise ${\ensuremath{\gamma}}_{0}$ is a function of $\ensuremath{\epsilon}/\ensuremath{\gamma}$ and ${t}_{m};$ example values are ${\ensuremath{\epsilon}/\ensuremath{\gamma}{,t}_{m},{\ensuremath{\gamma}}_{0}}={{1,1,10}^{\ensuremath{-}3}},$ ${0.01,1,3\ifmmode\times\else\texttimes\fi{}{10}^{\ensuremath{-}3}},$ ${{1,100,10}^{\ensuremath{-}4}},$ ${0.01,100,2\ifmmode\times\else\texttimes\fi{}{10}^{\ensuremath{-}3}},$ assuming zero cost for information transport. This represents an order of magnitude increase in tolerated memory noise, compared with previous calculations, which is made possible by recent insights into the fault-tolerant QEC process.

arXiv:quant-ph/0207119•Physical Review A•Oct 22, 2003•389 citations

The effect of the ancilla verification on the quantum error correction

Ali Abu-Nada

Communication is the prototypical application of error-correction methods. To communicate, a sender needs to convey information to a receiver over a noisy "communication channel." Such a channel can be thought of as a means of transmitting an information-carrying physical system from one place to another. During transmission, the physical system is subject to disturbances (noise) that can adversely affect the information carried. To use a communication channel, the sender needs to encode the information to be transmitted in the physical system. After transmission, the receiver decodes the information. Quantum error correction is used in quantum computing to protect quantum information from errors due to decoherence and other quantum noise. Quantum error correction is essential if one is to achieve fault-tolerant quantum computation that can deal with both noise on stored quantum information, and also with faulty quantum gates, faulty quantum preparation,and faulty measurements. In this dissertation, we look at how additional information about the structure of the quantum circuit and noise can improve or alter the performance of techniques in quantum error correction. Chapter 1 and 2, are an introduction to the quantum computation, quantum error correction codes and fault-tolerant quantum computing. These chapters are written to be a useful for students at the graduate and advanced undergraduate level. Also. The first two chapters of this dissertation will be useful to researchers in other fields who would like to understand how quantum error correction and fault-tolerant quantum computing are possible. In chapter 3, we present numerical simulation results comparing the logical error rates for the fault-tolerant [[7, 1, 3]] 's 7 code using the technique of ancilla verification vs. the newer method of ancilla decoding as described in [1]. In chapter 4, we determine how often one should apply error correction. Therefore, we provide a relationship between the logical error rate and the physical error rate for a sequence of logical gates, sometimes followed by noisy quantum error correction

•Jan 1, 2015•0 citations
Quantum error correction methods use processing power to combat noise. The noise level which can be tolerated in a fault-tolerant method is therefore a function of the computational resources available, especially the size of computer and degree of parallelism. I present an analysis of error correction with block codes, made fault-tolerant through the use of prepared ancilla blocks. The preparation and verification of the ancillas is described in detail. It is shown that the ancillas need only be verified against a small set of errors. This, combined with previously known advantages, makes this ’︁ancilla factory‚ the best method to apply error correction, whether in concatenated or block coding. I then consider the resources required to achieve 2 · 1010 computational steps reliably in a computer of 2150 logical qubits, finding that the simplest [[n, 1, d]] block codes can tolerate more noise with smaller overheads than the 7L-bit concatenated code. The scaling is such that block codes remain the better choice for all computations one is likely to contemplate.
The threshold theorem indicates that if errors are all local and their rates are below a certain threshold, it is possible to implement large scale quantum computation with arbitrarily small error based on active quantum error correction (QEC). However, most fault-tolerant quantum computation (FTQC) schemes require enormous overhead to achieve this rate by increasing either the concatenation levels for concatenated codes or the distance (hence the size) for topological codes. As a result, a logical qubit is usually encoded in more than thousands of physical qubits, even when the error rate is below the threshold. In this thesis, we try to reduce the resource overhead of FTQC. We first study a quantum computation scheme using clouds of atoms trapped on atomic chips. It suggests that this scheme is robust to noise to some extent and has potential to be scalable. Secondly, we propose a FTQC scheme of encoding many logical qubits into large code blocks. The error performance of such scheme is numerically studied. Preparation of various ancilla states necessary for computation is also explored. Thirdly, we explore the idea of introducing energy gap to suppress thermal noise on each qubit. We show that fault-tolerant holonomic quantum computation (HQC) can be implemented in stabilizer codes with the existence of such energy protection. Especially, we studied fault-tolerant HQC in surface codes in detail. This scheme opens the possibility for self-correcting quantum computation in 2D lattice.
In fault-tolerant quantum computing schemes, the overhead is often dominated by the cost of preparing codewords reliably. This cost generally increases quadratically with the block size of the underlying quantum error-correcting code. In consequence, large codes that are otherwise very efficient have found limited fault-tolerance applications. Fault-tolerant preparation circuits therefore are an important target for optimization. We study the Golay code, a 232323-qubit quantum error-correcting code that protects the logical qubit to a distance of seven. In simulations, even using a na{\"i}ve ancilla preparation procedure, the Golay code is competitive with other codes both in terms of overhead and the tolerable noise threshold. We provide two simplified circuits for fault-tolerant preparation of Golay code-encoded ancillas. The new circuits minimize error propagation, reducing the overhead by roughly a factor of four compared to standard encoding circuits. By adapting the malignant set counting technique to depolarizing noise, we further prove a threshold above $\threshOverlap$ noise per gate.
Quantum computation holds the promise of solving certain complex problems exponentially faster than classical computers. However, the high prevalent noise in current quantum devices impedes the accurate execution of even basic algorithms. This can be remedied by protecting quantum information with a quantum error-correcting code, where the logical information of an algorithmic qubit is spread across multiple physical qubits. Individual quantum errors are then located and corrected by the fault-tolerant measurement of multi-qubit stabilizer operators (parity checks). Unfortunately, error correction and fault tolerance both impose large demands on the qubit overhead: hundreds to thousands of physical qubits per logical qubit. We reduce the spacetime cost of fault tolerance by redesigning key building blocks of an error-corrected quantum computer. First, we develop a combinatorial proof with flag fault tolerance that exponentially reduces the extra qubits needed to measure a stabilizer of any size, while tolerating one fault. We leverage these proofs to then design state preparation circuits for the Steane and Golay codes with 100% yield. Next, we improve error correction on a planar layout by showing that a distance-four code encoding six logical qubits protects information as well as the distance-five surface code, using one-tenth as many physical qubits. Finally, we optimize the time overhead of logical gates in surface code quantum computers by protecting measurement results with a classical code, cutting computation time by a factor of two to six. Our hardware-agnostic optimizations of fault tolerance overheads thus suggest new routes to advance the timeline of error-free quantum computing.
Fault-tolerant quantum computation (FTQC) schemes that use multiqubit large block codes can potentially reduce the resource overhead to a great extent. A major obstacle is the requirement for a large number of clean ancilla states of different types without correlated errors inside each block. These ancilla states are usually logical stabilizer states of the data-code blocks, which are generally difficult to prepare if the code size is large. Previously, we have proposed an ancilla distillation protocol for Calderbank-Shor-Steane (CSS) codes by classical error-correcting codes. It was assumed that the quantum gates in the distillation circuit were perfect; however, in reality, noisy quantum gates may introduce correlated errors that are not treatable by the protocol. In this paper, we show that additional postselection by another classical error-detecting code can be applied to remove almost all correlated errors. Consequently, the revised protocol is fully fault tolerant and capable of preparing a large set of stabilizer states sufficient for FTQC using large block codes. At the same time, the yield rate can be boosted from $O({t}^{\ensuremath{-}2})$ to O(1)O(1)O(1) in practice for an [[n,k,d=2t+1]][[n,k,d=2t+1]][[n,k,d=2t+1]] CSS code. Ancilla preparation for the [[23,1,7]] quantum Golay code is numerically studied in detail through Monte Carlo simulation. The results support the validity of the protocol when the gate failure rate is reasonably low. To the best of our knowledge, this approach is one of the first attempts to prepare general large block stabilizer states free of correlated errors for FTQC in a fault-tolerant and efficient manner.
Fault-tolerant quantum error correction (QEC) networks are studied by a combination of numerical and approximate analytical treatments. The probability of failure of the recovery operation is calculated for a variety of Calderbank-Shor-Steane codes, including large block codes and concatenated codes. Recent insights into the syndrome extraction process, which render the whole process more efficient and more noise tolerant, are incorporated. The average number of recoveries that can be completed without failure is thus estimated as a function of various parameters. The main parameters are the gate $\ensuremath{\gamma}$ and memory $\ensuremath{\epsilon}$ failure rates, the physical scale-up of the computer size, and the time tm{t}_{m}tm​ required for measurements and classical processing. The achievable computation size is given as a surface in parameter space. This indicates the noise threshold as well as other information. It is found that concatenated codes based on the [[23,1,7]][[23,1,7]][[23,1,7]] Golay code give higher thresholds than those based on the [[7,1,3]][[7,1,3]][[7,1,3]] Hamming code under most conditions. The threshold gate noise ${\ensuremath{\gamma}}_{0}$ is a function of $\ensuremath{\epsilon}/\ensuremath{\gamma}$ and tm;{t}_{m};tm​; example values are ${\ensuremath{\epsilon}/\ensuremath{\gamma}{,t}_{m},{\ensuremath{\gamma}}_{0}}={{1,1,10}^{\ensuremath{-}3}},$ ${0.01,1,3\ifmmode\times\else\texttimes\fi{}{10}^{\ensuremath{-}3}},$ ${{1,100,10}^{\ensuremath{-}4}},$ ${0.01,100,2\ifmmode\times\else\texttimes\fi{}{10}^{\ensuremath{-}3}},$ assuming zero cost for information transport. This represents an order of magnitude increase in tolerated memory noise, compared with previous calculations, which is made possible by recent insights into the fault-tolerant QEC process.
Communication is the prototypical application of error-correction methods. To communicate, a sender needs to convey information to a receiver over a noisy "communication channel." Such a channel can be thought of as a means of transmitting an information-carrying physical system from one place to another. During transmission, the physical system is subject to disturbances (noise) that can adversely affect the information carried. To use a communication channel, the sender needs to encode the information to be transmitted in the physical system. After transmission, the receiver decodes the information. Quantum error correction is used in quantum computing to protect quantum information from errors due to decoherence and other quantum noise. Quantum error correction is essential if one is to achieve fault-tolerant quantum computation that can deal with both noise on stored quantum information, and also with faulty quantum gates, faulty quantum preparation,and faulty measurements. In this dissertation, we look at how additional information about the structure of the quantum circuit and noise can improve or alter the performance of techniques in quantum error correction. Chapter 1 and 2, are an introduction to the quantum computation, quantum error correction codes and fault-tolerant quantum computing. These chapters are written to be a useful for students at the graduate and advanced undergraduate level. Also. The first two chapters of this dissertation will be useful to researchers in other fields who would like to understand how quantum error correction and fault-tolerant quantum computing are possible. In chapter 3, we present numerical simulation results comparing the logical error rates for the fault-tolerant [[7, 1, 3]] 's 7 code using the technique of ancilla verification vs. the newer method of ancilla decoding as described in [1]. In chapter 4, we determine how often one should apply error correction. Therefore, we provide a relationship between the logical error rate and the physical error rate for a sequence of logical gates, sometimes followed by noisy quantum error correction