Get best of the week

Comment π combine des blocs en collision et un algorithme de recherche quantique

Un physicien curieux a découvert un lien inattendu entre la théorie des blocs de collision et le célèbre algorithme de recherche quantique




Qu'ont en commun les chiffres de π, les blocs en collision et les algorithmes de recherche quantique? Plus que vous ne le pensez. Cette connexion est fournie par deux travaux scientifiques humoristiques - l' un de 2003 et le second de décembre 2019. Ensemble, ils combinent les mondes de la dynamique, de la géométrie et de l'informatique quantique, montrant comment même les puzzles mathématiques les plus abstraits peuvent étonnamment révéler un lien avec la physique.

Fermer à clé


Pour commencer à comprendre ces connexions, imaginez deux blocs métalliques pesant chacun 1 kg. Ils sont en surface sans frottement, à droite de la paroi fixe. Le bloc le plus proche du mur est immobile, le second glisse vers lui, s'approchant à droite. Une série d'affrontements doit inévitablement se produire; Supposons que l'énergie cinétique ne disparaisse pas lors des collisions. Dans de telles conditions idéales, ce processus se déroulera comme suit:


Le bloc droit frappe la gauche, lui donnant toute l'impulsion. Le bloc gauche rebondit sur le mur, revient vers la droite pour une autre collision et une autre transmission d'impulsion complète.

Cependant, si vous augmentez la masse du bloc droit, la situation deviendra plus intéressante. S'il pèse 100 kg, à chaque collision, il ne transmettra qu'une petite partie de son élan au plus petit bloc, et au lieu du nombre de collisions, il passera de 3 à 31.


Avec un rapport de masse de 10 000 à 1, la situation sera résolue après 314 collisions.


Augmentez la différence en multipliant la masse par 100, et vous pourrez observer une tendance choquante: le nombre de collisions commencera à se rapprocher du nombre π de plus en plus.


Gregory Galperin, un mathématicien de l'Université d'East Illinois, a été le premier à remarquer ce phénomène [en 1993]. En 2003, il l'a expliqué en visualisant les mouvements des blocs à travers un point mobile, dont les coordonnées x indiquent l'emplacement d'un bloc et les coordonnées y du second. La trajectoire d'un point sur le plan est reliée à un demi-cercle, d'où apparaît π.

Un résultat remarquable, même si ces conditions idéales le rendent apparemment inutile. Cependant, si vous négligez la négligence du monde réel en mathématiques, vous pouvez trouver une régularité pure qui révèle des liens inattendus avec d'autres domaines de la science.

En 2019, j'ai publié un ensemble de trois vidéosexpliquant les résultats de Halperin, et parmi ceux qui les ont regardés, il y avait Adam Brown, un chercheur de Google et un physicien à l'Université de Stanford. Après quelques mois à la conférence, il m'a pris à part pour partager son observation. À sa grande joie, il a découvert que les mathématiques qui décrivent la dynamique de ces blocs, d'un certain point de vue, deviennent identiques aux mathématiques qui décrivent l'un des algorithmes quantiques les plus célèbres.

Approche quantique


Cela nous amène à la deuxième partie du puzzle: comment fonctionne la recherche quantique.

Supposons que vous ayez une longue liste de noms sans tri - disons, un million - et que vous ayez besoin de trouver un nom spécifique. Vous n'avez pas d'autre option que de vérifier un nom après l'autre jusqu'à ce que vous tombiez sur le bon. En moyenne, cela vous prendra un demi-million d'itérations. Parfois plus, parfois moins, mais en tout cas cela vous prendra du temps.

Un ordinateur pourrait effectuer cette recherche pour vous, mais le problème avec les grandes listes est que le temps nécessaire pour les traiter augmentera proportionnellement à leur taille. Au moins lors de l'utilisation d'un ordinateur classique. Mais en 1996, Love Grover, qui travaillait dans les laboratoires de Bell, a décritcomment un ordinateur quantique peut effectuer une telle recherche beaucoup plus rapidement et en pas plus de 1000 étapes. Dans le cas général, un ordinateur quantique fera face à une liste de longueur N par pas de π / 4 √N. Notez que lorsque le nombre N augmente, le nombre d'étapes d'un ordinateur quantique croît plus lentement qu'un pas classique.

Une telle efficacité de recherche est possible car un ordinateur quantique traite tous les éléments de la liste en même temps. Cependant, il ne fait pas seulement la même chose qu'un ordinateur classique, mais en même temps.

Un ordinateur classique répond à la question: «Le 21e élément de la liste est-il le nom dont j'ai besoin?» Et il le répète pour chaque position de la liste, de 0 à 999 999. Directement, mais pas très efficace.

Mais l'algorithme de Grover fonctionne avec une méthode de liste, qui semble à première vue étrange, mais au final est plus utile. Un ordinateur classique peut simplement lire des bits de la mémoire. Les incertitudes présentes dans l'informatique quantique conduisent au fait que vous ne pouvez pas retirer directement les composants du vecteur avec lequel vous travaillez. Chaque position dans la liste a une structure probabiliste supplémentaire. Vous ne regardez pas quel nom est dans cette position, vous mesurez la liste entière, obtenant une position aléatoire - l'index - conformément aux probabilités. En raison de la mécanique quantique sous-jacente, au lieu de travailler directement avec des valeurs probabilistes, nous travaillons avec des nombres dont le carré correspond à la probabilité d'obtenir un indice correspondant au nom que vous recherchez.



