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

IEEE International Symposium on Information Theory (ISIT)

Asymptotic Improvements to Provable Algorithms for the Code Equivalence Problem

Huck Bennett, Drisana Bhatia, Jean‐François Biasse, Medha Durisheti, Lucas LaBuff, Vincenzo Pallozzi Lavorante, Philip Waitkevich

Published Jun 22, 2025• 2 citations
Publisher

Abstract

We present several new provable algorithms for two variants of the code equivalence problem on linear error-correcting codes, the Linear Code Equivalence Problem (LCE) and the Permutation Code Equivalence Problem (PCE). Specifically, for arbitrary codes of block length$n$and dimension$k$over any finite field$\mathbb{F}_{q}$, we show: 1)A deterministic algorithm running in$2^{n+o(n+q)}$time for LCE. 2)A randomized algorithm running in$2^{n / 2+o(n+q)}$time for LCE and PCE. 3)A quantum algorithm running in$2^{n / 3+o(n+q)}$time for LCE and PCE. The second two algorithms improve on recent work of Nowakowski (PQCrypto 2025), which gave algorithms with similar running times but only for code equivalence on random codes and only over fields of order$q \geq 7$.

DOI
10.1109/isit63088.2025.11195271

Related papers

Asymptotic Improvements to Provable Algorithms for the Code Equivalence Problem

Huck Bennett, Drisana Bhatia, Jean‐François Biasse +4 more

We present several new provable algorithms for two variants of the code equivalence problem on linear error-correcting codes, the Linear Code Equivalence Problem (LCE) and the Permutation Code Equivalence Problem (PCE). Specifically, for arbitrary codes of block lengthnand dimensionkover any finite field Fq, we show: 1) A deterministic algorithm running in 2n+o(n+q)time for LCE. 2) A randomized algorithm running in 2n/2+o(n+q)time for LCE and PCE. 3) A quantum algorithm running in 2n/3+o(n+q)time for LCE and PCE. The second two algorithms improve on recent work of Nowakowski (PQCrypto 2025), which gave algorithms with similar running times but only for code equivalence onrandomcodes and only over fields of orderq≥ 7.

IEEE Transactions on Information Theory•Nov 26, 2025•3 citations

Linear-Time Encodable and Decodable Quantum Error-Correcting Codes

Adam Wills, Ting-Chun Lin, Rachel Yun Zhang +1 more

Recent years have seen rapid development in the subject of quantum coding theory, with breakthroughs on many exciting classes of codes, including quantum LDPC codes, quantum locally testable codes, and quantum codes with interesting transversal gates. However, a natural class of quantum codes, which has been well-studied classically, has not yet been treated: those which can be quickly encoded and decoded. This problem concerns the channel capacity setting, where a noise channel sits between perfect encoding and unencoding/decoding operations; this is the setting that is relevant for communication between fault-tolerant quantum computers. In this work, we construct asymptotically good quantum codes that can be encoded and unencoded by quantum circuits of logarithmic depth and consisting of a linear total number of gates. The classical decoding algorithms also run in logarithmic depth and use $\mathcal{O}(n \log n)$ gates, or alternatively a linear number of gates but with higher depth. We further construct explicit and asymptotically good quantum codes whose encoding, unencoding and decoding all use a linear number of gates, and additionally whose encoding and unencoding may be run in logarithmic depth.

quant-pharXiv:2603.04543•Mar 6, 2026•2 citations

The Code Distortion Problem

Huck Bennett, Matthew S. Fox, Bryant Morrell

