The DOI matches its Crossref record; 26 of the 26 references it cites were found in a registry or an index.
Optimal and efficient decoding of concatenated quantum block codes
Open accessAbstract
We consider the problem of optimally decoding a quantum error correction code---that is, to find the optimal recovery procedure given the outcomes of partial ``check'' measurements on the system. In general, this problem is NP hard. However, we demonstrate that for concatenated block codes, the optimal decoding can be efficiently computed using a message-passing algorithm. We compare the performance of the message-passing algorithm to that of the widespread blockwise hard decoding technique. Our Monte Carlo results using the five-qubit and Steane's code on a depolarizing channel demonstrate significant advantages of the message-passing algorithms in two respects: (i) Optimal decoding increases by as much as 94$%$ the error threshold below which the error correction procedure can be used to reliably send information over a noisy channel; and (ii) for noise levels below these thresholds, the probability of error after optimal decoding is suppressed at a significantly higher rate, leading to a substantial reduction of the error correction overhead.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“These outer codes have distances two and four respectively which, by utilizing the soft information provided by the inner surface codes30, double and quadruple the inner code distance.”
From Yoked surface codes (2025) · cites this paper as [30]
In the citing paper
“Passing this information to the outer code helps it to identify likely culprit errors30.”
From Yoked surface codes (2025) · cites this paper as [30]
Citations
Cites
Low-density parity-check codes
Gallager, R. G. (1962) · IEEE Transactions on Information Theory · doi:10.1109/tit.1962.1057683 · Cited by 10,727
Fault-tolerant quantum computation by anyons
Kitaev, A. Y. (2003) · Annals of Physics · doi:10.1016/s0003-4916(02)00018-0 · Cited by 7,238
Information theory, inference, and learning algorithms
(2004) · Choice Reviews Online · doi:10.5860/choice.41-5949 · Cited by 6,536
Mixed-state entanglement and quantum error correction
Bennett, C. H., DiVincenzo, D. P., Smolin, J. A., & Wootters, W. K. (1996) · Physical Review A · doi:10.1103/physreva.54.3824 · Cited by 5,272
Information Theory, Inference, and Learning Algorithms
(2004) · Kybernetes · doi:10.1108/03684920410534506 · Cited by 4,937
Scheme for reducing decoherence in quantum computer memory
Shor, P. W. (1995) · Physical Review A · doi:10.1103/physreva.52.r2493 · Cited by 4,479
Error Correcting Codes in Quantum Theory
Steane, A. M. (1996) · Physical Review Letters · doi:10.1103/physrevlett.77.793 · Cited by 2,677
Richardson, T., & Urbanke, R. L. (2008) · Cambridge University Press eBooks · doi:10.1017/cbo9780511791338 · Cited by 2,287
Theory of quantum error-correcting codes
Knill, E., & Laflamme, R. (1997) · Physical Review A · doi:10.1103/physreva.55.900 · Cited by 1,593
On the inherent intractability of certain coding problems (Corresp.)
Berlekamp, E. R., McEliece, R. J., & van Tilborg, H. (1978) · IEEE Transactions on Information Theory · doi:10.1109/tit.1978.1055873 · Cited by 1,508
Multiple-particle interference and quantum error correction
(1996) · Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.1996.0136 · Cited by 1,284
Quantum computing with realistically noisy devices
Knill, E. (2005) · Nature · doi:10.1038/nature03350 · Cited by 1,184
Preskill, J. (1998) · Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.1998.0167 · Cited by 994
Perfect Quantum Error Correcting Code
Laflamme, R., Miquel, C., Paz, J. P., & Zurek, W. H. (1996) · Physical Review Letters · doi:10.1103/physrevlett.77.198 · Cited by 966
Multiple particle interference and quantum error correction
Steane, A. M. (1996) · Cited by 871
The generalized distributive law
Aji, S. M., & McEliece, R. J. (2000) · IEEE Transactions on Information Theory · doi:10.1109/18.825794 · Cited by 737
Sparse-Graph Codes for Quantum Error Correction
Mackay, D., Mitchison, G., & McFadden, P. L. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.834737 · Cited by 380
Stabilizer Formalism for Operator Quantum Error Correction
Poulin, D. (2005) · Physical Review Letters · doi:10.1103/physrevlett.95.230504 · Cited by 375
Self-citationResilient quantum computation: error models and thresholds
Knill, E., Laflamme, R., & Zurek, W. H. (1998) · Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.1998.0166 · Cited by 346
Resilient Quantum Computation: Error Models and Thresholds
Knill, E. H., Laflamme, R., & Zurek, W. H. (1997) · CERN Document Server (European Organization for Nuclear Research) · Cited by 299
Quantum-channel capacity of very noisy channels
DiVincenzo, D. P., Shor, P. W., & Smolin, J. A. (1998) · Physical Review A · doi:10.1103/physreva.57.830 · Cited by 297
Exact performance of concatenated quantum codes
Rahn, B., Doherty, A. C., & Mabuchi, H. (2002) · Physical Review A · doi:10.1103/physreva.66.032304 · Cited by 64
Constructions and performance of classes of quantum LDPC codesPreprint
Camara, T., Ollivier, H., & Tillich, J. (2005) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0502086 · Cited by 60
Forney, D. (2009) · Scholarpedia · doi:10.4249/scholarpedia.8374 · Cited by 36
Proceedings of the 13th Symposium on Information Theory in the Benelux
Heideman, G., Hoeksema, F. W., & Tattje, H. E. P. (1992) · University of Twente Research Information · Cited by 34
Trellises for stabilizer codes: Definition and uses
Ollivier, H., & Tillich, J. (2006) · Physical Review A · doi:10.1103/physreva.74.032304 · Cited by 13
Research works printed but not linked: 3
- P. W. Shor, 1996, Proceedings of the 37th Symposium on the Foundations of Computer Science
- A. Y. Kitaev, 1997, Proceedings of the Third International Conference on Quantum Communication and Measurement
- D. Aharonov, 1997, Proc. 29th Ann. ACM Symp. on Theory of Computing
Cited by
Sorted by citations
Quantum error correction for quantum memories
Terhal, B. M. (2015) · Reviews of Modern Physics · doi:10.1103/revmodphys.87.307 · Cited by 1,354
An introduction to quantum error correction and fault-tolerant quantum computation
Gottesman, D. (2010) · Proceedings of symposia in applied mathematics · doi:10.1090/psapm/068/2762145 · Cited by 795
Quantum networks based on color centers in diamond
Ruf, M., Wan, N., Choi, H., Englund, D. R., & Hanson, R. (2021) · Journal of Applied Physics · doi:10.1063/5.0056534 · Cited by 334
Fast Decoders for Topological Quantum Codes
Duclos-Cianci, G., & Poulin, D. (2010) · Physical Review Letters · doi:10.1103/physrevlett.104.050504 · Cited by 244
Self-citationQuantum networks based on color centers in diamond
Ruf, M., Wan, N., Choi, H., Englund, D., & Hanson, R. (2021) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 238
Metadata
- Authors
- Poulin, D.
- Affiliations
- California Institute of Technology (US)
- Corresponding author
- Poulin, David
- Venue
- Physical Review A
- Publisher
- American Physical Society (APS)
- Published
- 2006-11-22
- Volume
- 74
- Issue
- 5
- ISSN
- 0556-2791 (ISSN-L)
- 1050-2947
- 1094-1622
- OpenAlex
- W2109785828
- Cited by
- 105
- References
- 26
- Citations by year
- 2026: 6 · 2025: 12 · 2024: 7 · 2023: 5 · 2022: 12 · 2021: 8 · 2020: 1 · 2019: 4 · 2018: 9 · 2017: 9 · 2016: 1 · 2015: 4 · 2014: 8 · 2013: 2
- FWCI
- 3.81
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Physical Review A (publishedVersion)
- arXiv (Cornell University) (publishedVersion)
- CaltechAUTHORS (California Institute of Technology) (submittedVersion)
- CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation
- Gordon and Betty Moore Foundation
- California Institute of Technology
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Physical Sciences › Computer Science › Computer Networks and Communications › Error Correcting Code Techniques
- Keywords
- quantum error correction, optimal decoding, message passing algorithm, five-qubit code, Steane code, depolarizing channel, error threshold, decoding overhead, NP-hardness
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
