# An Efficient Quantum Decoder for Prime-Power Fields

Lior Eldar

###### Abstract

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

##  1 Introduction

Error correcting codes are linear subspaces of finite-field vector spaces that
allow to protect information against random, and even adversarial errors. The
problem of designing good, efficiently decodable, error-correcting codes is
notoriously difficult, and is in fact tantamount to an art form:
interestingly, it is difficult not because large minimal-distance codes are
hard to find (in fact typically a random code does have a large minimal
distance), but rather because it is hard to find such codes that are
simultaneously efficiently decodable.

The Maximum Likelihood Decoding (MLD) Problem of error correcting codes is
well known to be NP-hard since the work of Berlekamp, McEliece and Tilborg
[BMT78]. Formally, for the MLD problem we are given a ”syndrome”
$\mathbf{s}\in\mathbb{F}_{q}^{m}$, a ”parity check matrix” $\mathbf{A}$ and
are asked to find $\mathbf{e}\in\mathbb{F}_{q}^{n}$ of weight at most $w$ such
that $\mathbf{A}\mathbf{e}=\mathbf{s}$. In a related problem, called the
Nearest Codeword Problem (NCP) [Aro+97, Reg03], we are given a target vector
$\mathbf{t}$, a generator matrix $\mathbf{A}$ and are asked to find the
closest codeword to $\mathbf{t}$, namely $\mathbf{s}$ such that
$\mathbf{A}\mathbf{s}$ is closest to $\mathbf{t}$, provided that this distance
is at most $w$. This problem too, is known to be NP-hard even to sub-
polynomial approximation factors [Aro+97] under reasonable complexity
assumptions.

###  1.1 Defining BNCP

The NCP problem is analogous to the closest vector problem (CVP) defined on
Euclidean lattices, which is also notoriously hard (see e.g. [Din+03]). Yet,
as is often the case in error-correcting scenarios where the error has bounded
length, and similarly to the MLD problem, one can consider a bounded error
variant of NCP which we call here the Bounded NCP, namely we given a target
vector $\mathbf{t}$, a matrix $\mathbf{A}$ we are asked to find $\mathbf{t}$’s
closest vector in the span of $\mathbf{A}$, provided that this distance is,
say, at most $1/10$ of the minimal error correcting distance.

######  Definition 1.

Bounded Nearest Codeword Problem, Hamming Metric

Given an error correcting code ${\cal C}=[n,k,d]\subseteq\mathbb{F}_{2}^{n}$,
where $d$ is the minimal Hamming distance between any pair of distinct
codewords in ${\cal C}$, and is generated by matrix
$\mathbf{A}\in\mathbb{F}_{2}^{n\times k}$, and a vector $\mathbf{t}$ such that
for some $\mathbf{s}\in\mathbb{F}_{2}^{k}$:

$\Delta(\mathbf{t},\mathbf{A}\mathbf{s})\leq{\varepsilon}\cdot d$

where $\Delta(\mathbf{x},\mathbf{y})$ refers to the Hamming distance between
$\mathbf{x},\mathbf{y}$. We are asked to find $\mathbf{s}$.

The definition above uses the Hamming distance between words - namely the
number of positions in which two strings are different. Yet, for non-binary
$q$-ary alphabets, it is of interest to consider different metrics that take
into account the actual labels. Considering the alphabet as the additive group
${\mathbb{Z}}_{q}$, one such distance is called the Lee Distance 111In fact,
the Lee distance over the ring of integers generates a metric space over the
ring since it satisfies, in addition to positivity, and symmetry, the triangle
inequality. and is defined as follows:

$\Delta_{\rm
L}(\mathbf{x},\mathbf{y})=\sum_{i=1}^{n}\min\\{|x_{i}-y_{i}|,q-|x_{i}-y_{i}|\\}$

Another distance on ${\mathbb{Z}}_{q}$ is the well-known Manhattan distance
corresponding to the $\ell_{1}$-norm of Euclidean space:

$\Delta_{{\rm M}}(\mathbf{x},\mathbf{y})=\sum_{i=1}^{n}|x_{i}-y_{i}|$

One can then reconsider Definition 1 for large alphabets:

######  Definition 2.

Bounded Nearest Codeword Problem (${\varepsilon}$-BNCP), Manhattan Distance

Given is an error correcting code ${\cal C}=[n,k,d]$, where $d$ is the minimal
Manhattan distance between any pair of distinct codewords in ${\cal C}$.
${\cal C}$ is generated by matrix $\mathbf{A}\in\mathbb{F}_{q}^{n\times k}$.
We are also given a vector $\mathbf{t}$ such that for some
$\mathbf{s}\in\mathbb{F}_{q}^{k}$:

$\Delta_{M}(\mathbf{t},\mathbf{A}\mathbf{s})\leq{\varepsilon}\cdot d$

We are asked to find $\mathbf{s}$.

###  1.2 Hardness of BNCP

In general, BNCP has no known efficient classical algorithms, and the assumed
hardness of this problem is, in fact, central to the security of the McEliece
cryptosystem ([CS98], [Ber+18]), one of the finalists in the NIST effort to
design quantum-secure cryptosystems [Nis].

For $q=2$ the definition above generalizes the Hamming metric, hence BNCP is
NP-hard to solve for general $q$. Let us now examine the behavior of its
complexity for specific values of $q$. On one hand, for $q$ which is a prime
number, $\mathbb{F}_{q}$ inherits its multiplication / addition table from
${\mathbb{Z}}_{q}$ and in that case the problem is nearly identical 222Up to
the fact that $q$-ary lattices are in fact integer lattices with a shortest
vector length at most $q$, whereas $\mathbb{F}_{q}$ lattices can have longer
shortest vectors, for example the $1$-dimensional code generated by
$(1,2,\ldots,q-1)$ to the Bounded Distance Decoding for $q$-ary lattices, a
problem whose ${\varepsilon}$-approximation is known to be at least as hard as
computing the (unique) shortest vector of an integer lattice up to a factor
$1/{\varepsilon}$ [LM09].

As further testament for the generic hardness of this problem: the result of
[Aro+97] on the hardness of approximation of the decisional version of the
nearest-codeword problem w.r.t. the Hamming metric, can be readily extended to
the Manhattan / Lee distances, albeit with a diminished promise gap:

######  Theorem 3.

NP-hardness of constant factor approximation of decisional BNCP

Let ${\cal C}=[n,k,d]$ be some code of $\mathbb{F}_{q}^{n}$. There exists a
constant $c>0$ such that if $q=p^{m}$ for some integer $m$, and $c>p$ then it
is NP-hard to decide whether a vector $\mathbf{t}\in\mathbb{F}_{q}^{n}$ is at
Manhattan distance at most $L$ or at distance at least $(c/p)\cdot L$ from
${\cal C}$.

The proof appears in the appendix.

The resemblance of large-alphabet BNCP to $q$-ary BDD is also apparent in the
behavior of random lattices: one can check that just as random $q$-ary
lattices have relatively long shortest vectors, similar bounds are satisfied
w.r.t. the Manhattan/Lee distance for $\mathbb{F}_{q}$ random lattices, for
any $q$. We provide a formal statement w.r.t. the Manhattan distance.

######  Lemma 4.

Let $A$ be a uniformly random $n\times k$ matrix over $\mathbb{F}_{q}$ where
$n\geq k\log(q)$. Then

$\Pr_{A}\left(\min_{\mathbf{x}\neq\mathbf{y},\mathbf{x},\mathbf{y}\in{\cal
C}}\Delta_{M,q}(\mathbf{x},\mathbf{y})\geq q^{1-k/n}/2\right)\geq
1-2^{-n/200}$

The proof appears in the appendix. Hence for a ”typical” error-correcting code
the shortest vector can be of length, say, $q^{0.99}$ even for linear rate
codes ($k/n=0.01$). Thus, one can define non-trivial ${\varepsilon}$-BNCP on
random ensembles for very small values of ${\varepsilon}$, say
${\varepsilon}=1/\sqrt{q}$. When allowing $q$ to grow with $n$ we thus achieve
a setting that is similar to lattice problems used for cryptography. In this
analogy: ${\varepsilon}$ corresponds to the security parameter of the instance
(usually signifed by $\alpha$ for the Learning-with-Errors cryptosystem), and
an instance is considered to be ”hard”, or ”secure”, for cryptographic
purposes whenever ${\varepsilon}\cdot q>\sqrt{n}$.

###  1.3 Main Results

Despite the apparent difficulty of this problem, we show, that surprisingly,
for a code ${\cal C}=[n,k,d]$ over $\mathbb{F}_{q}$, for $q$ which is a prime
power, namely $q=p^{m}$ for prime $p$, there exists an efficient quantum
algorithm that solves BNCP for ${\varepsilon}<1/(p\cdot n^{2})$:

######  Theorem 5.

(sketch of Theorem 17)

A Quantum Decoder for Prime-Power Fields

There exists a quantum algorithm that for any $q=p^{m}$, where $p$ is prime,
solves ${\varepsilon}$-BNCP on $\mathbb{F}_{q}$ w.r.t. the Manhattan distance
for ${\varepsilon}<1/(pn^{2})$ in time ${\rm poly}(n,p,\log(q))$. 333The
dependency on $m$ is accounted for in the dependency on $\log(q)$. We note
that this algorithm can be easily adapted to the Lee metric by symmetrizing
over the difference from $q$.

We note that by a slight assumption on the distance to the lattice being an
integer power of $p$ one can increase ${\varepsilon}$ to $1/n^{2}$. We note
that for $q=2$ the above does not provide a meaningful statement since the
largest possible value for the minimal error correcting distance is at most
$n$. It is only for relatively large values of $q$, say $q=n^{3}$ that this
approximation provides a non-trivial statement.

###  1.4 Classical Algorithms

####  1.4.1 Direct Inversion

