Quantum Reduction of Finding Short Code Vectors to the Decoding Problem

• URL: http://arxiv.org/abs/2106.02747v2
• Date: Fri, 2 Jun 2023 18:45:07 GMT
• Title: Quantum Reduction of Finding Short Code Vectors to the Decoding Problem
• Authors: Thomas Debris-Alazard, Maxime Remaud and Jean-Pierre Tillich
• Abstract summary: We give a quantum reduction from finding short codewords in a random linear code to decoding for the Hamming metric. This is the first time such a reduction (classical or quantum) has been obtained.
• Score: 0.9269394037577176
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We give a quantum reduction from finding short codewords in a random linear code to decoding for the Hamming metric. This is the first time such a reduction (classical or quantum) has been obtained. Our reduction adapts to linear codes Stehl\'e-Steinfield-Tanaka-Xagawa' re-interpretation of Regev's quantum reduction from finding short lattice vectors to solving the Closest Vector Problem. The Hamming metric is a much coarser metric than the Euclidean metric and this adaptation has needed several new ingredients to make it work. For instance, in order to have a meaningful reduction it is necessary in the Hamming metric to choose a very large decoding radius and this needs in many cases to go beyond the radius where decoding is always unique. Another crucial step for the analysis of the reduction is the choice of the errors that are being fed to the decoding algorithm. For lattices, errors are usually sampled according to a Gaussian distribution. However, it turns out that the Bernoulli distribution (the analogue for codes of the Gaussian) is too much spread out and cannot be used, as such, for the reduction with codes. This problem was solved by using instead a truncated Bernoulli distribution.

Related papers

• Online Gaussian elimination for quantum LDPC decoding [3.1952340441132474]
  We present an online variant of the Gaussian elimination algorithm which maintains an LUP decomposition. It is equivalent to performing Gaussian elimination once on the final system of equations. We show empirically that our online variant outperforms the original offline decoder in average-case time complexity.
  arXiv  Detail & Related papers  (2025-04-07T13:49:00Z)
• Space-Efficient Quantum Error Reduction without log Factors [50.10645865330582]
  We present a new highly simplified construction of a purifier, that can be understood as a weighted walk on a line similar to a random walk interpretation of majority voting. Our purifier has exponentially better space complexity than the previous one, and quadratically better dependence on the soundness-completeness gap of the algorithm being purified.
  arXiv  Detail & Related papers  (2025-02-13T12:04:39Z)
• Quantum advantage from soft decoders [0.7728149002473877]
  We provide improvements for some instantiations of the Optimal Polynomial Interpolation (OPI) problem. Our results provide natural and convincing decoding problems for which we believe to have a quantum advantage. In order to be able to use a decoder in the setting of Regev's reduction, we provide a novel reduction from a syndrome to a coset sampling problem.
  arXiv  Detail & Related papers  (2024-11-19T15:12:03Z)
• Limitations of the decoding-to-LPN reduction via code smoothing [59.90381090395222]
  The Learning Parity with Noise (LPN) problem underlies several classic cryptographic primitives. This paper attempts to find a reduction from the decoding problem of linear codes, for which several hardness results exist. We characterize the efficiency of the reduction in terms of the parameters of the decoding and problems.
  arXiv  Detail & Related papers  (2024-08-07T12:54:43Z)
• The Quantum Decoding Problem [0.23310087539224286]
  We consider the quantum decoding problem, where we are given a superposition of noisy versions of a codeword. We show that when the noise rate is small enough, then the quantum decoding problem can be solved in quantum time. We also show that the problem can in principle be solved quantumly for noise rates for which the associated classical decoding problem cannot be solved.
  arXiv  Detail & Related papers  (2023-10-31T17:21:32Z)
• Analysis of the Error-Correcting Radius of a Renormalisation Decoder for Kitaev's Toric Code [0.0]
  Kitaev's toric code is arguably the most studied quantum code. Renormalisation decoders exhibit one of the best trade-offs between efficiency and speed.
  arXiv  Detail & Related papers  (2023-09-21T15:23:41Z)
• Bounds on Autonomous Quantum Error Correction [3.9119979887528125]
  We analyze Markovian autonomous decoders that can be implemented with a wide range of qubit and bosonic error-correcting codes. For many-body quantum codes, we show that, to achieve error suppression comparable to active error correction, autonomous decoders generally require correction rates that grow with code size.
  arXiv  Detail & Related papers  (2023-08-30T18:00:07Z)
• Fault-Tolerant Computing with Single Qudit Encoding [49.89725935672549]
  We discuss stabilizer quantum-error correction codes implemented in a single multi-level qudit. These codes can be customized to the specific physical errors on the qudit, effectively suppressing them. We demonstrate a Fault-Tolerant implementation on molecular spin qudits, showcasing nearly exponential error suppression with only linear qudit size growth.
  arXiv  Detail & Related papers  (2023-07-20T10:51:23Z)
• 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)
• 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 computation on a 19-qubit wide 2d nearest neighbour qubit array [59.24209911146749]
  This paper explores the relationship between the width of a qubit lattice constrained in one dimension and physical thresholds. We engineer an error bias at the lowest level of encoding using the surface code. We then address this bias at a higher level of encoding using a lattice-surgery surface code bus.
  arXiv  Detail & Related papers  (2022-12-03T06:16:07Z)
• Correcting spanning errors with a fractal code [7.6146285961466]
  We propose an efficient decoder for the Fibonacci code'; a two-dimensional classical code that mimics the fractal nature of the cubic code. We perform numerical experiments that show our decoder is robust to one-dimensional, correlated errors.
  arXiv  Detail & Related papers  (2020-02-26T19:00:06Z)

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.