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$.
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 fieldFq, we show: 1)A deterministic algorithm running in2n+o(n+q)time for LCE. 2)A randomized algorithm running in2n/2+o(n+q)time for LCE and PCE. 3)A quantum algorithm running in2n/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≥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(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.
Color codes are an important family of topological quantum error-correcting codes, in part because they support a richer set of transversal logical gates than surface codes. Their practical use, however, requires efficient decoding. Minimum-weight decoding is natural under independent noise, but Walters and Turner recently proved that it is NP-hard for the two-dimensional color code. Subsequent independent work of Walters and of Gu, Wang, and Kubica gave polynomial-time approximation schemes; in terms of lattice size N, their running times are O(N2+528/ε) and N(logN)O(1/ε), respectively, for a (1+ε)-approximation. We ask whether stronger guarantees are possible for random instances generated by a natural iid noise model. For triangular color-code lattices with N faces and iid face-error probability p, we obtain near-linear-time algorithms throughout the noise range considered. If p=o(1/log2N), we compute an exact minimum-weight correction in deterministic N1+o(1) time with high probability. If p=Ω(1/log2N), with p bounded away from 1/2, we compute a 1+o(1)-approximation in deterministic N1+o(1) time with high probability. When the syndrome is supplied sparsely and has size s, the corresponding high-probability running times improve to (1+s)No(1) and s1+o(1), respectively. The algorithms exploit different random structure at different noise scales: localization into small exact subproblems in the sparse regime, peeling of locally unambiguous errors at intermediate densities, and a block decomposition whose additive loss is negligible relative to the typical optimum at larger densities. Together, these results give a near-linear average-case counterpart to recent worst-case hardness and approximation results for color-code decoding.
We investigate Permutation-Invariant (PI) quantum error-correcting codes encoding a logical qudit of dimension dL in PI states using physical qudits of dimension dP. We extend the Knill--Laflamme (KL) conditions for d−1 deletion errors from qubits to qudits and investigate numerically both qubit (dL=dP=2) and qudit (dL>2 or dP>2) PI codes. We analyze the scaling of the block length n in terms of the code distance d, and compare to existing families of PI codes due to Ouyang, Aydin--Alekseyev--Barg (AAB) and Pollatsek--Ruskai (PR). Our three main findings are: (i) We conjecture that qubit PI codes correcting up to d−1 deletion errors have block length n(d)≥(3d2+1)/4, which implies an upper bound d≤12n−3/3 on their code distance, and that PR codes can saturate this bound. (ii) For qudit PI codes encoding a single qudit we numerically observe that increasing dP results in n monotonically decreasing and approaching the quantum Singleton bound n(d)≥2d−1. (iii) We propose a semi-analytic extension of the qubit AAB construction to qudits that finds explicit solutions by solving a linear program. Our results therefore provide key insights into lower bounds on the block length scaling of both qubit and qudit PI codes, and demonstrate the benefit of increased physical local dimension in the context of PI codes.