Consider an error correcting code ${\cal C}\subseteq\mathbb{F}_{q}^{n}$ for
$q=p^{m}$ for some integer $m$, and recall that each element of
$\mathbb{F}_{q}$ can be regarded as an $m$-tuple of numbers in
$\mathbb{F}_{p}$. Given a target vector $\mathbf{y}\in\mathbb{F}_{q}^{n}$ that
is close to ${\cal C}$, on may be tempted to think that for a sufficiently
small noise level each coordinate of $\mathbf{y}$, viewed as an $m$
dimensional vector in $\mathbb{F}_{p}^{m}$, has sufficiently many noise-free
coordinates - namely the ”most-significant” bits, that allow us to determine
$\mathbf{y}$’s closest vector precisely. In other words, instead of solving
the optimization problem:

$\min_{\mathbf{x}\in{\cal C}}\Delta(\mathbf{A}\mathbf{x},\mathbf{y})$

we solve the linear system of equations:

$\tilde{\mathbf{y}}=\tilde{\mathbf{A}}\cdot\tilde{\mathbf{x}}$

where $\tilde{\mathbf{y}},\tilde{\mathbf{x}}$ correspond to the top-bits in
the representations of $\mathbf{x},\mathbf{y}$ as vectors in
$\mathbb{F}_{p}^{m}$, and $\tilde{\mathbf{A}}$ is the corresponding
$\mathbb{F}_{p}$ sub-matrix of $\mathbf{A}$.

However, such a scheme fails immediately the test of invertibility: one can
easily generate a matrix $\mathbf{A}\in\mathbb{F}_{q}^{n\times n}$ that is
invertible over $\mathbb{F}_{q}$, yet regarding $\mathbf{A}$ as an $mn\times
mn$ linear operator over $\mathbb{F}_{p}$ and taking the submatrix
$\mathbf{A}_{k}$ corresponding to the top $k<m$ coordinates in each tuple
results in a matrix that fails to be invertible over $\mathbb{F}_{p}$. For
example, considering $q=4p=2$, and constructing $\mathbb{F}_{4}$ via the
irreducible polynomial $x^{2}+x+1$ over $\mathbb{F}_{2}$ one can check that
the matrix

$\mathbf{A}=\begin{bmatrix}1&2\\\ 3&0\end{bmatrix}$

over $\mathbb{F}_{4}$ can be written as a linear operator over
$\mathbb{F}_{2}^{4}$ as follows:

$\tilde{\mathbf{A}}=\begin{bmatrix}1&0&0&1\\\ 0&1&1&1\\\ 1&1&0&0\\\
1&0&0&0\end{bmatrix}$

However, extracting the sub-matrix corresponding the top coordinate of each
vector results in the following matrix:

$\tilde{\mathbf{A}}_{1}=\begin{bmatrix}1&0\\\ 1&0\\\ \end{bmatrix}$

which is not invertible over $\mathbb{F}_{2}$.

It is plausible to hope that such examples are pathological, in the sense that
they rarely appear for random codes. Yet, even for random codes this problem
is prevalent. Let us consider concrete estimates: according to Lemma 4 the
typical minimal distance $d$ of a random $\mathbb{F}_{q}$ code is at least
$q^{1-k/n}/2$. If

$\Delta{\varepsilon}<q^{1-k/n}/2$

then viewing each number $x\in\mathbb{F}_{q}$ as an $m$-dimensional vector
$\mathbf{x}\in\mathbb{F}_{p}^{m}$ we have that the top $mk/n$ $\mathbb{F}_{p}$
coordinates of each coordinate of the target vector
$\mathbf{y}\in\mathbb{F}_{q}^{n}$ are equal to the corresponding coordinates
of some codeword $\mathbf{c}\in{\cal C}$. Hence, as above, we can write a
linear system of equations over $\mathbb{F}_{p}$:

$\tilde{\mathbf{y}}=\tilde{\mathbf{A}}\cdot\tilde{\mathbf{x}}$

corresponding to the top coordinates in the $\mathbb{F}_{p}$ expansion of each
$\mathbb{F}_{q}$ number. By assumption of the random instance, the submatrix
$\tilde{\mathbf{A}}$ is in fact a random $mk\times mk$ matrix over
$\mathbb{F}_{p}$, which is invertible with probability roughly $p^{-p}$, i.e.
independently of $n$.

In order to increase the probability that $\tilde{\mathbf{A}}$ is invertible
over $\mathbb{F}_{p}$ to nearly $1$, one would need to decrease the parameter
${\varepsilon}$ controlling the relative distance to the lattice further so
that

$\Delta{\varepsilon}\sim q^{1-\beta k/n}$

for $\beta=\Omega(\log(p))$ but this implies increasing the promise from
${\varepsilon}$ to roughly ${\varepsilon}^{\beta-1}$.

####  1.4.2 Information-Set Decoding

Other classical attacks against McEliece that might also be relevant for BNCP
include mainly variants of the Information-Set Decoding algorithm (see e.g.
[Pet10], and in the context of the Lee metric see more recent works in [CDE21,
HTW19]), but that algorithm’s run-time scales exponentially in the rate $k$.
Since ”good” codes, i.e. codes which have linear distance and linear rate are
usually the target codes considered for both theoretic and practical
applications, such algorithms are prohibitive.

####  1.4.3 Summary

Thus, to the best of our knowledge, efficient decoding w.r.t. the Manhattan
distance is only available for random ensembles where the submatrix
$\tilde{\mathbf{A}}$ is invertible with overwhelming probability. We compute
below the quantum-classical separation for $p=16$, $q^{k/n}=n^{6}$, $d=q\cdot
n^{-6}$ and hence $q^{\beta k/n}=n^{24}$:

Quantum-Classical Separation for Worst-Case/Average-Case instances of BNCP for
$q=16^{m}$.

Worst-case | Quantum | Classical
---|---|---
$1/n^{2}$ | ${\rm poly}(n)$ | $e^{\Omega(n)}$
$1/n^{18}$ | ${\rm poly}(n)$ | $e^{\Omega(n)}$
Average-case | Quantum | Classical
---|---|---
$1/n^{2}$ | ${\rm poly}(n)$ | $e^{\Omega(n)}$
$1/n^{18}$ | ${\rm poly}(n)$ | ${\rm poly}(n)$

###  1.5 Context on the Main Result

Hard computational problems related to lattices and error correcting codes
have resisted efficient quantum algorithms for nearly two decades now, despite
their underlying Abelian structure that presumably makes them more susceptible
to such algorithms. This resistance has given rise to the belief that quantum
computers cannot outperform classical ones on problems that require any form
of ”bounded distance decoding” even with an inverse polynomial promise gap.
Our main result suggest that this intuition may be false.

Notably, our result, as it is, does not directly pose a threat to any known
public key crypto-system since its parameter range is quite different than
those considered for established PQC systems [Nis]: for the main code-based
PQC cryptosystems the alphabet size is constant with the block-size (see e.g.
BIKE, HQC, Classic McEliece), whereas for lattice-based cryptosystems, namely
descendants of the LWE cryptosystem [Reg09, Pei09, Bra+13], where the alphabet
size is in fact allowed to grow with the lattice dimension, the underlying
algebraic structure is not a finite field but rather the ring of integers.

Yet, we believe that this parameter mismatch does not capture the full story:
our work here suggests that using low-order QFT’s to optimize over high-order
groups, (in this case, prime-power fields) in conjunction with the recent
construction of [EH22] of approximate eigenvectors of the vector shift
operator, does in fact lead to an exponential quantum speed-up for lattice
related problems. We hope that further study of the approach outlined here
will lead to additional discoveries in this field, classical or quantum.

##  2 Preliminaries

###  2.1 Notation

$\mathbb{F}_{q}$ denotes the field of order $q$, $\omega_{p}$ denotes the
$p$-th root of unity. For $\mathbf{x},\mathbf{y}\in\mathbb{F}_{q}^{n}$ we use
$\Delta_{M,q}(\mathbf{x},\mathbf{y})$ to denote the Manhattan distance between
$\mathbf{x},\mathbf{y}$ (see Definition 8). An $\mathbb{F}_{q}$ error-
correcting code is denoted by ${\cal C}=[n,k,d]\subseteq\mathbb{F}_{q}^{n}$
where $n$ is the block-length, $k$ is the rate, and $d$ is the minimal
Manhattan distance between any pair of codewords:

$d=\min_{\mathbf{x}\neq\mathbf{y},\mathbf{x},\mathbf{y}\in{\cal
C}}\Delta_{M,q}(\mathbf{x},\mathbf{y}).$

A code ${\cal C}$ of rate $k$ is generated by a matrix
$\mathbf{A}\in\mathbb{F}_{q}^{n\times k}$. Often we omit the subscript $q$
when it is clear from context. Similarly, we use $\Delta_{\rm L}$ to signify
the Lee distance. For a subset $S\subseteq\mathbb{F}_{q}^{n}$

$\Delta(\mathbf{x},S)$

signifies the minimal distance between $\mathbf{x}$ and any $\mathbf{y}\in S$.
For $\mathbf{x}\in\mathbb{F}_{q}^{n}$ let $U_{\mathbf{x}}$ denote the shift
operator:
$U_{\mathbf{x}}{|{\mathbf{y}}\rangle}={|{\mathbf{x}+\mathbf{y}}\rangle}$. The
quantum Fourier Transform on the $n$-dimensional vector space (module) w.r.t.
the ring of integers ${\mathbb{Z}}_{p}$ is denoted by ${\cal F}_{p}^{n}$.

###  2.2 Vector Representation of Prime Power Fields

Let $p$ be a prime number, and let $\mathbb{F}_{q}$ be a prime number field of
order $q=p^{m}$ relative to some degree-$m$ irreducible polynomial
$P\in\mathbb{F}_{p}[x]$:

$\mathbb{F}_{q}=F_{p}[x]/P$

