Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2210.11552

An Efficient Quantum Decoder for Prime-Power Fields

Lior Eldar

Published Oct 20, 2022• 0 citations
arXivHTMLPDF

Abstract

We consider a version of the nearest-codeword problem on finite fields $\mathbb{F}_q$ using the Manhattan distance, an analog of the Hamming metric for non-binary alphabets. Similarly to other lattice related problems, this problem is NP-hard even up to constant factor approximation. We show, however, that for $q = p^m$ where $p$ is small relative to the code block-size $n$, there is a quantum algorithm that solves the problem in time ${\rm poly}(n)$, for approximation factor $1/n^2$, for any $p$. On the other hand, to the best of our knowledge, classical algorithms can efficiently solve the problem only for much smaller inverse polynomial factors. Hence, the decoder provides an exponential improvement over classical algorithms, and places limitations on the cryptographic security of large-alphabet extensions of code-based cryptosystems like Classic McEliece.

DOI
10.48550/arxiv.2210.11552

Related papers

DECODING M-ARY LINEAR CODES WITH THE QUANTUM APPROXIMATE OPTIMIZATION ALGORITHM

Markel Epelde, Elías F. Combarro, I. F. R ́ua

Abstract The NP-hardness of the Minimum Distance Decoding Problem (MDDP) is the core of the McEliece cryptosystem. The difficulty of decoding a received word to the closest codeword in a given arbitrary code is key to its security. Related to the MDDP is the Coset Leader Problem (CLP), which consists in finding a word of a given syndrome and minimum Hamming weight. Both can be modelled as optimization problems, and solved using the Quantum Approximate Optimization Algorithm (QAOA), a well-known hybrid quantum- classical algorithm. In this paper, we model both the MDDP and CLP for linear codes over arbitrary m−ary alphabets, we make the theoretical analysis of the first level for the binary CLP problem, and introduce some experiments to test its performance. The experiments were carried out on both quantum computer simulators and real quantum devices, and use codes of different lengths and different depths of the QAOA.

Eurasian Journal of Mathematical and Computer Applications•Mar 1, 2022•0 citations

Efficiently constructing a quantum uniform superposition over bit strings near a binary linear code

Edward Farhi, Stephen P. Jordan

We demonstrate that a high fidelity approximation to $\ket{\Psi_b}$, the quantum superposition over all bit strings within Hamming distance $b$ of the codewords of a dimension-$k$ linear code over $\mathbb{Z}_2^n$, can be efficiently constructed by a quantum circuit for large values of $n$, $b$ and $k$ which we characterize. We do numerical experiments at $n=1000$ which back up our claims. The achievable radius $b$ is much larger than the distance out to which known classical algorithms can efficiently find the nearest codeword. Hence, these states cannot be prepared by quantum constuctions that require uncomputing to find the codeword nearest a string. Unlike the analogous states for lattices in $\mathbb{R}^n$, $\ket{\Psi_b}$ is not a useful resource for bounded distance decoding because the relevant overlap falls off too quickly with distance and known classical algorithms do better. Furthermore the overlap calculation can be dequantized. Perhaps these states could be used to solve other code problems. The technique used to construct these states is of interest and hopefully will have applications beyond codes.

arXiv:2404.16129•Quantum Information and Computation•Dec 1, 2024•1 citation

The Quantum Decoding Problem

André Chailloux, Jean–Pierre Tillich

One of the founding results of lattice based cryptography is a quantum reduction from the Short Integer Solution problem to the Learning with Errors problem introduced by Regev. It has recently been pointed out by Chen, Liu and Zhandry that this reduction can be made more powerful by replacing the learning with errors problem with a quantum equivalent, where the errors are given in quantum superposition. In the context of codes, this can be adapted to a reduction from finding short codewords to a quantum decoding problem for random linear codes. We therefore consider in this paper the quantum decoding problem, where we are given a superposition of noisy versions of a codeword and we want to recover the corresponding codeword. When we measure the superposition, we get back the usual classical decoding problem for which the best known algorithms are in the constant rate and error-rate regime exponential in the codelength. However, we will show here that when the noise rate is small enough, then the quantum decoding problem can be solved in quantum polynomial time. Moreover, we also show that the problem can in principle be solved quantumly (albeit not efficiently) for noise rates for which the associated classical decoding problem cannot be solved at all for information theoretic reasons. We then revisit Regev's reduction in the context of codes. We show that using our algorithms for the quantum decoding problem in Regev's reduction matches the best known quantum algorithms for the short codeword problem. This shows in some sense the tightness of Regev's reduction when considering the quantum decoding problem and also paves the way for new quantum algorithms for the short codeword problem.

