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

Physical Review A

Soft-decision decoder for quantum erasure and probabilistic-gate error models

Hayato Goto, Hironori Uchikawa

Published Feb 18, 2014• 3 citations
Publisher

Abstract

A soft-decision decoder for quantum erasure errors with standard depolarizing errors is proposed for concatenated Calderbank-Shor-Steane codes. This decoding is computationally efficient as long as the block size of each concatenation level is sufficiently small. The numerical simulation with a specific quantum code called the ${C}_{4}/{C}_{6}$ code shows that this decoder can achieve almost optimal performance and the so-called hashing bound for the erasure and depolarizing error model. Since probabilistic-gate errors can be regarded as erasure errors, this decoder is useful for fault-tolerant quantum computation with probabilistic gates. To demonstrate this, we perform numerical simulation with the ${C}_{4}/{C}_{6}$ code. Consequently, it turns out that the error probability of a logical controlled-not gate with probabilistic physical two-qubit gates is improved by three orders of magnitude by the present decoder compared to a previous hard-decision decoder.

DOI
10.1103/physreva.89.022322

Related papers

Bidirectional Decoding for Concatenated Quantum Hamming Codes

Chao Zhang, Zipeng Wu, Jiahui Wu +1 more

High-rate concatenated quantum codes offer a promising pathway toward fault-tolerant quantum computation, yet designing efficient decoders that fully exploit their error-correction capability remains a significant challenge. In this work, we introduce a hard-decision decoder for concatenated quantum Hamming codes with time complexity polynomial in the block length. This decoder overcomes the limitations of conventional local decoding by leveraging higher-level syndrome information to revise lower-level recovery decisions -- a strategy we refer to as bidirectional decoding. For the concatenated $[[15,7,3]]$ quantum Hamming code under independent bit-flip noise, the bidirectional decoder improves the threshold from approximately $1.56\%$ to $4.35\%$ compared with standard local decoding. Moreover, the decoder empirically preserves the full $3^{L}$ code-distance scaling for at least three levels of concatenation, resulting in substantially faster logical-error suppression than the $2^{L+1}$ scaling offered by local decoders. Our results can enhance the competitiveness of concatenated-code architectures for low-overhead fault-tolerant quantum computation.

quant-pharXiv:2601.09131•Jan 15, 2026•0 citations

Fault-tolerant quantum computation with a soft-decision decoder for error correction and detection by teleportation

Hayato Goto, Hironori Uchikawa

Fault-tolerant quantum computation with quantum error-correcting codes has been considerably developed over the past decade. However, there are still difficult issues, particularly on the resource requirement. For further improvement of fault-tolerant quantum computation, here we propose a soft-decision decoder for quantum error correction and detection by teleportation. This decoder can achieve almost optimal performance for the depolarizing channel. Applying this decoder to Knill's C4/C6 scheme for fault-tolerant quantum computation, which is one of the best schemes so far and relies heavily on error correction and detection by teleportation, we dramatically improve its performance. This leads to substantial reduction of resources.

Scientific Reports•Jun 20, 2013•18 citations

Erasure Decoding Scheme of Topological Fault Tolerance Quantum Computation With 3D Concatenation Codes

Zhaoyi Li, Issac Kim, Patrick M. Hayden

The possibility of practical large-scale quantum computation is largely dictated by the error threshold and qubit overhead of the error correcting scheme. To achieve this goal, architectures that perform fault tolerance quantum computation (FTQC) with 3D cluster states have been designed; however, the current benchmarks for such constructions are still below general experimental requirements. In light of this, we propose a new 3D FTQC scheme by exploiting geometric tolerance to erasure errors using cluster states with novel lattice structures, specifically, by replacing the physical qubits with small-sized error detection codes that allow simple applications of logical CZ gates. We are able to locate Pauli errors locally and effectively convert them into loss errors. With a combination of code concatenation and multi-staged decoding, the scheme is able to achieve higher performance than traditional cubic lattices in protecting quantum information. We have surveyed a wide range of possible concatenation schemes and Monte-Carlo simulations have been performed on the decoders to study their respective scaling behavior. The scheme has demonstrated an overall decrement in active qubit overhead and an improvement of the error threshold, which varies from 10 % to 160% depending on the noise model, indicating a relatively higher rate of fault tolerance compared with previous cluster states-based codes.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 1, 2022•0 citations