Comment la lecture d'un index aléatoire peut-elle être utile? L'art de l'informatique quantique consiste à manipuler une liste de probabilités qui crée des chances en votre faveur. Dans notre exemple, cela signifie inventer un moyen (ce que fait l'algorithme de Grover) pour obtenir le nombre associé à l'index du nom que vous recherchez, proche de l'unité, afin que tous les autres nombres soient proches de zéro. Ensuite, en lisant cette liste et en recevant un index en réponse, vous savez probablement qu'elle correspond au nom que vous recherchez.

Les outils informatiques quantiques consistent en des opérations qu'un chercheur peut appliquer à cette liste de probabilités. En mathématiques, une telle liste est appelée vecteur. Il est souvent pratique d'imaginer un vecteur comme un point dans un système de coordonnées, ou comme une flèche tirée de l'origine à ce point.



Un vecteur à deux composants peut être représenté par une flèche dans un espace à deux dimensions. Un vecteur avec 1 000 000 de composants vit dans un espace étonnant de 1 000 000 dimensions. Les opérations effectuées par un ordinateur quantique ressemblent aux virages et aux retournements de cette flèche. Numériquement, chaque opération est indiquée par une matrice.



Les calculs quantiques sont particulièrement rapides car chaque opération est effectuée avec le vecteur de probabilité entier, et ne passe pas par composant. Grover a découvert un moyen délicat de manipuler un vecteur donné avec une paire d'opérations intermittentes, résultant en un vecteur avec les probabilités dont nous avons besoin. Il est important que le nombre total d'opérations requises soit beaucoup plus petit que la taille de la liste.

S'il vous est difficile d'imaginer comment cela peut fonctionner, vous n'êtes pas le seul. Par conséquent, Adam Brown était tellement heureux de découvrir un moyen d'imaginer ces manipulations vectorielles abstraites en termes de puzzle plus compréhensible.

Liens cachés


Il s'est avéré que lorsque j'ai regardé mes vidéos sur le calcul du nombre π en utilisant des blocs en collision, Brown avait juste en tête l'algorithme de Grover, alors il a immédiatement remarqué leur connexion. "Si vous passez toute la journée à penser à la recherche quantique, alors tout commence à ressembler à une recherche quantique", a déclaré Brown, "et il se trouve que ce cas s'est avéré être lié à la recherche quantique."

Et si le travail de Galperin sur les collisions de blocs utilisait un espace qui codait l'emplacement de chaque bloc, alors la connexion avec la recherche quantique de Grover commence par un vecteur dont les composantes x et y codent la vitesse de chaque bloc. Chaque collision de blocs se traduit par une opération spécifique sur ce vecteur, changeant ses composants. Par exemple, lorsque le bloc gauche entre en collision avec le mur, en changeant la direction à l'opposé, cela signifie que la composante de notre vecteur est multipliée par -1, et la composante x reste inchangée. D'un point de vue géométrique, cela ressemble à une réflexion d'un vecteur autour de l'axe x.

De même, lorsque deux blocs entrent en collision, un changement de leur vitesse est similaire à un autre retournement de ce vecteur, uniquement décalé par rapport au centre. Lorsque la simulation se poursuit, le bloc gauche entrera de nouveau en collision avec le mur, ce qui entraînera un autre virage sur l'axe x. Une autre collision de blocs signifie une autre révolution. Par conséquent, avec un nombre suffisant de collisions, le vecteur remplira la courbe familière: le cercle.


Brown a noté que si cette situation est correctement décrite, alors ces deux opérations, changeant dans un sens ou dans l'autre, sont identiques aux deux opérations que Grover a utilisées dans son algorithme de recherche quantique.

Pour comprendre comment cela se produit, imaginez un grand bloc droit sous la forme de plusieurs kilogrammes collés ensemble. Ensuite, au lieu d'un vecteur bidimensionnel décrivant chaque vitesse, nous obtenons un vecteur N dimensionnel, où N est le nombre total de petits blocs, y compris le bloc isolé à gauche. Chacun des petits blocs correspond à un nom dans une liste non triée et un bloc séparé à gauche correspond au nom cible.

Dans son travail, Brown a prouvé que la façon dont ces collisions de blocs modifient le vecteur qui les décrit est absolument identique à la façon dont l'algorithme de Grover modifie le vecteur quantique dénotant une liste non triée de noms. Le moment dans le système de blocs en collision, quand un gros bloc est sur le point de tourner, et presque toute l'énergie du système est dans un petit bloc, correspond au moment dans l'algorithme Grover, où presque toute la probabilité est dans le nom que vous devez trouver.

Le fait que le nombre π apparaisse lors du comptage des collisions se reflète dans l'algorithme de Grover: π / 4 √N pas. La racine carrée de l'expression reflète également jusqu'où va le comptage des chiffres de π (en degrés 10) après avoir multiplié la masse d'un grand bloc par 10.

"Jusqu'à présent, ce n'est qu'un gadget", a déclaré Brown. "Mais en physique, nous avons appris que plus nous pouvons réfléchir à un problème, plus nous pouvons voir d'idées - j'espère donc que ce fait sera utile un jour." Nous avons peu de bonnes alternatives pour visualiser l'algorithme de Grover.

Ces connexions mettent l'accent sur les capacités du langage universel des mathématiques. L'utilisation de vecteurs pour coder l'état d'un système physique fonctionne à la fois sur les collisions à grande échelle de blocs et sur les microscales des états quantiques. De nombreuses idées fondamentales en mathématiques, qui à première vue semblent désagréablement dissociées de la réalité, s'avèrent être des outils puissants, car si vous omettez les détails physiques dans un domaine, vous pouvez trouver ses connexions cachées avec l'autre.

More articles:


All Articles