# Quantum Reduction of Finding Short Code Vectors to the Decoding Problem

Thomas Debris-Alazard, Maxime Remaud, Jean-Pierre Tillich

► To cite this version:

Thomas Debris-Alazard, Maxime Remaud, Jean-Pierre Tillich. Quantum Reduction of Finding Short Code Vectors to the Decoding Problem. IEEE Transactions on Information Theory, 2024, 70 (7), pp.5323-5342. 10.1109/TIT.2023.3327759. hal-04276190v2

HAL Id: hal-04276190

https://inria.hal.science/hal-04276190v2

Submitted on 8 Nov 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Quantum Reduction of Finding Short Code Vectors to the Decoding Problem

Thomas Debris-Alazard, Maxime Remaud and Jean-Pierre Tillich

**Abstract**—We give a quantum reduction from finding short codewords in a random linear code to decoding for the Hamming metric. This is the first time such a reduction (classical or quantum) has been obtained. Our reduction adapts to linear codes the Stehlé-Steinfield-Tanaka-Xagawa' re-interpretation of Regev's quantum reduction from finding short lattice vectors to solving the Closest Vector Problem. The Hamming metric is a much coarser metric than the Euclidean metric and this adaptation has needed several new ingredients to make it work. For instance, in order to have a meaningful reduction it is necessary in the Hamming metric to choose a very large decoding radius and this needs in many cases to go beyond the radius where decoding is always unique. Another crucial step for the analysis of the reduction is the choice of the errors that are being fed to the decoding algorithm. For lattices, errors are usually sampled according to a Gaussian distribution. However, it turns out that the Bernoulli distribution (the analogue for codes of the Gaussian) is too much spread out and cannot be used, as such, for the reduction with codes. This problem was solved by using instead a truncated Bernoulli distribution.

## 1. INTRODUCTION

**Code-based Cryptography.** Many cryptosystems such as public-key encryption schemes [1], [2], [3], authentication protocols [4] or pseudorandom generators [5] are built relying on the hardness of finding the closest codeword, a task called decoding. In the case of a random linear code, which is the standard case, this problem can be expressed as follows:

**Problem 1** ($DP(q, n, k, t)$): The decoding problem with parameters $q, n, k, t \in \mathbb{N}$ is defined as:

* Given: $(\mathbf{G}, \mathbf{u}\mathbf{G} + \mathbf{e})$ where $\mathbf{G} \in \mathbb{F}_q^{k \times n}$ and $\mathbf{u} \in \mathbb{F}_q^k$ are sampled uniformly at random over their domain and $\mathbf{e} \in \mathbb{F}_q^n$ over the words of weight $t$,

* Find: $\mathbf{e}$.

This problem really corresponds to decoding the $k$-dimensional vector space $\mathcal{C}$ (i.e., the code) generated by the rows of $\mathbf{G}$:

$$ \mathcal{C} \stackrel{\text{def}}{=} \{\mathbf{u}\mathbf{G}: \mathbf{u} \in \mathbb{F}_q^k\}. \quad (1) $$

Thomas Debris-Alazard is with Inria and the LIX, École polytechnique, 91120 Palaiseau, France (e-mail: thomas.debris@inria.fr)

Maxime Remaud is with Inria and Eviden Quantum Lab, 75012 Paris, France (e-mail: maxime.remaud@inria.fr)

Jean-Pierre Tillich is with Inria, 75012 Paris, France (e-mail: jean-pierre.tillich@inria.fr)

We are given the noisy codeword $\mathbf{c} + \mathbf{e}$ where $\mathbf{c}$ belongs to $\mathcal{C}$ and we are asked to find the error $\mathbf{e}$ (or what amounts to the same, the original codeword $\mathbf{c}$). This problem for random codes has been studied for a long time and despite many efforts on this issue, the best algorithms are exponential in the codelength $n$ in the regime where $t$ and $k$ are linear in $n$.

Usually this decoding problem is considered, for the Hamming weight $|\mathbf{e}| \stackrel{\text{def}}{=} \#\{i \in [1, n], e_i \neq 0\}$, in the regime where the code rate $R \stackrel{\text{def}}{=} \frac{k}{n}$ is fixed in $(0, 1)$ and $q = 2$, but there are also other interesting parameters for cryptographic applications. For instance, the Learning Parity with Noise problem (LPN) corresponds to $DP(2, n, k, t)$ where $n$ is the number of samples, $k$ the length of the secret while the error is sampled according to a Bernoulli distribution of fixed rate $t/n$. As the number of samples in LPN is unlimited, this problem really corresponds to decoding a code of rate arbitrarily close to 0.

While the security of many code-based cryptosystems relies on the hardness of the decoding problem, it can also be based on finding a “short” codeword (as in [3] or in [6], [7], [8] to build collision resistant hash functions), a problem which is stated as follows.

**Problem 2** ($SCP(q, n, k, w)$): The short codeword problem with parameters $q, n, k, w \in \mathbb{N}$ is defined as:

* Given: $\mathbf{H} \in \mathbb{F}_q^{(n-k) \times n}$ which is sampled uniformly at random,

* Find: $\mathbf{c} \in \mathbb{F}_q^n$ such that $\mathbf{H}\mathbf{c}^\top = \mathbf{0}$ and the weight of $\mathbf{c}$ belongs to $[1, w]$.

Here we are looking for a non-zero codeword $\mathbf{c}$ of weight $\leq w$ in the $k$-dimensional code $\mathcal{C}$ defined by the so-called parity-check matrix $\mathbf{H}$, namely:

$$ \mathcal{C} \stackrel{\text{def}}{=} \{\mathbf{c} \in \mathbb{F}_q^n: \mathbf{H}\mathbf{c}^\top = \mathbf{0}\}. $$

Decoding and looking for short codewords are problems that have been conjectured to be extremely close. They have been studied for a long time [9], [10], [11], [12], [13], [14], [15], [16], and for instance in the regime of parameters where the code rate $R$ is fixed in $(0, 1)$, the best algorithms for solving them are the same (namely Information Set Decoding). A reduction from decoding to the problem of finding short codewords is known but in an LPN context [6], [7], [8], [17]. However, even in an LPN context, no reduction is known in the
other direction. These problems can be viewed in some sense as a code version of the LWE and SIS problems respectively in lattice-based cryptography [18]. Our contribution in this article is precisely to give the code-based version of this reduction, namely a quantum reduction from finding short codewords to decoding. This problem was open for quite some time. To simplify the statements, we will state it in the regime of parameters where the rate $R$ is fixed in (0, 1), but actually it also works in the LPN setting (but needs to be adapted in several places where we use exponential bounds in $n$).

There is a fundamental difficulty of reducing the research of low weight codewords to decoding a linear code which is due to the fact that the nature of these two problems is very different. Decoding concentrates on a region of parameters where there is typically just one solution, whereas finding low weight codewords concentrates on a region of parameters where there are solutions (and typically an exponential number of solutions). This makes these problems inherently very different. This was also the case for the reduction of SIS to LWE and the fact that we can have a reduction from one to another by looking for quantum reductions instead of classical reductions was really a breakthrough at that time. It should be also be noted that the fact that we are interested here in the random linear code case makes many natural approaches ineffective for reducing one problem to another. For instance, a natural way to reduce decoding to finding a low weight codeword arguing that in order to decode an error $e$ of weight $t$ in a code generated by $\mathbf{G}$ (assuming that $t$ is less than half the minimum distance of the code), we just have to find a non zero codeword of this weight in the code generated by $\begin{pmatrix} \mathbf{G} \\ \mathbf{c}+\mathbf{e} \end{pmatrix}$ does not work. Even if the only solution is a non zero multiple of $e$ with the assumption made on $t$, the code generated $\begin{pmatrix} \mathbf{G} \\ \mathbf{c}+\mathbf{e} \end{pmatrix}$ does not behave at all like a random linear code even if $\mathbf{G}$ is random. Indeed, it has a codeword (namely $e$) of too small weight for a (typical) random linear code.