For $a\in\mathbb{F}_{q}$, $q=p^{m}$, let $\hat{a}\in\mathbb{F}_{p}^{m}$ denote
its $\mathbb{F}_{p}$ vector representation. Likewise for a vector
$\mathbf{a}\in\mathbb{F}_{q}^{k}$ let
$\hat{\mathbf{a}}\in\mathbb{F}_{p}^{m\cdot k}$ denote the concatenation of the
$\mathbb{F}_{p}$ expansion of each of its coordinates. As an additive group,
$\mathbb{F}_{q}$ is equal to the $m$-dimensional vector space over
$\mathbb{F}_{p}$:

$\mathbb{F}_{q}=\mathbb{F}_{p}\times\mathbb{F}_{p}\times\ldots\times\mathbb{F}_{p}$

We assign $q$-ary labels $a\in\mathbb{F}_{q}$ to the elements of
$\mathbb{F}_{p}^{m}$ as a $p$-ary expansion order:

$\displaystyle\widehat{{\mathbf{0}}}$
$\displaystyle=\underbrace{(0,0,\ldots,0,0)}_{m\mbox{ coordinates}}$
$\displaystyle\widehat{\mathbf{1}}$ $\displaystyle=(0,0,\ldots,0,1)$
$\displaystyle\vdots$ $\displaystyle\widehat{\mathbf{p-1}}$
$\displaystyle=(0,0,\ldots,0,p-1)$ $\displaystyle\vdots$
$\displaystyle\widehat{\mathbf{q-p}}$ $\displaystyle=(p-1,p-1,\ldots,p-1,0)$
$\displaystyle\widehat{\mathbf{q-p+1}}$ $\displaystyle=(p-1,p-1,\ldots,p-1,1)$
$\displaystyle\vdots$ $\displaystyle\widehat{\mathbf{q-1}}$
$\displaystyle=(p-1,p-1,\ldots,p-1,p-1)$

This corresponds to interpreting $\hat{a}$ as the $\mathbb{F}_{p}$ coefficient
vector of the polynomial corresponding to $\hat{a}$:

$\hat{a}(x)=\sum_{i=1}^{m}\hat{a}_{i}\cdot x^{i-1}$

When we use the ordering $x<y$ on $x,y\in\mathbb{F}_{q}$ it means that $x<y$
as numbers in ${\mathbb{Z}}$. If $\sigma=p^{r}$ and $x<\sigma$ we will often
use the notation

$\hat{x}\in 0^{n-r}[p]^{r}$

signifying that $x$’s representation as a $p$-ary vector has $0$ in the first
$n-r$ positions (MSB).

Unless stated otherwise, for $x,y\in\mathbb{F}_{q}$ the expressions
$x+y,x\cdot y$ denote addition / multiplication over $\mathbb{F}_{q}$. The
following proposition is immediately implied by definition:

######  Proposition 6.

$\forall\mathbf{x},\mathbf{y}\in\mathbb{F}_{q}^{n}\quad\widehat{\mathbf{x}+\mathbf{y}}=\hat{\mathbf{x}}+\hat{\mathbf{y}}$

where the addition in LHS is over $\mathbb{F}_{q}$ and the RHS addition is
over $\mathbb{F}_{p}^{m}$.

For example for $1\in\mathbb{F}_{q}$ and $3\in\mathbb{F}_{q}$, $q=16=2^{4}$ we
have that $1+3=2$.

###  2.3 Extending The Manhattan Distance to Prime Power Fields

The Manhattan distance was developed as an alternative to the Hamming distance
for transmission of non-binary signals taken from some $q$-ary alphabet. The
Manhattan distance

${\mathbb{Z}}_{q}^{n}\times{\mathbb{Z}}_{q}^{n}\to{\mathbb{Z}}^{+}$

is defined as follows:

$\forall\mathbf{x},\mathbf{y}\in{\mathbb{Z}}_{q}^{n},\quad\Delta_{{\rm
M}}(\mathbf{x},\mathbf{y}):=\sum_{i=1}^{n}|x_{i}-y_{i}|$

In the context of linear codes, one considers the finite field
$\mathbb{F}_{q}$ and not ${\mathbb{Z}}_{q}$. These objects are quite
different, and are equal only for prime $q$, yet in this study we consider $q$
which itself is a prime power, i.e. $q=p^{m}$. To this end we define a mapping
from $\mathbb{F}_{q}$ to the ring of integers ${\mathbb{Z}}_{q}$ using the
natural $p$-ary expansion above:

######  Definition 7.

$p$-ary expansion mapping

For $a\in\mathbb{F}_{q}$, $q=p^{m}$ we define $\hat{a}\in{\mathbb{Z}}_{q}$ by
writing $a$ as a vector
$(\hat{a}_{1},\ldots,\hat{a}_{m})\in\mathbb{F}_{p}^{m}$, i.e.
$\hat{a}_{i}\in\mathbb{F}_{p}$ and defining the polynomial

$\hat{a}(x)=\sum_{i=1}^{m}\hat{a}_{i}\cdot x^{i-1}$

we then set the ${\mathbb{Z}}_{q}$ representation of $a$, namely $\tilde{a}$,
as the evaluation of the polynomial $\hat{a}(x)$ at point $x=p$:

$\tilde{a}=\hat{a}(p)=\sum_{i=1}^{m}\hat{a}_{i}p^{i-1}$

For $\mathbf{x}\in\mathbb{F}_{q}^{n}$ we define
$\tilde{\mathbf{x}}\in{\mathbb{Z}}_{q}^{n}$ as applying the map above
coordinate-wise.

We then extend the Manhattan distance to finite fields $\mathbb{F}_{q}$ by
setting:

######  Definition 8.

Manhattan Distance for $\mathbb{F}_{q}$:

$\forall\mathbf{x},\mathbf{y}\in\mathbb{F}_{q}^{n}\quad\Delta_{M,q}(\mathbf{x},\mathbf{y})=\Delta_{M}(\tilde{\mathbf{x}},\tilde{\mathbf{y}}).$

and define the length of a vector $\mathbf{x}\in\mathbb{F}_{q}^{n}$ as its
distance from $0$:

$\|\mathbf{x}\|_{M}=\Delta_{M,q}(\mathbf{x},0)=\Delta_{M}(\tilde{\mathbf{x}},0)$

When we consider $\mathbb{F}_{q}$-linear codes we would like to consider the
”minimal distance” of a code, or the distance of a given word from an
$\mathbb{F}_{q}$ codespace, however, since the Manhattan distance is not a
metric, then in particular it is not shift invariant on ${\mathbb{Z}}_{q}$:
for example, setting $q=p$ for prime $p$ and $n=1$ we have:

$p-1=\Delta_{M}(p-1,0)\neq\Delta_{M}(p-1+1,0+1)=\Delta_{M}(0,1)=1$

Similarly, the shift-invariance property does not hold for the distance
${\Delta}_{M,q}$. However what one can show, is that specifically for the
$p$-ary expansion mapping the following gap-presevation property does hold:

######  Proposition 9.

Gap Preserving Property

For all $\mathbf{x},\mathbf{y}\in\mathbb{F}_{q}^{n}$ if for some $r<m$

$\Delta_{M,q}(\mathbf{x},\mathbf{y})<p^{r}$

then

$\Delta_{M,q}(\mathbf{x}-\mathbf{y},0)\leq n\cdot p^{r}$

In particular, if ${\cal C}\subseteq\mathbb{F}_{q}^{n}$ is such that for some
$r<m$

$d=\min_{\mathbf{x}\neq\mathbf{y},\mathbf{x},\mathbf{y}\in{\cal
C}}\Delta_{M,q}(\mathbf{x},\mathbf{y})<p^{r}$

then the shortest vector $\mathbf{x}$ of ${\cal C}$ satisfies:

$\|\mathbf{x}\|_{M}<n\cdot p^{r}$

###### Proof.

If $\Delta_{M,q}(\mathbf{x},\mathbf{y})<p^{r}$ then

$\forall
i\in[n]\quad\Delta_{M}(\widetilde{\mathbf{x}_{i}},\widetilde{\mathbf{y}_{i}})<p^{r}$

This implies that for each $i\in[n]$ the respective $p$-ary expansions of
$\widehat{\mathbf{x}_{i}},\widehat{\mathbf{y}_{i}}\in\mathbb{F}_{p}^{m}$ are
identical on indices $m,m-1,\ldots,r+1$. Thus
$\mathbf{z}=\mathbf{x}-\mathbf{y}$ (subtraction over $\mathbb{F}_{q}$) is such
that for each $i\in[n]$ the $p$-ary expansion of $\mathbf{z}_{i}$, i.e.
$\widehat{\mathbf{z}_{i}}$ is $0$ for the top $m-r$ coordinates. In particular
$\widetilde{\mathbf{z}_{i}}<p^{r}$ so

$\|\mathbf{z}\|_{M}\equiv\sum_{i\in[n]}\widetilde{\mathbf{z}_{i}}<n\cdot
p^{r}$

∎

We note that if one replaces the Manhattan distance with the Lee distance,
which is in fact a metric on ${\mathbb{Z}}_{q}$ one obtains a metric space on
$\mathbb{F}_{q}^{n}$ via the $p$-ary expansion mapping defined above, and
under the partial order on elements of $\mathbb{F}_{q}$ defined above for the
$p$-ary expansion. This would imply, in particular that one would be able to
improve the performance of the proposed quantum algorithm by a factor of $n$.
Still, we decided to develop this study using the Manhattan distance and not
the Lee distance, losing the property of a metric space, for a more general
statement.

###  2.4 Invertibility of Random Matrices over Finite Fields

The well-established theory of random matrices over finite fields
characterizes the probability that a uniformly random matrix over a finite
field is invertible as follows:

######  Lemma 10.

Theorem 1.1 in [Map10]

Let $A\sim U[\mathbb{F}_{p}^{n\times k}]$. There exists a constant $c>0$ such
that:

