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

Generalized Quantum Data-Syndrome Codes and Belief Propagation Decoding for Phenomenological Noise

Kao-Yueh Kuo, Ching–Yi Lai

Published Jan 14, 2025• 5 citations
arXivHTMLPDF

Abstract

Quantum stabilizer codes often struggle with syndrome errors due to measurement imperfections. Typically, multiple rounds of syndrome extraction are employed to ensure reliable error information. In this paper, we consider phenomenological decoding problems, where data qubit errors may occur between extractions, and each measurement can be faulty. We introduce generalized quantum data-syndrome codes along with a generalized check matrix that integrates both quaternary and binary alphabets to represent diverse error sources. This results in a Tanner graph with mixed variable nodes, enabling the design of belief propagation (BP) decoding algorithms that effectively handle phenomenological errors. Importantly, our BP decoders are applicable to general sparse quantum codes. Through simulations, we achieve an error threshold of more than 3% for quantum memory protected by rotated toric codes, using solely BP without post-processing. Our results indicate that d rounds of syndrome extraction are sufficient for a toric code of distance d. We observe that at high error rates, fewer rounds of syndrome extraction tend to perform better, while more rounds improve performance at lower error rates. Additionally, we propose a method to construct effective redundant stabilizer checks for single-shot error correction. Our simulations show that BP decoding remains highly effective even with a high syndrome error rate.

DOI
10.1109/tit.2025.3529773

Related papers

Decoding Strategies for Generalized Quantum Data-Syndrome Coding Problems

Kao-Yueh Kuo, Ching–Yi Lai

Quantum stabilizer codes often face the challenge of syndrome errors due to error-prone measurements and multiple rounds of syndrome extraction are typically employed. In this paper, we consider phenomenological decoding problems, where data qubit errors may occur between two syndrome extractions, and each syndrome measurement can be faulty. To handle these diverse error sources, we define a generalized check matrix over mixed quaternary and binary alphabets to characterize their error syndromes. This generalized check matrix leads to the creation of a Tanner graph comprising quaternary and binary variable nodes, which facilitates the development of belief propagation (BP) decoding algorithms to tackle phenomenological errors. Additionally, our BP decoders are applicable to general sparse quantum codes.

IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•0 citations

Decoding of Quantum Data-Syndrome Codes via Belief Propagation

Kao-Yueh Kuo, I-Chun Chern, Ching–Yi Lai

Quantum error correction is necessary to protect logical quantum states and operations. However, no meaningful data protection can be made when the syndrome extraction is erroneous due to faulty measurement gates. Quantum data-syndrome (DS) codes are designed to protect the data qubits and syndrome bits concurrently. In this paper, we propose an efficient decoding algorithm for quantum DS codes with sparse check matrices. Based on a refined belief propagation (BP) decoding for stabilizer codes, we propose a DS-BP algorithm to handle the quaternary quantum data errors and binary syndrome bit errors. Moreover, a sparse quantum code may inherently be able to handle minor syndrome errors so that fewer redundant syndrome measurements are necessary. We demonstrate this with simulations on a quantum hypergraph-product code.

arXiv:2102.01984•IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•14 citations

Refined Belief Propagation Decoding of Sparse-Graph Quantum Codes

Kao-Yueh Kuo, Ching–Yi Lai

Quantum stabilizer codes constructed from sparse matrices have good performance and can be efficiently decoded by belief propagation (BP). A conventional BP decoding algorithm treats binary stabilizer codes as additive codes over GF(4). This algorithm has a relatively complex process of handling check-node messages, which incurs higher decoding complexity. Moreover, BP decoding of a stabilizer code usually suffers a performance loss due to the many short cycles in the underlying Tanner graph. In this paper, we propose a refined BP decoding algorithm for quantum codes with complexity roughly the same as binary BP. For a given error syndrome, this algorithm decodes to the same output as the conventional quaternary BP but the passed node-to-node messages are single-valued, unlike the quaternary BP, where multivalued node-to-node messages are required. Furthermore, the techniques of message strength normalization can naturally be applied to these single-valued messages to improve the performance. Another observation is that the message-update schedule affects the performance of BP decoding against short cycles. We show that running BP with message strength normalization according to a serial schedule (or other schedules) may significantly improve the decoding performance and error floor in computer simulation.

arXiv:2002.06502•IEEE Journal on Selected Areas in Information Theory•Jul 24, 2020•48 citations

Refined Belief-Propagation Decoding of Quantum Codes with Scalar Messages

Kao-Yueh Kuo, Ching-Yi Lai

