Un algorithme quantique important pourrait en fait être une propriété de la nature

Illustration conceptuelle de la double hélice d'ADN Mme Tech ; Image originale : Wikimedia commons

En 1996, un physicien quantique des Bell Labs du New Jersey a publié une nouvelle recette pour effectuer des recherches dans une base de données de N entrées. Les informaticiens savent depuis longtemps que ce processus prend environ N étapes car dans le pire des cas, le dernier élément de la liste pourrait être celui qui vous intéresse.

Cependant, ce physicien, Lov Grover, a montré comment les règles étranges de la mécanique quantique permettaient de faire la recherche en un nombre d'étapes égal à la racine carrée de N .

C'était une grosse affaire. La recherche dans les bases de données est une tâche fondamentale en informatique, utilisée pour tout, de la recherche de numéros de téléphone à la rupture des codes cryptographiques. Ainsi, toute accélération est une avancée significative.

Histoire connexe

Qu'est-ce que l'informatique quantique ?

La mécanique quantique a apporté une touche supplémentaire. À l'époque, la recette de Grover n'était que le deuxième algorithme quantique qui avait été prouvé plus rapide que son homologue classique. (Le premier était l'algorithme de Peter Shor pour la factorisation des nombres, qu'il a découvert en 1994.) Le travail de Grover a été un facteur important dans la préparation de la voie à la révolution informatique quantique qui est toujours en cours aujourd'hui.

Mais malgré l'intérêt, la mise en œuvre de l'algorithme de Grover a pris du temps en raison des défis techniques importants impliqués. Le premier ordinateur quantique capable de le mettre en œuvre est apparu en 1998, mais la première version évolutive n'est apparue qu'en 2017, et même alors, il ne fonctionnait qu'avec trois qubits. De nouvelles façons d'implémenter l'algorithme sont donc désespérément nécessaires.

Aujourd'hui, Stéphane Guillet et ses collègues de l'Université de Toulon en France disent que cela peut être plus facile que prévu. Ils disent avoir des preuves que l'algorithme de recherche de Grover est un phénomène naturel. Nous fournissons la première preuve que dans certaines conditions, les électrons peuvent naturellement se comporter comme une recherche Grover, à la recherche de défauts dans un matériau, disent-ils.

Cela a des implications évidentes pour l'informatique quantique, mais sa portée réelle peut être beaucoup plus profonde. Pendant un certain temps, les théoriciens se sont demandé si la recherche quantique pouvait expliquer l'un des plus grands mystères de l'origine de la vie. L'idée que les recherches de Grover se produisent dans la nature pourrait enfin résoudre l'énigme.

Tout d'abord un peu de contexte. Parce qu'il est si fondamental, l'algorithme de recherche de Grover peut être reformulé de différentes manières. L'un d'eux est une marche quantique sur une surface, la façon dont une particule quantique se déplacerait au hasard d'un point à un autre.

Histoire connexe

Qu'est-ce que la communication quantique ? Des chercheurs et des entreprises créent des réseaux de communication ultra-sécurisés qui pourraient constituer la base d'un internet quantique. Voilà comment cela fonctionne.

De toute évidence, ce processus est une sorte de recherche de l'espace à deux dimensions. Mais parce qu'une particule quantique peut explorer plusieurs chemins en même temps, elle est beaucoup plus rapide qu'une recherche classique.

La nature de la surface a une influence importante sur la recherche. Par exemple, un type de surface consiste en une grille carrée où la particule quantique a quatre mouvements possibles à chaque sommet.

Mais il existe de nombreuses autres grilles possibles ; un triangulaire, par exemple, où la particule quantique a trois choix à chaque sommet. La grille triangulaire est particulièrement intéressante en raison de sa ressemblance avec plusieurs matériaux naturels semblables à des cristaux, disent Guillet et co.

L'équipe s'est concentrée sur la simulation du fonctionnement d'une recherche Grover pour les électrons explorant des grilles triangulaires et carrées, mais elle a également inclus d'autres effets physiquement réalistes, tels que des défauts dans la grille sous la forme de trous, et des propriétés quantiques telles que des effets d'interférence.

Les résultats sont révélateurs. La question qu'ils posent est de savoir à quelle vitesse un électron peut trouver le trou dans une grille. Et la grande percée de l'équipe est de montrer que ces simulations reproduisent le comportement des électrons réels dans des matériaux réels.