**Parameter range for DP and SCP.** An important parameter for the reduction is the decoding distance parameter $t$. The largest value of $t$ for which the decoding problem is ensured to have a unique solution is equal to $\lfloor \frac{d_{\min}-1}{2} \rfloor$ where $d_{\min} \stackrel{\text{def}}{=} \min\{d(\mathbf{c}, \mathbf{c}'): \mathbf{c} \in \mathcal{C}, \mathbf{c}' \in \mathcal{C}, \mathbf{c} \neq \mathbf{c}'\}$ is the minimum distance of $\mathcal{C}$ (which depends of course on the metric $d(\cdot, \cdot)$ that is considered). Standard probabilistic arguments can be used to show that the minimum distance of a random linear code (code $\mathcal{C}$ obtained as in Equation (1) by a generator matrix $\mathbf{G}$ chosen uniformly at random in $\mathbb{F}_q^{k \times n}$) is with very high probability equal, up to an additive constant, to the Gilbert-Varshamov distance $d_{\text{GV}}(n, k)$ (or simply $d_{\text{GV}}$ if there is no ambiguity). It is defined (for all translation invariant metrics) for a code of dimension $k$ and length $n$, as the largest integer

$t$ for which

$$q^k B_t \le q^n \quad (2)$$

where $B_t$ is the size$^{(1)}$ of a ball of radius $t$. It is generally convenient to consider the normalized Gilbert-Varshamov distance defined as $\delta_{\text{GV}}(n, k) \stackrel{\text{def}}{=} \frac{d_{\text{GV}}(n, k)}{n}$. For the Hamming metric, we have

$$\delta_{\text{GV}}(n, k) = h_q^{-1}\left(1 - \frac{k}{n}\right) + O\left(\frac{1}{n}\right) \quad \text{where}$$

$$h_q(x) \stackrel{\text{def}}{=} -x \log_q \left( \frac{x}{q-1} \right) - (1-x) \log_q(1-x)$$

and $h_q^{-1}$ is its inverse, ranging over $[0, \frac{q-1}{q}]$.

This Gilbert-Varshamov distance also happens to quantify the region where we typically have unique decoding. More precisely, it turns out that for many metrics of interest, including the Hamming metric, the same probabilistic arguments also show that the solution to the decoding problem is unique with probability $1 - 2^{-\Omega(n)}$ and when $n$ goes to infinity for fixed positive $\varepsilon$, $t \le (1 - \varepsilon)d_{\text{GV}}(n, k)$.

The best algorithms for solving the decoding problem have exponential complexity in $n$ as soon as $t$ is linear in $n$ and the code rate $R$ is bounded away from 0 and 1. This is in contrast to the short codeword problem which becomes easy when the weight $w$ is above a certain range. The reason is that it is easy to produce codewords of small weight by using the fact that the code is a vector space of dimension $k$. Thus we can just produce codewords with $k-1$ entries equal to 0 by solving a linear system which gives good candidates for having a small weight. It is straightforward that this strategy produces in polynomial time, for instance with the Hamming metric, codewords of weight $\approx \omega_{\text{easy}}(n, k)n$ where

$$\omega_{\text{easy}}(n, k) \stackrel{\text{def}}{=} \frac{q-1}{q} \left(1 - \frac{k}{n}\right) \quad (3)$$

Obtaining larger weights is also readily obtained by choosing only part of the $k-1$ entries to be equal to 0. It should be noted that below $\omega_{\text{easy}}(n, k)$ the best known algorithms for solving this problem have all exponential complexity for a fixed rate $R$ and a fixed ratio $\omega = \frac{w}{n}$.

**Regev's quantum reduction strategy adapted to coding theory.** In [19] (see also the extended version [18]) Regev showed how to transform a random oracle solving the decoding problem in a lattice into a quantum algorithm outputting a rather small vector in the dual lattice. Our aim is to show here that the natural translation of this approach in coding theory gives an algorithm that outputs a rather small vector in the dual code. Roughly speaking Regev's approach relies on a fundamental result about the Fourier transform.

<footnote>$^{(1)}$ Note that because of the translation invariance, this size does not depend on the center.</footnote>
**Proposition 1.1:** Consider an Abelian group $G$ and a function $f: G \to \mathbb{C}$ that is constant on the cosets of a subgroup $H$ of $G$. Then the Fourier transform $\hat{f}$ is constant on the dual subgroup $H^{\perp}$.

This innocent looking fact, together with the fact that the quantum Fourier transform (QFT for short) can be performed in polylog time when the group $G$ is Abelian, is arguably the key to several remarkable quantum algorithms solving in polynomial time the period finding in a vectorial Boolean function [20], the factoring problem [21] or the discrete logarithm problem [21]. All of these problems can be rephrased in terms of the hidden Abelian subgroup problem, where one is given such a function $f$ that is constant (and distinct) on the cosets of an unknown subgroup $H$ and one is asked to recover $H$. This is achieved by

(i) creating the uniform superposition $\frac{1}{\sqrt{|G|}} \sum_{x \in G} |x\rangle |f(x)\rangle$,

(ii) measuring the second register and discarding it, yielding a quantum state of the form $\frac{1}{\sqrt{|H|}} \sum_{h \in H} |x+h\rangle$,

(iii) applying the QFT to it yielding a superposition of elements in the dual subgroup $H^{\perp}$ (and therefore gaining information on $H$ in this way).

**Proposition 1.1** is used in a similar way in Regev's reduction. Translating Regev's reduction in coding theory would use this framework by considering that the linear code $\mathcal{C}$ we want to decode plays the role of the aforementioned $H$. From now on we will assume that this code is of dimension $k$ and length $n$ over $\mathbb{F}_q$. The algorithm would basically look as follows for reducing the search of small codewords in the dual code $\mathcal{C}^{\perp} = \{\mathbf{c}^{\perp} \in \mathbb{F}_q^n : \mathbf{c} \cdot \mathbf{c}^{\perp} = 0, \forall \mathbf{c} \in \mathcal{C}\}$ (where $\mathbf{x} \cdot \mathbf{y} = \sum_{i=1}^n x_i y_i$ is the standard inner product in $\mathbb{F}_q^n$) to decoding errors of weight $t$ in $\mathcal{C}$.

**Step 1.** Use a quantized version of the decoding algorithm to prepare the state

$$ \frac{1}{\sqrt{Z}} \sum_{\mathbf{c} \in \mathcal{C}, \mathbf{e} \in \mathbb{F}_q^n} \pi_{\mathbf{e}} |\mathbf{c} + \mathbf{e}\rangle $$

where $Z$ is a normalizing constant and $(|\pi_{\mathbf{e}}|^2)_{\mathbf{e}}$ is a probability distribution on errors that concentrate around the weight $t$ we are able to decode. This is done

(i) by preparing first a superposition of codewords and errors,

$$ \frac{1}{\sqrt{Z}} \sum_{\mathbf{c} \in \mathcal{C}} \sum_{\mathbf{e} \in \mathbb{F}_q^n} \pi_{\mathbf{e}} |\mathbf{c}\rangle |\mathbf{e}\rangle, $$

(ii) then adding the second register to the first one to get the entangled state

$$ \frac{1}{\sqrt{Z}} \sum_{\mathbf{c} \in \mathcal{C}} \sum_{\mathbf{e} \in \mathbb{F}_q^n} \pi_{\mathbf{e}} |\mathbf{c} + \mathbf{e}\rangle |\mathbf{e}\rangle $$

(iii) and finally disentangling it thanks to a quantized version of the decoding algorithm, which from $\mathbf{c} + \mathbf{e}$

recover $\mathbf{e}$ and subtracts it from the second register to get the state

$$ \frac{1}{\sqrt{Z}} \sum_{\mathbf{c} \in \mathcal{C}} \sum_{\mathbf{e} \in \mathbb{F}_q^n} \pi_{\mathbf{e}} |\mathbf{c} + \mathbf{e}\rangle |\mathbf{0}\rangle. $$

**St. 2.** Apply the QFT on $\mathbb{F}_q^n$ to obtain a superposition of elements $\mathbf{c}^{\perp}$ in the dual code

$$ \sum_{\mathbf{c}^{\perp} \in \mathcal{C}^{\perp}} \alpha_{\mathbf{c}^{\perp}} |\mathbf{c}^{\perp}\rangle. $$

**St. 3.** Measure the register to output $\mathbf{c}^{\perp}$ of rather small norm in $\mathcal{C}^{\perp}$.

The second step is a direct consequence of Proposition 1.1. The last one raises the issue of whether or not the QFT concentrates the weight of the vector output by this algorithm on weights $t'$ for which finding a codeword in $\mathcal{C}^{\perp}$ is not known to be easy, as it is the case for Regev's reduction on lattices equipped with the Euclidean metric.

**On the difficulty of translating Regev's reduction to the Hamming metric.** This thread of research has been pioneered by Yilei Chen [22] and later on in [23], where basically the following approach was taken. The natural analog in the Hamming metric case of the Gaussian noise model used in Regev's reduction [18] is the $q$-ary symmetric channel. Its associated quantum state is given by

$$ \begin{aligned} |\pi^{\text{SC}}\rangle &\stackrel{\text{def}}{=} \sum_{\mathbf{e} \in \mathbb{F}_q^n} (1-\tau)^{\frac{n-|\mathbf{e}|}{2}} \left(\frac{\tau}{q-1}\right)^{\frac{|\mathbf{e}|}{2}} |\mathbf{e}\rangle \\ &= \left(\sqrt{1-\tau}|0\rangle + \sum_{\alpha \in \mathbb{F}_q^*} \sqrt{\frac{\tau}{q-1}} |\alpha\rangle\right)^{\otimes n} \end{aligned} $$

where $|\mathbf{e}|$ stands for the Hamming weight of $\mathbf{e}$, $n$ for the length of $\mathbf{e}$ and $\tau$ is the crossover probability of the $q$-ary symmetric channel. Indeed, measuring such a state yields an error distributed like a $q$-ary symmetric channel of crossover probability $\tau$. In both cases (be it for the Gaussian noise or the $q$-ary symmetric channel), the Fourier transform yields a dual noise which is again Gaussian or $q$-ary symmetric respectively and the quantum state corresponding to the error is a product state which considerably simplifies the computation. In the case of the $q$-ary symmetric noisy channel, applying the QFT on $|\pi^{\text{SC}}\rangle$ yields the quantum state

$$ \begin{aligned} & \sum_{\mathbf{e} \in \mathbb{F}_q^n} (1 - \tau^{\perp})^{\frac{n-|\mathbf{e}|}{2}} \left( \frac{\tau^{\perp}}{q-1} \right)^{\frac{|\mathbf{e}|}{2}} |\mathbf{e}\rangle \\ &= \left( \sqrt{1 - \tau^{\perp}} |0\rangle + \sum_{\alpha \in \mathbb{F}_q^*} \sqrt{\frac{\tau^{\perp}}{q-1}} |\alpha\rangle \right)^{\otimes n} \\ &\stackrel{\text{def}}{=} |\pi^{\text{SC}}\rangle \end{aligned} $$

where (see Fact 2.1)

$$ \tau^{\perp} \stackrel{\text{def}}{=} \frac{(\sqrt{(q-1)(1-\tau)} - \sqrt{\tau})^2}{q}. $$
This new quantum state represents a q-ary symmetric channel of parameter $\tau^{\perp}$. If we measure $|\pi^{\text{SC}}\rangle$ we get relative weights $\approx \tau$ whereas if we measure $|\pi^{\text{SC}}\rangle$ we get relative weights around $\tau^{\perp}$.

It would thus be tempting to conclude that the “ideal” version of the algorithm presented above will output dual codewords (in Step 3) of relative Hamming weight $\approx \tau^{\perp} < \omega_{\text{easy}}$, i.e., in the regime where there is a chance that it is difficult to produce such words. However, this natural approach runs into the following problem. The parameter $\tau$ of the Bernoulli noise has to be chosen so that the typical error weight $\tau n$ is equal to or slightly below the weight $t$ we can decode. Such a $\tau$ is therefore at most the relative Gibert-Varshamov $\delta_{\text{GV}}$. However [23] proved that in this case the most likely relative weight we measure at Step 3 is typically zero if $\tau^{\perp} < \omega_{\text{easy}}$. In other words, the straightforward application of Regev’s approach to coding theory fails to give a useful reduction.

We will give in Remark 3.2 another explanation for the failure of this approach. It can be summarized by saying that the Bernoulli noise model is not concentrated enough on its typical weight $\tau n$.

**Our approach.** To tackle this issue, it would therefore be natural to choose the most concentrated noise model on the weight $t$, namely:

$$|\pi^{\text{unif}}\rangle = \sum_{e: |e|=t} \frac{1}{\sqrt{S_t}} |e\rangle$$

where $S_t$ is the cardinality of the sphere of radius $t$ in the Hamming metric, i.e., $S_t = (q-1)^t \binom{n}{t}$. Understanding of which weight $w$ is the outcome after measuring the state $\sum_{e^{\perp} \in e^{\perp}} \alpha_{e^{\perp}} |e^{\perp}\rangle$ in Step 3 is more difficult in the constant weight error model than in the Bernoulli noise model. In particular, it involves properties of Krawtchouk polynomials. However, it can be shown that when $\omega \stackrel{\text{def}}{=} \frac{w}{n}$ lies in a whole interval $[\tau^{\perp}, \tau_{+}^{\perp}]$ where $\tau_{+}^{\perp} \stackrel{\text{def}}{=} \frac{(\sqrt{(q-1)(1-\tau)+\sqrt{\tau}})^2}{q}$, we have many points where the probability of measuring a word of weight $w$ is actually $\frac{1}{\text{poly}(n)}$. The “dual” weight distribution is not really concentrated on a single value but spread over a large interval. This would provide a useful reduction when we use a decoding algorithm that succeeds on a non-negligible set of inputs.

Unfortunately, to be relevant in a cryptographic context, we must consider the case where decoding succeeds only for a potentially very low probability $\epsilon$, the aim being to turn our decoding algorithm into an algorithm that produces a low weight codeword from the dual with some probability poly($\epsilon$). This cannot be obtained with the uniform distribution on the sphere of radius $t$. Indeed, the “ideal” version of the algorithm we presented before (where we assume we always succeed with our decoding algorithm) describes a state we obtain in Step 2 that is not completely orthogonal (the scalar product is

bounded from below by a quantity poly($\epsilon$)) to the “real” state after applying this approximate decoding process and the QFT. If we were to measure this state directly (starting from the uniform noise model over the sphere of radius $t$), we would only be sure to measure a word of some relative weight lying in the interval $[\tau^{\perp}, \tau_{+}^{\perp}]$ with probability poly($\epsilon$), since the “ideal” state concentrates its relative weight distribution in all this interval. In this way, we cannot ensure the measurement of a dual codeword of smallest possible relative weight, namely $\tau^{\perp}$, it could be $1/2 \in [\tau^{\perp}, \tau_{+}^{\perp}]$. We really need here a distribution that is rather sharply concentrated around the decoding radius of our decoding algorithm, but whose Fourier transform is also sharply concentrated around a certain weight.

So far, two noise models have been considered for the reduction to work, each with an advantage and a drawback:

* the q-ary symmetric noise $|\pi^{\text{SC}}\rangle$ is not concentrated enough on its typical weight $\tau n$ but its dual noise is sufficiently concentrated on $\tau^{\perp}n$,

* the uniform noise $|\pi^{\text{unif}}\rangle$ on the sphere of radius $\tau n$ is sufficiently concentrated but its dual noise is spread out on the whole interval $(\tau^{\perp}n, \tau_{+}^{\perp}n)$.

Interestingly, the issues with these two distributions are opposite. Fortunately, it turns out that we have a natural noise model to get a best-of-both-worlds model: truncating the q-ary symmetric noisy channel. More precisely, consider the following noise model (for some small enough constant $\epsilon > 0$),

$$|\pi^{\text{Trunc}}\rangle = \frac{1}{\sqrt{N}} \sum_{\substack{e: \\ |e| \in [(1-\epsilon)t, (1+\epsilon)t]}} (1-\tau)^{\frac{n-|e|}{2}} \left(\frac{\tau}{q-1}\right)^{\frac{|e|}{2}} |e\rangle$$

where $N$ is a normalizing factor. This noise model solves our above issues with $|\pi^{\text{SC}}\rangle$ and $|\pi^{\text{unif}}\rangle$ because it verifies our two constraints for the reduction to work:

(i) its weight distribution is sufficiently concentrated around $\tau n$,

(ii) its dual noise after applying the Fourier transform is concentrated on the relative weight $\tau^{\perp}n$.

Contrary to (i), assertion (ii) may seem unclear. It relies on the following equality as we will show in Lemma 3.18

$$\| |\pi^{\text{Trunc}}\rangle - |\pi^{\text{SC}}\rangle \| = 2^{-\Omega(n)}$$

where $\|\cdot\|$ stands for the norm of the Hilbert space in which the quantum states are embedded. Therefore, applying the Fourier transform (which is an isometry for $\|\cdot\|$) on $|\pi^{\text{Trunc}}\rangle$ will yield a quantum state which is $2^{-\Omega(n)}$-close of $|\pi^{\text{SC}}\rangle$.

With our approach and the truncated q-ary symmetric channel, we transform through the QFT a decoding algorithm correcting $\tau n$ errors into an algorithm outputting with non-negligible probability words of weight $\approx \tau^{\perp}n$ in the dual code. The distance $\tau^{\perp}$ is clearly a decreasing function of $\tau$ and the issue is now whether or not there exists a $\tau < \delta_{\text{GV}}(n, k)$
(this is the biggest value for which we can hope that decoding is successful with probability $1-o(1)$) such that $\tau^{\perp} < \omega_{\text{easy}}(n, n-k)$ (here we want to find short codewords in the dual code $\mathbb{C}^{\perp}$ which is of dimension $n-k$), since this would yield a useful reduction. It turns out that in many cases we have to choose $\tau > \delta_{\text{GV}}(n, k)/2$, meaning that we are not in the regime where decoding necessarily has at most one solution. This complicates the proof of the reduction somewhat since with a quantized version of the decoding algorithm, we will not be able to produce at Step 1 the state $\frac{1}{\sqrt{Z}} \sum_{c \in \mathbb{C}} \sum_{e \in \mathbb{F}_q^n} \pi_e |c+e\rangle$ (since decoding fails for some $e$) but we will show that as long as $\tau < \delta_{\text{GV}}(n, k)$, we will get a state close to it. This will be enough for our purpose.

By putting all these ingredients together, we are able to prove the following result.

**Theorem 1 (informal):** The short codeword problem $\text{SCP}(q, n, n-k, w)$ reduces to the decoding problem $\text{DP}(q, n, k, t)$ for $w = \tau^{\perp}n + O(1)$ where

$$ \tau \stackrel{\text{def}}{=} \frac{t}{n} \quad \text{and} \quad \tau^{\perp} \stackrel{\text{def}}{=} \frac{\left(\sqrt{(q-1)(1-\tau)} - \sqrt{\tau}\right)^2}{q}. $$

It will turn out that for $q=2$ (see Section 4) we can find for any rate $R = \frac{k}{n}$ in $(0,1)$ a $t < d_{\text{GV}}(n, k)$ for which the corresponding $w$ is below $\omega_{\text{easy}}(n, n-k)n$ (the reduction is useful in this case). It also corresponds to parameter ranges that are relevant for certain cryptographic applications (see [24] whose security relies on the SCP problem in a parameter range which is covered by our reduction and [4] which is an identification scheme whose security actually relies on the decoding problem just below the Gilbert-Varshamov distance). Unfortunately, this is not true anymore when $q \ge 5$, where there is always a range for $R$ for which $w$ is above $\omega_{\text{easy}}(n, n-k)n$, for any choice of $t < d_{\text{GV}}(n, k)$: the reduction becomes useless in this case. Roughly speaking, when $q$ grows, the Hamming metric gets coarser (we have only $n+1$ different values for the metric on $\mathbb{F}_q^n$, whereas the size of the ambient space gets bigger) and this results in the range of values of $R$ for which this reduction is useful becoming smaller.

**Considering other metrics.** The whole approach we have followed here (properly choosing the error distribution and going beyond the unique decoding radius for decoding if necessary) can of course be adapted to other metrics. It is easy for instance to apply it to the rank metric which is becoming increasingly popular in code-based cryptography, see for instance [25], [26], [27], [28]. This metric is even coarser than the Hamming metric: on $\mathbb{F}_q^{m \times n}$ there are only $1+\min(m,n)$ different values for the rank weight (given a matrix, it is defined as its rank). In this case, as we will see, the reduction is always useless (i.e., reduces to weights which are always easy to produce for a random linear code).

## 2. NOTATION AND SOME USEFUL FACTS

**General Notation.** For $a$ and $b$ integers with $a \le b$, we denote by $\llbracket a, b \rrbracket$ the set of integers $\{a, a+1, \dots, b\}$. We extend this notation when $a$ and $b$ are not integers to the set of integers in $[a, b]$. Vectors are in row notation and they will be written with bold letters (such as $\mathbf{e}$). Uppercase bold letters are used to denote matrices (such as $\mathbf{H}$). Notation $S_t$ is the sphere of radius $t$ around 0 in $\mathbb{F}_q^n$ (for a metric $|\cdot|$ that will be clear from the context) and $S_t$ is its cardinality. In all this paper, $\text{poly}(n)$ denotes a quantity which is an $O(n^a)$ for some constant $a$. A function $f: \mathbb{F}_q^n \to \mathbb{C}$ is said to be radial if $f(\mathbf{x})$ is only function of $|\mathbf{x}|$.

**Subspaces and Gaussian binomial coefficient.** $F \le \mathbb{F}_q^n$ denotes that $F$ is a subspace of $\mathbb{F}_q^n$. When $\mathbb{E}$ is a matrix, we denote its rank by $|\mathbb{E}|$.

The following asymptotic expressions will be extremely useful. For the rank metric, $S_\ell$ is equal to the number of matrices in $\mathbb{F}_q^{m \times n}$ of rank $\ell$. From this interpretation we obtain

$$ S_{\ell} = \prod_{j=0}^{\ell-1} (q^m - q^j) \begin{bmatrix} n \\ \ell \end{bmatrix}_{\ell} $$

$$ \text{with} \quad \begin{bmatrix} n \\ t \end{bmatrix}_{q} = \begin{cases} \prod_{i=0}^{t-1} \frac{q^n - q^i}{q^t - q^i} & \text{if } t \le n, \\ 0 & \text{otherwise.} \end{cases} $$

It follows by using the fact that $\prod_{i=1}^{\infty} (1-q^{-i})$ is some constant depending on $q$, that as $n \to +\infty$

$$ \begin{bmatrix} n \\ \ell \end{bmatrix}_{q} = \Theta \left( q^{\ell(n-\ell)} \right), \quad (4) $$

$$ S_{\ell} = \Theta \left( q^{\ell(m+n-\ell)} \right). \quad (5) $$

From (5) we deduce that

$$ \frac{S_{u+1}}{S_u} = \Theta \left( \frac{q^{(u+1)(m+n-u-1)}}{q^{u(m+n-u)}} \right) = \Theta (q^{m+n-2u-1}). \quad (6) $$

**Quantum Fourier Transform (QFT).** The Quantum Fourier Transform $\widehat{\psi}\rangle$ of a state $|\psi\rangle \stackrel{\text{def}}{=} \sum_{\mathbf{x} \in \mathbb{F}_q^n} \alpha_{\mathbf{x}} |\mathbf{x}\rangle$ is defined by using the characters $\chi_y$ of the additive group $\mathbb{F}_q^n$ (there are as many characters as there are elements in $\mathbb{F}_q^n$ and we assume that the characteristic of $\mathbb{F}_q$ is the prime $p$ with $q = p^s$) as

$$ \widehat{\psi} \stackrel{\text{def}}{=} \frac{1}{\sqrt{q^n}} \sum_{\mathbf{y} \in \mathbb{F}_q^n} \widehat{\alpha}_{\mathbf{y}} |\mathbf{y}\rangle \quad \text{with} \quad \widehat{\alpha}_{\mathbf{y}} \stackrel{\text{def}}{=} \sum_{\mathbf{x} \in \mathbb{F}_q^n} \alpha_{\mathbf{x}} \chi_{\mathbf{y}}(\mathbf{x}) $$

where

$$ \chi_y(\mathbf{x}) \stackrel{\text{def}}{=} e^{\frac{2i\pi \text{Tr}(\mathbf{x} \cdot \mathbf{y})}{p}}, \quad \text{with} $$

$$ \mathbf{x} \cdot \mathbf{y} \stackrel{\text{def}}{=} \sum_{i=1}^{n} x_i y_i \quad \text{with} \quad \mathbf{x} = (x_i)_{i=1}^n \quad \text{and} \quad \mathbf{y} = (y_i)_{i=1}^n, $$

$$ \text{Tr}(a) \stackrel{\text{def}}{=} a + a^p + a^{p^2} + \dots + a^{p^{s-1}}. $$
A useful computation is the QFT of a state representing the
q-ary symmetric channel of crossover probability $\tau$:

Fact 2.1: Let $|\pi^{\text{SC}}\rangle \stackrel{\text{def}}{=} (\sqrt{1-\tau}|0\rangle + \sum_{\alpha \in \mathbb{F}_q^*} \sqrt{\frac{\tau}{q-1}}|\alpha\rangle)^{\otimes n}$,
where $\tau \in [0, \frac{q-1}{q}]$, then

$$
|\pi^{\text{SC}}\rangle = \left( \sqrt{1 - \tau^{\perp}} |0\rangle + \sum_{\alpha \in \mathbb{F}_q^*} \sqrt{\frac{\tau^{\perp}}{q-1}} |\alpha\rangle \right)^{\otimes n} (7)
$$

$$
\text{where } \tau^{\perp} \stackrel{\text{def}}{=} \frac{\left( \sqrt{(q-1)(1-\tau)} - \sqrt{\tau} \right)^2}{q}.
$$

Proof: Let $|\psi\rangle \stackrel{\text{def}}{=} \sqrt{1-\tau}|0\rangle + \sum_{\alpha \in \mathbb{F}_q^*} \sqrt{\frac{\tau}{q-1}} |\alpha\rangle$. Then, it is readily verified that

$$
|\widehat{\pi^{\text{SC}}}\rangle = (|\widehat{\psi}\rangle)^{\otimes n}
$$

$$
\text{where } |\widehat{\psi}\rangle = \frac{1}{\sqrt{q}} \left( \beta_0 + \sum_{y \in \mathbb{F}_q^*} \beta_y |y\rangle \right)
$$

$$
\text{with } \beta_0 = \sqrt{1 - \tau} + (q - 1) \sqrt{\frac{\tau}{q - 1}}
$$

$$
\text{and } \beta_y = \sqrt{1 - \tau} + \sqrt{\frac{\tau}{q-1}} \sum_{x \in \mathbb{F}_q^*} \chi_y(x).
$$

It is easy to verify that for any $y \in \mathbb{F}_q^*$ we have for any
$x_0 \in \mathbb{F}_q^*$:

$$
\sum_{x \in \mathbb{F}_q} \chi_y(x) = \sum_{x \in \mathbb{F}_q} \chi_y(x_0 \cdot x) = \chi_y(x_0) \sum_{x \in \mathbb{F}_q} \chi_y(x)
$$

Since there exists $x_0 \in \mathbb{F}_q^*$ such that $\chi_y(x_0) \neq 1$, we deduce that $\sum_{x \in \mathbb{F}_q} \chi_y(x) = 0$. Now since $\sum_{x \in \mathbb{F}_q} \chi_y(x) = 1 + \sum_{x \in \mathbb{F}_q^*} \chi_y(x)$, we have $\sum_{x \in \mathbb{F}_q^*} \chi_y(x) = -1$ for any $y$ in $\mathbb{F}_q^*$ and therefore

$$
\begin{align*}
\frac{\beta_y}{\sqrt{q}} &= \sqrt{\frac{1-\tau}{q}} - \sqrt{\frac{\tau}{q(q-1)}} \\
&= \sqrt{\frac{(q-1)(1-\tau)}{q(q-1)}} - \sqrt{\frac{\tau}{q(q-1)}} \\
&= \frac{\sqrt{\frac{(q-1)(1-\tau)}{q}} - \sqrt{\frac{\tau}{q}}}{\sqrt{q-1}} \\
&= \frac{\sqrt{\tau^{\perp}}}{\sqrt{q-1}}.
\end{align*}
$$

It is then clear that $\frac{\beta_0}{\sqrt{q}} = \sqrt{1 - \tau^{\perp}}$ from $\sum_{y \in \mathbb{F}_q} |\beta_y|^2 = 1$, concluding the proof. ■

The dual code $\mathcal{C}^{\perp}$ of a linear code $\mathcal{C}$ over $\mathbb{F}_q$ is easily seen to be defined equivalently from the characters or from the inner product $\mathbf{x} \cdot \mathbf{y}$ as follows:

$$
\begin{align*}
\mathcal{C}^{\perp} &\stackrel{\text{def}}{=} \{ \mathbf{y} \in \mathbb{F}_q^n : \forall \mathbf{c} \in \mathcal{C}, \chi_{\mathbf{y}}(\mathbf{c}) = 1 \} \\
&= \{ \mathbf{y} \in \mathbb{F}_q^n : \forall \mathbf{c} \in \mathcal{C}, \mathbf{y} \cdot \mathbf{c} = 0 \}.
\end{align*}
$$

3. QUANTUM REDUCTION FROM SAMPLING SHORT
CODEWORDS TO DECODING

A. A general result

We assume here that we have a probabilistic algorithm $\mathcal{A}$ that solves (sometimes) the decoding problem at distance $t$. Its inputs are a generator matrix $\mathbf{G} \in \mathbb{F}_q^{k \times n}$ of a code $\mathcal{C} \subseteq \mathbb{F}_q^n$ (i.e., $\mathcal{C} = \{\mathbf{uG}: \mathbf{u} \in \mathbb{F}_q^k\}$) and a noisy codeword $\mathbf{c}+\mathbf{e}$ where $\mathbf{c}$ belongs to $\mathcal{C}$. We denote by $\mathbf{r} \in \mathbb{F}_2^\ell$ the internal coins of $\mathcal{A}$. It outputs with a certain probability $\varepsilon$, the “right” $\mathbf{e}$ when being fed with $\mathbf{c}+\mathbf{e}$ where $\mathbf{c}$ and $\mathbf{e}$ are uniformly chosen at random in $\mathcal{C}$ and among the errors of weight $t$ respectively:

$$
\epsilon \stackrel{\text{def}}{=} \mathbb{P}_{\mathbf{G}, \mathbf{c}, \mathbf{e}, \mathbf{r}} (\mathcal{A}(\mathbf{G}, \mathbf{c} + \mathbf{e}, \mathbf{r}) = \mathbf{e}). \quad (8)
$$

The quantum reduction starts by building the initial superpo-
sition

$$
\frac{1}{\sqrt{2^l q^k}} \sum_{\mathbf{e} \in \mathbb{F}_q^n} \sum_{\mathbf{c} \in \mathcal{C}} \sum_{\mathbf{r} \in \mathbb{F}_2^l} \pi_{\mathbf{e}} |\mathbf{e}\rangle |\mathbf{c}\rangle |\mathbf{r}\rangle
$$

where $|\pi\rangle \stackrel{\text{def}}{=} \sum_{\mathbf{e} \in \mathbb{F}_q^n} \pi_{\mathbf{e}} |\mathbf{e}\rangle$ is some quantum superposition of errors. In practice, we will voluntarily omit to write the internal coins of $\mathcal{A}$ for the sake of readability and will therefore start from

$$
\frac{1}{\sqrt{q^k}} \sum_{\mathbf{e} \in \mathbb{F}_q^n} \sum_{\mathbf{c} \in \mathcal{C}} \pi_{\mathbf{e}} |\mathbf{e}\rangle |\mathbf{c}\rangle
$$

For the same reason, we will write

$$
\epsilon = \mathbb{P}_{\mathbf{G}, \mathbf{c}, \mathbf{e}} (\mathcal{A}(\mathbf{G}, \mathbf{c} + \mathbf{e}) = \mathbf{e}).
$$

The quantum algorithm that gives the reduction can then be
described as follows.

**Algorithm of the quantum reduction.**

Initial state: $\frac{1}{\sqrt{q^k}} \sum_{\mathbf{e} \in \mathbb{F}_q^n} \sum_{\mathbf{c} \in \mathcal{C}} \pi_{\mathbf{e}} |\mathbf{e}\rangle |\mathbf{c}\rangle$

add $\mathbf{e}$ to $\mathbf{c} \mapsto \frac{1}{\sqrt{q^k}} \sum_{\mathbf{e} \in \mathbb{F}_q^n} \sum_{\mathbf{c} \in \mathcal{C}} \pi_{\mathbf{e}} |\mathbf{e}\rangle |\mathbf{c} + \mathbf{e}\rangle$

apply $\mathcal{A} \mapsto \frac{1}{\sqrt{q^k}} \sum_{\mathbf{e} \in \mathbb{F}_q^n} \sum_{\mathbf{c} \in \mathcal{C}} \pi_{\mathbf{e}} |\mathbf{e} - \mathcal{A}(\mathbf{G}, \mathbf{c} + \mathbf{e})\rangle |\mathbf{c} + \mathbf{e}\rangle$

QFT on the 2nd register $\mapsto |\widehat{\psi_{\mathcal{A}}}\rangle$ (9)

measure the whole state $\mapsto |\mathbf{e}\rangle|\mathbf{c}^{\perp}\rangle$

In what follows, we let

$$
|\psi_{\mathcal{A}}\rangle \stackrel{\text{def}}{=} \frac{1}{\sqrt{q^k}} \sum_{\mathbf{e} \in \mathbb{F}_q^n} \sum_{\mathbf{c} \in \mathcal{C}} \pi_{\mathbf{e}} |\mathbf{e} - \mathcal{A}(\mathbf{G}, \mathbf{c} + \mathbf{e})\rangle |\mathbf{c} + \mathbf{e}\rangle . \quad (10)
$$

We will now give a general theorem about an algorithm of this
kind and will show that it produces a codeword of the dual
code $\mathcal{C}^{\perp}$ of some weight $u$ with probability $\text{poly}(\varepsilon)$ when
certain conditions are met.
**Theorem 3.1:** Assume that $|\pi\rangle$ is radial and non-negative, i.e., $\pi_e = f(|e|)$ for some non-negative function $f$. Assume that $\widehat{|\pi\rangle} = \sum_{e \in \mathbb{F}_q^n} \widehat{\pi_e} |e\rangle$ is radial too$^{(2)}$ and let $\widehat{f}(w) = \widehat{\pi_e}$ for any element $e$ of $\mathbb{F}_q^n$ of weight $w$. Furthermore, assume that there exists an interval $\mathcal{W} \subseteq [0, n]$ such that:

* Concentration of $\pi$:

$$ \frac{\langle \pi | \mathbf{1} \rangle^2}{q^{n-k}} = 2^{-\Omega(n)}, \quad (C1) $$

* Exponentially many dual codewords of weight $u \in \mathcal{W}$:

$$ \sum_{u \in \mathcal{W}} \frac{q^k}{S_u} = 2^{-\Omega(n)}, \quad (C2) $$

* Concentration of the dual distribution $\widehat{\pi}$ on $\mathcal{W}$

$$ \sum_{u \in \mathcal{W}} S_u |\hat{f}(u)|^2 = 1 - 2^{-\Omega(n)}, \quad (C3) $$

with $|\mathbf{1}\rangle$ being the (unnormalized) superposition of errors : $|\mathbf{1}\rangle \stackrel{\text{def}}{=} \sum_{e \in \mathbb{F}_q^n} |e\rangle$.

Suppose that there exists an algorithm $\mathcal{A}$ solving the decoding problem $\text{DP}(q, n, k, t)$ with success probability $\varepsilon$. Then, there exists a quantum algorithm which takes as input a generator matrix $\mathbf{G} \in \mathbb{F}_q^{k \times n}$ of $\mathcal{C}$ and outputs a codeword of weight $u \in \mathcal{W}$ in $\mathcal{C}^{\perp}$ with probability greater than $\frac{p_t^2 \varepsilon^3}{16} - O(p_t^4 \varepsilon^5) - 2^{-\Omega(n)} - O(q^{-\min(k, n-k)})$ where $p_t \stackrel{\text{def}}{=} \sum_{e: |e|=t} |\pi_e|^2 = S_t f(t)^2$.

**Remark 3.2:**

* We will use this theorem for Hamming and rank metrics, but it can be applied to any metric for which the Fourier transform is radially preserving.

* When $\pi_e$ is non-negative, Condition (C1) basically requires the probability distribution on $\mathbb{F}_q^n$, $\mu \stackrel{\text{def}}{=} (\pi_e^2)_{e \in \mathbb{F}_q^n}$, to be sufficiently concentrated. This quantity can be expressed as $q^k(1 - H^2(\mu, U))^2$, where $U$ stands for the uniform distribution over $\mathbb{F}_q^n$ and $H(\mathbf{p}, \mathbf{q}) \stackrel{\text{def}}{=} \sqrt{1 - \sum_i \sqrt{p_i q_i}}$ is the Hellinger distribution between two probability distributions $\mathbf{p}$ and $\mathbf{q}$ defined over a same probability space.

1) The above Hellinger distance is clearly maximal for $\mu$ being the uniform probability distribution over $\mathbb{F}_q^n$, and

2) on the other hand, when considering the Hamming metric and $|\pi\rangle = |\pi^{\text{SC}}\rangle$, we have

