Quantum Reduction of Finding Short Code Vectors to the Decoding Problem

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

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)…