$\Pr_{\mathbf{A}}\left(\mathbf{A}\mbox{ is
invertible}\right)\geq\prod_{k=1}^{\infty}(1-p^{-k})-e^{-cT}$

##  3 Quantum PCS States on Finite Fields

In [EH22] the authors define the ”Phased Coset State” (or PCS) on $q$-ary
lattices as a certain superposition on the lattice, comprised of copies of a
bounded function - each centered around an individual lattice point and
multiplied by a phase that depends on that lattice point. Here we redefine the
PCS on finite fields:

######  Definition 11.

PCS on Finite Fields

For $\sigma\in\mathbb{F}_{q}$ define the set
$[{\sigma}]=\\{0,\ldots,\sigma-1\\}\subseteq\mathbb{F}_{q}$ and
$[{\sigma}]^{n}$ as the n-th fold product thereof.

  1. 1.

Define the cube state anchored at a point $\mathbf{y}\in\mathbb{F}_{q}^{n}$ by

${|{C(\mathbf{y})}\rangle}=\sigma^{-n/2}\cdot\sum_{\mathbf{z}\in[{\sigma}]^{n}}{|{\mathbf{y}+\mathbf{z}}\rangle}.$

  2. 2.

Let ${\cal C}=[n,k,d]\subseteq\mathbb{F}_{q}^{n}$ with $q=p^{m}$. The phased
cube state with label $\widehat{\mathbf{a}}\in\mathbb{F}_{p}^{m\cdot k}$ is
the following state:

${|{\psi_{\widehat{\mathbf{a}}}}\rangle}=q^{-k/2}\cdot\sum_{\mathbf{c}\in\mathbb{F}_{q}^{k}}\omega_{p}^{\hat{\mathbf{a}}\cdot\hat{\mathbf{c}}}{|{C(\mathbf{G}\mathbf{c})}\rangle}=q^{-k/2}\cdot\sigma^{-n/2}\cdot\sum_{\mathbf{c}\in\mathbb{F}_{q}^{k}}\omega_{p}^{\hat{\mathbf{a}}\cdot\hat{\mathbf{c}}}\sum_{\mathbf{z}\in[{\sigma}]^{n}}{|{\mathbf{G}\mathbf{c}+\mathbf{z}}\rangle}.$

Note that the quantum state is defined on a register with numbers in
$\mathbb{F}_{q}$ whereas the phase that multiplies each basis element is a
power of the primitive root $\omega_{p}$.

######  Lemma 12 (Cube state properties).

  1. 1.

$\forall\mathbf{x},\mathbf{y}\in\mathbb{F}_{q}^{n},U_{\mathbf{x}}{|{C(\mathbf{y})}\rangle}={|{C(\mathbf{x}+\mathbf{y})}\rangle}$,
and the transformation ${|{C(\mathbf{y})}\rangle}{|{\mathbf{x}}\rangle}$ to
${|{C(\mathbf{x}+\mathbf{y})}\rangle}{|{\mathbf{x}}\rangle}$ is computable in
time ${\rm poly}(n,\log q)$.

  2. 2.

Let ${|{C(\mathbf{y})}\rangle}$ be a cube state of side length $\sigma=p^{r}$
for some $r>0,\mathbf{y}\in\mathbb{F}_{q}^{n}$ and let
$\mathbf{\Delta}\in\mathbb{F}_{q}^{n}$.

    1. (a)

If $\|\mathbf{\Delta}\|_{M,q}\leq\sigma$ then
${|{C(\mathbf{y})}\rangle}={|{C(\mathbf{y}+\mathbf{\Delta})}\rangle}$.

    2. (b)

If $\|\mathbf{\Delta}\|_{M,q}>n\cdot\sigma$ then $\langle
C(\mathbf{y}){|{C(\mathbf{y}+\mathbf{\Delta})}\rangle}=0$.

Consider the implication of Item 2a: it implies that the PCS is not ”periodic”
on the code-space in the usual sense of having symmetric support around each
codeword (/lattice point). The function of symmetric support around each
codeword is a different function which is the convolution of the Hamming ball
and the code-space. Rather, the support of the cube-shaped super-position
starts at the point which is the original codeword with all the right-most $r$
coordinates erased. Note that the ”erased” information is encoded in the phase
that multiplies each cube. For example, the cube anchored at a codeword $c$
such that $\hat{c}\in[p]^{n-r}0^{r}$ is situated to the ”bottom-right” of the
codeword, whereas if $\hat{c}\in[p]^{n-r}1^{r}$ it is situated on the ”top-
left” of the codeword.

###### Proof.

Item: 1

$\displaystyle\forall\mathbf{x}\in\mathbb{F}_{q}^{n}\quad
U_{\mathbf{x}}{|{C(\mathbf{y})}\rangle}$
$\displaystyle=\sigma^{-n/2}\cdot\sum_{\mathbf{z}\in[{\sigma}]^{n}}U_{\mathbf{x}}{|{\mathbf{y}+\mathbf{z}}\rangle}$
(1)
$\displaystyle=\sigma^{-n/2}\cdot\sum_{\mathbf{z}\in[{\sigma}]^{n}}{|{\mathbf{x}+\mathbf{y}+\mathbf{z}}\rangle}$
(2) $\displaystyle={|{C(\mathbf{x}+\mathbf{y})}\rangle}$ (3)

Therefore, given ${|{C(\mathbf{y})}\rangle}{|{\mathbf{x}}\rangle}$, one
addition from the second register into the first register results in
${|{C(\mathbf{x}+\mathbf{y})}\rangle}{|{\mathbf{x}}\rangle}$.

Item: 2a

Start with

$\Big{\|}{|{C(\mathbf{y})}\rangle}-{|{C(\mathbf{y}+\mathbf{\Delta})}\rangle}\Big{\|}^{2}=2\cdot(1-\Re(\langle
C(\mathbf{y}){|{C(\mathbf{y}+\mathbf{\Delta})}\rangle})).$

We have:

$\displaystyle\langle
C(\mathbf{y}){|{C(\mathbf{y}+\mathbf{\Delta})}\rangle}=\langle
C({\mathbf{0}}){|{C(\mathbf{\Delta})}\rangle}$ Item 1 for the shift by
$\mathbf{y}$ (4)

Since $\|\mathbf{\Delta}\|_{M}\leq\sigma$ then

$\forall i\in[n]\quad\widetilde{\mathbf{\Delta}_{i}}\leq\sigma.$

Hence, for each $i$ the set $[{\sigma}]$ is invariant under shift by
$\mathbf{\Delta}_{i}$:

$\displaystyle\mathbf{\Delta}_{i}+[{\sigma}]$
$\displaystyle=\\{x+\mathbf{\Delta}_{i},\ x\in[{\sigma}]\\}$ (5)
$\displaystyle=\\{x+\mathbf{\Delta}_{i},\ \hat{x}\in
0^{n-r}[p]^{r}\\}\quad\mbox{By the assumption that $\sigma=p^{r}$}$ (6)
$\displaystyle=\\{x+\mathbf{\Delta}_{i},\
\widehat{x+\mathbf{\Delta}_{i}}+\widehat{\mathbf{\Delta}}_{i}\in
0^{n-r}[p]^{r}\\}\quad\mbox{By Proposition \ref{prop:1}}$ (7)
$\displaystyle=\\{x,\ \hat{x}+\widehat{\mathbf{\Delta}_{i}}\in
0^{n-r}[p]^{r}\\}\quad\mbox{Re-indexing}$ (8) $\displaystyle=\\{x,\
\widehat{x}\in 0^{n-r}[p]^{r}\\}\quad\mbox{By the assumption that
$\mathbf{\Delta}_{i}\leq\sigma$}$ (9) $\displaystyle=\\{x,\ x\in[\sigma]\\}$
(10) $\displaystyle=[{\sigma}]$ (11)

It follows that:

$\langle C({\mathbf{0}}){|{C(\mathbf{\Delta})}\rangle}=1$

Substituting in Equation 4 implies:
$\big{\|}{|{C(\mathbf{y})}\rangle}-{|{C(\mathbf{y}+\mathbf{\Delta})}\rangle}\big{\|}=0$.

Item: 2b

If $\|\mathbf{\Delta}\|_{M}\geq n\cdot\sigma+1$ there exists at least one
coordinate $i\in[n]$ such that

$\widetilde{\mathbf{\Delta}_{i}}>\sigma$

in that case $\widehat{\mathbf{\Delta}_{i}}\notin 0^{n-r}[p]^{r}$, and
together with the assumption $\sigma=p^{r}$ we have:

$\forall x\in[{\sigma}]\quad\hat{x}+\widehat{\mathbf{\Delta}_{i}}\notin
0^{n-r}[p]^{r}$

so

$\langle C({\mathbf{0}}){|{C(\mathbf{\Delta})}\rangle}=0$

∎

We conclude from the lemma above that
${|{\psi_{\widehat{\mathbf{a}}}}\rangle}$ is an eigenvector of
$U_{\mathbf{t}}$, for $\mathbf{t}$ that is $\sigma$-close to a word
$\mathbf{s}$ with eigenvalue
$\omega_{p}^{-\hat{\mathbf{a}}\cdot\hat{\mathbf{s}}}$.

######  Lemma 13.

Let ${|{\psi_{\widehat{\mathbf{a}}}}\rangle}$ denote a PCS state with label
$\widehat{\mathbf{a}}\in\mathbb{F}_{p}^{m\cdot k}$ and parameter
$\sigma=p^{r}$ for integer $r<m$, and let $\mathbf{t}\in\mathbb{F}_{q}^{n}$
such that

$\Delta_{M,q}(\mathbf{t},\mathbf{A}\mathbf{s})\leq\sigma/n$

for some $\mathbf{s}\in\mathbb{F}_{q}^{k}$. Then