$$ \frac{\langle \pi^{\text{SC}} | \mathbf{1} \rangle^2}{q^{n-k}} = \frac{q^k}{q^n} \left| \sum_{\mathbf{y} \in \mathbb{F}_q^n} \chi_{\mathbf{y}}(0) \pi_{\mathbf{y}} \right|^2 = q^k |\hat{f}(0)|^2 \\ = q^k (1 - \tau^{\perp})^n. $$

It can be verified that there is no way to choose $\tau$ such that at the same time:

(i) $\tau n \le d_{\text{GV}}(n, k)$ (otherwise there is no hope to decode correctly most of the time),

(ii) $\tau^{\perp} \le \omega_{\text{easy}}$ (otherwise finding codewords in $\mathcal{C}^{\perp}$ of weight $\tau^{\perp}n$ is easy),

(iii) $q^k(1 - \tau^{\perp})^n = o(1)$.

The quantity $\frac{\langle \pi^{\text{SC}} | \mathbf{1} \rangle^2}{q^{n-k}}$ is just too big, or in other words, the distribution of $\mu$ is too much spread out and not concentrated enough on its typical weight.

* Condition (C2) expresses that $u$ lies in a subset of values for which a random $[n, n-k]$-code has an exponential expected number of codewords. Indeed, the expected number of codewords of weight $u$ is equal to $\frac{S_u}{q^k}$.

* Finally, Condition (C3) expresses that the dual probability distribution $\hat{\mu} \stackrel{\text{def}}{=} (|\hat{\pi}_e|^2)_{e \in \mathbb{F}_q^n}$ is almost completely supported on $\mathcal{W}$ up to an exponentially small vanishing term.

## B. Outline of the proof of Theorem 3.1

Let us first give a general outline of the proof before detailing each step.

**Step 1.** We prove that after applying $\mathcal{A}$ in the reduction, $|\psi_{\mathcal{A}}\rangle$ is close enough to the “disentangled” state

$$ |\psi_{\text{ideal}}\rangle \stackrel{\text{def}}{=} \frac{1}{\sqrt{Z}} \sum_{e \in \mathbb{F}_q^n} \sum_{c \in \mathcal{C}} \pi_e |0_n\rangle |c+e\rangle \quad (11) $$

where $Z$ is a normalizing constant.

**Step 2.** We then analyze the effect of the QFT on the “ideal state” $|\psi_{\text{ideal}}\rangle$ and a subsequent measurement of it. We namely prove that measuring it produces a codeword $c^{\perp} \in \mathcal{C}^{\perp}$ of weight $u$ with probability $|\hat{f}(u)|^2$, up to a normalizing factor.

**Step 3.** Then we prove that the number of codewords of weight $u$ in $\mathcal{C}^{\perp}$ is typically very close to $\frac{S_u}{q^k}$. With Step 2 and the assumptions of Theorem 3.1, we infer that the probability of observing a dual codeword of weight in the set $\mathcal{W}$ after measuring $|\psi_{\text{ideal}}\rangle$ is exponentially close to 1.

**Step 4.** We upper-bound the statistical distance between the probability distribution of the states after measuring $|\psi_{\mathcal{A}}\rangle$ and $|\psi_{\text{ideal}}\rangle$ respectively by using Step 1 and the properties of the trace distance given in Fact 3.3 below.

<footnote>(2) In other words, we assume that the Fourier transform is radially preserving. This property depends on the characters chosen to define the Fourier transform and the metric. Recall that a radial function is a function which is constant on spheres centered around 0. This property clearly holds for functions $f: \mathbb{F}_q^n \to \mathbb{C}$ with the characters chosen here and the Hamming metric. We give this more general statement in order to apply it in other cases of interest, for instance the rank metric.</footnote>
Let us give more details about these steps.

**Step 1.** For this purpose, we use the trace distance between quantum states (as in [29] where this has been used in the lattice setting). It is defined as follows:

$$D_{\text{tr}}(|\phi\rangle, |\psi\rangle) \stackrel{\text{def}}{=} \sqrt{1 - |\langle\phi|\psi\rangle|^2}. \quad (12)$$

This distance meets the following properties that will prove useful in our context:

**Fact 3.3:**

(I) The trace distance never increases after a quantum evolution [30, §9, Th. 9.1];

(II) The pair of probability distributions $(p_m, q_m)$ of the measurement outcome $m$ of any quantum measurement performed on the pair of states $(|\phi\rangle, |\psi\rangle)$ satisfies [30, §9, Th. 9.2]

$$D_{\text{stat}}(p_m, q_m) \le D_{\text{tr}}(|\phi\rangle, |\psi\rangle) \quad (13)$$

where $D_{\text{stat}}$ is the statistical distance (also called the total variation distance) between two probability distributions. It is defined by:

$$D_{\text{stat}}(p, q) \stackrel{\text{def}}{=} \frac{1}{2} \sum_{x \in \mathcal{X}} |p(x) - q(x)|$$

where $p$ and $q$ are two discrete probability distributions on $\mathcal{X}$.

The following proposition gives an upper-bound for trace distance between $|\psi_A\rangle$ and $|\psi_{\text{ideal}}\rangle$.

**Proposition 3.4:** With probability greater than $1 - \frac{\langle\pi|1\rangle^2}{q^{n-k}} - O(q^{-\min(k,n-k)})$ over the choices of $\mathbf{G}$ we have:

$$D_{\text{tr}}(|\psi_A\rangle, |\psi_{\text{ideal}}\rangle) \le \sqrt{1 - \frac{p_t^2}{2}} \varepsilon_{\mathbf{G}}^2,$$

where $\varepsilon_{\mathbf{G}}$ is the probability that $A$ returns the right error $e$ when the input matrix is $\mathbf{G}$, i.e.,

$$\varepsilon_{\mathbf{G}} \stackrel{\text{def}}{=} \mathbb{P}_{c,e}(\mathcal{A}(\mathbf{G}, \mathbf{c} + \mathbf{e}) = \mathbf{e}). \quad (14)$$

The proof of this result follows immediately from three lemmas (whose proof is in Appendix A-A). The first one bounds the trace distance in terms of $\varepsilon_{\mathbf{G}}$ and $Z$, and the second one gives a tight upper-bound on the expected value of $Z$ for a related probabilistic model. The latter is used to derive the third one which is fundamental and states that it is very unlikely for $Z$ to be much greater than the “natural” constant $q^k$:

**Lemma 3.5:** We have:

$$D_{\text{tr}}(|\psi_A\rangle, |\psi_{\text{ideal}}\rangle) \le \sqrt{1 - \frac{q^k p_t^2}{Z}} \varepsilon_{\mathbf{G}}^2.$$

**Lemma 3.6:** Assume that $\mathcal{C}$ is chosen by uniformly drawing at random a parity-check matrix $\mathbf{H}$ for it. We have:

$$\mathbb{E}(Z) \le q^k \left( 1 + \frac{\langle\pi|1\rangle^2}{q^{n-k}} \right). \quad (15)$$

**Lemma 3.7:** Let $\eta > 0$. We have:

$$\mathbb{P}_{\mathbf{G}}(Z > q^k(1+\eta)) \le \frac{1}{\eta} \frac{\langle\pi|1\rangle^2}{q^{n-k}} + O\left(q^{-\min(k,n-k)}\right).$$

**Proposition 3.4** immediately follows by using $\eta = 1$ in Lemma 3.7 and plugging this bound on $Z$ in Lemma 3.5. The quantity $q^k$ is the natural value for $Z$ since it is what we can expect when all the $\mathbf{c} + \mathbf{e}$ terms (taking all $\mathbf{c}$ in $\mathcal{C}$ and all typical $\mathbf{e}$) are different. The constant $Z$ increases precisely when there are many collisions for the $\mathbf{c} + \mathbf{e}$ terms. However, in this case, we do not expect to be able to solve the decoding problem anymore.

**Step 2.** More precisely, we prove that

**Lemma 3.8:** If the Fourier transform is radially preserving, meaning that it transforms a radial function into a radial function, then after measuring $|\psi_{\text{ideal}}\rangle$ we obtain a state $|0_n\rangle|\mathbf{c}^{\perp}\rangle$ with $\mathbf{c}^{\perp} \in \mathcal{C}^{\perp}$ of weight $u$ with probability $\frac{q^{2k}}{Z} N_u^{\perp} |\hat{f}(u)|^2$ where $\hat{f}(u) \stackrel{\text{def}}{=} \hat{\pi}_e$ for an arbitrary $e$ of weight $u$ and $N_u^{\perp}$ is the number of codewords of weight $u$ in $\mathcal{C}^{\perp}$.

The proof is given in Appendix A-B.

**Step 3.** This step consists in quantifying how close to 1 the probability of observing a dual codeword of weight in the set $\mathcal{W}$ after measuring $|\psi_{\text{ideal}}\rangle$ is. More specifically, we have

**Proposition 3.9:** Under the assumptions made in Theorem 3.1, the probability of obtaining a codeword $\mathbf{c}^{\perp} \in \mathcal{C}^{\perp}$ of weight $u \in \mathcal{W}$ when measuring $|\psi_{\text{ideal}}\rangle$ is $\ge 1 - \alpha(\pi)$ for a proportion $\ge 1 - \beta(\pi)$ of matrices $\mathbf{G}$, where:

$$\alpha(\pi) \stackrel{\text{def}}{=} \sum_{u \in \mathcal{W}} \left( \frac{q^k}{S_u} \right)^{1/4} + \sqrt{\frac{\langle\pi|1\rangle^2}{q^{n-k}}} - 2^{-\Omega(n)},$$

$$\beta(\pi) \stackrel{\text{def}}{=} (q-1) \sum_{u \in \mathcal{W}} \sqrt{\frac{q^k}{S_u}} + \sqrt{\frac{\langle\pi|1\rangle^2}{q^{n-k}}} + O\left(q^{-\min(k,n-k)}\right).$$

This proposition is proved in Appendix A-C.

**Step 4.** We first prove the following point

**Lemma 3.10:** Call $\mathcal{G}$ the set of “good matrices” $\mathbf{G} \in \mathbb{F}_q^{k \times n}$ that satisfy at the same time:

(i) $\varepsilon_{\mathbf{G}} \ge \varepsilon/2$ (where $\varepsilon$ and $\varepsilon_{\mathbf{G}}$ are defined in Equations (8) and (14)),

(ii) $Z \le 2q^k$.

The proportion of good matrices is at least $\varepsilon/2 - \delta(\pi)$ where $\delta(\pi) \stackrel{\text{def}}{=} \frac{\langle\pi|1\rangle^2}{q^{n-k}} + O(q^{-\min(k,n-k)})$.

*Proof:* By definition,

$$\varepsilon = \frac{1}{q^{kn}} \sum_{\mathbf{G} \in \mathbb{F}_q^{k \times n}} \varepsilon_{\mathbf{G}}.$$

Let $\mathcal{B}$ be the set of matrices $\mathbf{G}$ that are not good, namely for which (a) $\varepsilon_{\mathbf{G}} < \varepsilon/2$ or (b) $Z > 2q^k$. By Lemma 3.7,
the density of matrices verifying (b) is smaller than $\delta(\pi)$. Therefore,

$$ \varepsilon \le \frac{1}{q^{kn}} \sum_{G \notin \mathcal{B}} (1 + \delta(\pi)) \frac{\varepsilon}{2} \le \frac{1}{q^{kn}} \sum_{G \notin \mathcal{B}} (1 + \delta(\pi)) + \frac{\varepsilon}{2} $$

which concludes the proof.

<figure><img src="image_2.png" /></figure>

We use this lemma to prove that the statistical distance between the weight distributions obtained by measuring $|\psi_{\mathcal{A}}\rangle$ and $|\psi_{\text{ideal}}\rangle$ cannot be too far away:

**Lemma 3.11:** Let $P$, respectively $Q$, be the distribution of the weights $|\mathbf{c}^{\perp}|$ of the state $|e\rangle$ $|\mathbf{c}^{\perp}\rangle$ obtained by measuring the state $|\psi_{\mathcal{A}}\rangle$, respectively $|\psi_{\text{ideal}}\rangle$. We have

$$ D_{\text{stat}}(P, Q) \le 1 - \frac{p_t^2 \varepsilon^3}{16} + O(p_t^4 \varepsilon^5) + \delta(\pi). $$

