Biased Quantum Walks as Value Heuristics for the Quantum Backtracking Algorithm
Michel Fabrice Serret · PolyPublie (École Polytechnique de Montréal) · 2021
L'algorithme de retour arrière est une méthode de résolution de problèmes combinatoires par énumération des solutions utilisée dans le cadre de la programmation par contraintes.L'utilisation d'heuristiques permet dans de nombreux cas de guider la recherche en utilisant la structure du problème pour déterminer les branchements de variables et de valeurs.L'informatique quantique est un domaine en plein essor et un algorithme de backtracking quantique a été récemment développé utilisant des marches quantiques afin d'explorer l'arbre de retour arrière et permettant ainsi un gain quadratique en complexité algorithmique.Cependant, contrairement à l'applicabilité directe d'heuristiques de choix de variables à cette méthode, un équivalent d'heuristique de choix de valeurs n'est pas un résultat immédiat.Nous présentons dans ce mémoire une modification de la marche quantique de l'algorithme de retour arrière basée sur l'amplification d'amplitude afin de biaiser la marche quantique par une distribution de valeur a priori, méthode que nous appelons heuristique de distribution de valeurs.Nous montrons ensuite le gain de performance obtenu grâce à l'heuristique de distribution de valeurs en simulant la marche quantique sur 28 000 exemplaires de Carré Magique partiellement rempli en utilisant les distributions de valeurs obtenues par la propagation de croyance (Belief Propagation) sur les contraintes.Nous décrivons ensuite le travail préliminaire fait pour l'estimation de la taille du circuit de l'algorithme de retour arrière avec la propagation des croyances ainsi que l'heuristique de distribution de valeurs associée.Nous concluons sur les étapes restantes pour l'obtention d'une estimation réaliste de taille du circuit ainsi que par les nombreuses pistes de recherche autour de l'heuristique de distribution de valeurs.vi