$U_{{\mathbf{t}}}{|{\psi_{\widehat{\mathbf{a}}}}\rangle}=\omega_{p}^{-\hat{\mathbf{a}}\cdot\hat{\mathbf{s}}}\cdot{|{\psi_{\widehat{\mathbf{a}}}}\rangle}.$

###### Proof.

Since $\Delta_{M,q}(\mathbf{t},\mathbf{A}\mathbf{s})\leq\sigma/n$, for
$\sigma=p^{r}$, $r<m$ then by Proposition 9 we can write:

$\mathbf{t}=\mathbf{A}\mathbf{s}+\mathbf{\Delta}$

where $\|\mathbf{\Delta}\|_{M,q}\leq\sigma$. Therefore

$\displaystyle U_{\mathbf{t}}{|{\psi_{\widehat{\mathbf{a}}}}\rangle}$
$\displaystyle=q^{-k/2}\cdot
U_{\mathbf{t}}\cdot\sum_{\mathbf{c}\in\mathbb{F}_{q}^{k}}\omega_{p}^{\hat{\mathbf{a}}\hat{\mathbf{c}}}{|{C(\mathbf{A}\mathbf{c})}\rangle}$
(12) $\displaystyle=q^{-k/2}\cdot U_{\mathbf{\Delta}}\cdot
U_{\mathbf{A}\mathbf{s}}\cdot\sum_{\mathbf{c}\in\mathbb{F}_{q}^{k}}\omega_{p}^{\hat{\mathbf{a}}\hat{\mathbf{c}}}{|{C(\mathbf{A}\mathbf{c})}\rangle}$
(13) $\displaystyle=q^{-k/2}\cdot
U_{\mathbf{\Delta}}\cdot\sum_{\mathbf{c}\in\mathbb{F}_{q}^{k}}\omega_{p}^{\hat{\mathbf{a}}\hat{\mathbf{c}}}{|{C(\mathbf{A}\mathbf{c}+\mathbf{A}\mathbf{s})}\rangle}\mbox{
definition of shift over $\mathbb{F}_{q}$}$ (14) $\displaystyle=q^{-k/2}\cdot
U_{\mathbf{\Delta}}\cdot\sum_{\mathbf{c}\in\mathbb{F}_{q}^{k}}\omega_{p}^{\hat{\mathbf{a}}\hat{\mathbf{c}}}{|{C(\mathbf{A}(\mathbf{c}+\mathbf{s}))}\rangle}\mbox{
linearity over $\mathbb{F}_{q}$}$ (15) $\displaystyle=q^{-k/2}\cdot
U_{\mathbf{\Delta}}\cdot\omega_{p}^{-\hat{\mathbf{a}}\hat{\mathbf{s}}}\sum_{\mathbf{c}\in\mathbb{F}_{q}^{k}}\omega_{p}^{\hat{\mathbf{a}}(\hat{\mathbf{c}}+\hat{\mathbf{s}})}{|{C(\mathbf{A}(\mathbf{c}+\mathbf{s}))}\rangle}$
(16) $\displaystyle=q^{-k/2}\cdot
U_{\mathbf{\Delta}}\cdot\omega_{p}^{-\hat{\mathbf{a}}\hat{\mathbf{s}}}\sum_{\mathbf{c}\in\mathbb{F}_{q}^{k}}\omega_{p}^{\hat{\mathbf{a}}\cdot\widehat{\mathbf{c}+\mathbf{s}}}{|{C(\mathbf{A}(\mathbf{c}+\mathbf{s}))}\rangle}\quad\mbox{Proposition
\ref{prop:1}}$ (17)
$\displaystyle=\omega_{p}^{-\hat{\mathbf{a}}\hat{\mathbf{s}}}\cdot
q^{-k/2}\cdot
U_{\mathbf{\Delta}}\sum_{\mathbf{c}\in\mathbb{F}_{q}^{k}}\omega_{p}^{\hat{\mathbf{a}}\hat{\mathbf{c}}}{|{C(\mathbf{A}\mathbf{c})}\rangle}\quad\mbox{Re-
indexing $c+s\to c$}$ (18)
$\displaystyle=\omega_{p}^{-\hat{\mathbf{a}}\hat{\mathbf{s}}}\cdot
q^{-k/2}\sum_{\mathbf{c}\in\mathbb{F}_{q}^{k}}\omega_{p}^{\hat{\mathbf{a}}\hat{\mathbf{c}}}{|{C(\mathbf{A}\mathbf{c})}\rangle}\quad\mbox{Item
\ref{it:dist-close} since $\|\mathbf{\Delta}\|_{M,q}\leq\sigma$}$ (19)
$\displaystyle=\omega_{p}^{-\hat{\mathbf{a}}\hat{\mathbf{s}}}{|{\psi_{\widehat{\mathbf{a}}}}\rangle}$
(20)

∎

We now show an efficient algorithm for sampling a PCS state
${|{\psi_{\hat{\mathbf{a}}}}\rangle}$ for random $\hat{\mathbf{a}}$:

######  Lemma 14.

An efficient quantum PCS sampler

Let ${\cal C}=[n,k,d]$ be a code of $\mathbb{F}_{q}^{n}$ generated by matrix
$\mathbf{A}\in\mathbb{F}_{q}^{n\times k}$, $q=p^{m}$,i.e.

$d=\min_{\mathbf{x}\neq\mathbf{y},\mathbf{x},\mathbf{y}\in{\cal}}\Delta_{M,q}(\mathbf{x},\mathbf{y})$

There exists a quantum algorithm that samples
${|{\psi_{\hat{\mathbf{a}}}}\rangle}$ for $\hat{\mathbf{a}}\sim
U\left[\mathbb{F}_{p}^{m\cdot k}\right]$ in time ${\rm poly}(n,\log(q))$,
whenever $\sigma<d/n$.

###### Proof.

Consider the following evolution according to the computational steps
specified in each equation:

$\displaystyle{|{{\mathbf{0}}}\rangle}_{1}\otimes{|{{\mathbf{0}}}\rangle}_{2}$
$\displaystyle\to{|{{\mathbf{0}}}\rangle}_{1}\otimes{|{C({\mathbf{0}})}\rangle}_{2}\quad\mbox{QFT:
}I\otimes{\cal F}_{\sigma}^{n}$ (21) $\displaystyle\to
q^{-k/2}\cdot\sum_{\mathbf{c}\in\mathbb{F}_{q}^{k}}{|{\mathbf{c}}\rangle}\otimes{|{C({\mathbf{0}})}\rangle}\quad\mbox{QFT:
}{\cal F}_{q}^{k}\otimes I$ (22) $\displaystyle\to
q^{-k/2}\cdot\sum_{\mathbf{c}\in\mathbb{F}_{q}^{k}}{|{\mathbf{c}}\rangle}\otimes{|{C(\mathbf{A}\mathbf{c})}\rangle}\quad\mbox{
controlled shift by }\mathbf{A}\mathbf{c}$ (23) $\displaystyle\to
q^{-k/2}\cdot\sum_{\mathbf{c}\in\mathbb{F}_{q}^{k}}{|{\hat{\mathbf{c}}}\rangle}\otimes{|{C(\mathbf{A}\mathbf{c})}\rangle}\quad\mbox{Change
rep.: }\mathbb{F}_{q}^{k}\mbox{ to }\mathbb{F}_{p}^{m\cdot k}$ (24)
$\displaystyle\to
q^{-k/2}\cdot\sum_{\mathbf{c}\in\mathbb{F}_{q}^{k}}\left(q^{-k/2}\cdot\sum_{\hat{\mathbf{a}}\in\mathbb{F}_{p}^{mk}}\omega_{p}^{\hat{\mathbf{a}}\hat{\mathbf{c}}}{|{\hat{\mathbf{a}}}\rangle}\right)\otimes{|{C(\mathbf{A}\mathbf{c})}\rangle}\quad\mbox{QFT:
}{\cal F}_{p}^{m\cdot k}\otimes I$ (25)
$\displaystyle=q^{-k}\sum_{\hat{\mathbf{a}}\in\mathbb{F}_{p}^{mk}}{|{\hat{\mathbf{a}}}\rangle}\otimes\left(\sum_{\mathbf{c}\in\mathbb{F}_{q}^{k}}\omega_{p}^{\hat{\mathbf{a}}\hat{\mathbf{c}}}{|{C(\mathbf{A}\mathbf{c})}\rangle}\right)$
(26)

By definition we have

$\forall\mathbf{c}\in\mathbb{F}_{q}^{k}\quad\|\mathbf{A}\mathbf{c}\|_{M}\equiv\Delta_{M,q}(\mathbf{A}\mathbf{c},0)\geq
d>\sigma\cdot n.$

Then by Item 2b it follows that the set
$\left\\{{|{C(\mathbf{A}\mathbf{c})}\rangle}\right\\}_{c\in\mathbb{F}_{q}^{k}}$
forms an orthonormal set. Hence

$\forall\hat{\mathbf{a}}\in\mathbb{F}_{p}^{mk}\quad\Pr(\widehat{\mathbf{a}})=q^{-k}$

which is independent of $\widehat{\mathbf{a}}$, i.e. $\hat{a}$ is sampled
uniformly from ${\mathbb{Z}}_{p}^{mk}$. The running time of the procedure is
determined by the complexity of the Fourier transform over
$\mathbb{F}_{p}^{mk}$, which is at most

$\log(p)\cdot m\cdot k={\rm poly}(n,\log(q)).$

∎

##  4 An Algorithm for BNCP for Prime-Power Fields

We now define the following quantum bounded-distance decoder: We first define
the algorithm in terms of $q=2^{m}$ for simplicity of exposition, and later
we’ll generalize it to any $q=p^{m}$ for prime $p$:

######  Algorithm 15.

A Quantum Decoder for Finite Field BNCP

Input: $(\mathbf{A}\in\mathbb{F}_{q}^{n\times
k},\mathbf{t}\in\mathbb{F}_{q}^{n})$, $q=2^{m}$, and parameter $\sigma>0$.

  1. 1.