*Proof:* Let,

$$ P_G(u) \stackrel{\text{def}}{=} \mathbb{P}_{c,e} \left( \begin{array}{l} \text{measuring } |\mathbf{c}^{\perp}\rangle \text{ of weight } u \text{ in the 2nd} \\ \text{register of } |\widehat{\psi_{\mathcal{A}}\rangle} \text{ for a code choice } \mathbf{G} \end{array} \right) \quad (16) $$

$$ Q_G(u) \stackrel{\text{def}}{=} \mathbb{P}_{c,e} \left( \begin{array}{l} \text{measuring } |\mathbf{c}^{\perp}\rangle \text{ of weight } u \text{ in the 2nd} \\ \text{register of } |\widehat{\psi_{\text{ideal}}\rangle} \text{ for a code choice } \mathbf{G} \end{array} \right) \quad (17) $$

We start the proof by noticing that

$$ \begin{align*} D_{\text{stat}}(P, Q) &= \frac{1}{2} \sum_u |P(u) - Q(u)| \\ &= \frac{1}{2} \sum_u \left| \sum_{G \in \mathbb{F}_q^{k \times n}} \frac{1}{q^{kn}} (P_G(u) - Q_G(u)) \right| \\ &\le \frac{1}{q^{kn}} \sum_{G \in \mathbb{F}_q^{k \times n}} \frac{1}{2} \sum_u |P_G(u) - Q_G(u)| \\ &= \frac{1}{q^{kn}} \sum_{G \in \mathbb{F}_q^{k \times n}} D_{\text{stat}}(P_G, Q_G) \\ &= \sum_{G \in \mathcal{G}} \frac{D_{\text{stat}}(P_G, Q_G)}{q^{kn}} + \sum_{G \notin \mathcal{G}} \frac{D_{\text{stat}}(P_G, Q_G)}{q^{kn}} \\ &\le \sum_{G \in \mathcal{G}} \frac{D_{\text{tr}}(|\psi_{\mathcal{A}}\rangle, |\psi_{\text{ideal}}\rangle)}{q^{kn}} + \sum_{G \notin \mathcal{G}} \frac{1}{q^{kn}} \quad \text{(by Eq. 13)} \\ &\le \sum_{G \in \mathcal{G}} \frac{\sqrt{1 - \frac{p_t^2 \varepsilon^2}{4}}}{q^{kn}} + \sum_{G \notin \mathcal{G}} \frac{1}{q^{kn}} \quad \text{(by Proposition 3.4)} \\ &\le \sqrt{1 - \frac{p_t^2 \varepsilon^2}{4}} (\varepsilon/2 - \delta(\pi)) + 1 - \varepsilon/2 + \delta(\pi) \end{align*} $$

where in the last inequality we used Lemma 3.10. Therefore,

$$ \begin{align*} D_{\text{stat}}(P, Q) &\le \sqrt{1 - \frac{p_t^2 \varepsilon^2}{4}} (\varepsilon/2 - \delta(\pi)) + 1 - \varepsilon/2 + \delta(\pi) \\ &\le (\varepsilon/2 - \delta(\pi)) \left(1 - \frac{p_t^2 \varepsilon^2}{8} + O(p_t^4 \varepsilon^4)\right) + 1 \\ &\quad - \varepsilon/2 + \delta(\pi) \\ &\le 1 - \frac{p_t^2 \varepsilon^3}{16} + O(p_t^4 \varepsilon^5) + \delta(\pi) \end{align*} $$

which concludes the proof.

<figure><img src="image_3.png" /></figure>

### C. Proof of Theorem 3.1

We are now ready to prove Theorem 3.1. By Proposition 3.9 we know that

$$ \sum_{u \in \mathcal{W}} Q(u) \ge (1 - \alpha(\pi))(1 - \beta(\pi)) \ge 1 - \alpha(\pi) - \beta(\pi). $$

But now we have the following computation,

$$ \begin{align*} \sum_{u \in \mathcal{W}} P(u) &\ge \sum_{u \in \mathcal{W}} Q(u) - D_{\text{stat}}(P, Q) \\ &\ge 1 - \alpha(\pi) - \beta(\pi) - 1 + \frac{p_t^2 \varepsilon^3}{16} - O(p_t^4 \varepsilon^5) - \delta(\pi) \\ &= \frac{p_t^2 \varepsilon^3}{16} - O(p_t^4 \varepsilon^5) - \alpha(\pi) - \beta(\pi) - \delta(\pi) \end{align*} $$

which concludes the proof by definition of $\alpha(\pi)$, $\beta(\pi)$ and $\delta(\pi)$.

### D. Application to the Hamming metric

The assumptions of Theorem 3.1 will be satisfied for the Hamming metric for weights $u$ close to $\tau^{\perp}n$ (where $\tau^{\perp}$ is given in Equation (7)) and we will prove that

**Theorem 3.12:** Suppose that there exists an algorithm $\mathcal{A}$ solving with success probability $\varepsilon$ the decoding problem $DP(q, n, k, t)$ at Hamming distance $1 \le t \stackrel{\text{def}}{=} \tau n \le (1 - \delta)d_{\text{GV}}(n, k)$ for any arbitrary $\delta > 0$. Then, there exists a quantum algorithm which takes as input a generator matrix $\mathbf{G} \in \mathbb{F}_q^{k \times n}$ of a code $\mathcal{C} \subseteq \mathbb{F}_q^n$ and outputs $\mathbf{c}^{\perp} \in \mathcal{C}^{\perp}$ of weight $u \in \llbracket (1 - \alpha)\tau^{\perp}n, (1 + \alpha)\tau^{\perp}n \rrbracket$ (where $\alpha$ is any arbitrary constant $> 0$) with probability over a uniform choice of $\mathbf{G}$ given by a $\Omega\left(\frac{\varepsilon^3}{n} - O\left(\frac{\varepsilon^5}{n^2}\right) - 2^{-\Omega(n)}\right)$ where:

$$ \tau^{\perp} \stackrel{\text{def}}{=} \frac{1}{q} \left( \sqrt{(q-1)(1-\tau)} - \sqrt{\tau} \right)^2. \quad (18) $$

The proof of this theorem relies on Theorem 3.1, for a suitable choice of quantum state $|\pi\rangle$. This is done by choosing $|\pi\rangle = |\pi^{\text{Trunc}}\rangle$ which represents a truncated q-ary symmetric channel of crossover probability $\tau$. All its weights are in an interval $\llbracket (1 - \eta)t, (1 + \eta)t \rrbracket$ where $\eta$ is some positive constant which will be chosen later on. More precisely, let us first define the (untruncated) quantum state representing the q-ary symmetric channel of crossover probability $\tau$:

$$ |\pi^{\text{SC}}\rangle \stackrel{\text{def}}{=} \left( \sqrt{1-\tau} |0\rangle + \sqrt{\tau/(q-1)} \sum_{\alpha \in \mathbb{F}_q^*} |\alpha\rangle \right)^{\otimes n} . $$

Indeed, since $|\pi^{\text{SC}}\rangle$ can also be written as

$$ |\pi^{\text{SC}}\rangle = \sum_{\mathbf{e} \in \mathbb{F}_q^n} \pi_{\mathbf{e}} |\mathbf{e}\rangle \quad \text{with} \quad \pi_{\mathbf{e}} \stackrel{\text{def}}{=} \sqrt{(1-\tau)^{n-|\mathbf{e}|} \left(\frac{\tau}{q-1}\right)^{|\mathbf{e}|}} $$
measuring $|\pi^{\text{SC}}\rangle$ mimics the error we have in a $q$-ary symmetric channel of crossover probability $\tau$, i.e.,

$$ \mathbb{P}(\text{measurement outputs } \mathbf{e}) = |\pi_{\mathbf{e}}|^2 = \left(\frac{\tau}{q-1}\right)^{|\mathbf{e}|} (1-\tau)^{n-|\mathbf{e}|}. $$

We will be interested in the truncated version given by

$$ |\pi^{\text{Trunc}}\rangle \stackrel{\text{def}}{=} \sum_{\mathbf{e} \in \mathbb{F}_q^n} \pi_{\mathbf{e}}^{\text{Trunc}} |\mathbf{e}\rangle $$

$$ \pi_{\mathbf{e}}^{\text{Trunc}} \stackrel{\text{def}}{=} \begin{cases} \frac{\pi_{\mathbf{e}}}{\sqrt{N}} & \text{if } |\mathbf{e}| \in [(1-\eta)t, (1+\eta)t] \\ 0 & \text{otherwise} \end{cases} $$

where $N$ is the normalizing constant given by

$$ N \stackrel{\text{def}}{=} \sum_{\mathbf{e} \in \mathbb{F}_q^n} |\pi_{\mathbf{e}}|^2. \quad (19) $$

It will be helpful to notice that for all $\eta > 0$, $N$ is exponentially close to 1:

**Lemma 3.13:** For all $\eta > 0$, we have

$$ N = 1 - 2^{-\Omega(n)}. $$

**Proof:** Notice that by Equation (19),

$$ \begin{aligned} 1-N &= \sum_{\substack{\mathbf{e} \in \mathbb{F}_q^n \\ |\mathbf{e}| \le [(1-\eta)t, (1+\eta)t]}} |\pi_{\mathbf{e}}|^2 = \mathbb{P}_{\mathbf{e}}(|\mathbf{e}| \notin [(1-\eta)t, (1+\eta)t]) \\ &= \mathbb{P}_{\mathbf{e}}(|\mathbf{e}| < (1-\eta)\tau n) + \mathbb{P}_{\mathbf{e}}(|\mathbf{e}| > (1+\eta)\tau n) \quad (20) \end{aligned} $$

where $|\mathbf{e}|$ is the sum of $n$ independent (binary) Bernoulli random variables of parameter $\tau$. Therefore, by Hoeffding's inequality, we have for all $\eta > 0$,

$$ \mathbb{P}_{\mathbf{e}}(|\mathbf{e}| < (1-\eta)\tau n) \le e^{-2\eta^2 \tau^2 n} \quad \text{and} $$

$$ \mathbb{P}_{\mathbf{e}}(|\mathbf{e}| > (1+\eta)\tau n) \le e^{-2\eta^2 \tau^2 n} $$

which concludes the proof by plugging this in Equation (20).

<figure><img src="image_4.png" /></figure>

**Theorem 3.12** is proved by showing that $|\pi^{\text{Trunc}}\rangle$ satisfies all the requirements of Theorem 3.1 when $\eta$ is small enough.

**Step 1: Verification of Condition (C1).**

This amounts to proving the following lemma

**Lemma 3.14:** For $\eta > 0$ small enough, we have,

$$ \frac{\langle \pi^{\text{Trunc}} | \mathbf{1} \rangle^2}{q^{n-k}} = 2^{-\Omega(n)}. $$

Before proving this result, it will be helpful to notice that:

**Lemma 3.15:** If $u \le (1-\delta)d_{\text{GV}}(n, k)$ for some $\delta > 0$, then

$$ \frac{S_u}{q^{n-k}} = 2^{-\Omega(n)}. $$

**Proof:** Recall that the size $B_u$ of the Hamming ball of radius $u$ is of the form

$$ B_u = q^n h_q(\mu)(1+o(1)) $$

where $\mu \stackrel{\text{def}}{=} u/n$. From this we obtain

$$ \begin{aligned} \frac{S_u}{q^{n-k}} &\le \frac{B_u}{B_{d_{\text{GV}}}} \quad (\text{since } S_u \le B_u \text{ and } B_{d_{\text{GV}}} \le q^{n-k}) \\ &\le q^{n(h_q(\mu)-h_q(\delta_{\text{GV}})+o(1))} \\ &\le q^{n(h_q((1-\delta)\delta_{\text{GV}})-h_q(\delta_{\text{GV}})+o(1))}. \end{aligned} $$

We finish the proof by noticing that $h_q((1-\delta)\delta_{\text{GV}}) - h_q(\delta_{\text{GV}}) < 0$. ■

We are now ready to prove Lemma 3.14.

**Proof of Lemma 3.14:** We have the following computation,

$$ \begin{aligned} \langle \pi^{\text{Trunc}} | \mathbf{1} \rangle &= \sum_{\substack{\mathbf{e} \in \mathbb{F}_q^n \\ |\mathbf{e}| \le [(1-\eta)t, (1+\eta)t]}} \pi_{\mathbf{e}}^{\text{Trunc}} \\ &= \sum_{r \in [(1-\eta)t, (1+\eta)t]} \sum_{\substack{\mathbf{e} \in \mathbb{F}_q^n \\ |\mathbf{e}|=r}} \frac{\pi_{\mathbf{e}}}{\sqrt{N}} \\ &= \frac{1}{\sqrt{N}} \sum_{r \in [(1-\eta)t, (1+\eta)t]} \sqrt{\binom{n}{r}} (q-1)^r \\ &\quad \times \sqrt{\binom{n}{r}} (q-1)^r (1-\tau)^{n-r} \left(\frac{\tau}{q-1}\right)^r \\ &\le \frac{1}{\sqrt{N}} \sum_{r \in [(1-\eta)t, (1+\eta)t]} \sqrt{\binom{n}{r}} (q-1)^r \end{aligned} \quad (21) $$

where in the last line we used that $\binom{n}{u}(q-1)^u \left(\frac{\tau}{q-1}\right)^u (1-\tau)^{n-u} \le 1$ for any $u \in [0, n]$. Therefore, using Equation (21), we have the following computation

$$ \begin{aligned} \langle \pi^{\text{Trunc}} | \mathbf{1} \rangle^2 &\le \frac{1}{N} \left( \sum_{r=\lceil(1-\eta)t\rceil}^{\lfloor(1+\eta)t\rfloor} \sqrt{\binom{n}{r}} (q-1)^r \right) \\ &\quad \times \left( \sum_{r'=\lceil(1-\eta)t\rceil}^{\lfloor(1+\eta)t\rfloor} \sqrt{\binom{n}{r'}} (q-1)^{r'} \right) \\ &\le \frac{(n+1)^2}{N} \\ &\quad \times \max_{r,r' \in [(1-\eta)t, (1+\eta)t]} \sqrt{\binom{n}{r} \binom{n}{r'} (q-1)^r (q-1)^{r'}} \end{aligned} $$

where in the last inequality we used that $\#[(1-\eta)t, (1+\eta)t] \le n+1$. Therefore, using the fact that the max is reached for $r=r'=(1+\eta)t$, we obtain,

$$ \begin{aligned} \langle \pi^{\text{Trunc}} | \mathbf{1} \rangle^2 &\le \frac{(n+1)^2}{N} \binom{n}{r} (q-1)^{(1+\eta)t} \\ &= \frac{(n+1)^2}{N} S_{(1+\eta)t} \end{aligned} $$
Using this last inequality and Lemmas 3.13 and 3.15, we obtain

$$ \frac{\langle \pi^{\text{Trunc}} | \mathbf{1} \rangle^2}{q^{n-k}} = O \left( (n+1)^2 \frac{S_{(1+\eta)t}}{q^{n-k}} \right) = 2^{-\Omega(n)} $$

