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
- 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) - Quantum Lego Expansion Pack: Enumerators from Tensor Networks [1.489619600985197]
We provide the first tensor network method for computing quantum weight enumerators in the most general form.
For non-(Pauli)-stabilizer codes, this constitutes the current best algorithm for computing the code distance.
We show that these enumerators can be used to compute logical error rates exactly and thus construct decoders for any i.i.d. single qubit or qudit error channels.
arXiv Detail & Related papers (2023-08-09T18:00:02Z) - 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) - Distributed Quantum-classical Hybrid Shor's Algorithm [1.7396274240172125]
Shor's algorithm is considered as one of the most significant quantum algorithms of the Noisy Intermediate Quantum era.
To reduce the resources required for Shor's algorithm, we propose a new distributed quantum-classical hybrid order-finding algorithm.
arXiv Detail & Related papers (2023-04-24T13:52:05Z) - 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) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits.
Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit.
We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
arXiv Detail & Related papers (2022-06-30T03:15:23Z) - 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.