arXiv:2310.20651•Leibniz international proceedings in informatics•Oct 31, 2023•1 citation

On the Hardnesses of Several Quantum Decoding Problems

Kao-Yueh Kuo, Chung-Chin Lu

We classify the time complexities of three important decoding problems for quantum stabilizer codes. First, regardless of the channel model, quantum bounded distance decoding is shown to be NP-hard, like what Berlekamp, McEliece and Tilborg did for classical binary linear codes in 1978. Then over the depolarizing channel, the decoding problems for finding a most likely error and for minimizing the decoding error probability are also shown to be NP-hard. Our results indicate that finding a polynomial-time decoding algorithm for general stabilizer codes may be impossible, but this, on the other hand, strengthens the foundation of quantum code-based cryptography.

arXiv:1306.5173•Jun 21, 2013•6 citations

Hardness of Approximating Quantum Code Distance Beyond $\sqrt{N}$

Upendra Kapshikar

We study the computational complexity of approximating the minimum distance of a stabilizer code. Classically, the minimum distance problem is NP-hard to approximate even to within an additive gap linear in the block length. For quantum codes, however, the reductions of Kapshikar and Kundu and of Grigorescu, Jha and Samperton reach only an additive $O(\sqrt{N})$ gap in the block length $N$. We close this gap and, in a separate direction, initiate the fine-grained study of the problem. We show that no randomized algorithm approximates the distance to within an additive $αN$, for a constant $α> 0$, unless $\mathsf{NP} \subseteq \mathsf{coRP}$. In the fine-grained setting, for every $\varepsilon > 0$, no randomized $2^{(1-\varepsilon)κ}\,\mathrm{poly}(N)$-time algorithm computes the distance of a code with $κ$ logical qubits unless SETH falls; and no randomized $2^{o(N)}$-time algorithm approximates the distance to within a linear additive gap, on instances where block length, number of logical qubits, and gap are simultaneously linear, unless non-uniform Gap-ETH falls.

quant-pharXiv:2609.33956•Sep 29, 2026•0 citations

On the hardness of decoding quantum stabilizer codes under the depolarizing channel

Kao-Yueh Kuo, Chung-Chin Lu

We classify the complexity classes of several important decoding problems for quantum stabilizer codes. First, regardless of the channel model, quantum bounded distance decoding is shown to be NP-hard, like what Berlekamp, McEliece and Tilborg did for classical binary linear codes in 1978. Then under the depolarizing channel, the decoding problems for finding a most likely error and for minimizing the decoding error probability are also shown to be NP-hard. Our results indicate that finding a polynomial-time decoding algorithm for general stabilizer codes may not be possible, but this, on the other hand, strengthens the foundation of quantum code-based cryptography.