ERROR THRESHOLD ESTIMATION BY MEANS OF THE [[7,1,3]] CSS QUANTUM CODE

Pedro J. Salas, Angel L. Sanz

The states needed in quantum computation are extremely affected by decoherence. Several methods have been proposed to control error spreading. They use two main tools: fault-tolerant constructions and concatenated quantum error correcting codes. In this work, we estimate the threshold conditions necessary to make a long enough quantum computation. The [[7,1,3]] CSS quantum code together with the Shor method to measure the error syndrome is used. No concatenation is included. The decoherence is introduced by means of the depolarizing channel error model, obtaining several thresholds from the numerical simulation. Regarding the maintenance of a qubit stabilized in the memory, the error probability must be smaller than 2.9 × 10-5. In order to implement a one or two-qubit encoded gate in an effective fault-tolerant way, it is possible to choose an adequate non-encoded noisy gate if the memory error probability is smaller than 1.3 × 10-5. In addition, fulfilling this last condition permits us to assume a more efficient behavior compared to the equivalent non-encoded process.

arXiv:quant-ph/0411042•International Journal of Quantum Information•May 31, 2005•2 citations

Fault-tolerant logical gate networks for Calderbank-Shor-Steane codes

Andrew M. Steane, Ben Ibinson

Fault-tolerant logical operations for qubits encoded by Calderbank-Shor-Steane codes are discussed, with emphasis on methods that apply to codes of high rate, encoding $k$ qubits per block with $k>1$. It is shown that the logical qubits within a given block can be prepared by a single recovery operation in any state whose stabilizer generator separates into $X$ and $Z$ parts. Optimized methods to move logical qubits around and to achieve controlled-NOT and Toffoli gates are discussed. It is found that the number of time steps required to complete a fault-tolerant quantum computation is the same when $k>1$ as when $k=1$.

arXiv:quant-ph/0311014•Physical Review A•Nov 30, 2005•44 citations

Fault-Tolerant Quantum Computation with Constant Error Rate

Dorit Aharonov, Michael Ben-Or

This paper shows that quantum computation can be made fault-tolerant against errors and inaccuracies when $\eta$, the probability for an error in a qubit or a gate, is smaller than a constant threshold $\eta_c$. This result improves on Shor's result [Proceedings of the 37th Symposium on the Foundations of Computer Science, IEEE, Los Alamitos, CA, 1996, pp. 56–65], which shows how to perform fault-tolerant quantum computation when the error rate $\eta$ decays polylogarithmically with the size of the computation, an assumption which is physically unreasonable. The cost of making the quantum circuit fault-tolerant in our construction is polylogarithmic in time and space. Our result holds for a very general local noise model, which includes probabilistic errors, decoherence, amplitude damping, depolarization, and systematic inaccuracies in the gates. Moreover, we allow exponentially decaying correlations between the errors both in space and in time. Fault-tolerant computation can be performed with any universal set of gates. The result also holds for quantum particles with $p>2$ states, namely, p-qudits, and is also generalized to one-dimensional quantum computers with only nearest-neighbor interactions. No measurements, or classical operations, are required during the quantum computation. We estimate the threshold of our construction to be $\eta_c\simeq 10^{-6}$, in the best case. By this we show that local noise is in principle not an obstacle for scalable quantum computation. The main ingredient of our proof is the computation on states encoded by a quantum error correcting code (QECC). To this end we introduce a special class of Calderbank–Shor–Steane (CSS) codes, called polynomial codes (the quantum analogue of Reed–Solomon codes). Their nice algebraic structure allows all of the encoded gates to be transversal. We also provide another version of the proof which uses more general CSS codes, but its encoded gates are slightly less elegant. To achieve fault tolerance, we encode the quantum circuit by another circuit by using one of these QECCs. This step is repeated polyloglog many times, each step slightly improving the effective error rate, to achieve the desired reliability. The resulting circuit exhibits a hierarchical structure, and for the analysis of its robustness we borrow terminology from Khalfin and Tsirelson [Found. Phys., 22 (1992), pp. 879–948] and Gács [Advances in Computing Research: A Research Annual: Randomness and Computation, JAI Press, Greenwich, CT, 1989]. The paper is to a large extent self-contained. In particular, we provide simpler proofs for many of the known results we use, such as the fact that it suffices to correct for bit-flips and phase-flips, the correctness of CSS codes, and the fact that two-qubit gates are universal, together with their extensions to higher-dimensional particles. We also provide full proofs of the universality of the sets of gates we use (the proof of universality was missing in Shor's paper). This paper thus provides a self-contained and complete proof of universal fault-tolerant quantum computation in the presence of local noise.

