Biased Quantum Walks as Value Heuristics for the Quantum Backtracking Algorithm

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 util-isant 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 backtrack-ing 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 propa-gation 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.

Abstract

The backtracking algorithm is one of the fundamental methods of constraint programming for the resolution of combinatorial problems by the enumeration of the search space. For most problems, this enumeration can be e˙ectively guided to a solution by the use of heuristics; both in the choice of variable and value branching. While we are still at the dawn of quantum computation, a quantum walk-based quantum backtracking algorithm providing a quadratic speedup over its classical counterpart has already been developed. However, while the concept of variable-branching heuristics is easily applicable to the quantum algorithm as well, the quantum-walk nature of the value exploration does not permit the direct use of classical value-branching heuristics for the quantum backtracking algorithm.In this work we propose a modification of the quantum walk algorithm using amplitude amplification that induces a bias of the quantum walk probability distribution according to what we termed a value-distribution heuristic. We proceed to show the improvements in the simulated performance of the algorithm using a belief propagation-based value distribution on 28 000 partially-filled magic square instances. We then describe the preliminary work done on the determination of an estimate of a realistic circuit size for the backtracking algorithm with the belief propagation distribution calculations and the biased quantum walk.