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(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 are called linearly equivalent if there is a linear isometry mapping
C1 to
C2. In this work, we generalize the notion of linear equivalence and study the minimum distortion
D(C1,C2) of a linear mapping between codes
C1,C2⊆Fqn, which quantifies how similar
C1 and
C2 are. We introduce and study the Code Distortion Problem (CDP), which asks to find a minimum distortion mapping between two input codes
C1 and
C2. CDP generalizes the Linear Code Equivalence Problem (LCE), which is essentially the special case of CDP where
D(C1,C2)=1 and which is well-studied because of its role in cryptography. We prove that (decisional) CDP is
NP-hard to approximate to within any constant factor, and that it is in
Σ2P. We also give a single-exponential-time
k2-approximation algorithm for CDP, where
k is the dimension of the input codes. Furthermore, we give a single-exponential-time
(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→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.