SIAM Journal on Computing•Jan 1, 2008•507 citations
A soft-decision decoder for quantum erasure errors with standard depolarizing errors is proposed for concatenated Calderbank-Shor-Steane codes. This decoding is computationally efficient as long as the block size of each concatenation level is sufficiently small. The numerical simulation with a specific quantum code called the C4/C6{C}_{4}/{C}_{6}C4​/C6​ code shows that this decoder can achieve almost optimal performance and the so-called hashing bound for the erasure and depolarizing error model. Since probabilistic-gate errors can be regarded as erasure errors, this decoder is useful for fault-tolerant quantum computation with probabilistic gates. To demonstrate this, we perform numerical simulation with the C4/C6{C}_{4}/{C}_{6}C4​/C6​ code. Consequently, it turns out that the error probability of a logical controlled-not gate with probabilistic physical two-qubit gates is improved by three orders of magnitude by the present decoder compared to a previous hard-decision decoder.
High-rate concatenated quantum codes offer a promising pathway toward fault-tolerant quantum computation, yet designing efficient decoders that fully exploit their error-correction capability remains a significant challenge. In this work, we introduce a hard-decision decoder for concatenated quantum Hamming codes with time complexity polynomial in the block length. This decoder overcomes the limitations of conventional local decoding by leveraging higher-level syndrome information to revise lower-level recovery decisions -- a strategy we refer to as bidirectional decoding. For the concatenated [[15,7,3]][[15,7,3]][[15,7,3]] quantum Hamming code under independent bit-flip noise, the bidirectional decoder improves the threshold from approximately 1.56%1.56\%1.56% to 4.35%4.35\%4.35% compared with standard local decoding. Moreover, the decoder empirically preserves the full 3L3^{L}3L code-distance scaling for at least three levels of concatenation, resulting in substantially faster logical-error suppression than the 2L+12^{L+1}2L+1 scaling offered by local decoders. Our results can enhance the competitiveness of concatenated-code architectures for low-overhead fault-tolerant quantum computation.
Fault-tolerant quantum computation with quantum error-correcting codes has been considerably developed over the past decade. However, there are still difficult issues, particularly on the resource requirement. For further improvement of fault-tolerant quantum computation, here we propose a soft-decision decoder for quantum error correction and detection by teleportation. This decoder can achieve almost optimal performance for the depolarizing channel. Applying this decoder to Knill's C4/C6 scheme for fault-tolerant quantum computation, which is one of the best schemes so far and relies heavily on error correction and detection by teleportation, we dramatically improve its performance. This leads to substantial reduction of resources.
The possibility of practical large-scale quantum computation is largely dictated by the error threshold and qubit overhead of the error correcting scheme. To achieve this goal, architectures that perform fault tolerance quantum computation (FTQC) with 3D cluster states have been designed; however, the current benchmarks for such constructions are still below general experimental requirements. In light of this, we propose a new 3D FTQC scheme by exploiting geometric tolerance to erasure errors using cluster states with novel lattice structures, specifically, by replacing the physical qubits with small-sized error detection codes that allow simple applications of logical CZ gates. We are able to locate Pauli errors locally and effectively convert them into loss errors. With a combination of code concatenation and multi-staged decoding, the scheme is able to achieve higher performance than traditional cubic lattices in protecting quantum information. We have surveyed a wide range of possible concatenation schemes and Monte-Carlo simulations have been performed on the decoders to study their respective scaling behavior. The scheme has demonstrated an overall decrement in active qubit overhead and an improvement of the error threshold, which varies from 10 % to 160% depending on the noise model, indicating a relatively higher rate of fault tolerance compared with previous cluster states-based codes.
The states needed in quantum computation are extremely affected by decoherence. Several methods have been proposed to control error spreading. They use two main tools: fault-tolerant constructions and concatenated quantum error correcting codes. In this work, we estimate the threshold conditions necessary to make a long enough quantum computation. The [[7,1,3]] CSS quantum code together with the Shor method to measure the error syndrome is used. No concatenation is included. The decoherence is introduced by means of the depolarizing channel error model, obtaining several thresholds from the numerical simulation. Regarding the maintenance of a qubit stabilized in the memory, the error probability must be smaller than 2.9 × 10-5. In order to implement a one or two-qubit encoded gate in an effective fault-tolerant way, it is possible to choose an adequate non-encoded noisy gate if the memory error probability is smaller than 1.3 × 10-5. In addition, fulfilling this last condition permits us to assume a more efficient behavior compared to the equivalent non-encoded process.
Fault-tolerant logical operations for qubits encoded by Calderbank-Shor-Steane codes are discussed, with emphasis on methods that apply to codes of high rate, encoding kkk qubits per block with k>1k>1k>1. It is shown that the logical qubits within a given block can be prepared by a single recovery operation in any state whose stabilizer generator separates into XXX and ZZZ parts. Optimized methods to move logical qubits around and to achieve controlled-NOT and Toffoli gates are discussed. It is found that the number of time steps required to complete a fault-tolerant quantum computation is the same when k>1k>1k>1 as when k=1k=1k=1.
This paper shows that quantum computation can be made fault-tolerant against errors and inaccuracies when η\etaη, the probability for an error in a qubit or a gate, is smaller than a constant threshold ηc\eta_cηc​. This result improves on Shor's result [Proceedings of the 37th Symposium on the Foundations of Computer Science, IEEE, Los Alamitos, CA, 1996, pp. 56–65], which shows how to perform fault-tolerant quantum computation when the error rate η\etaη decays polylogarithmically with the size of the computation, an assumption which is physically unreasonable. The cost of making the quantum circuit fault-tolerant in our construction is polylogarithmic in time and space. Our result holds for a very general local noise model, which includes probabilistic errors, decoherence, amplitude damping, depolarization, and systematic inaccuracies in the gates. Moreover, we allow exponentially decaying correlations between the errors both in space and in time. Fault-tolerant computation can be performed with any universal set of gates. The result also holds for quantum particles with p>2p>2p>2 states, namely, p-qudits, and is also generalized to one-dimensional quantum computers with only nearest-neighbor interactions. No measurements, or classical operations, are required during the quantum computation. We estimate the threshold of our construction to be ηc≃10−6\eta_c\simeq 10^{-6}ηc​≃10−6, in the best case. By this we show that local noise is in principle not an obstacle for scalable quantum computation. The main ingredient of our proof is the computation on states encoded by a quantum error correcting code (QECC). To this end we introduce a special class of Calderbank–Shor–Steane (CSS) codes, called polynomial codes (the quantum analogue of Reed–Solomon codes). Their nice algebraic structure allows all of the encoded gates to be transversal. We also provide another version of the proof which uses more general CSS codes, but its encoded gates are slightly less elegant. To achieve fault tolerance, we encode the quantum circuit by another circuit by using one of these QECCs. This step is repeated polyloglog many times, each step slightly improving the effective error rate, to achieve the desired reliability. The resulting circuit exhibits a hierarchical structure, and for the analysis of its robustness we borrow terminology from Khalfin and Tsirelson [Found. Phys., 22 (1992), pp. 879–948] and Gács [Advances in Computing Research: A Research Annual: Randomness and Computation, JAI Press, Greenwich, CT, 1989]. The paper is to a large extent self-contained. In particular, we provide simpler proofs for many of the known results we use, such as the fact that it suffices to correct for bit-flips and phase-flips, the correctness of CSS codes, and the fact that two-qubit gates are universal, together with their extensions to higher-dimensional particles. We also provide full proofs of the universality of the sets of gates we use (the proof of universality was missing in Shor's paper). This paper thus provides a self-contained and complete proof of universal fault-tolerant quantum computation in the presence of local noise.