Codes based on sparse matrices have good performance and can be efficiently decoded by belief-propagation (BP). Decoding binary stabilizer codes needs a quaternary BP for (additive) codes over GF(4), which has a higher check-node complexity compared to a binary BP for codes over GF(2). Moreover, BP decoding of stabilizer codes suffers a performance loss from the short cycles in the underlying Tanner graph. In this paper, we propose a refined BP algorithm for decoding quantum codes by passing scalar messages. For a given error syndrome, this algorithm decodes to the same output as the conventional quaternary BP but with a check-node complexity the same as binary BP. As every message is a scalar, the message normalization can be naturally applied to improve the performance. Another observation is that the message-update schedule affects the BP decoding performance against short cycles. We show that running BP with message normalization according to a serial schedule (or other schedules) may significantly improve the decoding performance and error-floor in computer simulation.

arXiv:2102.07122•IEEE Globecom Workshops (GC Wkshps)•Dec 1, 2020•8 citations

Dynamic local single-shot checks for toric codes

Yingjia Lin, Abhinav Anand, Kenneth R. Brown

Quantum error correction typically requires repeated syndrome extraction due to measurement noise, which results in substantial time overhead in fault-tolerant computation. Single-shot error correction aims to suppress errors using only one round of syndrome extraction. However, for most codes, it requires high-weight checks, which significantly degrade, and often eliminate, single-shot performance at the circuit level. In this work, we introduce local single-shot checks, where we impose constraints on check weights. Using a dynamic measurement scheme, we show that the number of required measurement rounds can be reduced by a factor determined by this constraint. As an example, we show through numerical simulation that our scheme can improve decoding performance compared to conventional checks when using sliding-window decoding with a reduced window size under circuit-level noise models for toric codes. Our work provides a new direction for constructing checks that can reduce time overhead in large-scale fault-tolerant quantum computation.

quant-pharXiv:2511.20576•Nov 26, 2025•0 citations

Improved Single-Shot Decoding of Higher-Dimensional Hypergraph-Product Codes

Oscar Higgott, Nikolas P. Breuckmann

In this work, we study the single-shot performance of higher-dimensional hypergraph product codes decoded using belief propagation and ordered-statistics decoding [P.Panteleev and G. Kalachev, Quantum 5, 585 (2021)].We find that decoding data-qubit and syndrome-measurement errors together in a single stage leads to single-shot thresholds that greatly exceed all previously observed single-shot thresholds for these codes.For the three-dimensional toric code and a phenomenological noise model, our results are consistent with a sustainable threshold of 7.1% for Z errors, compared to the threshold of 2.90% previously found using a two-stage decoder [Quintavalle et al., 2021].For the four-dimensional (4D) toric code, for which both X and Z error correction is single shot, our results are consistent with a sustainable single-shot threshold of 4.3%, which is even higher than the threshold of 2.93% for the two-dimensional toric code for the same noise model but using L rounds of stabilizer measurement.We also explore the performance of balanced-product and 4D hypergraph-product codes, which we show lead to a reduction in qubit overhead compared the surface code for phenomenological error rates as high as 1%.