International Symposium on Information Theory and its Applications•Oct 1, 2012•7 citations
We consider a version of the nearest-codeword problem on finite fields Fq\mathbb{F}_qFq​ using the Manhattan distance, an analog of the Hamming metric for non-binary alphabets. Similarly to other lattice related problems, this problem is NP-hard even up to constant factor approximation. We show, however, that for q=pmq = p^mq=pm where ppp is small relative to the code block-size nnn, there is a quantum algorithm that solves the problem in time poly(n){\rm poly}(n)poly(n), for approximation factor 1/n21/n^21/n2, for any ppp. On the other hand, to the best of our knowledge, classical algorithms can efficiently solve the problem only for much smaller inverse polynomial factors. Hence, the decoder provides an exponential improvement over classical algorithms, and places limitations on the cryptographic security of large-alphabet extensions of code-based cryptosystems like Classic McEliece.
Abstract The NP-hardness of the Minimum Distance Decoding Problem (MDDP) is the core of the McEliece cryptosystem. The difficulty of decoding a received word to the closest codeword in a given arbitrary code is key to its security. Related to the MDDP is the Coset Leader Problem (CLP), which consists in finding a word of a given syndrome and minimum Hamming weight. Both can be modelled as optimization problems, and solved using the Quantum Approximate Optimization Algorithm (QAOA), a well-known hybrid quantum- classical algorithm. In this paper, we model both the MDDP and CLP for linear codes over arbitrary m−ary alphabets, we make the theoretical analysis of the first level for the binary CLP problem, and introduce some experiments to test its performance. The experiments were carried out on both quantum computer simulators and real quantum devices, and use codes of different lengths and different depths of the QAOA.
We demonstrate that a high fidelity approximation to ∣Ψb⟩\ket{\Psi_b}∣Ψb​⟩, the quantum superposition over all bit strings within Hamming distance bbb of the codewords of a dimension-kkk linear code over Z2n\mathbb{Z}_2^nZ2n​, can be efficiently constructed by a quantum circuit for large values of nnn, bbb and kkk which we characterize. We do numerical experiments at n=1000n=1000n=1000 which back up our claims. The achievable radius bbb is much larger than the distance out to which known classical algorithms can efficiently find the nearest codeword. Hence, these states cannot be prepared by quantum constuctions that require uncomputing to find the codeword nearest a string. Unlike the analogous states for lattices in Rn\mathbb{R}^nRn, ∣Ψb⟩\ket{\Psi_b}∣Ψb​⟩ is not a useful resource for bounded distance decoding because the relevant overlap falls off too quickly with distance and known classical algorithms do better. Furthermore the overlap calculation can be dequantized. Perhaps these states could be used to solve other code problems. The technique used to construct these states is of interest and hopefully will have applications beyond codes.
One of the founding results of lattice based cryptography is a quantum reduction from the Short Integer Solution problem to the Learning with Errors problem introduced by Regev. It has recently been pointed out by Chen, Liu and Zhandry that this reduction can be made more powerful by replacing the learning with errors problem with a quantum equivalent, where the errors are given in quantum superposition. In the context of codes, this can be adapted to a reduction from finding short codewords to a quantum decoding problem for random linear codes. We therefore consider in this paper the quantum decoding problem, where we are given a superposition of noisy versions of a codeword and we want to recover the corresponding codeword. When we measure the superposition, we get back the usual classical decoding problem for which the best known algorithms are in the constant rate and error-rate regime exponential in the codelength. However, we will show here that when the noise rate is small enough, then the quantum decoding problem can be solved in quantum polynomial time. Moreover, we also show that the problem can in principle be solved quantumly (albeit not efficiently) for noise rates for which the associated classical decoding problem cannot be solved at all for information theoretic reasons. We then revisit Regev's reduction in the context of codes. We show that using our algorithms for the quantum decoding problem in Regev's reduction matches the best known quantum algorithms for the short codeword problem. This shows in some sense the tightness of Regev's reduction when considering the quantum decoding problem and also paves the way for new quantum algorithms for the short codeword problem.
We classify the time complexities of three important decoding problems for quantum stabilizer codes. First, regardless of the channel model, quantum bounded distance decoding is shown to be NP-hard, like what Berlekamp, McEliece and Tilborg did for classical binary linear codes in 1978. Then over the depolarizing channel, the decoding problems for finding a most likely error and for minimizing the decoding error probability are also shown to be NP-hard. Our results indicate that finding a polynomial-time decoding algorithm for general stabilizer codes may be impossible, but this, on the other hand, strengthens the foundation of quantum code-based cryptography.
Hardness of Approximating Quantum Code Distance Beyond N\sqrt{N}N​
We study the computational complexity of approximating the minimum distance of a stabilizer code. Classically, the minimum distance problem is NP-hard to approximate even to within an additive gap linear in the block length. For quantum codes, however, the reductions of Kapshikar and Kundu and of Grigorescu, Jha and Samperton reach only an additive O(N)O(\sqrt{N})O(N​) gap in the block length NNN. We close this gap and, in a separate direction, initiate the fine-grained study of the problem. We show that no randomized algorithm approximates the distance to within an additive αNαNαN, for a constant α>0α> 0α>0, unless NP⊆coRP\mathsf{NP} \subseteq \mathsf{coRP}NP⊆coRP. In the fine-grained setting, for every ε>0\varepsilon > 0ε>0, no randomized 2(1−ε)κ poly(N)2^{(1-\varepsilon)κ}\,\mathrm{poly}(N)2(1−ε)κpoly(N)-time algorithm computes the distance of a code with κκκ logical qubits unless SETH falls; and no randomized 2o(N)2^{o(N)}2o(N)-time algorithm approximates the distance to within a linear additive gap, on instances where block length, number of logical qubits, and gap are simultaneously linear, unless non-uniform Gap-ETH falls.
We classify the complexity classes of several important decoding problems for quantum stabilizer codes. First, regardless of the channel model, quantum bounded distance decoding is shown to be NP-hard, like what Berlekamp, McEliece and Tilborg did for classical binary linear codes in 1978. Then under the depolarizing channel, the decoding problems for finding a most likely error and for minimizing the decoding error probability are also shown to be NP-hard. Our results indicate that finding a polynomial-time decoding algorithm for general stabilizer codes may not be possible, but this, on the other hand, strengthens the foundation of quantum code-based cryptography.