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
- List Decodable Quantum LDPC Codes [49.2205789216734]
We give a construction of Quantum Low-Density Parity Check (QLDPC) codes with near-optimal rate-distance tradeoff.
We get efficiently list decodable QLDPC codes with unique decoders.
arXiv Detail & Related papers (2024-11-06T23:08:55Z) - Effective Distance of Higher Dimensional HGPs and Weight-Reduced Quantum LDPC Codes [0.0]
We show that there exists single-ancilla syndrome extraction circuits that largely preserve the effective distance of the weight-reduced qLDPC codes.
As a corollary, our result shows that higher-dimensional hypergraph product codes have no troublesome hook errors when using any single-ancilla syndrome extraction circuit.
arXiv Detail & Related papers (2024-09-03T18:02:33Z) - 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 (LDPC) 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) - 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) - 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.