arXiv:2206.03122•PRX Quantum•May 30, 2023•40 citations
Quantum stabilizer codes often struggle with syndrome errors due to measurement imperfections. Typically, multiple rounds of syndrome extraction are employed to ensure reliable error information. In this paper, we consider phenomenological decoding problems, where data qubit errors may occur between extractions, and each measurement can be faulty. We introduce generalized quantum data-syndrome codes along with a generalized check matrix that integrates both quaternary and binary alphabets to represent diverse error sources. This results in a Tanner graph with mixed variable nodes, enabling the design of belief propagation (BP) decoding algorithms that effectively handle phenomenological errors. Importantly, our BP decoders are applicable to general sparse quantum codes. Through simulations, we achieve an error threshold of more than 3% for quantum memory protected by rotated toric codes, using solely BP without post-processing. Our results indicate that d rounds of syndrome extraction are sufficient for a toric code of distance d. We observe that at high error rates, fewer rounds of syndrome extraction tend to perform better, while more rounds improve performance at lower error rates. Additionally, we propose a method to construct effective redundant stabilizer checks for single-shot error correction. Our simulations show that BP decoding remains highly effective even with a high syndrome error rate.
Quantum stabilizer codes often face the challenge of syndrome errors due to error-prone measurements and multiple rounds of syndrome extraction are typically employed. In this paper, we consider phenomenological decoding problems, where data qubit errors may occur between two syndrome extractions, and each syndrome measurement can be faulty. To handle these diverse error sources, we define a generalized check matrix over mixed quaternary and binary alphabets to characterize their error syndromes. This generalized check matrix leads to the creation of a Tanner graph comprising quaternary and binary variable nodes, which facilitates the development of belief propagation (BP) decoding algorithms to tackle phenomenological errors. Additionally, our BP decoders are applicable to general sparse quantum codes.
Quantum error correction is necessary to protect logical quantum states and operations. However, no meaningful data protection can be made when the syndrome extraction is erroneous due to faulty measurement gates. Quantum data-syndrome (DS) codes are designed to protect the data qubits and syndrome bits concurrently. In this paper, we propose an efficient decoding algorithm for quantum DS codes with sparse check matrices. Based on a refined belief propagation (BP) decoding for stabilizer codes, we propose a DS-BP algorithm to handle the quaternary quantum data errors and binary syndrome bit errors. Moreover, a sparse quantum code may inherently be able to handle minor syndrome errors so that fewer redundant syndrome measurements are necessary. We demonstrate this with simulations on a quantum hypergraph-product code.
Quantum stabilizer codes constructed from sparse matrices have good performance and can be efficiently decoded by belief propagation (BP). A conventional BP decoding algorithm treats binary stabilizer codes as additive codes over GF(4). This algorithm has a relatively complex process of handling check-node messages, which incurs higher decoding complexity. Moreover, BP decoding of a stabilizer code usually suffers a performance loss due to the many short cycles in the underlying Tanner graph. In this paper, we propose a refined BP decoding algorithm for quantum codes with complexity roughly the same as binary BP. For a given error syndrome, this algorithm decodes to the same output as the conventional quaternary BP but the passed node-to-node messages are single-valued, unlike the quaternary BP, where multivalued node-to-node messages are required. Furthermore, the techniques of message strength normalization can naturally be applied to these single-valued messages to improve the performance. Another observation is that the message-update schedule affects the performance of BP decoding against short cycles. We show that running BP with message strength normalization according to a serial schedule (or other schedules) may significantly improve the decoding performance and error floor in computer simulation.
Codes based on sparse matrices have good performance and can be efficiently decoded by belief-propagation (BP). Decoding binary stabilizer codes needs a quaternary BP for (additive) codes over GF(4), which has a higher check-node complexity compared to a binary BP for codes over GF(2). Moreover, BP decoding of stabilizer codes suffers a performance loss from the short cycles in the underlying Tanner graph. In this paper, we propose a refined BP algorithm for decoding quantum codes by passing scalar messages. For a given error syndrome, this algorithm decodes to the same output as the conventional quaternary BP but with a check-node complexity the same as binary BP. As every message is a scalar, the message normalization can be naturally applied to improve the performance. Another observation is that the message-update schedule affects the BP decoding performance against short cycles. We show that running BP with message normalization according to a serial schedule (or other schedules) may significantly improve the decoding performance and error-floor in computer simulation.
Quantum error correction typically requires repeated syndrome extraction due to measurement noise, which results in substantial time overhead in fault-tolerant computation. Single-shot error correction aims to suppress errors using only one round of syndrome extraction. However, for most codes, it requires high-weight checks, which significantly degrade, and often eliminate, single-shot performance at the circuit level. In this work, we introduce local single-shot checks, where we impose constraints on check weights. Using a dynamic measurement scheme, we show that the number of required measurement rounds can be reduced by a factor determined by this constraint. As an example, we show through numerical simulation that our scheme can improve decoding performance compared to conventional checks when using sliding-window decoding with a reduced window size under circuit-level noise models for toric codes. Our work provides a new direction for constructing checks that can reduce time overhead in large-scale fault-tolerant quantum computation.
In this work, we study the single-shot performance of higher-dimensional hypergraph product codes decoded using belief propagation and ordered-statistics decoding [P.Panteleev and G. Kalachev, Quantum 5, 585 (2021)].We find that decoding data-qubit and syndrome-measurement errors together in a single stage leads to single-shot thresholds that greatly exceed all previously observed single-shot thresholds for these codes.For the three-dimensional toric code and a phenomenological noise model, our results are consistent with a sustainable threshold of 7.1% for Z errors, compared to the threshold of 2.90% previously found using a two-stage decoder [Quintavalle et al., 2021].For the four-dimensional (4D) toric code, for which both X and Z error correction is single shot, our results are consistent with a sustainable single-shot threshold of 4.3%, which is even higher than the threshold of 2.93% for the two-dimensional toric code for the same noise model but using L rounds of stabilizer measurement.We also explore the performance of balanced-product and 4D hypergraph-product codes, which we show lead to a reduction in qubit overhead compared the surface code for phenomenological error rates as high as 1%.