En d'autres termes, cela prouve que les électrons libres implémentent naturellement l'algorithme de recherche de Grover lorsqu'ils se déplacent à la surface de certains cristaux.

Histoire connexe

Histoire connexe

Cela a des implications immédiates pour l'informatique quantique. [Ce travail] peut être la voie vers un saut technologique sérieux, par lequel l'expérimentateur contournerait le besoin d'un ordinateur quantique à part entière, évolutif et correcteur d'erreurs, et prendrait le raccourci de la recherche d''occurrences naturelles' de la recherche Grover à la place, dit l'équipe.

Le travail a également des implications pour notre réflexion sur le code génétique et l'origine de la vie. Chaque créature vivante sur Terre utilise le même code, dans lequel l'ADN stocke des informations à l'aide de quatre bases nucléotidiques. Les séquences de nucléotides codent des informations pour construire des protéines à partir d'un alphabet de 20 acides aminés.

Mais pourquoi ces chiffres - quatre et 20 - et pas d'autres ? En 2000, quelques années seulement après la publication de son travail par Grover, Apoorva Patel de l'Indian Institute of Science de Bangalore a montré comment l'algorithme de Grover pouvait expliquer ces chiffres .

L'idée de Patel est liée à la façon dont l'ADN est assemblé à l'intérieur des cellules. Dans cette situation, la machinerie moléculaire à l'intérieur d'une cellule doit parcourir la soupe moléculaire de bases nucléotidiques pour trouver la bonne. S'il y a quatre choix, une recherche classique comporte en moyenne quatre étapes. Ainsi, les machines devraient essayer quatre bases différentes à chaque étape d'assemblage.

Mais une recherche quantique utilisant l'algorithme de Grover est beaucoup plus rapide : Patel a montré que lorsqu'il y a quatre choix, une recherche quantique peut distinguer quatre alternatives en une seule étape. En effet, quatre est le nombre optimal.

Cette réflexion explique également pourquoi il existe 20 acides aminés. Dans l'ADN, chaque ensemble de trois nucléotides définit un seul acide aminé. Ainsi, la séquence de triplets dans l'ADN définit la séquence d'acides aminés dans une protéine.

Mais lors de l'assemblage des protéines, chaque acide aminé doit être choisi parmi une soupe de 20 options différentes. L'algorithme de Grover explique ces chiffres : une recherche quantique en trois étapes peut trouver un objet dans une base de données contenant jusqu'à 20 types d'entrées. Encore une fois, 20 est le nombre optimal.

En d'autres termes, si les processus de recherche impliqués dans l'assemblage de l'ADN et des protéines doivent être aussi efficaces que possible, le nombre de bases doit être de quatre et le nombre d'acides aminés doit être de 20, exactement comme on le trouve. La seule mise en garde est que les recherches doivent être de nature quantique.

Lorsque Patel a publié son idée, les physiciens quantiques l'ont immédiatement rejetée. À l'époque, ils s'enlisaient dans leurs propres tentatives de contrôle des processus quantiques, ce qu'ils ne pouvaient faire qu'en isolant les particules quantiques dans des environnements extrêmes comme à des températures proches du zéro absolu.

Le problème évident, ont-ils dit, était que les êtres vivants opèrent dans un environnement chaud et désordonné dans lequel les états quantiques seraient immédiatement détruits.

Les biologistes étaient tout aussi dédaigneux, affirmant que les processus quantiques ne pouvaient pas être à l'œuvre à l'intérieur des êtres vivants.

Depuis lors, un nombre croissant de preuves a émergé que les processus quantiques jouent un rôle important dans un certain nombre de mécanismes biologiques. La photosynthèse, par exemple, est maintenant considérée comme un processus essentiellement quantique.

L'ouvrage de Guillet et co jette un nouveau regard sur tout cela. Cela suggère que l'algorithme de Grover n'est pas seulement possible dans certains matériaux ; cela semble être une propriété de la nature. Et si c'est vrai, alors les objections aux idées de Patel commencent à s'effondrer.

Il se peut que la vie ne soit qu'un exemple de la recherche quantique de Grover à l'œuvre, et que cet algorithme soit lui-même une propriété fondamentale de la nature. C'est une grande idée s'il en est.

Réf : arxiv.org/abs/1908.11213 : La recherche Grover en tant que phénomène naturel

cacher