Quantum Fourier Sampling, Code Equivalence, and the Quantum Security of the McEliece and Sidelnikov Cryptosystems
The Code Equivalence problem is that of determining whether two given linear codes are equivalent to each other up to a permutation of the coordinates. This problem has a direct reduction to a non abelian Hidden Subgroup Problem (HSP), suggesting a possible quantum algorithm analogous to Shor's algorithms for factoring or discrete log. However, in Dinh et al. , the authors showed that in many cases of interest - including Goppa codes - solving this case of the HSP requires rich, entangled measurements. Thus, solving these cases of Code Equivalence via Fourier sampling appears to be out of reach of current families of quantum algorithms.