Laboratoire de Physique Théorique
Toulouse - UMR 5152

Une des motivations de l’information quantique est de proposer des algorithmes adaptés à un futur ordinateur quantique permettant de rendre plus performants des algorithmes dits « classiques », c’est-à-dire ceux utilisés de nos jours sur nos ordinateurs. Dans cette optique, trois chercheurs du LPT de Toulouse et du LPTMS d’Orsay ont récemment publié dans Physical Review Letters (de juin 2010) un travail où ils proposent une version quantique de l’algorithme dit de « couplage depuis le passé », proposé il y a une quinzaine d’années par James Propp et David Wilson. Cet algorithme célèbre permet d’échantillonner exactement des configurations d’un système parmi un grande nombre, et ceci selon une distribution de probabilités connue mais quelconque. Il s’agit d’une problématique récurrente aussi bien en mathématiques appliquées ou en informatique qu’en physique théorique. L’idée clé de cet algorithme est de suivre en parallèle l’histoire de toutes les configurations possibles lorsqu’elles évoluent selon un algorithme Monte Carlo traditionnel. Lorsque toutes ces histoires on convergé vers une même configuration, alors cette dernière est exactement distribuée selon la distribution souhaitée. Malheureusement, en pratique, suivre toutes ces histoires est prohibitif en termes de capacités de calcul. D’où l’idée proposée par les trois chercheurs de paralléliser cette tâche sur un processeur quantique, qui y est naturellement adapté. La dernière étape de leur algorithme quantique, la détection de la convergence, requiert l’utilisation de l’algorithme de Grover, un algorithme célèbre de l’information quantique, qui permet de trouver efficacement un élément dans une liste non structurée.

En haut : l’algorithme de Propp et Wilson schématisé, où chaque ligne horizontale représente une configuration et où chaque colonne représente un pas de l’algorithme ; une suite de flèches vertes représente une histoire, et toutes ces histoires ont convergé vers la même configuration (l’état 2 ici) à la fin de l’algorithme. En bas : la version quantique d’un pas, où chaque ligne représente maintenant un bit quantique (ou « qubit »).

Les détails se trouvent dans l’article
Quantum algorithm for exact Monte Carlo sampling
N. Destainville, B. Georgeot, O. Giraud
Phys. Rev. Lett. 104, 250502 (2010)