where we choose $\eta$ small enough such that $(1+\eta)t \le (1-\delta')d_{\text{GV}}(n,k)$ for some $\delta' > 0$ (recall that by assumption $t \le (1-\delta)d_{\text{GV}}(n,k)$ for $\delta > 0$).

**Remark 3.16:** As explained in the introduction and Remark 3.2, Lemma 3.14 is not satisfied by $|\pi^{\text{SC}}\rangle$. Here truncating the error distribution is essential to verify this concentration lemma.

**Step 2: Verification of Conditions (C2) and (C3).**

We prove here that the Conditions (C2) and (C3) of Theorem 3.1 are met by $|\pi^{\text{Trunc}}\rangle$. This results from a combination of arguments: (i) these two conditions are met for $|\pi^{\text{SC}}\rangle$ (ii) $|\pi^{\text{SC}}\rangle$ and $|\pi^{\text{Trunc}}\rangle$ are very close and so are $|\widehat{\pi^{\text{SC}}}\rangle$ and $|\widehat{\pi^{\text{Trunc}}}\rangle$ (because they are obtained from the first pair by applying a QFT, which is unitary).

More precisely we are going to prove that

**Lemma 3.17:** Let $t^{\perp} \stackrel{\text{def}}{=} \frac{(\sqrt{(q-1)(n-t)-\sqrt{t})}^2}{q}$ and $\alpha > 0$ be some constant small enough. We let $|\widehat{\pi^{\text{Trunc}}}| = \sum_{e \in \mathbb{F}_q^n} \pi_e^{\text{Trunc}} |e\rangle$. This state is radial and we let $f^{\text{Trunc}}(w) = \widehat{\pi_e^{\text{Trunc}}}$ for any element $e$ of $\mathbb{F}_q^n$ of Hamming weight $w$. We have

$$ p_t = \Omega\left(\frac{1}{\sqrt{n}}\right) \quad \text{and} \quad \forall u \in [t^{\perp}(1-\alpha), t^{\perp}(1+\alpha)], $$

$$ \frac{q^k}{S_u} = 2^{-\Omega(n)} \quad \text{and} \quad \sum_{u=[t^{\perp}(1-\alpha)]}^{[t^{\perp}(1+\alpha)]} S_u |\widehat{f^{\text{Trunc}}}(u)|^2 = 1 - 2^{-\Omega(n)}. $$

As explained above, to prove this result we will rely on the following lemma

**Lemma 3.18:** For all $\eta > 0$, we have

$$ \|\pi^{\text{Trunc}}\rangle - \pi^{\text{SC}}\rangle = \|\widehat{\pi^{\text{Trunc}}} - \widehat{\pi^{\text{SC}}}\rangle = 2^{-\Omega(n)} \quad (22) $$

**Proof:** We have the following computation,

$$ \begin{align*} & \|\widehat{\pi^{\text{Trunc}}}| - |\pi^{\text{SC}}\rangle\|^2 \\ &= \sum_{e \in \mathbb{F}_q^n} (\pi_e - \pi_e^{\text{Trunc}})^2 \\ &= \sum_{\substack{e \in \mathbb{F}_q^n: \\ |e| \notin [(1-\eta)t, (1+\eta)t]}} \pi_e^2 + \sum_{\substack{e \in \mathbb{F}_q^n: \\ |e| \in [(1-\eta)t, (1+\eta)t]}} \left(\pi_e - \frac{\pi_e}{\sqrt{N}}\right)^2 \\ &= 1 - N + \frac{(1 - \sqrt{N})^2}{N} \sum_{\substack{e \in \mathbb{F}_q^n: \\ |e| \in [(1-\eta)t, (1+\eta)t]}} \pi_e^2 \quad \text{(by Eq. (19))} \\ &= 1 - N + (1 - \sqrt{N})^2 \quad \text{(by Eq. (19))} \\ &\le 2^{-\Omega(n)} \quad \text{(by Lemma (3.13)).} \end{align*} $$

The second relation follows, since the QFT is an isometry with respect to $\|\cdot\|$. ■

With this lemma at hand, we are ready to prove Lemma 3.17.

**Proof of Lemma 3.17.:** By definition,

$$ \begin{align*} p_t &= \frac{1}{N} \sum_{e: |e|=t} (1-\tau)^{n-t} \left(\frac{\tau}{q-1}\right)^t \\ &= \frac{\binom{n}{t} (q-1)^t q^{nh_q(\tau)}}{N} = \Omega\left(\frac{1}{\sqrt{n}}\right) \end{align*} $$

where in the last equality we used Lemma 3.13 and Stirling's formula.

The equality $\frac{q^k}{S_u} = 2^{-\Omega(n)}$ is verified when $u$ is sufficiently close to $t^{\perp}$ ($\alpha$ small enough), because it is readily verified that there exists some constant $\beta > 0$ such that $t^{\perp} \ge (1+\beta)d_{\text{GV}}(n,k)$. This together with $t^{\perp} \le \frac{(q-1)n}{q}$ implies that $\frac{q^k}{S_u} = 2^{-\Omega(n)}$ for any $u$ in $[t^{\perp}(1-\alpha), t^{\perp}(1+\alpha)]$.

The untruncated distribution $|\pi^{\text{SC}}\rangle = \sum_e \pi_e |e\rangle$ is radial, and so is its Fourier transform $|\widehat{\pi^{\text{SC}}}| = \sum_e \widehat{\pi}_e |e\rangle$. We let $\hat{f}(u) = \widehat{\pi}_e$ where $e$ is any $e \in \mathbb{F}_q^n$ of Hamming weight $u$. We notice that

$$ \sum_{u=[t^{\perp}(1-\alpha)]}^{[t^{\perp}(1+\alpha)]} S_u |\hat{f}(u)|^2 = \sum_{e \in \mathbb{F}_q^n: |e| \in [(1-\alpha)t^{\perp}, (1+\alpha)t^{\perp}]} |\hat{\pi}_e|^2 \\ = \mathbb{P}_e (|e| \in [(1-\alpha)t^{\perp}, (1+\alpha)t^{\perp}]) $$

where $\tau^{\perp} = \frac{t^{\perp}}{n}$ and $|e|$ is the sum of $n$ independent (binary) Bernoulli random variables of parameter $\tau^{\perp}$. Therefore, by using Hoeffding's bound again we obtain that

$$ \sum_{u \in [(1-\alpha)t^{\perp}, (1+\alpha)t^{\perp}]} S_u |\hat{f}(u)|^2 = 1 - 2^{-\Omega(n)}, \quad (23) $$

meaning that $\hat{f}$ concentrates around vectors of weight $t^{\perp}$. Consider the projection of $|\pi^{\text{SC}}\rangle$ and $|\pi^{\text{Trunc}}\rangle$ on the space spanned by the states $|e\rangle$ for $|e| \in [(1-\alpha)t^{\perp}, (1+\alpha)t^{\perp}]$:

$$ \begin{align*} |\widehat{\pi^{\text{SC}}}\rangle &\stackrel{\text{def}}{=} \sum_{e \in \mathbb{F}_q^n: |e| \in [(1-\alpha)t^{\perp}, (1+\alpha)t^{\perp}]} \hat{\pi}_e |e\rangle \\ |\widehat{\pi^{\text{Trunc}}}\rangle &\stackrel{\text{def}}{=} \sum_{e \in \mathbb{F}_q^n: |e| \in [(1-\alpha)t^{\perp}, (1+\alpha)t^{\perp}]} \widehat{\pi}_e^{\text{Trunc}} |e\rangle \end{align*} $$

Since a projection can only reduce the norm, we have

$$ \|\widehat{\pi^{\text{SC}}} - \widehat{\pi^{\text{Trunc}}}\| \le \|\widehat{\pi^{\text{SC}}} - \widehat{\pi^{\text{Trunc}}}\| = 2^{-\Omega(n)}. \quad (24) $$

We deduce from the triangle inequality that

$$ \|\widehat{\pi^{\text{Trunc}}}|\| \ge \|\widehat{\pi^{\text{SC}}}|\| - \|\widehat{\pi^{\text{SC}}}|\widehat{\pi^{\text{Trunc}}}|\| \quad (25) $$

and then from Equations (24) and (23) (which says $\|\widehat{\pi^{\text{SC}}}|\|^2 = 1 - 2^{-\Omega(n)}$) that $\|\widehat{\pi^{\text{Trunc}}}|\| \ge 1 - 2^{-\Omega(n)}$. Since $\|\widehat{\pi^{\text{Trunc}}}|\| \le \|\widehat{\pi^{\text{Trunc}}}|\| = 1$ we finally obtain

$$ \|\widehat{\pi^{\text{Trunc}}}|\| = 1 - 2^{-\Omega(n)}. $$
This directly implies $\sum_{u \in [(1-\alpha)t^{\perp}, (1+\alpha)t^{\perp}]} S_u |\hat{f}_{\text{Trunc}}(u)|^2 = \| |\pi_{\text{Trunc}}| \|^2 = 1 - 2^{-\Omega(n)}$.

**Proof of Theorem 3.12.**

This immediately follows from Lemmas 3.14 and 3.17 which show that the relevant assumptions of Theorem 3.1 are verified for the choice $|\pi\rangle = |\pi^{\text{Trunc}}\rangle$ for $\eta$ small enough.

### E. Application to the rank metric

The assumptions of Theorem 3.1 will also be satisfied in the context of codes $\mathcal{C} \subseteq \mathbb{F}_q^{m \times n}$ embedded with the rank metric (given some matrix in $\mathbb{F}_q^{m \times n}$, its weight is defined as its rank). The Gilbert-Varshamov distance $d_{\text{GV}}(m, n, k)$ is defined in a similar way, but it depends on three parameters here and corresponds to the largest radius $t$ of a ball in the rank metric for which

$$q^k B_t \le q^{m \times n}.$$

We will be able to prove that

**Theorem 3.19:** Suppose that there exists an algorithm $\mathcal{A}$ solving with success probability $\varepsilon$ the decoding problem at rank distance $1 \le t < d_{\text{GV}}(m, n, k)$ where $m \ge n$. Then, there exists a quantum algorithm which takes as input a generator matrix of $\mathcal{C} \subseteq \mathbb{F}_q^{m \times n}$ and outputs $\mathbf{c}^{\perp} \in \mathcal{C}^{\perp}$ of weight $u \in (t^{\perp} - \eta n, t^{\perp}]$ where $t^{\perp} = \text{def} \equiv n - t$ (for any arbitrary constant $\eta > 0$) with probability over a uniform choice of the generator matrix given by a $\Omega(\varepsilon^3 - O(\varepsilon^5) - 2^{-\Omega(n)})$.

**Remark 3.20:** Our assumption that $m \ge n$ can be done without loss of generality. In the case where $n > m$ we can just consider the transposed code $\mathcal{C}^{\text{T}} \stackrel{\text{def}}{=} \{\mathbf{M}^{\text{T}} : \mathbf{M} \in \mathcal{C}\}$: taking the transpose is a linear automorphism and can be used to transform any algorithm decoding $\mathcal{C}$ into an algorithm decoding $\mathcal{C}^{\text{T}}$ with the same complexity.

As in the Hamming case, Theorem 3.19 will be a consequence of Theorem 3.1. Therefore we first have to choose appropriately a quantum state $|\pi\rangle$ that will model the noise distribution.

### Step 1: Choosing $|\pi\rangle$.

Let,

$$|\pi\rangle \stackrel{\text{def}}{=} \frac{1}{\sqrt{N}} \sum_{\substack{V \le \mathbb{F}_q^n \\ \dim V = t}} |\pi_V\rangle \quad \text{where} \quad (26)$$

$$|\pi_U\rangle \stackrel{\text{def}}{=} \left( \frac{1}{\sqrt{q^{\dim U}}} \sum_{\mathbf{u} \in U} |\mathbf{u}\rangle \right)^{\otimes m} \quad (27)$$

and $N$ is a normalizing constant. $|\pi_U\rangle$ can be viewed as a uniform superposition of matrices whose rows belong to $U$. These matrices have rank at most $\dim U$ and $|\pi\rangle$ is close to

a uniform distribution of all matrices of rank $t$. We also have the following alternative description for $|\pi\rangle$.

**Lemma 3.21:** $|\pi\rangle$ is radial, i.e., we may write $|\pi\rangle$ as

$$|\pi\rangle = \sum_{\mathbf{E} \in \mathbb{F}_q^{m \times n}: |\mathbf{E}| \le t} \pi_{\mathbf{E}} |\mathbf{E}\rangle$$

with $|\mathbf{E}\rangle \stackrel{\text{def}}{=} |\mathbf{E}_1\rangle \otimes \dots \otimes |\mathbf{E}_m\rangle$ where the $\mathbf{E}_i$'s denote the rows of $\mathbf{E}$ and $\pi_{\mathbf{E}} = f(|\mathbf{E}|)$ where

$$f(u) = \begin{cases} \frac{[n-u]}{\sqrt{q^{mt}N}} & \text{if } u \le t, \\ 0 & \text{otherwise.} \end{cases}$$

This lemma is proved in Appendix B-A, as well as the following one, which gives estimations for $N$ and $p_t$ in order to apply Theorem 3.1.

**Lemma 3.22:** We have:

$$N = \Theta \left( \begin{bmatrix} n \\ t \end{bmatrix}_q \right) \quad \text{and} \quad p_t = \Theta(1).$$

### Step 2: Verification that $|\pi\rangle$ is radial.

The following proposition states that $|\pi\rangle$ has actually the same form as $|\pi\rangle$ where $t$ is replaced by $n-t$:

**Proposition 3.23:** We have,

$$|\pi\rangle = \frac{1}{\sqrt{N}} \sum_{\substack{W \le \mathbb{F}_q^n \\ \dim W = n-t}} |\pi_W\rangle.$$

**Proof:** We apply the QFT on $|\pi\rangle$, defined in Equation (26). It gives,

$$|\pi\rangle = \frac{1}{\sqrt{N}} \sum_{\substack{V \le \mathbb{F}_q^n \\ \dim V = t}} \left( \frac{1}{\sqrt{q^{n+t}}} \sum_{\mathbf{y} \in \mathbb{F}_q^n} \left( \sum_{\mathbf{v} \in V} \chi_{\mathbf{y}}(\mathbf{v}) \right) |\mathbf{y}\rangle \right)^{\otimes m}$$

By distinguishing the cases where $\mathbf{y} \in V^{\perp}$ (the dual of $V$ with the standard inner product) or not:

$$\begin{aligned} |\pi\rangle &= \frac{1}{\sqrt{N}} \sum_{\substack{V \le \mathbb{F}_q^n \\ \dim V = t}} \left( \frac{1}{\sqrt{q^{n+t}}} \sum_{\mathbf{y} \in V^{\perp}} q^t |\mathbf{y}\rangle \right)^{\otimes m} \\ &= \frac{1}{\sqrt{N}} \sum_{\substack{W \le \mathbb{F}_q^n \\ \dim W = n-t}} \left( \frac{1}{\sqrt{q^{n-t}}} \sum_{\mathbf{y} \in W} |\mathbf{y}\rangle \right)^{\otimes m} \end{aligned}$$

which concludes the proof.

We can now straightforwardly apply Lemma 3.21 on $|\pi\rangle$ and obtain

**Lemma 3.24:** The state $|\pi\rangle$ is radial and can be written as $\sum_{\mathbf{E} \in \mathbb{F}_q^{m \times n}: |\mathbf{E}| \le n-t} \hat{f}(u) \stackrel{\text{def}}{=} \hat{\pi}_{\mathbf{E}}$ for any $\mathbf{E} \in \mathbb{F}_q^{m \times n}$ of rank $u$, we have

$$\hat{f}(u) = \begin{cases} \frac{[n-u]}{\sqrt{q^{m(n-t)}N}} & \text{if } u \le n-t, \\ 0 & \text{otherwise.} \end{cases}$$
**Step 3: Verification of Conditions (C1), (C2) and (C3).**

This is achieved in the following Lemmas that are proved in Appendix B-B.

**Lemma 3.25:** We have,

$$ \frac{S_t}{q^{mn-k}} = q^{-\Omega(n)} \quad \text{and} \quad \frac{\langle \pi | \mathbf{1} \rangle^2}{q^{mn-k}} = q^{-\Omega(n)}. $$

**Lemma 3.26:** For any $\eta > 0$, we have $\forall u \in [(1-\eta)n-t, n-t]$

$$ \frac{q^k}{S_u} = q^{-\Omega(n)} $$

and,

$$ \sum_{u \in [(1-\eta)n-t, n-t]} S_u |\hat{f}(u)|^2 = 1 - q^{-\Omega(n)}. $$

**Proof of Theorem 3.19.**

This follows from Lemmas 3.21, 3.24, 3.25 and 3.26 that allow to apply Theorem 3.1, completing the proof.

## 4. ABOUT THE USEFULNESS OF OUR REDUCTION.

It is now interesting to look at the parameters for which our reduction is useful for both the Hamming and rank metrics.

### A. Hamming case

A lower-bound on $\tau$ is obtained with the following arguments. First, if one wants to compute dual codewords (via the quantum measure) for which no poly-time algorithm is known, one has to ensure that $\tau^{\perp} < \omega_{\text{easy}}(n, n-k) = \frac{q-1}{q} \frac{k}{n}$. But notice that $\tau \mapsto \tau^{\perp}$ is a decreasing involution on $[0, \frac{1}{2}]$. Therefore, for the reduction to be meaningful, it is necessary that

$$ \begin{aligned} \tau > \omega_{\text{easy}}(n, n-k)^{\perp} \\ = \frac{1}{q} \left( \sqrt{(q-1) \left(1 - \frac{q-1}{q} \frac{k}{n}\right)} - \sqrt{\frac{q-1}{q} \frac{k}{n}} \right)^2 \\ = \frac{q-1}{q^2} \left( \sqrt{q - (q-1) \frac{k}{n}} - \sqrt{\frac{k}{n}} \right)^2 \end{aligned} \quad (28) $$

Furthermore, according to Theorem 3.12, the relative decoding distance $\tau$ has to verify

$$ \begin{aligned} \tau < \frac{d_{\text{GV}}(n, k)}{n} &= h_q^{-1} \left(1 - \frac{k}{n}\right) + O\left(\frac{1}{n}\right) \\ &= \delta_{\text{GV}}(n, k) + O\left(\frac{1}{n}\right). \end{aligned} $$

Roughly speaking, it gives the tightest upper-bound for which we can expect to correctly decode with an overwhelming probability. Combining this with (28) leads to a whole interval in which $\tau$ needs to lie for the reduction to work and be meaningful. In Figure 1, we draw (asymptotically in $n$) this

range of values of $\tau$ as function of $R \stackrel{\text{def}}{=} \frac{k}{n}$ for different values of $q$ (the green area). Two important remarks can be made from these graphs:

1) the range of interesting values for $\tau$ (i.e., values such that we solve a hard instance of SCP) shrinks as $q$ grows and depending on $R$;

2) the lower bound on $\tau$ corresponding to $\tau^{\perp} < \omega_{\text{easy}}(n, n-k)$ is almost always above $\delta_{\text{GV}}(n, k)/2$, meaning that in order to solve a hard instance of SCP, it is a necessity that $\tau$ goes beyond the unique decoding radius.

### B. Rank Case

It turns out that unfortunately, for the rank metric (which is coarser than the Hamming metric), we always reduce decoding $t$ errors to finding dual codewords of weight $t^{\perp} = n-t$ where $t^{\perp}$ belongs to a range of values for which it is always easy to find codewords of this weight as we now show.

To verify this point, consider a linear code $\mathcal{C} \subseteq \mathbb{F}_q^{m \times n}$ of dimension $K$ (with $m \ge n$). It is easy to find short codewords if they are above a certain range. To produce codewords of small weight, we use the fact that the dual code is a vector space of dimension $nm - K$. Thus, we can just produce codewords with $nm - K - 1$ entries equal to 0 that will be good candidates for having a small weight by solving a linear system. The entries are chosen so as to fill columns with zeroes. It is straightforward that this strategy produces in polynomial time codewords of weight $\approx Rn$ (since in our case $n \le m$) where $R$ is the rate of $\mathcal{C}$ defined by $R \stackrel{\text{def}}{=} \frac{K}{mn}$.

Notice now that $t^{\perp}$ is a decreasing function of the decoding distance $t$. The largest value for which we can hope to decode is the Gilbert-Varshamov distance $d_{\text{GV}}(m, n, K)$. The relative Gilbert-Varshamov distance $\delta_{\text{GV}}(m, n, K) \stackrel{\text{def}}{=} \frac{d_{\text{GV}}(m, n, K)}{n}$ satisfies the relation

$$ R = 1 - \delta_{\text{GV}}(1 + \nu - \delta_{\text{GV}}) $$

where $\nu \stackrel{\text{def}}{=} \frac{m}{n} \ge 1$. However, we have (where $\delta_{\text{GV}}^{\perp}$ is defined as $t^{\perp}/n$ when $t/n = \delta_{\text{GV}}(m, n, K)$)

$$ \frac{t^{\perp}}{n} \ge \delta_{\text{GV}}^{\perp} = 1 - \delta_{\text{GV}} = R + \delta_{\text{GV}}(\nu - \delta_{\text{GV}}) \ge R. $$

In other words, we are always in a regime where finding codewords of relative weight $t^{\perp}/n$ is easy.

## 5. CONCLUDING REMARKS

**Considering other metrics.** The whole approach we have followed here (properly choosing the error distribution and, if necessary, going beyond the unique decoding radius for decoding) can of course be adapted to other metrics than those we have considered here (Hamming and rank). For instance, it would be interesting to investigate it also for metrics like the Lee metric (more or less the $L_1$ norm version of the Euclidean
metric on $Z_q^n$) which has also begun to find its way in code-based cryptography [31] and should have a behavior closer to the Euclidean metric if the size of the alphabet grows with the code length.

**Devising quantum algorithms for producing low weight codewords.** Interestingly, the very same quantum reduction was recently used in [32] to devise a polynomial-time algorithm for finding moderately low weight codewords for the $L_\infty$ norm in a regime of parameters for which no known polynomial time algorithms exist to perform this task. The code rate regime considered there (vanishing with the codelength) avoids the technicalities we needed here (namely truncating the error distribution). Again, this work emphasizes the role of the dual noise model obtained by applying the Fourier transform.

**The dual error distribution.** Moving to this quantum setting allows us to define in a natural way a dual error distribution. Indeed, consider the quantum state representing the noise added to the codeword

$$|\pi\rangle \stackrel{\text{def}}{=} \sum_{e \in \mathbb{F}_q^n} \pi_e |e\rangle.$$

($|\pi e|^2$)$_{e \in \mathbb{F}_q^n}$ is a probability distribution of the error and its quantum Fourier transform $\widehat{\pi} \stackrel{\text{def}}{=} \sum_{e \in \mathbb{F}_q^n} \hat{\pi}_e |e\rangle$ gives a “dual” probability distribution of the noise ($|\hat{\pi}_e|^2$)$_{e \in \mathbb{F}_q^n}$ which we view as the dual noise distribution. Note that a given noise distribution $(p_e)_{e \in \mathbb{F}_q^n}$ may be represented by several different quantum states $\sum_{e \in \mathbb{F}_q^n} \pi_e |e\rangle$ since it is sufficient that $p_e = |\pi_e|^2$ for all $e$. The choice of $\pi_e = \sqrt{p_e}$ is natural but not canonical and is used to define what we call the dual noise distribution. Interestingly enough, this dual noise distribution seems to capture very fundamental quantities in coding theory as we will explain in the following paragraph. Moreover, contrarily to the dual noise considered in [33, §IX], which is also obtained by taking the Fourier transform and dualizing the sum-product algorithm and does not always yield a probability distribution when applied to a probability distribution, we define here a dual noise distribution that is always a probability distribution.

