Fiche de REMAUD Maxime

Titre : Applications of Quantum Fourier Sampling and the Dihedral Hidden Subgroup Problem
Date : 17 novembre 2023
Heure: 08:00
Résumé : Nous introduisons un algorithme quantique pour résoudre le problème de recherche de mot de poids faible dans un code aléatoire construit à partir d'un algorithme décodant son dual. Ceci est une adaptation en métrique de Hamming d'une réduction quantique entre problèmes analogues en métrique euclidienne, qui utilise la technique d'échantillonnage de Fourier quantique et une idée dûe à Regev. Nous rappelons ensuite comment résoudre le problème de classes diédrales (DCP), auquel la sécurité de cryptosystèmes (eg CSIDH) se réduit. Il peut-être résolu de manière directe à l'aide de CNOT et de mesures, ou alors réduit à un problème de subsetsum classique. Nous décrivons un algorithme d'une nouvelle sorte en s'inspirant des mêmes techniques qu'utilisées précédemment, réduisant le DCP à un problème de subsetsum quantique, ainsi qu'une interpolation qui en découle. Enfin, nous explorons l'approche n'utilisant que des CNOT et des mesures pour résoudre le DCP en utilisant peu d'espace.
Lieu : Inria de Paris