Viderman's algorithm for quantum LDPC codes

• URL: http://arxiv.org/abs/2310.07868v1
• Date: Wed, 11 Oct 2023 20:17:21 GMT
• Title: Viderman's algorithm for quantum LDPC codes
• Authors: Anirudh Krishna, Inbal Livni Navon, Mary Wootters
• Abstract summary: We present a generalization of Viderman's algorithm to quantum LDPC codes. This is the first erasure-conversion algorithm that can correct up to $Omega(D)$ errors for constant-rate quantum LDPC codes.
• Score: 13.916368399461895
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum low-density parity-check (LDPC) codes, a class of quantum error correcting codes, are considered a blueprint for scalable quantum circuits. To use these codes, one needs efficient decoding algorithms. In the classical setting, there are multiple efficient decoding algorithms available, including Viderman's algorithm (Viderman, TOCT 2013). Viderman's algorithm for classical LDPC codes essentially reduces the error-correction problem to that of erasure-correction, by identifying a small envelope $L$ that is guaranteed to contain the error set. Our main result is a generalization of Viderman's algorithm to quantum LDPC codes, namely hypergraph product codes (Tillich, Z\'emor, IEEE T-IT, 2013). This is the first erasure-conversion algorithm that can correct up to $\Omega(D)$ errors for constant-rate quantum LDPC codes, where $D$ is the distance of the code. In that sense, it is also fundamentally different from existing decoding algorithms, in particular from the small-set-flip algorithm (Leverrier, Tillich, Z\'emor, FOCS, 2015). Moreover, in some parameter regimes, our decoding algorithm improves on the decoding radius of existing algorithms. We note that we do not yet have linear-time erasure-decoding algorithms for quantum LDPC codes, and thus the final running time of the whole decoding algorithm is not linear; however, we view our linear-time envelope-finding algorithm as an important first step.

Related papers

• Decoding Quasi-Cyclic Quantum LDPC Codes [23.22566380210149]
  Quantum low-density parity-check (qLDPC) codes are an important component in the quest for fault tolerance. Recent progress on qLDPC codes has led to constructions which are quantumally good, and which admit linear-time decoders to correct errors affecting a constant fraction of codeword qubits. In practice, the surface/toric codes, which are the product of two repetition codes, are still often the qLDPC codes of choice.
  arXiv  Detail & Related papers  (2024-11-07T06:25:27Z)
• 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)
• Engineering Quantum Error Correction Codes Using Evolutionary Algorithms [0.0]
  Quantum error correction and the use of quantum error correction codes is likely to be essential for the realisation of practical quantum computing. We present a novel evolutionary algorithm which searches for an optimal stabiliser code for a given error model. As part of this work, we also introduce an evolutionary algorithm QDistEvol for finding the distance of quantum error correction codes.
  arXiv  Detail & Related papers  (2024-09-19T18:00:02Z)
• Bit-flipping Decoder Failure Rate Estimation for (v,w)-regular Codes [84.0257274213152]
  We propose a new technique to provide accurate estimates of the DFR of a two-iterations (parallel) bit flipping decoder. We validate our results, providing comparisons of the modeled and simulated weight of the syndrome, incorrectly-guessed error bit distribution at the end of the first iteration, and two-itcrypteration Decoding Failure Rates (DFR)
  arXiv  Detail & Related papers  (2024-01-30T11:40:24Z)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al. We apply our algorithm to the quantum information bottleneck with three quantum systems. Our numerical analysis shows that our algorithm is better than their algorithm.
  arXiv  Detail & Related papers  (2023-11-19T00:06:11Z)
• Improved belief propagation decoding algorithm based on decoupling representation of Pauli operators for quantum LDPC codes [8.811819329067285]
  Decoupling representation to represent Pauli operators as vectors over $GF(2)$. Partially decoupled belief propagation and fully decoupled belief propagation decoding algorithm for quantum low density parity-check codes.
  arXiv  Detail & Related papers  (2023-05-27T15:59:42Z)
• Machine Learning-Aided Efficient Decoding of Reed-Muller Subcodes [59.55193427277134]
  Reed-Muller (RM) codes achieve the capacity of general binary-input memoryless symmetric channels. RM codes only admit limited sets of rates. Efficient decoders are available for RM codes at finite lengths.
  arXiv  Detail & Related papers  (2023-01-16T04:11:14Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• An efficient decoder for a linear distance quantum LDPC code [0.1657441317977376]
  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.
  arXiv  Detail & Related papers  (2022-06-14T02:17:09Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Quantum message-passing algorithm for optimal and efficient decoding [2.3020018305241328]
  We expand the understanding, formalism, and applicability of the BPQM algorithm. We provide the first formal description of the BPQM algorithm in full detail and without any ambiguity. We show some promising numerical results that indicate that BPQM on factor graphs with cycles can significantly outperform the best possible classical decoder.
  arXiv  Detail & Related papers  (2021-09-16T18:01:12Z)

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.