**About the dual distance** $t^\perp = \tau^\perp n$. This dual distribution also allows us to define a notion of “dual distance”. We namely consider here probability distributions (such as the Bernoulli noise) that are concentrated around a certain weight $s$ and such that the dual distribution concentrates around another weight as well that can be considered as the “dual weight” $s^\perp$. In the case of the Bernoulli noise of parameter $\tau$, the dual distribution is again a Bernoulli noise distribution, of parameter $\tau^\perp$. In other words, the dual distance $t^\perp$ can be defined as $\tau^\perp n$ when $t = \tau n$. Note that the choice we made for defining the dual distribution, namely that $\pi_e = \sqrt{p_e}$ (where $p_e$ is the probability that $e$ is drawn from a Bernoulli distribution of parameter $\tau$), minimizes the weight $t^\perp$ around which the dual

distribution converges. This gives the strongest reduction in our case.

Such an interpretation also holds in the lattice based setting (and the Euclidean distance) [19], [29] when the noise is distributed over $\mathbb{R}^n$ according to a Gaussian distribution $D_s(x) = \frac{e^{-\pi \|x\|^2/s^2}}{s^n}$ concentrated around the distance $t = s\sqrt{\frac{n}{2\pi}}$. The dual noise is obtained by taking the Fourier transform of $\sqrt{D_s}$ and squaring the result. The dual noise is a centered Gaussian

$$t^\perp \stackrel{\text{def}}{=} \frac{1}{2s} \sqrt{\frac{n}{2\pi}} = \frac{n}{4\pi t}$$

where in the last equality we used that $t = s\sqrt{\frac{n}{2\pi}}$.

The same also holds in the case of the rank metric, where we define a quantum state representing the noise $|\pi\rangle$ whose rank weight concentrates around the weight $t$ we can decode. After applying the quantum Fourier transform, $|\pi\rangle$ is a superposition of elements whose rank weight concentrates around $t^\perp \stackrel{\text{def}}{=} n-t$ (when we consider codes of length $n$).

This notion of dual distance has an intriguing connection with a very fundamental and old issue which is still open for an overwhelming majority of metric spaces: what is the largest packing density for a given packing radius? The answer is generally not even known asymptotically. One of the most powerful technique which gives the best known bounds in the case of the Hamming metric or for the Euclidean metric over $\mathbb{R}^n$ is obtained through a linear programming approach [34], [35], see [36], [37]. Interestingly enough, the first linear programming bound in coding theory [36] or the one [37], [38] for sphere packing in $\mathbb{R}^n$ can be rephrased in terms of our dual distance and the Gilbert-Varshamov distance. Strictly speaking, the Gilbert-Varshamov is a coding theoretic notion, but it has also an analogue for $\mathbb{R}^n$, see [39] for instance. For this purpose, let us express the Gilbert-Varshamov distance as a function $d_{GV}(\delta)$ of the packing density $\delta \stackrel{\text{def}}{=} \frac{|e|}{|\mathcal{E}|}$ where $|e|$ is the code size and $|\mathcal{E}|$ the ambient space size. It is the supremum of the radius $t$ of a ball $B_t$ such that

$$|B_t| \le \frac{1}{\delta}.$$

The Gilbert-Varshamov distance for $\mathbb{R}^n$ and a given packing density $\delta$ can be defined similarly as the supremum of the radius $t$ of a ball $B_t$ such that

$$\mathrm{Vol}(B_t) \le \frac{1}{\delta}.$$

With this notion, the first linear programming bound in coding theory [36] or the one [37] for sphere packing in $\mathbb{R}^n$ can be expressed as

$$t^\perp \ge d_{GV}(\delta^*)(1 + o(1)), \qquad (29)$$
where $\delta^*$ is the dual packing density: $\delta^* = \frac{1}{\delta}$ in the case of $\mathbb{R}^n$ and $\delta^* = \frac{1}{\delta|\varepsilon|}$ in coding theoretic setting$^{(3)}$. This indeed gives an upper-bound on $t$ since $t^\perp$ is a decreasing function of $t$. This suggests that there might be a direct proof of (29) relying only on the way $t^\perp$ is defined and could yield new bounds on the packing density/minimum distance of a code for the metrics where linear programming bounds are not known.

## ACKNOWLEDGEMENT

The authors would like to thank the anonymous reviewers for their helpful feedback. This work was partly funded by the French Agence Nationale de la Recherche through the France 2023 ANR project ANR-22-PETQ-0008PQ-TLS. Thomas Debris-Alazard would also like to thank support of the French Agence Nationale de la Recherche through ANR JCJC COLA (ANR-21-CE39-0011).

# APPENDIX A
PROOF OF THEOREM 3.1

## A. Step 1: Proof of Lemmas 3.5 and 3.7

Let us recall Lemma 3.5 first:

Lemma 3.5: We have:

$$D_{\text{tr}}(|\psi_{\mathcal{A}}\rangle, |\psi_{\text{ideal}}\rangle) \le \sqrt{1 - \frac{q^k p_t^2}{Z} \varepsilon_{\mathcal{G}}^2}.$$

*Proof:* Let $\mathcal{G}$ be the set of $(\mathbf{c}, \mathbf{e})$'s that correspond to inputs of weight $t$ to $\mathcal{A}$ that are correctly decoded:

$$\mathcal{G} \stackrel{\text{def}}{=} \{(\mathbf{c}, \mathbf{e}) \in \mathcal{C} \times \mathcal{S}_t : \mathcal{A}(\mathbf{G}, \mathbf{c} + \mathbf{e}) = \mathbf{e}\}.$$

Let us recall that

$$|\psi_{\mathcal{A}}\rangle = \frac{1}{\sqrt{q^k}} \sum_{\mathbf{e} \in \mathbb{F}_q^n} \sum_{\mathbf{c} \in \mathcal{C}} \pi_{\mathbf{e}} |\mathbf{e} - \mathcal{A}(\mathbf{G}, \mathbf{c} + \mathbf{e})\rangle |\mathbf{c} + \mathbf{e}\rangle$$

$$|\psi_{\text{ideal}}\rangle = \frac{1}{\sqrt{Z}} \sum_{\mathbf{e} \in \mathbb{F}_q^n} \sum_{\mathbf{c} \in \mathcal{C}} \pi_{\mathbf{e}} |\mathbf{0}_n\rangle |\mathbf{c} + \mathbf{e}\rangle$$

From this we deduce by using the non-negativity of $\pi_e$ that

