  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 Stehl\'e-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.
