An efficient decoder for a linear distance quantum LDPC code
- URL: http://arxiv.org/abs/2206.06557v1
- Date: Tue, 14 Jun 2022 02:17:09 GMT
- Title: An efficient decoder for a linear distance quantum LDPC code
- Authors: Shouzhen Gu, Christopher A. Pattison, Eugene Tang
- Abstract summary: We present a linear time decoder for the recent quantumally good qLDPC codes.
Our decoder is an iterative algorithm which searches for corrections within constant-sized regions.
- Score: 0.1657441317977376
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Recent developments have shown the existence of quantum low-density parity
check (qLDPC) codes with constant rate and linear distance. A natural question
concerns the efficient decodability of these codes. In this paper, we present a
linear time decoder for the recent quantum Tanner codes construction of
asymptotically good qLDPC codes, which can correct all errors of weight up to a
constant fraction of the blocklength. Our decoder is an iterative algorithm
which searches for corrections within constant-sized regions. At each step, the
corrections are found by reducing a locally defined and efficiently computable
cost function which serves as a proxy for the weight of the remaining error.
Related papers
- Breadth-first graph traversal union-find decoder [0.0]
We develop variants of the union-find decoder that simplify its implementation and provide potential decoding speed advantages.
We show how these methods can be adapted to decode non-topological quantum low-density-parity-check codes.
arXiv Detail & Related papers (2024-07-22T18:54:45Z) - Factor Graph Optimization of Error-Correcting Codes for Belief Propagation Decoding [62.25533750469467]
Low-Density Parity-Check codes possess several advantages over other families of codes.
The proposed approach is shown to outperform the decoding performance of existing popular codes by orders of magnitude.
arXiv Detail & Related papers (2024-06-09T12:08:56Z) - Improved Noisy Syndrome Decoding of Quantum LDPC Codes with Sliding
Window [0.0]
We study sliding-window decoding, which corrects errors from previous syndrome measurement rounds while leaving the most recent errors for future correction.
Remarkably, we find that this improvement may not cost a larger decoding complexity.
arXiv Detail & Related papers (2023-11-06T17:56:49Z) - The END: An Equivariant Neural Decoder for Quantum Error Correction [73.4384623973809]
We introduce a data efficient neural decoder that exploits the symmetries of the problem.
We propose a novel equivariant architecture that achieves state of the art accuracy compared to previous neural decoders.
arXiv Detail & Related papers (2023-04-14T19:46:39Z) - Deep Quantum Error Correction [73.54643419792453]
Quantum error correction codes (QECC) are a key component for realizing the potential of quantum computing.
In this work, we efficiently train novel emphend-to-end deep quantum error decoders.
The proposed method demonstrates the power of neural decoders for QECC by achieving state-of-the-art accuracy.
arXiv Detail & Related papers (2023-01-27T08:16:26Z) - Neural Belief Propagation Decoding of Quantum LDPC Codes Using
Overcomplete Check Matrices [60.02503434201552]
We propose to decode QLDPC codes based on a check matrix with redundant rows, generated from linear combinations of the rows in the original check matrix.
This approach yields a significant improvement in decoding performance with the additional advantage of very low decoding latency.
arXiv Detail & Related papers (2022-12-20T13:41:27Z) - Quantum Error Correction via Noise Guessing Decoding [0.0]
Quantum error correction codes (QECCs) play a central role in both quantum communications and quantum computation.
This paper shows that it is possible to both construct and decode QECCs that can attain the maximum performance of the finite blocklength regime.
arXiv Detail & Related papers (2022-08-04T16:18:20Z) - Efficient decoding up to a constant fraction of the code length for
asymptotically good quantum codes [0.38073142980732994]
Previous decoders for quantum low-density parity-check codes could only handle adversarial errors of weight $O(sqrtn log n)$.
We show that our decoder can be adapted to the Lifted Product codes of Panteleev and Kalachev.
arXiv Detail & Related papers (2022-06-15T14:46:06Z) - Improved decoding of circuit noise and fragile boundaries of tailored
surface codes [61.411482146110984]
We introduce decoders that are both fast and accurate, and can be used with a wide class of quantum error correction codes.
Our decoders, named belief-matching and belief-find, exploit all noise information and thereby unlock higher accuracy demonstrations of QEC.
We find that the decoders led to a much higher threshold and lower qubit overhead in the tailored surface code with respect to the standard, square surface code.
arXiv Detail & Related papers (2022-03-09T18:48:54Z) - Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
We show that the problem of calculating the $c-disjointness, or even approximating it to within a constant multiplicative factor, is NP-complete.
We provide bounds on the disjointness for various code families, including the CSS codes,$d codes and hypergraph codes.
Our results indicate that finding fault-tolerant logical gates for generic quantum error-correcting codes is a computationally challenging task.
arXiv Detail & Related papers (2021-08-10T15:00:20Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.