L'informatique quantique dispose désormais d'un puissant outil de recherche

Algorithme de Grover

En 1996, un informaticien appelé Lov Grover des Bell Labs dans le New Jersey a dévoilé un algorithme inhabituel pour rechercher dans une base de données. Les algorithmes de recherche sont parmi les plus importants en informatique. Ils rendent possibles des tâches banales telles que la recherche dans les annuaires téléphoniques, mais également des tâches plus exotiques telles que casser des codes cryptographiques. Ce type d'algorithme est omniprésent en informatique.

Ainsi, tout moyen d'accélérer la tâche est extrêmement important. Une recherche standard prend une période de temps qui est à peu près proportionnelle au nombre d'éléments dans la recherche. En effet, dans le pire des cas, l'algorithme doit parcourir tous les éléments pour en trouver un seul.

Mais l'algorithme de Grover est différent. Le temps que cela prend est proportionnel à la racine carrée du nombre d'éléments. Les informaticiens appellent cela une accélération quadratique. Et dans un monde où les augmentations de vitesse de quelques fractions de pour cent sont extrêmement précieuses, une accélération quadratique est une réalisation impressionnante.

L'astuce de Grover consistait à utiliser les idées étranges mais puissantes derrière la mécanique quantique. Dans le monde classique, les bits ne sont que des 0 et des 1. Mais dans le monde quantique, un seul bit quantique, ou qubit, peut être un 0 et un 1 en même temps. Les physiciens disent que le qubit est dans une superposition d'états.

La superposition est la clé. Dans cet état, un algorithme peut rechercher à la fois le 0 et le 1 au même instant. Parce qu'il peut rechercher plus d'un élément en même temps, un algorithme quantique peut parcourir une liste beaucoup plus rapidement qu'un algorithme limité par le rythme laborieux de la physique classique.

Les algorithmes quantiques doivent être mis en œuvre par un ordinateur quantique, et en 1996, lorsque Grover a fait son travail, ce n'était guère plus qu'un rêve lointain. Mais la percée est venue rapidement. Les physiciens ont fait la démonstration du premier ordinateur quantique primitif en 1998 et ont montré comment il pouvait exécuter l'algorithme de Grover la même année.

Mais cette forme particulière d'informatique quantique était extrêmement limitée. Cela a fonctionné sur quelques qubits mais pas plus et, même en principe, ne pourrait jamais être étendu à des calculs plus importants. Ce problème de construction et de démonstration d'ordinateurs quantiques évolutifs a tourmenté la discipline depuis lors.

Maintenant, quelque 20 ans plus tard, les physiciens commencent à construire des ordinateurs quantiques qui ont le potentiel d'évoluer et sont donc capables de calculs plus puissants. Et aujourd'hui, Caroline Figgatt et ses amis de l'Université du Maryland disent avoir exécuté pour la première fois l'algorithme de Grover sur un ordinateur quantique évolutif.

Le travail démontre l'accélération rapide des calculs quantiques et ouvre la voie à un travail plus ambitieux avec l'algorithme qui pourrait commencer à résoudre des problèmes du monde réel tels que la rupture de code.

L'ordinateur quantique avec lequel Figgatt et ses collaborateurs travaillent consiste en une chaîne de cinq ions d'ytterbium suspendus dans un champ électromagnétique. Chaque ion est comme un petit aimant qui peut être orienté vers le haut ou vers le bas et basculé d'un état à l'autre avec un laser. Ainsi, chaque ion peut stocker des informations : un 1 pour le spin up et un 0 pour le spin down par exemple. Et parce qu'ils sont des objets quantiques, les ions peuvent exister dans une superposition de ces états.

Les ions interagissent également les uns avec les autres via les forces répulsives associées à leur charge positive. Cette interaction permet à un qubit d'interagir avec un autre qubit pour traiter les informations. C'est l'essence du calcul quantique. L'ordre des étapes de ce calcul est l'algorithme quantique, dans ce cas l'algorithme de Grover.

Figgatt et co utilisent leur système pour créer un ordinateur quantique à trois qubits qui peut stocker jusqu'à huit éléments dans une base de données. Ils exécutent ensuite l'algorithme de Grover pour montrer qu'il est possible de trouver un élément beaucoup plus rapidement, en moyenne, qu'un ordinateur classique qui nécessiterait au moins huit bits. Nous rapportons les résultats d'un algorithme complet de recherche Grover à trois qubits utilisant la technologie informatique quantique évolutive des ions atomiques piégés, avec des performances supérieures à la classique, disent Figgatt et co.

C'est un travail intéressant avec un potentiel important. Cela ouvre la voie à une utilisation plus étendue de l'algorithme de recherche Grover pour résoudre des problèmes plus importants sur des ordinateurs quantiques, notamment en utilisant le circuit comme sous-programme pour d'autres algorithmes quantiques, selon l'équipe.

Mais le travail fournit également un aperçu intéressant de la course à la construction de puissants ordinateurs quantiques. Le vainqueur de cette course est susceptible de récolter d'énormes récompenses financières, mais personne ne sait exactement quelle technologie est la meilleure.

Ce monde a été plongé dans la confusion par une startup canadienne appelée D-Wave Systems qui a vendu des ordinateurs quantiques apparemment puissants à des entreprises telles que Google et Lockheed Martin. Ces ordinateurs fonctionnent avec 1 000 qubits, bien plus que toute autre technologie.

Mais de nombreux théoriciens affirment que les affirmations de D-Wave sont exagérées et que ses machines ne peuvent pas produire le type de puissance de calcul dont d'autres ordinateurs quantiques devraient être capables.

C'est pourquoi de nombreux groupes tentent de commercialiser d'autres technologies quantiques qui diffèrent considérablement dans la manière dont ils stockent et traitent les informations quantiques. Ceux-ci s'appuient de manière variée sur les photons, les électrons, les atomes, les ions et les molécules pour faire leur offre quantique.

Parmi ces techniques, l'une des plus anciennes et des mieux développées est l'informatique quantique à piège ionique, et le groupe de l'Université du Maryland est un leader mondial dans ce domaine. En effet, le leader du groupe, Chris Monroe, possède une startup appelée IonQ qui vise à commercialiser cette technologie.

Ainsi, la démonstration d'un ordinateur quantique évolutif capable d'implémenter l'algorithme de Grover, bien qu'avec seulement trois qubits, peut être considérée comme une déclaration d'intention.

En 1998, après la première mise en œuvre de l'algorithme de Grover, il y avait une gamme d'opinions sur le temps qu'il faudrait aux physiciens pour rendre la prochaine étape des ordinateurs évolutifs. Un certain nombre de startups dûment formées et effondrées sur la base de prévisions optimistes. Mais, à cette époque, 20 ans se situait à l'extrémité pessimiste du spectre des prédictions. Le fait qu'il ait fallu autant de temps relativise la difficulté de la tâche.

Contrôler l'univers à l'échelle quantique est difficile. Une question intéressante maintenant pour les technologues et les investisseurs en capital-risque est de savoir si le rythme du progrès technologique peut être significativement accéléré.

Réf : arxiv.org/abs/1703.10535  : Recherche complète de Grover à 3 qubits sur un ordinateur quantique programmable

cacher