Two linear error-correcting codes $\cal{C}_1, \cal{C}_2 \subseteq \mathbb{F}_q^n$ are called linearly equivalent if there is a linear isometry mapping $\cal{C}_1$ to $\cal{C}_2$. In this work, we generalize the notion of linear equivalence and study the minimum distortion $\cal{D}(\cal{C}_1, \cal{C}_2)$ of a linear mapping between codes $\cal{C}_1, \cal{C}_2 \subseteq \mathbb{F}_q^n$, which quantifies how similar $\cal{C}_1$ and $\cal{C}_2$ are. We introduce and study the Code Distortion Problem (CDP), which asks to find a minimum distortion mapping between two input codes $\cal{C}_1$ and $\cal{C}_2$. CDP generalizes the Linear Code Equivalence Problem (LCE), which is essentially the special case of CDP where $\cal{D}(\cal{C}_1, C_2) = 1$ and which is well-studied because of its role in cryptography. We prove that (decisional) CDP is $\mathsf{NP}$-hard to approximate to within any constant factor, and that it is in $Σ_2^P$. We also give a single-exponential-time $k^2$-approximation algorithm for CDP, where $k$ is the dimension of the input codes. Furthermore, we give a single-exponential-time $\big(\frac{2k + 1}{3})^2$-approximation algorithm for a natural special case of CDP, and we show that our analysis is tight in this case. We use techniques from analogous work on the Lattice Distortion Problem (LDP) by Bennett, Dadush, and Stephens-Davidowitz (ESA, 2016). We also introduce or study a number of additional concepts that might be of independent interest. These include an adaptation of the celebrated reduction of Goldreich, Micciancio, Safra, and Seifert (IPL, 1999) from the Shortest Vector Problem (SVP) to the Closest Vector Problem (CVP) on lattices to the analogous problems on codes; successive minima bases for codes; and the matrix $0 \to 0$ "norm" on subspaces.

arXiv:2607.26261•Leibniz international proceedings in informatics•Jan 1, 2026•0 citations

Distance verification for LDPC codes

Ilya I. Dumer, Alexey A. Kovalev, Leonid P. Pryadko

The problem of finding code distance has been long studied for the generic ensembles of linear codes and led to several algorithms that substantially reduce exponential complexity of this task. However, no asymptotic complexity bounds are known for distance verification in other ensembles of linear codes. Our goal is to re-design the existing generic algorithms of distance verification and derive their complexity for LDPC codes. We obtain new complexity bounds with provable performance expressed in terms of the erasure-correcting thresholds of long LDPC codes. These bounds exponentially reduce complexity estimates known for linear codes.

arXiv:1605.02410•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•2 citations

Distance Verification for LDPC Codes

Ilya I. Dumer, Alexey A. Kovalev, Leonid P. Pryadko +1 more

The problem of finding code distance has been long studied for the generic\nensembles of linear codes and led to several algorithms that substantially\nreduce exponential complexity of this task. However, no asymptotic complexity\nbounds are known for distance verification in other ensembles of linear codes.\nOur goal is to re-design the existing generic algorithms of distance\nverification and derive their complexity for LDPC codes. We obtain new\ncomplexity bounds with provable performance expressed in terms of the\nerasure-correcting thresholds of long LDPC codes. These bounds exponentially\nreduce complexity estimates known for linear codes.