Sample $T=k\cdot m$ quantum PCS states with parameter $\sigma$:

${|{\psi_{\widehat{\mathbf{a}_{1}}}}\rangle}\otimes\ldots\otimes{|{\psi_{\widehat{\mathbf{a}_{T}}}}\rangle}$

  2. 2.

Let $\hat{\mathbf{A}}$ denote the matrix whose columns are the labels of the
sampled PCS states:

$\hat{\mathbf{A}}=[\widehat{\mathbf{a}_{1}},\ldots,\widehat{\mathbf{a}_{T}}]$

Assume w.l.o.g. that $\hat{\mathbf{A}}$ is invertible over $\mathbb{F}_{2}$.

  3. 3.

Tensor with the uniform superposition

$q^{-k/2}\cdot\sum_{\mathbf{z}\in\mathbb{F}_{q}^{k}}{|{\widehat{\mathbf{z}}}\rangle}$

  4. 4.

Apply $\hat{\mathbf{A}}^{-1}$ to the register:

$q^{-k/2}\cdot\sum_{\mathbf{z}\in\mathbb{F}_{q}^{k}}{|{\hat{\mathbf{A}}^{-1}\cdot\widehat{\mathbf{z}}}\rangle}$

  5. 5.

Apply a controlled-shift operation where bit $j\in[T]$ of
$\hat{\mathbf{A}}^{-1}\widehat{\mathbf{z}}\in\mathbb{F}_{2}^{T}$ controls
whether or not we apply $U_{\mathbf{t}}$ to the $j$-th PCS state:

$q^{-k/2}\cdot\sum_{\mathbf{z}\in\mathbb{F}_{q}^{k}}{|{\hat{\mathbf{A}}^{-1}\cdot\widehat{\mathbf{z}}}\rangle}\otimes
U_{\mathbf{t}}^{(\hat{\mathbf{A}}^{-1}\widehat{\mathbf{z}})_{1}}{|{\psi_{\widehat{\mathbf{a}_{1}}}}\rangle}\otimes\ldots\otimes
U_{\mathbf{t}}^{(\hat{\mathbf{A}}^{-1}\widehat{\mathbf{z}})_{T}}{|{\psi_{\widehat{\mathbf{a}_{T}}}}\rangle}$

  6. 6.

Apply $\hat{\mathbf{A}}$ to the first register:

$q^{-k/2}\cdot\sum_{\mathbf{z}\in\mathbb{F}_{q}^{k}}{|{\widehat{\mathbf{z}}}\rangle}\otimes
U_{\mathbf{t}}^{(\hat{\mathbf{A}}^{-1}\widehat{\mathbf{z}})_{1}}{|{\psi_{\widehat{\mathbf{a}_{1}}}}\rangle}\otimes\ldots\otimes
U_{\mathbf{t}}^{(\hat{\mathbf{A}}^{-1}\widehat{\mathbf{z}})_{T}}{|{\psi_{\widehat{\mathbf{a}_{T}}}}\rangle}$

  7. 7.

Apply the $\mathbb{F}_{2}^{T}$ quantum Fourier transform on the first
register, and measure in the standard basis. Denote as output ${\cal O}$.

Using this algorithm we solve an instance of ${\varepsilon}$-BNCP to factor
${\varepsilon}=1/(2n^{2})$.

######  Theorem 16.

Let ${\cal C}=[n,k,d]$ be an error correcting code over $\mathbb{F}_{q}^{n}$
for $q=p^{m}$, $p=2$. Let $(\mathbf{A}\in\mathbb{F}_{q}^{n\times
k},\mathbf{t}\in\mathbb{F}_{q}^{n})$ be an instance of ${\varepsilon}$-BNCP
where

$\Delta(\mathbf{t},\mathbf{A}\mathbf{s})\leq d/(2n^{2})$

for some $\mathbf{s}\in\mathbb{F}_{q}^{k}$. Then upon input
$(\mathbf{A},\mathbf{t})$ and parameter $\sigma=2^{r},r<m$ that satisfies:

$(\ast)\quad d/(2n)\leq\sigma<d/n$

Algorithm 15 runs in expected time ${\rm poly}(n,\log(q))$ and returns an
outcome ${\cal O}=\hat{\mathbf{s}}$.

We note that the theorem above assumes a-priori knowledge of $d$. This is
reasonable in the error-correction setting, but in the computational theory of
lattices knowledge of the minimal distance amounts to an oracle to the GapSVP
problem which is also known to be a hard problem. However, by initializing
$\sigma=1$ and executing the algorithm on sequential doubling of the parameter
there will be at least one iteration such that $\sigma=2^{r}$ satisfies the
condition $(\ast)$. Since the correct answer can be easily checked this
essentially removes the need to know $d$ in advance.

###### Proof.

Assume for now that $\hat{\mathbf{A}}$ is invertible over $\mathbb{F}_{2}$ and
consider the output of step 6

${|{\psi}\rangle}=q^{-k/2}\cdot\sum_{\mathbf{z}\in\mathbb{F}_{q}^{k}}{|{\widehat{\mathbf{z}}}\rangle}\otimes
U_{\mathbf{t}}^{(\hat{\mathbf{A}}^{-1}\widehat{\mathbf{z}})_{1}}{|{\psi_{\widehat{\mathbf{a}_{1}}}}\rangle}\otimes\ldots\otimes
U_{\mathbf{t}}^{(\hat{\mathbf{A}}^{-1}\widehat{\mathbf{z}})_{T}}{|{\psi_{\widehat{\mathbf{a}_{T}}}}\rangle}$

By our choice of parameters we have:

$\sigma\geq n\cdot\Delta_{M,q}(\mathbf{t},\mathbf{A}\mathbf{s}).$

Since in addition $\sigma=2^{r}$, $r<m$, we can invoke Lemma 13 which implies:

$\forall\widehat{\mathbf{a}}\in\mathbb{F}_{2}^{T}\quad
U_{\mathbf{t}}{|{\psi_{\widehat{\mathbf{a}}}}\rangle}=(-1)^{\hat{\mathbf{a}}\hat{\mathbf{s}}}\cdot{|{\psi_{\widehat{\mathbf{a}}}}\rangle}.$

Observe that:

$U_{\mathbf{t}}^{1}=U_{\mathbf{t}}\quad U_{\mathbf{t}}^{0}=I.$

Hence each PCS state ${|{\psi_{\widehat{\mathbf{a}_{i}}}}\rangle}$ above is
multiplied by a phase $(-1)^{\widehat{\mathbf{a}_{i}}\hat{\mathbf{s}}}$ if
$(\hat{\mathbf{A}}^{-1}\widehat{\mathbf{z}})_{i}=1$ and by phase $1$ if
$(\hat{\mathbf{A}}^{-1}\widehat{\mathbf{z}})_{i}=0$:

$\displaystyle{|{\psi}\rangle}$
$\displaystyle=q^{-k/2}\cdot\sum_{\mathbf{z}\in\mathbb{F}_{q}^{k}}{|{\widehat{\mathbf{z}}}\rangle}\otimes(-1)^{(\hat{\mathbf{A}}^{-1}\widehat{\mathbf{z}})_{1}\cdot\widehat{\mathbf{a}_{1}}\cdot\hat{\mathbf{s}}}{|{\psi_{\widehat{\mathbf{a}_{1}}}}\rangle}\otimes\ldots\otimes(-1)^{(\hat{\mathbf{A}}^{-1}\widehat{\mathbf{z}})_{T}\cdot\widehat{\mathbf{a}_{T}}\cdot\hat{\mathbf{s}}}{|{\psi_{\widehat{\mathbf{a}_{T}}}}\rangle}$
(27)
$\displaystyle=q^{-k/2}\cdot\sum_{\mathbf{z}\in\mathbb{F}_{q}^{k}}{|{\widehat{\mathbf{z}}}\rangle}\otimes(-1)^{\hat{\mathbf{s}}\cdot\hat{\mathbf{A}}\cdot\hat{\mathbf{A}}^{-1}\cdot\hat{\mathbf{z}}}{|{\psi_{\widehat{\mathbf{a}_{1}}}}\rangle}\otimes\ldots\otimes{|{\psi_{\widehat{\mathbf{a}_{T}}}}\rangle}$
(28)
$\displaystyle=\left(q^{-k/2}\cdot\sum_{\mathbf{z}\in\mathbb{F}_{q}^{k}}(-1)^{\hat{\mathbf{s}}\cdot\hat{\mathbf{z}}}{|{\hat{\mathbf{z}}}\rangle}\right)\otimes{|{\psi_{\widehat{\mathbf{a}_{1}}}}\rangle}\otimes\ldots\otimes{|{\psi_{\widehat{\mathbf{a}_{T}}}}\rangle}$
(29)

In this case measuring register 1 in the $\mathbb{F}_{2}^{T}$ Fourier basis
results in outcome $\hat{\mathbf{s}}$ with probability $1$.

Running time: Since

$\sigma<d/n$

then by Lemma 14 we can sample PCS states
${|{\psi_{\widehat{\mathbf{a}}}}\rangle}$ such that $\widehat{\mathbf{a}}\sim
U[\mathbb{F}_{2}^{T}]$ in time ${\rm poly}(n,\log(q))$. By independence of
sampling this implies that the entries of $\hat{\mathbf{A}}$ are i.i.d.
uniform on $\mathbb{F}_{2}$. By Lemma 10 this implies that

$\Pr(\hat{\mathbf{A}}\mbox{ is
invertible})\geq\prod_{k=1}^{\infty}(1-2^{-k})-e^{-cT}\geq 1/10$

It follows that after $O(1)$ iterations of Step 1 the matrix
$\hat{\mathbf{A}}$ is invertible. The rest of the computational steps: namely
the Quantum Fourier Transform, the controlled shift operation, and
multiplication by $\hat{\mathbf{A}},\hat{\mathbf{A}}^{-1}$ all take time at
most ${\rm poly}(n,\log(q))$.

