.svg)
The Classiq Engine II : Electric Boogaloo (ou comment chercher une aiguille dans une botte de foin)
Dans notre précédent billet sur le moteur Classiq, nous avons commencé à expliquer ce que fait le moteur et nous avons donné un petit aperçu de la façon dont il le fait, à savoir l'algorithme de backtracking.
Cette fois, nous allons plonger dans le monde de la résolution des CSP (problèmes de satisfaction de contraintes). L'algorithme de retour en arrière est un moyen très simple de résoudre les CSP, mais il nécessite de parcourir l'ensemble de l'espace de recherche. Dans la plupart des CSP, cela est inacceptable - l'espace de recherche est tout simplement trop grand (exponentiel dans le meilleur des cas). Reprenons l'exemple du Sudoku mentionné dans l'article précédent. Il y a 9^81 façons possibles de remplir une planche de Sudoku. Cela équivaut à un peu moins de 2e77 (c'est-à-dire 2 suivi de 77 zéros). Même si nous considérons un exemple simple où la moitié des cases sont déjà remplies pour nous, nous avons environ 1,5e38 options possibles. Les examiner toutes prendrait trop de temps.
Dans cet article, nous allons expliquer comment nous pouvons améliorer l'algorithme de backtracking, ou en d'autres termes, comment vous pouvez chercher une aiguille dans une botte de foin de manière efficace.
Au début
Le mot backtracking va être mentionné à plusieurs reprises dans ce billet, mais nous n'avons même pas encore dit ce qu'il signifie, alors revenons en arrière (je suis désolé).
Les CSP sont définis comme un ensemble de variables, chacune avec un domaine de valeurs valides, et un ensemble de contraintes sur les affectations à ces variables. Une solution valide est une affectation de valeurs à toutes les variables telle que toutes les contraintes sont satisfaites.
L'algorithme de backtracking tente de construire progressivement une solution valide en affectant successivement une valeur à chaque variable. Après chaque affectation, nous pouvons vérifier si les contraintes sont satisfaites (au moins pour certaines d'entre elles). Si une contrainte ne peut plus être satisfaite, la solution partielle actuelle est une impasse. Nous revenons alors en arrière, c'est-à-dire que nous attribuons à nouveau une valeur différente à la dernière variable assignée. S'il n'y a plus de valeurs valables, nous revenons en arrière (=backtrack) jusqu'à la variable précédente et lui réattribuons une valeur.
Si nous atteignons un état où toutes les variables sont attribuées et toutes les contraintes satisfaites, nous avons trouvé une solution valable ! En revanche, si nous épuisons toutes les options, cela signifie qu'il n'existe aucune solution valable.
Si vous avez été attentif, vous avez peut-être remarqué que l'algorithme fait déjà quelque chose d'assez intelligent : il s'arrête dès qu'il reconnaît qu'une contrainte n'est plus satisfaisable.
Je sais, cela semble trivial. En effet, si vous résolvez un Sudoku et que vous trouvez une erreur, vous essayez immédiatement de la corriger, plutôt que de continuer à résoudre. Cependant, cette simple chose réduit déjà considérablement la taille de l'espace de recherche - inutile de continuer à chercher si l'on peut dire, à l'avance, que la recherche est futile. Nous reviendrons sur cette notion plus tard.
Je tiens également à souligner que de nombreuses choses "intelligentes" que nous faisons dans le backtracking peuvent sembler triviales. En effet, l'une des façons d'y parvenir est d'essayer de comprendre le processus de pensée d'une personne qui résout le même problème manuellement. Notre cerveau reste le meilleur ordinateur qui soit1.
Recherche ordonnée
En gardant cela à l'esprit, essayons d'imiter le processus de pensée d'une personne qui résout un Sudoku, et voyons où cela nous mène. Considérons un tableau de Sudoku partiellement rempli. Où allez-vous chercher la prochaine case à remplir ? Allez-vous regarder la colonne vide ou une colonne de 5 chiffres croisant une ligne de 4 chiffres ? Bien sûr, c'est cette dernière. Lorsque vous résolvez un Sudoku, vous recherchez naturellement les zones contenant de nombreux indices (c'est-à-dire les cases remplies). Demandons donc à notre ordinateur de faire de même !
Dans la résolution de CSP, on appelle cela l'heuristique d'ordre. En décrivant l'algorithme de backtracking, j'ai (implicitement) mentionné deux cas où l'algorithme fait des choix : décider quelle variable assigner ensuite, et décider quelle valeur lui assigner. Comment fait-il ces choix ? C'est à nous d'en décider. Nous pouvons implémenter des heuristiques qui l'aideront à prendre la bonne décision. Notez que les heuristiques ne garantissent pas que nous trouverons une solution valable immédiatement. Elles mettent normalement en œuvre une approche gourmande pour résoudre le problème, ce qui augmente la probabilité de trouver une solution valide plus tôt, tandis que l'algorithme de retour en arrière garantit que nous itérons toujours sur toutes les possibilités.
Notre exemple de Sudoku peut être considéré comme une variante de l'heuristique des valeurs restantes les plus faibles (LRV), qui nous dicte d'essayer d'attribuer une valeur à la variable ayant le plus petit nombre de valeurs valides restantes. Ces variables vont probablement poser un défi, il est donc bon de s'y attaquer dès le début.
Nous n'avons pas abordé les circuits quantiques aujourd'hui. Comme mentionné dans l'article précédent, le moteur Classiq alloue des ressources aux différentes fonctions du circuit. Dans quel ordre doit-il allouer les ressources ? Une réponse naturelle est l'ordre topologique du circuit, c'est-à-dire que si une fonction doit être appliquée avant une autre, alors nous devrions allouer ses ressources plus tôt. Bien qu'il ne soit pas nécessaire d'allouer les ressources dans cet ordre, cela permet au moteur d'identifier plus facilement les situations où les contraintes ne peuvent plus être satisfaites et constitue donc une bonne heuristique.
Que se passe-t-il si deux fonctions peuvent être appliquées dans l'un ou l'autre ordre ? Ici, il n'y a pas nécessairement de réponse naturelle. Cependant, nous pouvons utiliser une autre heuristique populaire : l'heuristique de la variable la plus contraignante (VPC), qui nous dicte de choisir la variable qui impose le plus de contraintes aux variables restantes. Dans ce cas, il s'agirait de la fonction qui nécessite le plus de ressources.
Qu'en est-il de la détermination de l'ordre des valeurs ? Une heuristique courante est celle de la valeur la moins contraignante (LCV2) : il s'agit de choisir la valeur qui, si elle est attribuée à la variable, exclut le moins de valeurs pour les autres variables. Par exemple, si nous essayons de synthétiser un circuit avec un nombre limité de qubits, nous essaierons d'abord d'allouer moins de qubits aux fonctions (afin que les fonctions suivantes disposent de plus de qubits). Encore une fois, cela peut nous sembler trivial, mais l'algorithme ne saurait pas comment le faire si nous ne lui disons pas explicitement de le faire.
L'oiseau matinal attrape le ver
J'ai indiqué précédemment que nous voulions arrêter la recherche dès qu'une seule contrainte n'est plus satisfaisante. Nous pouvons reprendre cette idée et l'étendre beaucoup plus loin. Parfois, il est facile de dire qu'une contrainte est insatisfaisante, par exemple si vous avez rempli une colonne avec tous les chiffres 1 à 8, mais que la ligne du dernier carré restant contient déjà un 9. Mais parfois, il faut regarder un peu plus loin. Il y a peut-être trois cases restantes dans une colonne, mais deux des chiffres manquants doivent se trouver dans la même case. Cela ne saute pas immédiatement aux yeux, mais avec suffisamment de réflexion, vous pouvez comprendre que cette contrainte est insatisfaisante.
Il existe différentes façons de mettre en œuvre ces idées dans la résolution de CSP. La première que nous allons aborder est le forward checking. Dans ce cas, nous allons garder une trace des valeurs valides restantes pour chaque variable (notez que cela peut également être utilisé pour mettre en œuvre l'heuristique d'ordre mentionnée plus tôt). Si vous avez déjà été bloqué dans la résolution d'un Sudoku et que vous avez commencé à écrire toutes les valeurs possibles dans les coins des carrés, c'est exactement cela.
Après chaque affectation, nous passerons en revue les valeurs valides restantes et supprimerons toute valeur qui n'est plus valide (en vérifiant les contraintes correspondantes). S'il n'y a plus de valeur valide, nous pouvons immédiatement revenir en arrière - cette affectation ne peut pas nous conduire à une solution valide.
Mais cette méthode n'est pas suffisante pour l'exemple ci-dessus - tous les carrés auront au moins une valeur valide. Nous devons faire quelque chose de plus sophistiqué. Nous avons besoin de la cohérence des arcs.
La cohérence des arcs s'intéresse aux paires de variables qui font partie de la même contrainte, plutôt qu'aux variables individuelles. Pour s'assurer qu'une valeur est valide, nous vérifions s'il existe une valeur valide de l'autre variable qui peut lui être associée pour satisfaire leur contrainte commune. Si nous n'en trouvons pas, alors cette valeur est certainement invalide : si nous la choisissons, nous ne parviendrons pas à satisfaire cette contrainte partagée.
Cela devient confus, n'est-ce pas ? Parfois, les choses triviales que nous faisons dans notre tête nécessitent un certain travail pour être traduites en algorithme. Et ce n'est pas tout : la cohérence des chemins s'intéresse aux triplets de variables, tandis que la k-consistance s'intéresse aux k-tuples de variables ! Ces questions sont assez complexes, mais le principe reste le même : plus tôt nous nous rendons compte que cette solution partielle est une impasse, mieux c'est.
Quand cela en vaut-il la peine ?
Toutes les méthodes évoquées jusqu'à présent nécessitent des calculs non triviaux. Leur exécution répétée au milieu d'une recherche déjà très longue peut-elle entraîner une dégradation du temps d'exécution ? Dans le pire des cas, la réponse est oui. Vous pourriez probablement construire un cas limite où tous les calculs sont inutiles, et où l'algorithme pourrait tout aussi bien essayer toutes les solutions possibles dans un ordre aléatoire. Mais dans la pratique, il est presque toujours avantageux d'effectuer ces calculs supplémentaires. Les problèmes que nous traitons dans la résolution de CSP sont au mieux de taille exponentielle, et donc tout sous-espace dans lequel nous n'avons pas à chercher est un énorme avantage. Si nos calculs sont polynomiaux, il sera toujours préférable de les effectuer plutôt que d'effectuer une recherche plus approfondie.
Est-ce que c'est ça ?
Non.
Avec les solveurs CSP, il n'y a jamais de fin. Vous pouvez toujours trouver de nouvelles heuristiques ou améliorer votre implémentation pour réduire le temps d'exécution de quelques pourcents. Il existe également des techniques encore plus complexes, telles que le backjumping ou l'apprentissage par contraintes.
C'est une course sans fin à l'amélioration pour que le moteur Classiq puisse synthétiser des circuits plus complexes encore plus rapidement.
1 En fait, c'est quelque chose que je dis toujours aux personnes qui débutent en programmation : les ordinateurs sont assez stupides, ils font exactement ce qu'on leur dit. La seule raison pour laquelle nous les utilisons est qu'ils le font beaucoup plus rapidement que les humains. Le backtracking en est un bon exemple.
2 LRV, MCV et LCV. Oui, les acronymes en informatique peuvent prêter à confusion.
Dans notre précédent billet sur le moteur Classiq, nous avons commencé à expliquer ce que fait le moteur et nous avons donné un petit aperçu de la façon dont il le fait, à savoir l'algorithme de backtracking.
Cette fois, nous allons plonger dans le monde de la résolution des CSP (problèmes de satisfaction de contraintes). L'algorithme de retour en arrière est un moyen très simple de résoudre les CSP, mais il nécessite de parcourir l'ensemble de l'espace de recherche. Dans la plupart des CSP, cela est inacceptable - l'espace de recherche est tout simplement trop grand (exponentiel dans le meilleur des cas). Reprenons l'exemple du Sudoku mentionné dans l'article précédent. Il y a 9^81 façons possibles de remplir une planche de Sudoku. Cela équivaut à un peu moins de 2e77 (c'est-à-dire 2 suivi de 77 zéros). Même si nous considérons un exemple simple où la moitié des cases sont déjà remplies pour nous, nous avons environ 1,5e38 options possibles. Les examiner toutes prendrait trop de temps.
Dans cet article, nous allons expliquer comment nous pouvons améliorer l'algorithme de backtracking, ou en d'autres termes, comment vous pouvez chercher une aiguille dans une botte de foin de manière efficace.
Au début
Le mot backtracking va être mentionné à plusieurs reprises dans ce billet, mais nous n'avons même pas encore dit ce qu'il signifie, alors revenons en arrière (je suis désolé).
Les CSP sont définis comme un ensemble de variables, chacune avec un domaine de valeurs valides, et un ensemble de contraintes sur les affectations à ces variables. Une solution valide est une affectation de valeurs à toutes les variables telle que toutes les contraintes sont satisfaites.
L'algorithme de backtracking tente de construire progressivement une solution valide en affectant successivement une valeur à chaque variable. Après chaque affectation, nous pouvons vérifier si les contraintes sont satisfaites (au moins pour certaines d'entre elles). Si une contrainte ne peut plus être satisfaite, la solution partielle actuelle est une impasse. Nous revenons alors en arrière, c'est-à-dire que nous attribuons à nouveau une valeur différente à la dernière variable assignée. S'il n'y a plus de valeurs valables, nous revenons en arrière (=backtrack) jusqu'à la variable précédente et lui réattribuons une valeur.
Si nous atteignons un état où toutes les variables sont attribuées et toutes les contraintes satisfaites, nous avons trouvé une solution valable ! En revanche, si nous épuisons toutes les options, cela signifie qu'il n'existe aucune solution valable.
Si vous avez été attentif, vous avez peut-être remarqué que l'algorithme fait déjà quelque chose d'assez intelligent : il s'arrête dès qu'il reconnaît qu'une contrainte n'est plus satisfaisable.
Je sais, cela semble trivial. En effet, si vous résolvez un Sudoku et que vous trouvez une erreur, vous essayez immédiatement de la corriger, plutôt que de continuer à résoudre. Cependant, cette simple chose réduit déjà considérablement la taille de l'espace de recherche - inutile de continuer à chercher si l'on peut dire, à l'avance, que la recherche est futile. Nous reviendrons sur cette notion plus tard.
Je tiens également à souligner que de nombreuses choses "intelligentes" que nous faisons dans le backtracking peuvent sembler triviales. En effet, l'une des façons d'y parvenir est d'essayer de comprendre le processus de pensée d'une personne qui résout le même problème manuellement. Notre cerveau reste le meilleur ordinateur qui soit1.
Recherche ordonnée
En gardant cela à l'esprit, essayons d'imiter le processus de pensée d'une personne qui résout un Sudoku, et voyons où cela nous mène. Considérons un tableau de Sudoku partiellement rempli. Où allez-vous chercher la prochaine case à remplir ? Allez-vous regarder la colonne vide ou une colonne de 5 chiffres croisant une ligne de 4 chiffres ? Bien sûr, c'est cette dernière. Lorsque vous résolvez un Sudoku, vous recherchez naturellement les zones contenant de nombreux indices (c'est-à-dire les cases remplies). Demandons donc à notre ordinateur de faire de même !
Dans la résolution de CSP, on appelle cela l'heuristique d'ordre. En décrivant l'algorithme de backtracking, j'ai (implicitement) mentionné deux cas où l'algorithme fait des choix : décider quelle variable assigner ensuite, et décider quelle valeur lui assigner. Comment fait-il ces choix ? C'est à nous d'en décider. Nous pouvons implémenter des heuristiques qui l'aideront à prendre la bonne décision. Notez que les heuristiques ne garantissent pas que nous trouverons une solution valable immédiatement. Elles mettent normalement en œuvre une approche gourmande pour résoudre le problème, ce qui augmente la probabilité de trouver une solution valide plus tôt, tandis que l'algorithme de retour en arrière garantit que nous itérons toujours sur toutes les possibilités.
Notre exemple de Sudoku peut être considéré comme une variante de l'heuristique des valeurs restantes les plus faibles (LRV), qui nous dicte d'essayer d'attribuer une valeur à la variable ayant le plus petit nombre de valeurs valides restantes. Ces variables vont probablement poser un défi, il est donc bon de s'y attaquer dès le début.
Nous n'avons pas abordé les circuits quantiques aujourd'hui. Comme mentionné dans l'article précédent, le moteur Classiq alloue des ressources aux différentes fonctions du circuit. Dans quel ordre doit-il allouer les ressources ? Une réponse naturelle est l'ordre topologique du circuit, c'est-à-dire que si une fonction doit être appliquée avant une autre, alors nous devrions allouer ses ressources plus tôt. Bien qu'il ne soit pas nécessaire d'allouer les ressources dans cet ordre, cela permet au moteur d'identifier plus facilement les situations où les contraintes ne peuvent plus être satisfaites et constitue donc une bonne heuristique.
Que se passe-t-il si deux fonctions peuvent être appliquées dans l'un ou l'autre ordre ? Ici, il n'y a pas nécessairement de réponse naturelle. Cependant, nous pouvons utiliser une autre heuristique populaire : l'heuristique de la variable la plus contraignante (VPC), qui nous dicte de choisir la variable qui impose le plus de contraintes aux variables restantes. Dans ce cas, il s'agirait de la fonction qui nécessite le plus de ressources.
Qu'en est-il de la détermination de l'ordre des valeurs ? Une heuristique courante est celle de la valeur la moins contraignante (LCV2) : il s'agit de choisir la valeur qui, si elle est attribuée à la variable, exclut le moins de valeurs pour les autres variables. Par exemple, si nous essayons de synthétiser un circuit avec un nombre limité de qubits, nous essaierons d'abord d'allouer moins de qubits aux fonctions (afin que les fonctions suivantes disposent de plus de qubits). Encore une fois, cela peut nous sembler trivial, mais l'algorithme ne saurait pas comment le faire si nous ne lui disons pas explicitement de le faire.
L'oiseau matinal attrape le ver
J'ai indiqué précédemment que nous voulions arrêter la recherche dès qu'une seule contrainte n'est plus satisfaisante. Nous pouvons reprendre cette idée et l'étendre beaucoup plus loin. Parfois, il est facile de dire qu'une contrainte est insatisfaisante, par exemple si vous avez rempli une colonne avec tous les chiffres 1 à 8, mais que la ligne du dernier carré restant contient déjà un 9. Mais parfois, il faut regarder un peu plus loin. Il y a peut-être trois cases restantes dans une colonne, mais deux des chiffres manquants doivent se trouver dans la même case. Cela ne saute pas immédiatement aux yeux, mais avec suffisamment de réflexion, vous pouvez comprendre que cette contrainte est insatisfaisante.
Il existe différentes façons de mettre en œuvre ces idées dans la résolution de CSP. La première que nous allons aborder est le forward checking. Dans ce cas, nous allons garder une trace des valeurs valides restantes pour chaque variable (notez que cela peut également être utilisé pour mettre en œuvre l'heuristique d'ordre mentionnée plus tôt). Si vous avez déjà été bloqué dans la résolution d'un Sudoku et que vous avez commencé à écrire toutes les valeurs possibles dans les coins des carrés, c'est exactement cela.
Après chaque affectation, nous passerons en revue les valeurs valides restantes et supprimerons toute valeur qui n'est plus valide (en vérifiant les contraintes correspondantes). S'il n'y a plus de valeur valide, nous pouvons immédiatement revenir en arrière - cette affectation ne peut pas nous conduire à une solution valide.
Mais cette méthode n'est pas suffisante pour l'exemple ci-dessus - tous les carrés auront au moins une valeur valide. Nous devons faire quelque chose de plus sophistiqué. Nous avons besoin de la cohérence des arcs.
La cohérence des arcs s'intéresse aux paires de variables qui font partie de la même contrainte, plutôt qu'aux variables individuelles. Pour s'assurer qu'une valeur est valide, nous vérifions s'il existe une valeur valide de l'autre variable qui peut lui être associée pour satisfaire leur contrainte commune. Si nous n'en trouvons pas, alors cette valeur est certainement invalide : si nous la choisissons, nous ne parviendrons pas à satisfaire cette contrainte partagée.
Cela devient confus, n'est-ce pas ? Parfois, les choses triviales que nous faisons dans notre tête nécessitent un certain travail pour être traduites en algorithme. Et ce n'est pas tout : la cohérence des chemins s'intéresse aux triplets de variables, tandis que la k-consistance s'intéresse aux k-tuples de variables ! Ces questions sont assez complexes, mais le principe reste le même : plus tôt nous nous rendons compte que cette solution partielle est une impasse, mieux c'est.
Quand cela en vaut-il la peine ?
Toutes les méthodes évoquées jusqu'à présent nécessitent des calculs non triviaux. Leur exécution répétée au milieu d'une recherche déjà très longue peut-elle entraîner une dégradation du temps d'exécution ? Dans le pire des cas, la réponse est oui. Vous pourriez probablement construire un cas limite où tous les calculs sont inutiles, et où l'algorithme pourrait tout aussi bien essayer toutes les solutions possibles dans un ordre aléatoire. Mais dans la pratique, il est presque toujours avantageux d'effectuer ces calculs supplémentaires. Les problèmes que nous traitons dans la résolution de CSP sont au mieux de taille exponentielle, et donc tout sous-espace dans lequel nous n'avons pas à chercher est un énorme avantage. Si nos calculs sont polynomiaux, il sera toujours préférable de les effectuer plutôt que d'effectuer une recherche plus approfondie.
Est-ce que c'est ça ?
Non.
Avec les solveurs CSP, il n'y a jamais de fin. Vous pouvez toujours trouver de nouvelles heuristiques ou améliorer votre implémentation pour réduire le temps d'exécution de quelques pourcents. Il existe également des techniques encore plus complexes, telles que le backjumping ou l'apprentissage par contraintes.
C'est une course sans fin à l'amélioration pour que le moteur Classiq puisse synthétiser des circuits plus complexes encore plus rapidement.
1 En fait, c'est quelque chose que je dis toujours aux personnes qui débutent en programmation : les ordinateurs sont assez stupides, ils font exactement ce qu'on leur dit. La seule raison pour laquelle nous les utilisons est qu'ils le font beaucoup plus rapidement que les humains. Le backtracking en est un bon exemple.
2 LRV, MCV et LCV. Oui, les acronymes en informatique peuvent prêter à confusion.
A propos de "The Qubit Guy's Podcast" (Le podcast du gars de Qubit)
Animé par The Qubit Guy (Yuval Boger, notre directeur marketing), le podcast accueille des leaders d'opinion de l'informatique quantique pour discuter de questions commerciales et techniques qui ont un impact sur l'écosystème de l'informatique quantique. Nos invités fournissent des informations intéressantes sur les logiciels et algorithmes d'ordinateurs quantiques, le matériel informatique quantique, les applications clés de l'informatique quantique, les études de marché de l'industrie quantique et bien plus encore.
Si vous souhaitez proposer un invité pour le podcast, veuillez nous contacter.
