En 2019, Google a affirmé qu'il était le premier à démontrer un ordinateur quantique effectuant un calcul au-delà des capacités des supercalculateurs les plus puissants d'aujourd'hui.

Mais la plupart du temps, créer un algorithme quantique qui a une chance de battre un ordinateur classique est un processus accidentel, Les scientifiques de l'Université Purdue disent. Pour mieux guider ce processus et le rendre moins arbitraire, ces scientifiques ont développé une nouvelle théorie qui pourrait éventuellement conduire à une conception plus systématique d'algorithmes quantiques.

La nouvelle théorie, décrit dans un article publié dans la revue Technologies quantiques avancées , est la première tentative connue pour déterminer quels états quantiques peuvent être créés et traités avec un nombre acceptable de portes quantiques pour surpasser un algorithme classique.

Les physiciens qualifient ce concept d'avoir le bon nombre de portes pour contrôler chaque état de « complexité ». Étant donné que la complexité d'un algorithme quantique est étroitement liée à la complexité des états quantiques impliqués dans l'algorithme, la théorie pourrait donc mettre de l'ordre dans la recherche d'algorithmes quantiques en caractérisant quels états quantiques répondent à ce critère de complexité.

Un algorithme est une séquence d'étapes pour effectuer un calcul. L'algorithme est généralement implémenté sur un circuit.

Dans les ordinateurs classiques, les circuits ont des portes qui commutent les bits à l'état 0 ou 1. Un ordinateur quantique repose plutôt sur des unités de calcul appelées "qubits" qui stockent les états 0 et 1 simultanément en superposition, permettant de traiter plus d'informations.

Ce qui rendrait un ordinateur quantique plus rapide qu'un ordinateur classique, c'est un traitement de l'information plus simple, caractérisé par l'énorme réduction du nombre de portes quantiques dans un circuit quantique par rapport à un circuit classique.

Dans les ordinateurs classiques, le nombre de portes dans les circuits augmente de façon exponentielle par rapport à la taille du problème d'intérêt. Ce modèle exponentiel croît si rapidement qu'il devient physiquement impossible à gérer, même pour un problème d'intérêt de taille moyenne.

"Par exemple, même une petite molécule de protéine peut contenir des centaines d'électrons. Si chaque électron ne peut prendre que deux formes, alors pour simuler 300 électrons il faudrait 2300 états classiques, qui est plus que le nombre de tous les atomes de l'univers, " dit Saber Kais, professeur au département de chimie de Purdue et membre du Purdue Quantum Science and Engineering Institute.

Pour les ordinateurs quantiques, il existe un moyen pour les portes quantiques de s'étendre « de manière polynomiale » - plutôt que simplement de manière exponentielle comme un ordinateur classique - avec la taille du problème (comme le nombre d'électrons dans le dernier exemple). « Polynôme » signifie qu'il y aurait considérablement moins d'étapes (portes) nécessaires pour traiter la même quantité d'informations, rendre un algorithme quantique supérieur à un algorithme classique.

Jusqu'à présent, les chercheurs n'ont pas eu un bon moyen d'identifier quels états quantiques pourraient satisfaire cette condition de complexité polynomiale.

"Il existe un très grand espace de recherche pour trouver les états et la séquence de portes qui correspondent en complexité pour créer un algorithme quantique utile capable d'effectuer des calculs plus rapidement qu'un algorithme classique, " dit Kais, dont le groupe de recherche développe des algorithmes quantiques et des méthodes d'apprentissage automatique quantique.

Kais et Zixuan Hu, un associé postdoctoral Purdue, utilisé la nouvelle théorie pour identifier un grand groupe d'états quantiques avec une complexité polynomiale. Ils ont également montré que ces états peuvent partager une caractéristique de coefficient qui pourrait être utilisée pour mieux les identifier lors de la conception d'un algorithme quantique.

"Compte tenu de n'importe quel état quantique, nous sommes maintenant en mesure de concevoir une procédure d'échantillonnage de coefficient efficace pour déterminer s'il appartient ou non à la classe, " a dit Hu.