  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.
