Related papers: The Quantum Decoding Problem : Tight Achievability Bounds and Application to Regev's Reduction

The Quantum Decoding Problem : Tight Achievability Bounds and Application to Regev's Reduction

URL: http://arxiv.org/abs/2509.24796v1
Date: Mon, 29 Sep 2025 13:48:05 GMT
Title: The Quantum Decoding Problem : Tight Achievability Bounds and Application to Regev's Reduction
Authors: Agathe Blanvillain, André Chailloux, Jean-Pierre Tillich,
Abstract summary: We show a quantum advantage for the Short Solution (SIS) problem for the $l_infty$ norm.<n>In a recent paper, Chailloux and Tillich proved that when we have a noise following a Bernoulli distribution, the quantum decoding problem can be solved in algorithm time.
Score: 6.140129238616484
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We consider the quantum decoding problem. It consists in recovering a codeword given a superposition of noisy versions of this codeword. By measuring the superposition, we get back to the classical decoding problem. It appears for the first time in Chen, Liu and Zhandry's work showing a quantum advantage for the Short Integer Solution (SIS) problem for the $l_\infty$ norm. In a recent paper, Chailloux and Tillich proved that when we have a noise following a Bernoulli distribution, the quantum decoding problem can be solved in polynomial time and is therefore easier than classical decoding for which the best known algorithms have an exponential complexity. They also give an information theoretic limit for the code rate at which this problem can be solved which turns out to be above the Shannon limit. In this paper, we generalize the last result to all memoryless noise models. We also show similar results in the rank metric case which corresponds to a noise model which is not memoryless. We analyze the Pretty Good Measurement, from which we derive an information theoretic limit for this problem. By using the algorithm for the quantum decoding problem together with Regev's reduction, we derive a quantum algorithm sampling codewords from the dual code according to a probability distribution which is the dual of the original noise. It turns out that at the information theoretic limit, we get the most likely nonzero codeword of the dual code. When the distribution is a decreasing function of the weight, we find minimal nonzero codewords. Note that Regev's reduction used together with classical decoding is much less satisfying since it is not able to output those minimum weight codewords.

Related papers

OPI x Soft Decoders [3.0458514384586404]
We build on a recent formulation of the reduction by Chailloux and Hermouet in the lattice-based setting.<n>We show that the results of Jordan et al. can be recovered under Bernoulli noise models.<n>This characterization then allows us to integrate the stronger soft decoders of Chailloux and Tillich into the OPI framework.
arXiv Detail & Related papers (2025-11-27T18:45:28Z)
Fast correlated decoding of transversal logical algorithms [67.01652927671279]
Quantum error correction (QEC) is required for large-scale computation, but incurs a significant resource overhead.<n>Recent advances have shown that by jointly decoding logical qubits in algorithms composed of logical gates, the number of syndrome extraction rounds can be reduced.<n>Here, we reform the problem of decoding circuits by directly decoding relevant logical operator products as they propagate through the circuit.
arXiv Detail & Related papers (2025-05-19T18:00: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.<n>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)
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)
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)
Scalable noisy quantum circuits for biased-noise qubits [37.69303106863453]
We consider biased-noise qubits affected only by bit-flip errors, which is motivated by existing systems of stabilized cat qubits. For realistic noise models, phase-flip will not be negligible, but in the Pauli-Twirling approximation, we show that our benchmark could check the correctness of circuits containing up to $106$ gates.
arXiv Detail & Related papers (2023-05-03T11:27:50Z)
Noisy decoding by shallow circuits with parities: classical and quantum [0.0]
We show that any classical circuit can correctly recover only a vanishingly small fraction of messages, if the codewords are sent over a noisy channel with positive error rate. We give a simple quantum circuit that correctly decodes the Hadamard code with probability $Omega(varepsilon2)$ even if a $(1/2 - varepsilon)$-fraction of a codeword is adversarially corrupted.
arXiv Detail & Related papers (2023-02-06T15:37:32Z)
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)
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)
Dense Coding with Locality Restriction for Decoder: Quantum Encoders vs. Super-Quantum Encoders [67.12391801199688]
We investigate dense coding by imposing various locality restrictions to our decoder. In this task, the sender Alice and the receiver Bob share an entangled state.
arXiv Detail & Related papers (2021-09-26T07:29:54Z)
Space-efficient binary optimization for variational computing [68.8204255655161]
We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
arXiv Detail & Related papers (2020-09-15T18:17:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.