$$\begin{aligned} \langle \psi_{\mathcal{A}} | \psi_{\text{ideal}} \rangle &\ge \frac{1}{\sqrt{q^k Z}} \sum_{(\mathbf{c}, \mathbf{e}) \in \mathcal{G}} \pi_e^2 \\ &= \sqrt{\frac{q^k}{Z}} S_t f(t)^2 \frac{\#\mathcal{G}}{q^k S_t} \\ &= \sqrt{\frac{q^k}{Z}} p_t \varepsilon_{\mathcal{G}} \end{aligned}$$

which concludes the proof.

<figure><img src="image_5.png" /></figure>

**Remark A.1:** Here we do not have as in the lattice case [29] to make the assumption that the decoder is “strongly solution

independent". In our case we can indeed have a uniform superposition over all the codewords and we can just use the way our error probability is defined, namely as the ratio $\frac{\#\mathcal{G}}{q^k S_t}$. All the probabilistic results of this section are easier to prove if, instead of choosing a code $\mathcal{C}$ by picking uniformly at random a generator matrix $\mathbf{G}$ for it, we slightly change the probabilistic model by picking uniformly at random a parity-check matrix $\mathbf{H} \in \mathbb{F}_q^{(n-k) \times n}$ for it, i.e.,

$$\mathcal{C} = \{\mathbf{x} \in \mathbb{F}_q^n : \mathbf{H}\mathbf{x}^\top = \mathbf{0}\}.$$

We will denote $\mathbb{P}_{\mathbf{G}}$ and $\mathbb{P}_{\mathbf{H}}$ respectively the probabilities in the initial model and the probabilities in the new model. The two probability distributions are closely related: the first model always produces linear codes of dimension $\le k$ and codes of dimension $= k$ with probability $1 - O(q^{-(n-k)})$ whereas the second model always produces linear codes of dimension $\ge k$ and codes of dimension $= k$ with probability $1 - O(q^{-k})$. This relationship is expressed by the following lemma.

**Lemma A.2:** Let $\mathcal{E}$ be an ensemble of linear codes of length $n$ in $\mathbb{F}_q$. We have

$$\mathbb{P}_{\mathbf{G}}(\mathcal{E}) \le \mathbb{P}_{\mathbf{H}}(\mathcal{E}) + O\left(q^{-\min(k,n-k)}\right).$$

With this new probabilistic model, the expected value of $Z$ is given by:

**Lemma A.3:** Assume that $\mathcal{C}$ is chosen by uniformly drawing at random a parity-check matrix $\mathbf{H}$ for it. We have:

$$\mathbb{E}(Z) \le q^k \left( 1 + \frac{\langle \pi | \mathbf{1} \rangle^2}{q^{n-k}} \right). \quad (15)$$

*Proof:* Computing $\mathbb{E}_{\mathbf{H}}(Z)$ with this alternate probabilistic model is straightforward. We have

$$\begin{aligned} Z &= \left\| \sum_{\mathbf{e} \in \mathcal{C}, \mathbf{e} \in \mathbb{F}_q^n} \pi_{\mathbf{e}} |\mathbf{0}_n\rangle |\mathbf{c} + \mathbf{e}\rangle \right\|^2 \\ &= q^k \sum_{\mathbf{e} \in \mathbb{F}_q^n} |\pi_{\mathbf{e}}|^2 + \sum_{(\mathbf{c}, \mathbf{e}) \ne (\mathbf{e}', \mathbf{e}') : \mathbf{c} + \mathbf{e} = \mathbf{c}' + \mathbf{e}'} \pi_{\mathbf{e}} \pi_{\mathbf{e}'} \\ &= q^k \left( 1 + \sum_{\mathbf{e} \ne \mathbf{e}'} \mathbf{H}(\mathbf{e} - \mathbf{e}')^\top = \mathbf{0} \right) \end{aligned}$$

where $\mathbf{H}$ is an arbitrary-parity check matrix for $\mathcal{C}$. Let

$$X \stackrel{\text{def}}{=} \sum_{\mathbf{e} \neq \mathbf{e}': \mathbf{H}(\mathbf{e}-\mathbf{e}')^{\top}=0} \pi_{\mathbf{e}} \pi_{\mathbf{e}'}.$$

The point of the probabilistic model where the parity-check matrix $\mathbf{H}$ is uniformly drawn at random is that for non-zero element $\mathbf{x} \in \mathbb{F}_q^n$ we have

$$\mathbb{P}_{\mathbf{H}}(\mathbf{x} \in \mathcal{C}) = \mathbb{P}_{\mathbf{H}}(\mathbf{H}\mathbf{x}^{\top} = \mathbf{0}) = \frac{1}{q^{n-k}}.$$

<footnote>$^{(3)}$ This notion is related to the notion of dual lattice or dual code. Indeed in the code case, if the density $|\mathcal{C}|/|\varepsilon|$ of a linear code $\mathcal{C}$ is $\delta$, the density of the dual code $\mathcal{C}^\perp$ is $\delta^*$ since $|\mathcal{C}^\perp| = |\mathcal{C}^\perp \cdot |\mathcal{C}|| = |\varepsilon|/|\mathcal{C}| \cdot |\mathcal{C}| = \frac{1}{\delta}|\varepsilon|$. Similarly, for $\mathbb{R}^n$ if the density of a lattice $\Lambda$ is $\delta$ the density of the dual lattice $\Lambda^* \stackrel{\text{def}}{=} \{\mathbf{y} \in \mathbb{R}^n : \langle \mathbf{x}, \mathbf{y} \rangle > Z, \forall \mathbf{x} \in \Lambda\}$ is $\frac{1}{\delta} = \delta^*$.</footnote>
From this we deduce

$$
\begin{align*}
\mathbb{E}_{\mathbf{H}}(X) &= \sum_{e \neq e'} \pi_e \pi_{e'} \mathbb{P}_{\mathbf{H}}((\mathbf{e} - \mathbf{e}') \in \mathcal{C}) \\
&= \sum_{e \neq e'} \frac{\pi_e \pi_{e'}}{q^{n-k}} \\
&\le \sum_{e, e'} \frac{\pi_e \pi_{e'}}{q^{n-k}} \\
&= \frac{\langle \pi | \mathbf{1} \rangle^2}{q^{n-k}}.
\end{align*}
$$

From this inequality we conclude the proof.

<figure><img src="image_6.png" /></figure>

With the help of these two lemmas, we can upper-bound the
probability for Z to be bigger than $q^k(1 + \eta)$ for any $\eta > 0$
and prove Lemma 3.7, that we recall:

Lemma 3.7: Let $\eta > 0$. We have:

$$
\mathbb{P}_{\mathbf{G}}(Z > q^k(1 + \eta)) \le \frac{1}{\eta} \frac{\langle \pi | \mathbf{1} \rangle^2}{q^{n-k}} + O\left(q^{-\min(k,n-k)}\right).
$$

Proof: We take back the notation from the proof of Lemma 3.6. We have

$$
\begin{align*}
\mathbb{P}_{\mathbf{G}}(Z > q^k(1 + \eta)) &= \mathbb{P}_{\mathbf{G}}(X > \eta) \\
&\le \mathbb{P}_{\mathbf{H}}(X > \eta) + O\left(q^{-\min(k,n-k)}\right) \quad \text{(by Lemma A.2)} \\
&\le \frac{1}{\eta} \mathbb{E}_{\mathbf{H}}(X) + O\left(q^{-\min(k,n-k)}\right) \quad \text{(Markov inequality)} \\
&\le \frac{1}{\eta} \frac{\langle \pi | \mathbf{1} \rangle^2}{q^{n-k}} + O\left(q^{-\min(k,n-k)}\right)
\end{align*}
$$

which concludes the proof.

<figure><img src="image_7.png" /></figure>

We have

$$
\begin{align*}
\widehat{|\mathbf{1}_{c+e}|} &= \sum_{\mathbf{c} \in \mathcal{C}} \frac{1}{\sqrt{q^n}} \sum_{\mathbf{y} \in \mathbb{F}_q^n} \chi_{\mathbf{y}}(\mathbf{c} + \mathbf{e}) |\mathbf{y}| \\
&= \frac{1}{\sqrt{q^n}} \sum_{\mathbf{y} \in \mathbb{F}_q^n} \chi_{\mathbf{y}}(\mathbf{e}) \sum_{\mathbf{c} \in \mathcal{C}} \chi_{\mathbf{y}}(\mathbf{c}) |\mathbf{y}| \\
&= \frac{q^k}{\sqrt{q^n}} \sum_{\mathbf{c}^{\perp} \in \mathcal{C}^{\perp}} \chi_{\mathbf{c}^{\perp}}(\mathbf{e}) |\mathbf{c}^{\perp}| \tag{30}
\end{align*}
$$

since $\sum_{\mathbf{c} \in \mathcal{C}} \chi_{\mathbf{y}}(\mathbf{c}) = 0$ if $\mathbf{y} \notin \mathcal{C}^{\perp}$ and $q^k$ otherwise. Therefore

$$
\begin{align*}
\widehat{\left| \sum_{e \in \mathbb{F}_q^n} \pi_e |\mathbf{c} + \mathbf{e}| \right|} &= \sum_{e \in \mathbb{F}_q^n} \pi_e |\mathbf{1}_{c+e}| \\
&= \frac{q^k}{\sqrt{q^n}} \sum_{e \in \mathbb{F}_q^n} \pi_e \sum_{\mathbf{c}^{\perp} \in \mathcal{C}^{\perp}} \chi_{\mathbf{c}^{\perp}}(e) |\mathbf{c}^{\perp}| \\
&= q^k \sum_{\mathbf{c}^{\perp} \in \mathcal{C}^{\perp}} \frac{1}{\sqrt{q^n}} \sum_{e \in \mathbb{F}_q^n} \pi_e \chi_{\mathbf{c}^{\perp}}(e) |\mathbf{c}^{\perp}| \\
&= q^k \sum_{\mathbf{c}^{\perp} \in \mathcal{C}^{\perp}} \hat{\pi}_{\mathbf{c}^{\perp}} |\mathbf{c}^{\perp}|.
\end{align*}
$$

It follows that

$$
\widehat{|\psi_{\text{ideal}}|} = \frac{q^k}{\sqrt{Z}} \sum_{\mathbf{c}^{\perp} \in \mathcal{C}^{\perp}} \hat{\pi}_{\mathbf{c}^{\perp}} |\mathbf{0}_n| |\mathbf{c}^{\perp}|.
$$

After measurement we get a state $|0_n\rangle|\mathbf{c}^{\perp}\rangle$ with probability $\frac{q^{2k}}{Z}|\hat{f}(|\mathbf{c}^{\perp}|)|^2$. By summing over all $\mathbf{c}^{\perp} \in \mathcal{C}^{\perp}$ of weight $u$, we conclude the proof.

<figure><img src="image_8.png" /></figure>

B. Step 2: Proof of Lemma 3.8

If we apply a QFT on the second register of $|\psi_{\text{ideal}}\rangle$ (given in Equation (11)), we obtain:

$$
\widehat{\psi_{\text{ideal}}} \stackrel{\text{def}}{=} (\mathbf{I} \otimes \text{QFT} \otimes \mathbf{I}) |\psi_{\text{ideal}}\rangle = \frac{q^k}{\sqrt{Z}} \sum_{\mathbf{c}^{\perp} \in \mathcal{C}^{\perp}} \hat{\pi}_{\mathbf{c}^{\perp}} |\mathbf{0}_n\rangle |\mathbf{c}^{\perp}\rangle,
$$

where $|\widehat{\pi}\rangle = \sum_{e \in \mathbb{F}_q^n} \hat{\pi}_e |e\rangle$ is the QFT of $|\pi\rangle$. We use this
remark to prove Lemma 3.8, that we recall:

Lemma 3.8: If the Fourier transform is radially preserving, meaning that it transforms a radial function into a radial function, then after measuring $|\widehat{\psi}_{\text{ideal}}\rangle$ we obtain a state $|0_n\rangle|\mathbf{c}^{\perp}\rangle$ with $\mathbf{c}^{\perp} \in \mathcal{C}^{\perp}$ of weight $u$ with probability $\frac{q^{2k}}{Z}N_u^{\perp}|\hat{f}(u)|^2$ where $\hat{f}(u) \stackrel{\text{def}}{=} \hat{\pi}_e$ for an arbitrary $e$ of weight $u$ and $N_u^{\perp}$ is the number of codewords of weight $u$ in $\mathcal{C}^{\perp}$.

Proof: For $e \in \mathbb{F}_q^n$, let

$$
|\mathbf{1}_{c+e}\rangle \stackrel{\text{def}}{=} \sum_{c \in \mathcal{C}} |c + e\rangle.
$$

C. Step 3 : Proof of Proposition 3.9

We first need for this a good estimation of $|\widehat{\psi_{\text{ideal}}}|$'s amplitudes.
This will be a consequence of the following lemma.

Lemma A.3: If the generator matrix **G** of a code **C** is chosen uniformly at random in $\mathbb{F}_q^{k \times n}$ then the number $N_u^{\perp}$ of codewords of weight **u** in $\mathcal{C}^{\perp}$ satisfies

$$
\mathbb{P}_{\mathbf{G}} \left( \left| N_u^{\perp} - \frac{S_u}{q^k} \right| \ge \left( \frac{S_u}{q^k} \right)^{3/4} \right) \le (q-1) \sqrt{\frac{q^k}{S_u}}.
$$

Proof: Let $\mathbb{1}_x$ be the indicator function of the event $\text{"x } \in \mathcal{C}^{\perp}$.
By definition,

$$
N_u^{\perp} = \sum_{\mathbf{x} \in \mathcal{S}_u} \mathbb{1}_{\mathbf{x}}. \qquad (31)
$$

We have $\mathbb{E}(\mathbb{1}_{\mathbf{x}}) = \mathbb{P}_{\mathbf{G}}(\mathbf{x} \in \mathcal{C}^{\perp}) = \frac{1}{q^k}$, implying that
$\mathbb{E}(N_u^{\perp}) = \frac{S_u}{q^k}$. By using Bienaymé-Tchebychev's inequality,
we obtain:

$$
\begin{align}
& \mathbb{P}\left(\left|N_u^{\perp} - \frac{S_u}{q^k}\right| \ge a\right) \nonumber \\
&\le \frac{\mathrm{Var}(N_u^{\perp})}{a^2} \nonumber \\
&= \frac{1}{a^2} \left( \sum_{\mathbf{x} \in \mathcal{S}_u} \mathrm{Var}(\mathbf{1}_{\mathbf{x}}) + \sum_{\substack{\mathbf{x}, \mathbf{y} \in \mathcal{S}_u \\ \mathbf{x} \neq \mathbf{y}}} \mathbb{E}(\mathbf{1}_{\mathbf{x}}\mathbf{1}_{\mathbf{y}}) - \mathbb{E}(\mathbf{1}_{\mathbf{x}})\mathbb{E}(\mathbf{1}_{\mathbf{y}}) \right) \nonumber \\
&\le \frac{1}{a^2} \left( \sum_{\mathbf{x} \in \mathcal{S}_u} \mathbb{E}(\mathbf{1}_{\mathbf{x}}) + \sum_{\substack{\mathbf{x}, \mathbf{y} \in \mathcal{S}_u \\ \mathbf{x} \neq \mathbf{y}}} \mathbb{E}(\mathbf{1}_{\mathbf{x}}\mathbf{1}_{\mathbf{y}}) - \mathbb{E}(\mathbf{1}_{\mathbf{x}})\mathbb{E}(\mathbf{1}_{\mathbf{y}}) \right) \nonumber \\
&= \frac{1}{a^2} \left( \frac{S_u}{q^k} + \sum_{\substack{\mathbf{x}, \mathbf{y} \in \mathcal{S}_u \\ \mathbf{x} \neq \mathbf{y}}} \mathbb{E}(\mathbf{1}_{\mathbf{x}}\mathbf{1}_{\mathbf{y}}) - \mathbb{E}(\mathbf{1}_{\mathbf{x}})\mathbb{E}(\mathbf{1}_{\mathbf{y}}) \right) \tag{32}
\end{align}
$$

where we used that $\mathrm{Var}(\mathbf{1}_x) \le \mathbb{E}(\mathbf{1}_x^2) = \mathbb{E}(\mathbf{1}_x)$. Let us now
upper-bound the second term of the inequality. It is readily
verified that:

$$
\mathbb{E}(\mathbf{1}_{\mathbf{x}}\mathbf{1}_{\mathbf{y}}) = \begin{cases} 1/q^k & \text{if } \mathbf{x} \text{ and } \mathbf{y} \text{ are colinear,} \\ 1/q^{2k} & \text{otherwise.} \end{cases}
$$

Therefore, we deduce that:

$$
\begin{align*}
\sum_{\substack{\mathbf{x}, \mathbf{y} \in \mathcal{S}_u \\ \mathbf{x} \neq \mathbf{y}}} \mathbb{E}(\mathbf{1}_{\mathbf{x}} \mathbf{1}_{\mathbf{y}}) - \mathbb{E}(\mathbf{1}_{\mathbf{x}}) \mathbb{E}(\mathbf{1}_{\mathbf{y}}) &= \sum_{\mathbf{x} \in \mathcal{S}_u} \sum_{\substack{\mathbf{y} \in \mathcal{S}_u \\ \mathbf{x} \neq \mathbf{y}}} \frac{1}{q^k} - \frac{1}{q^{2k}} \\
&\le \sum_{\mathbf{x} \in \mathcal{S}_u} \sum_{\substack{\mathbf{y} \in \mathcal{S}_u \\ \mathbf{x} \neq \mathbf{y}}} \frac{1}{q^k} \\
&\le \frac{(q-2)S_u}{q^k} \tag{33}
\end{align*}
$$

It gives by plugging (33) in (32):

$$
\mathbb{P}_{\mathbf{G}} \left( \left| N_u^{\perp} - \frac{S_u}{q^k} \right| \ge a \right) \le \frac{1}{a^2} \left( \frac{S_u}{q^k} + \frac{(q-2)S_u}{q^k} \right) \\
= \frac{(q-1)S_u}{a^2 q^k}
$$

which concludes the proof by choosing $a = \left(\frac{S_u}{q^k}\right)^{3/4}$. $\blacksquare$

We are ready to prove Proposition 3.9 which we now recall:

Proposition 3.9: Under the assumptions made in Theorem 3.1, the probability of obtaining a codeword $\mathbf{c}^{\perp} \in \mathcal{C}^{\perp}$ of weight $u \in \mathcal{W}$ when measuring $|\psi_{\text{ideal}}\rangle$ is $\ge 1 - \alpha(\pi)$ for a proportion $\ge 1 - \beta(\pi)$ of matrices $\mathbf{G}$, where:

$$
\alpha(\pi) \stackrel{\text{def}}{=} \sum_{u \in \mathcal{W}} \left(\frac{q^k}{S_u}\right)^{1/4} + \sqrt{\frac{\langle \pi | \mathbf{1} \rangle^2}{q^{n-k}}} - 2^{-\Omega(n)},
$$

$$
\beta(\pi) \stackrel{\text{def}}{=} (q-1) \sum_{u \in \mathcal{W}} \sqrt{\frac{q^k}{S_u}} + \sqrt{\frac{\langle \pi | \mathbf{1} \rangle^2}{q^{n-k}}} + O\left(q^{-\min(k,n-k)}\right).
$$

*Proof:* Let $\mathcal{Q}$ be the quantum algorithm starting from $|\psi\rangle$
which computes $(\mathbf{I} \otimes \text{QFT} \otimes \mathbf{I}) |\psi\rangle$. This algorithm succeeds

when measuring a dual codeword $\mathbf{c}^{\perp} \in \mathcal{C}^{\perp}$ of weight $u \in \mathcal{W}$.
When starting with $|\psi_{\text{ideal}}\rangle$, the probability of success of $\mathcal{Q}$ is
equal to $\sum_{u \in \mathcal{W}} \frac{q^{2k} N_u^{\perp}}{Z} |\hat{f}(u)|^2$ by Lemma 3.8. Let

$$
\mathcal{B} \stackrel{\text{def}}{=} \left\{ \mathbf{G} \in \mathbb{F}_q^{k \times n} : Z > q^k \left( 1 + \sqrt{\frac{\langle \pi | \mathbf{1} \rangle^2}{q^{n-k}}} \right) \right\} \quad \text{and} \\
\mathcal{E}_u \stackrel{\text{def}}{=} \left\{ \mathbf{G} \in \mathbb{F}_q^{k \times n} : \left| N_u^{\perp} - \frac{S_u}{q^k} \right| \ge \left( \frac{S_u}{q^k} \right)^{3/4} \right\}.
$$

By Lemmas 3.7 and A.3 we have that

$$
\mathbb{P} \left( \mathbf{G} \in \mathcal{B} \cup \bigcup_{u \in \mathcal{W}} \mathcal{E}_u \right) \le \beta(\pi) = (q-1) \sum_{u \in \mathcal{W}} \sqrt{\frac{q^k}{S_u}} \\
+ \sqrt{\frac{\langle \pi | \mathbf{1} \rangle^2}{q^{n-k}}} + O \left( q^{-\min(k,n-k)} \right).
$$

Therefore, for a proportion $\ge 1 - \beta(\pi)$ of codes (over matrices
**G**):

(i) $Z \le q^k \left(1 + \sqrt{\frac{\langle \pi | \mathbf{1} \rangle^2}{q^{n-k}}}\right)$ and $Z \ge q^k$ (this is true for any
$\mathbf{G}$ as $\pi_{\mathbf{e}} \ge 0$ for any $\mathbf{e}$),

(ii) for all $u$ in $\mathcal{W}$, $\left| \frac{q^k N_u^{\perp}}{S_u} - 1 \right| \le \left( \frac{q^k}{S_u} \right)^{1/4}$.

We deduce that for a proportion $\ge 1 - \beta(\pi)$ of codes and for all $u$ in $\mathcal{W}$:

$$
\frac{1 - \left( \frac{q^k}{S_u} \right)^{1/4}}{1 + \sqrt{\frac{\langle \pi | \mathbf{1} \rangle^2}{q^{n-k}}}} \le \frac{q^k N_u^{\perp}}{S_u Z} \le 1 + \left( \frac{q^k}{S_u} \right)^{1/4}.
$$

This implies that for a proportion $\ge 1 - \beta(\pi)$ of codes and for all $u$ in $\mathcal{W}$ we have that

$$
\frac{1 - \sum_{u \in \mathcal{W}} \left( \frac{q^k}{S_u} \right)^{1/4}}{1 + \sqrt{\frac{\langle \pi | \mathbf{1} \rangle^2}{q^{n-k}}}} \le \frac{q^{2k} N_u^{\perp}}{S_u Z} \le 1 + \sum_{u \in \mathcal{W}} \left( \frac{q^k}{S_u} \right)^{1/4},
$$

from which we deduce that under the same conditions we also
have

$$
S_u |\hat{f}(u)|^2 \left( \frac{1 - \sum_{u \in \mathcal{W}} \left( \frac{q^k}{S_u} \right)^{1/4}}{1 + \sqrt{\frac{\langle \pi | \mathbf{1} \rangle^2}{q^{n-k}}}} \right) \\
\le \sum_{u \in \mathcal{W}} \frac{q^{2k} N_u^{\perp}}{Z} |\hat{f}(u)|^2 \\
\le S_u |\hat{f}(u)|^2 \left( 1 + \sum_{u \in \mathcal{W}} \left( \frac{q^k}{S_u} \right)^{1/4} \right). \quad (34)
$$

Now,

$$
\frac{1 - \sum_{u \in \mathcal{W}} \left( \frac{q^k}{S_u} \right)^{1/4}}{1 + \sqrt{\frac{\langle \pi | \mathbf{1} \rangle^2}{q^{n-k}}}} \ge 1 - \sum_{u \in \mathcal{W}} \left( \frac{q^k}{S_u} \right)^{1/4} - \sqrt{\frac{\langle \pi | \mathbf{1} \rangle^2}{q^{n-k}}}
$$
Therefore, by plugging this in Equation (34) we have for a
proportion $\ge 1 - \beta(\pi)$ of codes:

$$
\begin{equation} \tag{35}
\begin{aligned}
\left(1 - \delta\right) \sum_{u \in \mathcal{W}} S_u |\hat{f}(u)|^2 &\le \sum_{u \in \mathcal{W}} \frac{q^{2k} N_u^{\perp}}{Z} |\hat{f}(u)|^2 \\
&\le (1 + \delta) \sum_{u \in \mathcal{W}} S_u |\hat{f}(u)|^2
\end{aligned}
\end{equation}
$$

where $\delta \stackrel{\text{def}}{=} \sum_{u \in \mathcal{W}} \left(\frac{q^k}{S_u}\right)^{1/4} + \sqrt{\frac{\langle \pi | \mathbf{1} \rangle^2}{q^{n-k}}}$. We finish the proof by applying Lemma 3.8: we namely know that after measuring the state obtained by $\mathcal{Q}$, we obtain a dual codeword of weight $u$ in $\mathcal{W}$ with probability $\sum_{u \in \mathcal{W}} \frac{q^{2k} N_u^{\perp}}{Z} |\hat{f}(u)|^2$. ■

APPENDIX B
PROOF OF THEOREM 3.19

A. Step 1 (choice of $|\pi\rangle$): Proofs of Lemmas 3.21 and 3.22

The following lemma will be very helpful in what follows.

Lemma B.1: [40, §9.3, Lem. 9.3.2] Let $V$ be a subspace of dimension $s$, then there are exactly $q^{(t-\ell)(s-\ell)} \begin{bmatrix} n-s \\ t-\ell \end{bmatrix}_q \begin{bmatrix} s \\ \ell \end{bmatrix}_q$ subspaces $W$ of dimension $t$ such that $\dim(V \cap W) = \ell$.

Let us now recall Lemma 3.21:

Lemma 3.21: $|\pi\rangle$ is radial, i.e., we may write $|\pi\rangle$ as

$$
|\pi\rangle = \sum_{\mathbf{E} \in \mathbb{F}_q^{m \times n}: \quad |\mathbf{E}| \le t} \pi_{\mathbf{E}} |\mathbf{E}\rangle
$$

with $|\mathbf{E}\rangle \stackrel{\text{def}}{=} |\mathbf{E}_1\rangle \otimes \dots \otimes |\mathbf{E}_m\rangle$ where the $\mathbf{E}_i$'s denote the rows of $\mathbf{E}$ and $\pi_{\mathbf{E}} = f(|\mathbf{E}|)$ where

$$
f(u) = \begin{cases} \frac{\begin{bmatrix} n-u \\ t-u \end{bmatrix}_q}{\sqrt{q^{mt}N}} & \text{if } u \le t, \\ 0 & \text{otherwise.} \end{cases}
$$

Proof: Let $U$ be the $\mathbb{F}_q$-space generated by the $\mathbf{E}_i$'s. We denote by $u$ the dimension of $U$. We have

$$
\pi_{\mathbf{E}} = \frac{1}{\sqrt{q^{mt}N}} \# \left\{ V \le \mathbb{F}_q^n : \dim V = t \text{ and } U \subseteq V \right\} \\
= \frac{\begin{bmatrix} n-u \\ t-u \end{bmatrix}_q}{\sqrt{q^{mt}N}},
$$

where we used Lemma B.1 for the last equality. It concludes
the proof.

■

Another asymptotic expression for $N$ and an estimate for $p_t$ are given by:

Lemma 3.22: We have:

$$
N = \Theta \left( \begin{bmatrix} n \\ t \end{bmatrix}_q \right) \quad \text{and} \quad p_t = \Theta(1).
$$

This lemma will be a consequence of the following lemmas.

Lemma B.2: For any $V, W \subseteq \mathbb{F}_q^n$ such that $V \neq W$ and $\dim V = \dim W = t$ we have,

$$
\langle \pi_V | \pi_W \rangle = q^{m(\dim(V \cap W) - t)}.
$$

*Proof:* Recall that,

$$
|\pi_U\rangle = \left( \frac{1}{\sqrt{q^{\dim U}}} \sum_{\mathbf{u} \in U} |\mathbf{u}\rangle \right)^{\otimes m}
$$

Therefore we have,

$$
\langle \pi_V | \pi_W \rangle = \left( \frac{1}{q^t} \sum_{\mathbf{v} \in V} \sum_{\mathbf{w} \in W} \langle \mathbf{v} | \mathbf{w} \rangle \right)^m = \left( \frac{1}{q^t} \mathfrak{H}(V \cap W) \right)^m
$$

which concludes the proof.

Lemma B.3: We have,

$$
\sum_{\substack{V \le \mathbb{F}_q^n \\ \dim V = t}} \sum_{\substack{W \le \mathbb{F}_q^n \\ \dim W = t}} \langle \pi_V | \pi_W \rangle = O \left( \begin{bmatrix} n \\ t \end{bmatrix}_q \right).
$$

Proof: We have

$$
\begin{align*}
\sum_{\substack{V \le \mathbb{F}_q^n \\ \dim V = t}} \sum_{\substack{W \le \mathbb{F}_q^n \\ \dim W = t}} \langle \pi_V | \pi_W \rangle &= \sum_{\substack{V \le \mathbb{F}_q^n \\ \dim V = t}} \sum_{\substack{W \le \mathbb{F}_q^n \\ \dim W = t}} q^{m(\dim(V \cap W) - t)} \\
&= \sum_{\substack{V \le \mathbb{F}_q^n \\ \dim V = t}} \sum_{\substack{\ell = 0 \\ \dim W = t}}^{t-1} \frac{1}{q^{m(t-\ell)}} \\
&= \sum_{\substack{V \le \mathbb{F}_q^n \\ \dim V = t}} \sum_{\substack{\ell = 0 \\ \dim(W \cap V) = \ell}}^{t-1} \frac{1}{q^{m(t-\ell)}} q^{(t-\ell)^2} \begin{bmatrix} t \\ \ell \end{bmatrix}_q \begin{bmatrix} n-t \\ t-\ell \end{bmatrix}_q \tag{36} \\
&= \begin{bmatrix} n \\ t \end{bmatrix}_q \sum_{\ell=0}^{t-1} q^{(t-\ell-m)(t-\ell)} \begin{bmatrix} t \\ \ell \end{bmatrix}_q \begin{bmatrix} n-t \\ t-\ell \end{bmatrix}_q
\end{align*}
$$

where in Equation (36) we used Lemma B.1. Now, there exists
some constant $c > 0$ such that:

$$
\begin{bmatrix} n \\ \ell \end{bmatrix}_q \le c q^{\ell(n-\ell)}.
$$

Then, for some constant $C > 0$,

$$
\begin{align*}
& \sum_{\substack{V \le \mathbb{F}_q^n \\ \dim V = t}} \sum_{\substack{W \le \mathbb{F}_q^n \\ \dim W = t}} \langle \pi_V | \pi_W \rangle \\
& \le C \begin{bmatrix} n \\ t \end{bmatrix}_q \sum_{\ell=0}^{t-1} q^{(t-\ell-m)(t-\ell) + \ell(t-\ell) + (t-\ell)(n-2t+\ell)} \\
& = C \begin{bmatrix} n \\ t \end{bmatrix}_q \sum_{\ell=0}^{t-1} q^{(t-\ell)(t-\ell-m+\ell+n-2t+\ell)} \\
& = C \begin{bmatrix} n \\ t \end{bmatrix}_q \sum_{\ell=0}^{t-1} q^{(t-\ell)(-t+\ell-m+n)} \\
& \le C \begin{bmatrix} n \\ t \end{bmatrix}_q \sum_{\ell=0}^{t-1} q^{-(t-\ell)^2} \quad (\text{since } n \le m)
\end{align*}
$$

which concludes the proof.

We are now ready to prove Lemma 3.22.
**Proof of Lemma 3.22:** By definition of $N$ we have:

$$
\begin{aligned}
N &= \left\| \sum_{\substack{V \le \mathbb{F}_q^n \\ \dim V = t}} \pi_V \right\|^2 \\
&= \sum_{\substack{V \le \mathbb{F}_q^n \\ \dim V = t}} \|\pi_V\|^2 + \sum_{\substack{V \le \mathbb{F}_q^n \\ \dim V = t}} \sum_{\substack{W \le \mathbb{F}_q^n \\ W \neq V}} \langle \pi_V, \pi_W \rangle
\end{aligned}
$$

and by definition of $\pi_V$:

$$
\sum_{\substack{V \le \mathbb{F}_q^n \\ \dim V = t}} \|\pi_V\|^2 = \left[\begin{matrix} n \\ t \end{matrix}\right]_q \left(\frac{1}{q^t} \sum_{v \in V} 1\right)^m = \left[\begin{matrix} n \\ t \end{matrix}\right]_q
$$

This concludes the proof that $N = \begin{bmatrix} n \\ t \end{bmatrix}_q$ by using Lemma B.3.

Now, by definition of $p_t$, we have:

$$
\begin{aligned}
p_t &= S_t f(t)^2 \\
&= S_t \frac{\begin{bmatrix} n-t \\ 0 \end{bmatrix}_q^2}{q^{mt} N} \quad (\text{by Lemma 3.21}) \\
&= \frac{S_t}{\Theta(S_t)} \quad (\text{by using the estimate for } N \text{ and Eq. (5)})
\end{aligned}
$$

allowing us to conclude that $p_t = \Theta(1)$.

## B. Step 3: Proofs of Lemmas 3.25 and 3.26

Recall Lemma 3.25 first:

Lemma 3.25: We have,

$$ \frac{S_t}{q^{mn-k}} = q^{-\Omega(n)} \quad \text{and} \quad \frac{\langle \pi | \mathbf{1} \rangle^2}{q^{mn-k}} = q^{-\Omega(n)}. $$

**Proof:** In order to prove the first equation, note that $d_{GV}(m, n, k)$ is defined such that $\frac{S_{d_{GV}}}{q^{mn-k}} \le 1$. From this and Equation (6) we deduce

$$
\frac{S_{d_{GV}-1}}{q^{mn-k}} = \frac{S_{d_{GV}-1}}{S_{d_{GV}}} \frac{S_{d_{GV}}}{q^{mn-k}} \\
\le \Theta \left( q^{-(m+n-2d_{GV}-1)} \right) = \Theta \left( q^{-\Omega(n)} \right)
$$

where the last equality follows from the fact that (see for instance [41])

$$ d_{GV}(m, n, k) = \frac{m + n - \sqrt{(m-n)^2 + 4k}}{2} (1 + o(1)). \quad (37) $$

Now, for the second equation, we have

$$
\begin{aligned}
\frac{\langle \pi | \mathbf{1} \rangle^2}{q^{mn}} &= |\hat{f}(0)|^2 \\
&= \frac{\begin{bmatrix} n \\ n-t \end{bmatrix}_q^2}{q^{m(n-t)} N} \quad (\text{by Lemma 3.24}) \\
&= \Theta \left( \frac{q^{mt} \begin{bmatrix} n \\ t \end{bmatrix}_q}{q^{mn}} \right) \quad (\text{By Lemma (3.22)}) \\
&= \Theta \left( \frac{S_t}{q^{mn}} \right) \quad (\text{By Equations (4) and (5)})
\end{aligned}
$$

Thanks to the first equation, we complete the proof.

The second lemma we need is recalled here:

**Lemma 3.26:** For any $\eta > 0$, we have $\forall u \in [(1-\eta)n-t, n-t]$

$$ \frac{q^k}{S_u} = q^{-\Omega(n)} $$

and,

$$ \sum_{u \in [(1-\eta)n-t, n-t]} S_u |\hat{f}(u)|^2 = 1 - q^{-\Omega(n)}. $$

**Proof:** The first equation can be proved in the same way as Lemma 3.25. For the second identity, first notice (by Lemma 3.24) that

$$ \sum_{u \in [(n-t-\eta)n, n-t]} S_u |\hat{f}(u)|^2 = 1 - \sum_{u < n-t-\eta n} S_u |\hat{f}(u)|^2. $$

Now, we have the following computation:

$$
\begin{aligned}
& \sum_{u < n-t-\eta n} S_u |\hat{f}(u)|^2 \\
&= \sum_{u < n-t-\eta n} S_u \frac{\begin{bmatrix} n-u \\ n-u-t \end{bmatrix}_q^2}{N q^{m(n-t)}} \quad (\text{by Lemma 3.25}) \\
&= \Theta \left( \sum_{u < n-t-\eta n} S_u \frac{\begin{bmatrix} n-u \\ n \\ t \end{bmatrix}_q}{q^{m(n-t)}} \right) \quad (\text{by Lemma 3.22}) \\
&= \Theta \left( \sum_{u < n-t-\eta n} q^{u(m+n-u)} \frac{q^{2(n-t-u)t}}{q^{t(n-t)} q^{m(n-t)}} \right) \\
&= \Theta \left( q^{\max_{u < n-t-\eta n} u(m+n-u-2t)} q^{(t-m)(n-t)} \right)
\end{aligned}
$$

where in the last equality we used Equations (4) and (5).

Therefore,

$$
\begin{aligned}
& \sum_{u < n-t-\eta n} S_u |\hat{f}(u)|^2 \\
&= \Theta \left( \sum_{u < n-t-\eta n} q^{u(m+n-u)} \frac{q^{2(n-t-u)t}}{q^{t(n-t)} q^{m(n-t)}} \right) \\
&= \Theta \left( q^{\max_{u < n-t-\eta n} u(m+n-u-2t)} q^{(t-m)(n-t)} \right)
\end{aligned}
$$

Let $g(u) \stackrel{\text{def}}{=} u(m+n-u-2t)$. Then, $g'(u) = m+n-2(t+u) \ge 0$ as $t+u \le n \le m$. Therefore, $g$ is an increasing function and by setting $u = n-t-\eta n$, we obtain

$$
\begin{aligned}
\sum_{u < n-t-\eta n} S_u |\hat{f}(u)|^2 &\le n \Theta \left( q^{(n-t-\eta n)(m-t+\eta n)} q^{(t-m)(n-t)} \right) \\
&= n \Theta \left( q^{(n-t)(t-m+m-t+\eta n)} q^{-\eta n(m-t+\eta n)} \right) \\
&= n \Theta \left( q^{-\eta n(m-t+\eta n-n+t)} \right) \\
&= n \Theta \left( q^{-\eta n(m-n+\eta n)} \right) \\
&= q^{-\Omega(n)}
\end{aligned}
$$

as $n \le m$ by assumption. It concludes the proof.
REFERENCES

[1] R. J. McEliece, *A Public-Key System Based on Algebraic Coding Theory*. Jet Propulsion Lab, 1978, pp. 114–116, dSN Progress Report 44.

[2] M. Alekhnovich, "More on average case vs approximation complexity," *Computational Complexity*, vol. 20, no. 4, pp. 755–786, 2011. [Online]. Available: http://dx.doi.org/10.1007/s00037-011-0029-x

[3] R. Misoczki, J.-P. Tillich, N. Sendrier, and P. S. L. M. Barreto, "MDPSC McEliece: New McEliece variants from moderate density parity-check codes," 2012. [Online]. Available: http://eprint.iacr.org/2012/409

[4] J. Stern, "A new identification scheme based on syndrome decoding," in *Advances in Cryptology - CRYPTO'93*, ser. LNCS, D. Stinson, Ed., vol. 773. Springer, 1993, pp. 13–21.

[5] J.-B. Fischer and J. Stern, "An efficient pseudo-random generator provably as secure as syndrome decoding," in *Advances in Cryptology - EUROCRYPT'96*, ser. LNCS, U. Maurer, Ed., vol. 1070. Springer, 1996, pp. 245–255.

[6] B. Applebaum, N. Haramaty, Y. Ishai, E. Kushilevitz, and V. Vaikuntanathan, "Low-complexity cryptographic hash functions," in *ITCS*, ser. LIPIcs, vol. 67. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, pp. 7:1–7:31.

[7] Z. Brakerski, V. Lyubashevsky, V. Vaikuntanathan, and D. Wichs, "Worst-case hardness for LPN and cryptographic hashing via code smoothing," in *Advances in Cryptology - EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques*, Darmstadt, Germany, May 19-23, 2019, *Proceedings, Part III*, ser. LNCS, Y. Ishai and V. Rijmen, Eds., vol. 11478. Springer, 2019, pp. 619–635. [Online]. Available: https://doi.org/10.1007/978-3-030-17659-4_21

[8] Y. Yu, J. Zhang, J. Weng, C. Guo, and X. Li, "Collision resistant hashing from sub-exponential learning parity with noise," in *ASIACRYPT (2)*, ser. Lecture Notes in Computer Science, vol. 11922. Springer, 2019, pp. 3–24.

[9] E. Prange, "The use of information sets in decoding cyclic codes," *IRE Transactions on Information Theory*, vol. 8, no. 5, pp. 5–9, 1962. [Online]. Available: http://dx.doi.org/10.1109/TIT.1962.1057777

[10] J. Stern, "A method for finding codewords of small weight," in *Coding Theory and Applications*, ser. LNCS, G. D. Cohen and J. Wolfmann, Eds., vol. 388. Springer, 1988, pp. 106–113.

[11] I. Dumer, "Two decoding algorithms for linear codes," *Probl. Inf. Transm.*, vol. 25, no. 1, pp. 17–23, 1989.

[12] A. May, A. Meurer, and E. Thomae, "Decoding random linear codes in $O(2^{0.054n})$," in *Advances in Cryptology - ASIACRYPT 2011*, ser. LNCS, D. H. Lee and X. Wang, Eds., vol. 7073. Springer, 2011, pp. 107–124.

[13] A. Becker, A. Joux, A. May, and A. Meurer, "Decoding random binary linear codes in $2^{n/20}$: How $1+1=0$ improves information set decoding," in *Advances in Cryptology - EUROCRYPT 2012*, ser. LNCS. Springer, 2012.

[14] A. May and I. Ozerov, "On computing nearest neighbors with applications to decoding of binary linear codes," in *Advances in Cryptology - EUROCRYPT 2015*, ser. LNCS, E. Oswald and M. Fischlin, Eds., vol. 9056. Springer, 2015, pp. 203–228.

[15] L. Both and A. May, "Decoding linear codes with high error rate and its impact for LPN security," in *Post-Quantum Cryptography 2018*, ser. LNCS, T. Lange and R. Steinwandt, Eds., vol. 10786. Fort Lauderdale, FL, USA: Springer, Apr. 2018, pp. 25–46. [Online]. Available: https://doi.org/10.1007/978-3-319-79063-3_12

[16] K. Carrier, T. Debris-Alazard, C. Meyer-Hilfiger, and J. Tillich, "Statistical decoding 2.0: Reducing decoding to LPN," in *Advances in Cryptology - ASIACRYPT 2022*, ser. LNCS. Springer, 2022. [Online]. Available: https://eprint.iacr.org/2022/1000

[17] T. Debris-Alazard and N. Resch, "Worst and average case hardness of decoding via smoothing bounds," preprint, Dec. 2022, eprint.

[18] O. Regev, "On lattices, learning with errors, random linear codes, and cryptography," 2009, extended version of [19], dated May 2009. [Online]. Available: https://cims.nyu.edu/~regev/papers/qcrypt.pdf

[19] ——, "On lattices, learning with errors, random linear codes, and cryptography," in *Proceedings of the 37th Annual ACM Symposium on Theory of Computing*, Baltimore, MD, USA, May 22-24, 2005, 2005, pp. 84–93. [Online]. Available: http://doi.acm.org/10.1145/1060590.1060603

[20] D. R. Simon, "On the power of quantum computation," in *35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994*. IEEE Computer Society, 1994, pp. 116–123. [Online]. Available: https://doi.org/10.1109/SFCS.1994.365701

[21] P. W. Shor, "Algorithms for quantum computation: Discrete logarithms and factoring," in *FOCS*, S. Goldwasser, Ed., 1994, pp. 124–134.

[22] Y. Chen, Personal communication.

[23] Y. Chen and J. Vuong, "Quantum reduction from binary SIS to LPN and more via generalized lattice tail bounds," preprint.

[24] D. Augot, M. Finiasz, and N. Sendrier, "A family of fast syndrome based cryptographic hash functions," in *Ed Dawson, Serge Vaudenay (editors). Progress cryptology-Mycrypt First international conference on cryptology Malaysia, ISBN 978-3-540-28938-8*, ser. LNCS, vol. 3715. Kuala Lumpur, Malaysia: Springer, Sep. 2005, pp. 64–83. [Online]. Available: https://doi.org/10.1007/11554868_6

[25] N. Aragon, O. Blazy, J.-C. Deneuville, P. Gaborit, A. Hauteville, O. Ruatta, J.-P. Tillich, G. Zémor, C. Aguilar Melchor, S. Bettaieb, L. Bidoux, M. Bardet, and A. Otmani, "ROLLO (merger of Rank-Uroboros, LAKE and LOCKER)," Second round submission to the NIST post-quantum cryptography call, Mar. 2019. [Online]. Available: https://pqc-rollo.org

[26] C. Aguilar Melchor, N. Aragon, S. Bettaieb, L. Bidoux, O. Blazy, M. Bros, A. Couvreur, J.-C. Deneuville, P. Gaborit, G. Zémor, and A. Hauteville, "Rank quasi cyclic (RQC)," Second Round submission to NIST Post-Quantum Cryptography call, Apr. 2020. [Online]. Available: https://pqc-rqc.org

[27] E. Bellini, F. Caullery, P. Gaborit, M. Manzano, and V. Mateu, "Improved Veron identification and signature schemes in the rank metric," in *Proc. IEEE Int. Symposium Inf. Theory - ISIT 2019*, vol. abs/1903.10212. Paris, France: IEEE, Jul. 2019, pp. 1872–1876.

[28] E. Bellini, P. Gaborit, A. Hasikos, and V. Mateu, "Enhancing code based zero-knowledge proofs using rank metric," in *Cryptology and Network Security - 19th International Conference, CANS 2020, Vienna, Austria, December 14-16, 2020, Proceedings*, ser. Lecture Notes in Computer Science, S. Krenn, H. Shulman, and S. Vaudenay, Eds., vol. 12579. Springer, 2020, pp. 570–592. [Online]. Available: https://doi.org/10.1007/978-3-030-65411-5_28

[29] D. Stehlé, R. Steinfeld, K. Tanaka, and K. Xagawa, "Efficient public key encryption based on ideal lattices," in *Advances in Cryptology - ASIACRYPT 2009, 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, December 6-10, 2009. Proceedings*, ser. LNCS, M. Matsui, Ed., vol. 5912. Springer, 2009, pp. 617–635. [Online]. Available: https://doi.org/10.1007/978-3-642-10366-7_36

[30] M. A. Nielsen and I. L. Chuang, *Quantum Computation and Quantum Information* (10th Anniversary edition). Cambridge University Press, 2016. [Online]. Available: https://www.cambridge.org/de/academic/subjects/physics/quantum-physics-quantum-information-and-quantum-computation/quantum-computation-and-quantum-information-10th-anniversary-edition?format=HB

[31] A.-L. Horlemann-Trautmann and V. Weger, "Information set decoding in the lee metric with applications to cryptography," *Advances in Mathematics of Communications*, vol. 0, 2020, online version, to appear. [Online]. Available: http://aimsciences.org/article/id/ab4b64c6-5f2f-4014-b0f2-eacc9058c7cf

[32] Y. Chen, Q. Liu, and M. Zhandry, "Quantum algorithms for variants of average-case lattice problems via filtering," in *Advances in Cryptology - EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques*, Trondheim, Norway, May 30 - June 3, 2022, *Proceedings, Part III*, ser. LNCS, O. Dunkelman and S. Dziembowski, Eds., vol. 13277. Springer, 2022, pp. 372–401. [Online]. Available: https://doi.org/10.1007/978-3-031-07082-2_14

[33] G. D. J. Forney, "Codes on graphs: Normal realizations," *IEEE Trans. Inform. Theory*, vol. 47, no. 2, pp. 520–548, 2001. [Online]. Available: https://doi.org/10.1109/18.910573
[34] P. Delsarte, "Bounds for unrestricted codes," *Philips Res. Rep.*, vol. 27, pp. 272-289, 1972.

[35] P. Delsarte and V. I. Levenshtein, "Association schemes and coding theory," *IEEE Trans. Inform. Theory*, vol. 44, no. 6, pp. 2477-2504, 1998.

[36] R. J. McEliece, E. R. Rodemich, H. Rumsey, and L. R. Welch, "New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities," *IEEE Trans. Inform. Theory*, vol. 23, no. 2, pp. 157-166, 1977. [Online]. Available: https://doi.org/10.1109/TIT.1977.1055688

[37] V. I. Levenshtein, "Bounds for packings in $n$-dimensional Euclidean space," *Soviet Math. Dokl.*, vol. 20, pp. 417-421, 1979.

[38] H. Cohn and N. Elkies, "New upper bounds on sphere packings I," *Ann. of Math. (2)*, vol. 157, no. 2, pp. 689-714, 2003. [Online]. Available: http://www.jstor.org/stable/3597215

[39] T. Debris-Alazard, L. Ducas, N. Resch, and J. Tillich, "Smoothing codes and lattices: Systematic study and new bounds," *CoRR*, vol. abs/2205.10552, 2022. [Online]. Available: https://doi.org/10.48550/arXiv.2205.10552

[40] A. E. Brouwer, A. M. Cohen, and A. Neumaier, *Distance-Regular Graphs*, ser. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge / A Series of Modern Surveys in Mathematics. Springer Verlag Berlin Heidelberg, 1989, no. 18.

[41] P. Loidreau, "Properties of codes in rank metric," 2006. [Online]. Available: http://arxiv.org/abs/cs/0610057A

**Thomas Debris-Alazard** received a PhD degree in computer science from the Sorbonne Université at Inria Paris (France) in 2019. He has been hired at Inria as a *chargé de recherche* (junior researcher) in 2020. His research interests are code- and lattice-based cryptography.

**Maxime Remaud** prepares a PhD degree in computer science at Sorbonne Université under the supervision of Jean-Pierre Tillich. He is an engineer at Eviden Quantum Lab. His research interests are quantum algorithms.

**Jean-Pierre Tillich** received his Ph.D. from École Nationale Supérieure des Télécommunications (ENST), Paris, in 1994. From 1997 to 2003, he was Assistant Professor at the University Paris XI. He is now a senior researcher at the Institut de Recherche en Informatique et Automatique (INRIA), Paris, France. From 2009 to 2012 he was an Associate Editor for Coding Theory for the IEEE TRANSACTIONS ON INFORMATION THEORY. His research interests include classical and quantum coding theory, cryptography and graph theory.

<figure><img src="image_9.png" /><figcaption>Fig. 1: Range of values for $\tau$ as function of $R$.</figcaption></figure>