∎

###  4.1 Generalization to Arbitrary Characteristic

In the previous section we have shown an algorithm to solve BNCP on fields
$\mathbb{F}_{q}$ of characteristic $2$, namely $q=2^{m}$ for some integer $m$.
In this section we’ll generalize this algorithm to arbitrary characteristic:
$q=p^{m}$ for prime $p$.

We consider again Algorithm 15 previously stated for $p=2$. For general $p$ we
require in Step 1 that $\hat{\mathbf{A}}$ is invertible over $\mathbb{F}_{p}$,
and in Step 1 we consider operators of the form $U_{\mathbf{t}}^{\ell}$ where
now $\ell$ can assume any number in $\mathbb{F}_{p}$ (instead of a binary
value) and $U_{\mathbf{t}}^{\ell}$ is then interpreted as taking the $\ell$-th
power of $U_{\mathbf{t}}$ where:

$U_{\mathbf{t}}^{\ell}=\underbrace{U_{\mathbf{t}}\cdot\ldots\cdot
U_{\mathbf{t}}}_{\ell\mbox{ times}}$

We now restate Theorem 16 for prime-power fields $q=p^{m}$. We note that the
distance to the lattice for which the theorem holds is now decreased by a
factor of $p$, i.e. we can solve the problem when the distance
$\Delta(\mathbf{t},{\cal C})$ is at most $d/(p\cdot n^{2})$. This extra
condition is set in order to allow the existence of a value $\sigma=p^{r},r<m$
that is at least $\Delta(\mathbf{t},{\cal C})$ and at most $d/n$. As before,
this condition can be omitted by making a numerical assumption on the distance
from ${\cal C}$.

######  Theorem 17.

Let ${\cal C}=[n,k,d]$ be an error correcting code over $\mathbb{F}_{q}^{n}$
for $q=p^{m}$ for prime $p$. Let $(\mathbf{A}\in\mathbb{F}_{q}^{n\times
k},\mathbf{t}\in\mathbb{F}_{q}^{n})$ be an instance of ${\varepsilon}$-BNCP
where

$\Delta_{M,q}(\mathbf{t},\mathbf{A}\mathbf{s})\leq d/(pn^{2})$

for some $\mathbf{s}\in\mathbb{F}_{q}^{k}$. Then upon input
$(\mathbf{A},\mathbf{t})$ and parameter $\sigma=p^{r},r<m$ that satisfies:

$(\ast)\quad d/(pn)<\sigma<d/n$

Algorithm 15 runs in expected time ${\rm poly}(n,p,\log(q))$ and returns
results an outcome ${\cal O}=\hat{\mathbf{s}}$.

###### Proof.

Assume for now that $\hat{\mathbf{A}}$ is invertible over $\mathbb{F}_{p}$ and
consider the output of step 6

${|{\psi}\rangle}=q^{-k/2}\cdot\sum_{\mathbf{z}\in\mathbb{F}_{q}^{k}}{|{\widehat{\mathbf{z}}}\rangle}\otimes
U_{\mathbf{t}}^{(\hat{\mathbf{A}}^{-1}\widehat{\mathbf{z}})_{1}}{|{\psi_{\widehat{\mathbf{a}_{1}}}}\rangle}\otimes\ldots\otimes
U_{\mathbf{t}}^{(\hat{\mathbf{A}}^{-1}\widehat{\mathbf{z}})_{T}}{|{\psi_{\widehat{\mathbf{a}_{T}}}}\rangle}$

By our choice of parameters we have:

$\sigma>n\cdot\Delta(\mathbf{t},\mathbf{A}\mathbf{s})$

and $\sigma=p^{r}$ for $r<m$. Thus we can invoke Lemma 13 which implies:

$\forall\widehat{\mathbf{a}}\in\mathbb{F}_{p}^{T},\quad
U_{\mathbf{t}}{|{\psi_{\widehat{\mathbf{a}}}}\rangle}=\omega_{p}^{-\hat{\mathbf{a}}\hat{\mathbf{s}}}\cdot{|{\psi_{\widehat{\mathbf{a}}}}\rangle}.$

Therefore

$\forall\ell\in\mathbb{F}_{p}\quad
U_{\mathbf{t}}^{\ell}=U_{\mathbf{t}}U_{\mathbf{t}}\cdot\ldots\cdot
U_{\mathbf{t}}{|{\psi_{\widehat{\mathbf{a}}}}\rangle}=\omega_{p}^{-\ell\cdot\hat{\mathbf{a}}\hat{\mathbf{s}}}\cdot{|{\psi_{\widehat{\mathbf{a}}}}\rangle}$

Hence each PCS state ${|{\psi_{\mathbf{a}_{i}}}\rangle}$ above is multiplied
by a phase $\omega_{p}^{-\ell\cdot\hat{\mathbf{a}}_{i}\hat{\mathbf{s}}}$ where
$\ell=(\hat{\mathbf{A}}^{-1}\widehat{\mathbf{z}})_{i}\in\mathbb{F}_{p}$:

$\displaystyle{|{\psi}\rangle}$
$\displaystyle=q^{-k/2}\cdot\sum_{\mathbf{z}\in\mathbb{F}_{q}^{k}}{|{\widehat{\mathbf{z}}}\rangle}\otimes\omega_{p}^{-(\hat{\mathbf{A}}^{-1}\widehat{\mathbf{z}})_{1}\cdot\widehat{\mathbf{a}_{1}}\cdot\hat{\mathbf{s}}}{|{\psi_{\widehat{\mathbf{a}_{1}}}}\rangle}\otimes\ldots\otimes\omega_{p}^{-(\hat{\mathbf{A}}^{-1}\widehat{\mathbf{z}})_{T}\cdot\widehat{\mathbf{a}_{T}}\cdot\hat{\mathbf{s}}}{|{\psi_{\widehat{\mathbf{a}_{T}}}}\rangle}$
(30)
$\displaystyle=q^{-k/2}\cdot\sum_{\mathbf{z}\in\mathbb{F}_{q}^{k}}{|{\widehat{\mathbf{z}}}\rangle}\otimes\omega_{p}^{-\hat{\mathbf{s}}\cdot\hat{\mathbf{A}}\cdot\hat{\mathbf{A}}^{-1}\cdot\hat{\mathbf{z}}}{|{\psi_{\widehat{\mathbf{a}_{1}}}}\rangle}\otimes\ldots\otimes{|{\psi_{\widehat{\mathbf{a}_{T}}}}\rangle}$
(31)
$\displaystyle=\left(q^{-k/2}\cdot\sum_{\mathbf{z}\in\mathbb{F}_{q}^{k}}\omega_{p}^{-\hat{\mathbf{s}}\cdot\hat{\mathbf{z}}}{|{\hat{\mathbf{z}}}\rangle}\right)\otimes{|{\psi_{\widehat{\mathbf{a}_{1}}}}\rangle}\otimes\ldots\otimes{|{\psi_{\widehat{\mathbf{a}_{T}}}}\rangle}$
(32)

In this case measuring register 1 in the $\mathbb{F}_{p}^{T}$ Fourier basis
results in outcome $-\hat{\mathbf{s}}$ with probability $1$. Taking the
negation of the answer yields ${\cal O}=\hat{\mathbf{s}}$.

Running time: Since

$\sigma<d/n$

then by Lemma 14 we can sample PCS states
${|{\psi_{\widehat{\mathbf{a}}}}\rangle}$ such that $\widehat{\mathbf{a}}\sim
U[\mathbb{F}_{p}^{T}]$ in time ${\rm poly}(n,\log(q))$. So by independence of
sampling this implies that the entries of $\hat{\mathbf{A}}$ are i.i.d.
uniform on $\mathbb{F}_{p}$. By Lemma 10 this implies that

$\Pr(\hat{\mathbf{A}}\mbox{ is
invertible})\geq\prod_{k=1}^{\infty}(1-p^{-k})-e^{-cT}\geq
1-\sum_{k=1}^{\infty}p^{-k}-e^{-cT}=1-\frac{1/p}{1-1/p}-e^{-cT}$
$=\frac{1-2/p}{1-1/p}-e^{-cT}\geq 1/4$

where the last inequality follows from assuming $p\geq 3$ and sufficiently
large $T$. It follows that after $O(1)$ iterations of Step 1 the matrix
$\hat{\mathbf{A}}$ is invertible. The rest of the computational steps: namely
the Quantum Fourier Transform, the controlled shift operation, and
multiplication by $\hat{\mathbf{A}},\hat{\mathbf{A}}^{-1}$ all take time at
most ${\rm poly}(n,p,\log(q))$, where the extra factor of $p$ comes from the
fact that $U_{\mathbf{t}}^{p}$ is implemented as $p$ sequential applications
of $U_{\mathbf{t}}$.

∎

##  5 Acknowledgements

The author thanks Léo Ducas, Saeed Mehraban, Peter Shor, Nicolas Sendrier, and
an anonymous reviewer for their useful comments and suggestions.