•Jan 1, 2016•2 citations

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•17 citations
We present several new provable algorithms for two variants of the code equivalence problem on linear error-correcting codes, the Linear Code Equivalence Problem (LCE) and the Permutation Code Equivalence Problem (PCE). Specifically, for arbitrary codes of block lengthnnnand dimensionkkkover any finite fieldFq\mathbb{F}_{q}Fq​, we show: 1)A deterministic algorithm running in2n+o(n+q)2^{n+o(n+q)}2n+o(n+q)time for LCE. 2)A randomized algorithm running in2n/2+o(n+q)2^{n / 2+o(n+q)}2n/2+o(n+q)time for LCE and PCE. 3)A quantum algorithm running in2n/3+o(n+q)2^{n / 3+o(n+q)}2n/3+o(n+q)time for LCE and PCE. The second two algorithms improve on recent work of Nowakowski (PQCrypto 2025), which gave algorithms with similar running times but only for code equivalence on random codes and only over fields of orderq≥7q \geq 7q≥7.
We present several new provable algorithms for two variants of the code equivalence problem on linear error-correcting codes, the Linear Code Equivalence Problem (LCE) and the Permutation Code Equivalence Problem (PCE). Specifically, for arbitrary codes of block lengthnand dimensionkover any finite field Fq, we show: 1) A deterministic algorithm running in 2n+o(n+q)time for LCE. 2) A randomized algorithm running in 2n/2+o(n+q)time for LCE and PCE. 3) A quantum algorithm running in 2n/3+o(n+q)time for LCE and PCE. The second two algorithms improve on recent work of Nowakowski (PQCrypto 2025), which gave algorithms with similar running times but only for code equivalence onrandomcodes and only over fields of orderq≥ 7.
Recent years have seen rapid development in the subject of quantum coding theory, with breakthroughs on many exciting classes of codes, including quantum LDPC codes, quantum locally testable codes, and quantum codes with interesting transversal gates. However, a natural class of quantum codes, which has been well-studied classically, has not yet been treated: those which can be quickly encoded and decoded. This problem concerns the channel capacity setting, where a noise channel sits between perfect encoding and unencoding/decoding operations; this is the setting that is relevant for communication between fault-tolerant quantum computers. In this work, we construct asymptotically good quantum codes that can be encoded and unencoded by quantum circuits of logarithmic depth and consisting of a linear total number of gates. The classical decoding algorithms also run in logarithmic depth and use O(nlog⁡n)\mathcal{O}(n \log n)O(nlogn) gates, or alternatively a linear number of gates but with higher depth. We further construct explicit and asymptotically good quantum codes whose encoding, unencoding and decoding all use a linear number of gates, and additionally whose encoding and unencoding may be run in logarithmic depth.
Two linear error-correcting codes C1,C2⊆Fqn\cal{C}_1, \cal{C}_2 \subseteq \mathbb{F}_q^nC1​,C2​⊆Fqn​ are called linearly equivalent if there is a linear isometry mapping C1\cal{C}_1C1​ to C2\cal{C}_2C2​. In this work, we generalize the notion of linear equivalence and study the minimum distortion D(C1,C2)\cal{D}(\cal{C}_1, \cal{C}_2)D(C1​,C2​) of a linear mapping between codes C1,C2⊆Fqn\cal{C}_1, \cal{C}_2 \subseteq \mathbb{F}_q^nC1​,C2​⊆Fqn​, which quantifies how similar C1\cal{C}_1C1​ and C2\cal{C}_2C2​ are. We introduce and study the Code Distortion Problem (CDP), which asks to find a minimum distortion mapping between two input codes C1\cal{C}_1C1​ and C2\cal{C}_2C2​. CDP generalizes the Linear Code Equivalence Problem (LCE), which is essentially the special case of CDP where D(C1,C2)=1\cal{D}(\cal{C}_1, C_2) = 1D(C1​,C2​)=1 and which is well-studied because of its role in cryptography. We prove that (decisional) CDP is NP\mathsf{NP}NP-hard to approximate to within any constant factor, and that it is in Σ2PΣ_2^PΣ2P​. We also give a single-exponential-time k2k^2k2-approximation algorithm for CDP, where kkk is the dimension of the input codes. Furthermore, we give a single-exponential-time (2k+13)2\big(\frac{2k + 1}{3})^2(32k+1​)2-approximation algorithm for a natural special case of CDP, and we show that our analysis is tight in this case. We use techniques from analogous work on the Lattice Distortion Problem (LDP) by Bennett, Dadush, and Stephens-Davidowitz (ESA, 2016). We also introduce or study a number of additional concepts that might be of independent interest. These include an adaptation of the celebrated reduction of Goldreich, Micciancio, Safra, and Seifert (IPL, 1999) from the Shortest Vector Problem (SVP) to the Closest Vector Problem (CVP) on lattices to the analogous problems on codes; successive minima bases for codes; and the matrix 0→00 \to 00→0 "norm" on subspaces.
The problem of finding code distance has been long studied for the generic ensembles of linear codes and led to several algorithms that substantially reduce exponential complexity of this task. However, no asymptotic complexity bounds are known for distance verification in other ensembles of linear codes. Our goal is to re-design the existing generic algorithms of distance verification and derive their complexity for LDPC codes. We obtain new complexity bounds with provable performance expressed in terms of the erasure-correcting thresholds of long LDPC codes. These bounds exponentially reduce complexity estimates known for linear codes.
The problem of finding code distance has been long studied for the generic\nensembles of linear codes and led to several algorithms that substantially\nreduce exponential complexity of this task. However, no asymptotic complexity\nbounds are known for distance verification in other ensembles of linear codes.\nOur goal is to re-design the existing generic algorithms of distance\nverification and derive their complexity for LDPC codes. We obtain new\ncomplexity bounds with provable performance expressed in terms of the\nerasure-correcting thresholds of long LDPC codes. These bounds exponentially\nreduce complexity estimates known for linear 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.