## References

  * [BMT78] E. Berlekamp, R. McEliece and H. Tilborg  “On the inherent intractability of certain coding problems (Corresp.)”  In _IEEE Transactions on Information Theory_ 24.3, 1978, pp. 384–386  DOI: 10.1109/TIT.1978.1055873
  * [Aro+97] Sanjeev Arora, László Babai, Jacques Stern and Z Sweedyk  “The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations”  In _Journal of Computer and System Sciences_ 54.2, 1997, pp. 317–331  DOI: https://doi.org/10.1006/jcss.1997.1472
  * [CS98] Anne Canteaut and Nicolas Sendrier  “Cryptanalysis of the Original McEliece Cryptosystem”  In _Advances in Cryptology — ASIACRYPT’98_ Berlin, Heidelberg: Springer Berlin Heidelberg, 1998, pp. 187–199
  * [Din+03] I. Dinur, Guy Kindler, R. Raz and S. Safra  “Approximating CVP to Within Almost-Polynomial Factors is NP-Hard”  In _Combinatorica_ 23, 2003, pp. 205–243  DOI: 10.1007/s00493-003-0019-y
  * [Reg03] O. Regev  “Improved inapproximability of lattice and coding problems with preprocessing”  In _18th IEEE Annual Conference on Computational Complexity, 2003\. Proceedings._ , 2003, pp. 363–370  DOI: 10.1109/CCC.2003.1214435
  * [LM09] Vadim Lyubashevsky and Daniele Micciancio  “On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem”  In _Advances in Cryptology - CRYPTO 2009_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2009, pp. 577–594
  * [Pei09] Chris Peikert  “Public-key cryptosystems from the worst-case shortest vector problem: extended abstract”  In _Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009_ ACM, 2009, pp. 333–342  DOI: 10.1145/1536414.1536461
  * [Reg09] Oded Regev  “On lattices, learning with errors, random linear codes, and cryptography”  In _J. ACM_ 56.6 New York, NY, USA: ACM, 2009, pp. 1–40
  * [Map10] Kenneth Maples  “Singularity of Random Matrices over Finite Fields”  In _arXiv: Combinatorics_ , 2010
  * [Pet10] Christiane Peters  “Information-Set Decoding for Linear Codes over Fq”  In _Post-Quantum Cryptography_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 81–94
  * [Bra+13] Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev and Damien Stehlé  “Classical Hardness of Learning with Errors”  In _STOC’13_ , 2013, pp. 575–584  DOI: 10.1145/2488608.2488680
  * [Ber+18] Daniel J. Bernstein, Tung Chou, Tanja Lange, Ingo Maurich, Rafael Misoczki, Ruben Niederhagen, Edoardo Persichetti, Christiane Peters, Peter Schwabe, Nicolas Sendrier, Jakub Szefer and Wen Wang  “Classic McEliece: conservative code-based cryptography”  In _PQCRYPTO Mini-School and Workshop_ , 2018
  * [HTW19] Anna-Lena Horlemann-Trautmann and Violetta Weger  “Information set decoding in the Lee metric with applications to cryptography”  In _Advances in Mathematics of Communications_ 15, 2019  DOI: 10.3934/amc.2020089
  * [CDE21] André Chailloux, Thomas Debris-Alazard and Simona Etinski  “Classical and Quantum Algorithms for Generic Syndrome Decoding Problems and Applications to the Lee Metric”  In _Post-Quantum Cryptography - 12th International Workshop, PQCrypto 2021, Daejeon, South Korea, July 20-22, 2021, Proceedings_ 12841, Lecture Notes in Computer Science  Springer, 2021, pp. 44–62  DOI: 10.1007/978-3-030-81293-5“˙3
  * [EH22] Lior Eldar and Sean Hallgren  “An efficient quantum algorithm for lattice problems achieving subexponential approximation factor”  In _CoRR_ abs/2201.13450, 2022  arXiv: https://arxiv.org/abs/2201.13450
  * [Nis] URL: https://csrc.nist.gov/News/2020/pqc-third-round-candidate-announcement

##  Appendix A Proof of Technical Lemmas

###  A.1 Proof of Lemma 4

###### Proof.

Consider $\mathbf{a}_{1},\ldots,\mathbf{a}_{k}$ random vectors in
$\mathbb{F}_{q}^{n}$ that generate ${\cal C}$, and a vector of coefficients
$\mathbf{x}=(x_{1},\ldots,x_{k})\in\mathbb{F}_{q}^{k}$. We have

$\displaystyle\Pr\left(\exists\mathbf{c}\in{\cal C},\ \mathbf{c}\neq 0\
\|\mathbf{c}\|_{\rm M}\leq n\cdot q^{1-k/n}/2\right)$
$\displaystyle\leq\Pr_{\mathbf{a}_{1},\ldots\mathbf{a}_{k}}\left(\exists\mathbf{x}\in\mathbb{F}_{q}^{k},\mathbf{x}\neq
0,\quad\left\|\sum_{i=1}^{k}\mathbf{a}_{i}x_{i}\right\|_{\rm M}\leq n\cdot
q^{1-k/n}/2\right)$ (33) $\displaystyle\leq q^{k}\cdot\Pr_{\mathbf{a}_{i}\sim
U[\mathbb{F}_{q}^{n}],\mathbf{x}\neq
0}\left(\left\|\sum_{i=1}^{k}\mathbf{a}_{i}x_{i}\right\|_{\rm M}\leq n\cdot
q^{1-k/n}/2\right)$ (34)

Considering the above, for any nonzero $\mathbf{x}\in\mathbb{F}_{q}^{k}$ each
coordinate $z_{j}\in\mathbb{F}_{q},j\in[n]$ of
$\mathbf{z}=\sum_{i}\mathbf{a}_{i}x_{i}$ is a uniformly random variable on
$\mathbb{F}_{q}$ that is independent of all other coordinates. We have

$\Pr(|z_{j}|\leq q^{1-k/n})\leq q^{-k/n}.$

Thus, by Chernoff:

$\Pr\left(\sum_{i}|z_{i}|\leq n\cdot q^{1-k/n}/2\right)\leq
2^{-n\cdot(q^{-k/n})^{2}/16}\leq 2^{-n/200}$

where the last inequality follows from $n\geq k\log(q)$. Applying the
contrapositive of Proposition 9 we conclude that

$\Pr\left(\min_{\mathbf{x}\neq\mathbf{y},\mathbf{x},\mathbf{y}\in{\cal
C}}\Delta_{M,q}(\mathbf{x},\mathbf{y})<q^{1-k/n}/2\right)<2^{-n/200}$

∎

###  A.2 Proof of Theorem 3

Consider the problem of $c$-approximate set-cover: a ground-set ${\cal U}$,
and a collection of subsets $S_{1},\ldots,S_{m}$. A cover is a sub-collection
of the $S_{i}$’s whose union is ${\cal U}$. The cover is exact if the sets in
the cover are disjoint. The size of a cover is the number of sets that
comprise it.

The construction of [Aro+97] defines $m+1$ vectors
$b_{0},\ldots,b_{m}\in\mathbb{F}_{2}^{r}$, $r=L|{\cal U}|+m$, $L=cK$ as
follows: for each set $S_{i}$ we define a vector $b_{i}$ on $L\cdot|U|+m$. The
first $L|{\cal U}|$ coordinates are considered as $|{\cal U}|$ tuples of $L$
coordinates each, where each tuple corresponds to an element of ${\cal U}$.
$b_{i}$ is zero except for the $L\cdot|S_{i}|$ coordinates corresponding to
the characteristic vector of $S_{i}$. The last $m$ coordinates are zero except
at the $i$-th position which is $1$. The vector $b_{0}$ is the all-ones vector
on the first $L|{\cal U}|$ coordinates, and $0$ on the last $m$. We now claim
similarly to [Aro+97]:

######  Lemma 18.

Let $q=p^{m}$ and suppose that $c>p$. Let $L=c\cdot K$. Define:

${\rm OPT}=\min_{\alpha}\Delta_{{\rm
M}}\left(b_{0},\sum_{i}\alpha_{i}b_{i}\right)$

and let ${\cal C}$ denote the linear span of the vector $b_{1},\ldots,b_{m}$
over $\mathbb{F}_{q}$. If there exists an exact cover of size $K$ then

$\displaystyle\Delta_{{\rm M}}(b_{0},{\cal C})\leq p\cdot K$ (35)

and if any cover is of size at most $c\cdot K$ then

$\displaystyle\Delta_{{\rm M}}(b_{0},{\cal C})\geq c\cdot K$ (36)

###### Proof.

Let $p$ denote the characteristic of $\mathbb{F}_{q}$, i.e. $q=p^{m}$ for some
integer $m>0$. If there exists an exact cover $S_{i_{1}},\ldots,S_{i_{K}}$
then choosing $\alpha_{i_{j}}=p-1$ for all $j\in[K]$ and $0$ otherwise has
that $b_{0}+\sum_{i}\alpha_{i}b_{i}$ is equal to $0$ on the first $|{\cal
U}|L$ bits. On the last $m$ bits the Manhattan weight of
$b_{0}+\sum_{i}\alpha_{i}b_{i}$ is precisely $\sum_{i}\alpha_{i}=(p-1)\cdot
K$. Hence

$\Delta_{{\rm M}}(b_{0},{\cal C})\leq(p-1)\cdot K$

Suppose now that any cover has size at least $L=c\cdot K$. Let
$\alpha=(\alpha_{1},\ldots,\alpha_{r})$ denote an assignment vector
$\alpha_{i}\in\mathbb{F}_{q}$. First, suppose that $\sum_{i}\alpha_{i}b_{i}$
has non-zero coordinates on each of the first $|{\cal U}|$ tuples of $L$ bits.
Then each tuple is ”covered” by at least one vector $b_{i}$, that corresponds
to set $S_{i}$, and $b_{i}$ is multiplied by a non-zero coefficient
$\alpha_{i}$. Thus $\sum_{i}\alpha_{i}\geq c\cdot K=L$ this is manifested in
the last $m$ coordinates, implying

$\Delta_{{\rm M}}(b_{0},\sum_{i}\alpha_{i}b_{i})\geq L$

On the other hand, if not all tuples are covered, i.e. there is at least one
$L$-tuple that is all zeros, then the Manhattan distance on the first $|{\cal
U}|L$ coordinates is at least $L$, implying

$\Delta_{{\rm M}}(b_{0},\sum_{i}\alpha_{i}b_{i})\geq L$

∎

The proof of Theorem 3 follows by applying the lemma in conjunction with the
fact that there exists a constant $c>0$ such that it is NP-hard to approximate
exact set-cover to factor at most $c$.