Pendant de nombreuses années, les ordinateurs quantiques n'étaient guère plus qu'une idée. Aujourd'hui, entreprises, les gouvernements et les agences de renseignement investissent dans le développement de la technologie quantique. Robert Konig, professeur de théorie des systèmes quantiques complexes à la TUM, en collaboration avec David Gosset de l'Institute for Quantum Computing de l'Université de Waterloo et Sergey Bravyi d'IBM, a désormais posé une pierre angulaire dans ce domaine prometteur.

Les ordinateurs conventionnels obéissent aux lois de la physique classique. Ils s'appuient sur les nombres binaires zéro et un. Ces nombres sont stockés et utilisés pour des opérations mathématiques. Dans les unités de mémoire conventionnelles, chaque bit - la plus petite unité d'information - est représenté par une charge qui détermine si le bit est mis à un ou à zéro.

Dans un ordinateur quantique, cependant, un bit peut être à la fois zéro et un. En effet, les lois de la physique quantique permettent aux électrons d'occuper plusieurs états à la fois. Bits quantiques, ou qubits, existent donc dans de multiples états qui se chevauchent. Cette soi-disant superposition permet aux ordinateurs quantiques d'effectuer des opérations sur de nombreuses valeurs d'un seul coup, alors qu'un seul ordinateur conventionnel doit exécuter ces opérations de manière séquentielle. La promesse de l'informatique quantique réside dans la capacité à résoudre certains problèmes beaucoup plus rapidement.

De la conjecture à la preuve

König et ses collègues ont maintenant démontré de manière concluante l'avantage des ordinateurs quantiques. À cette fin, ils ont développé un circuit quantique qui peut résoudre un problème algébrique difficile spécifique. Le nouveau circuit a une structure simple :il n'effectue qu'un nombre fixe d'opérations sur chaque qubit. Un tel circuit est dit à profondeur constante. Dans leur travail, les chercheurs prouvent que le problème posé ne peut pas être résolu en utilisant des circuits classiques à profondeur constante. Ils répondent en outre à la question de savoir pourquoi l'algorithme quantique bat n'importe quel circuit classique comparable :L'algorithme quantique exploite la non-localité de la physique quantique.

Avant ce travail, l'avantage des ordinateurs quantiques n'avait été ni prouvé ni démontré expérimentalement, malgré ces preuves allant dans ce sens. Un exemple est l'algorithme quantique de Shor, qui résout efficacement le problème de la factorisation en nombres premiers. Cependant, c'est simplement une conjecture de la théorie de la complexité que ce problème ne peut pas être résolu efficacement sans ordinateurs quantiques. Il est également concevable que la bonne approche n'ait tout simplement pas encore été trouvée pour les ordinateurs classiques.

Robert König considère les nouveaux résultats principalement comme une contribution à la théorie de la complexité. « Notre résultat montre que le traitement de l'information quantique offre vraiment des avantages, sans avoir à s'appuyer sur des conjectures théoriques de la complexité non prouvées, " dit-il. Au-delà, le travail fournit de nouvelles étapes sur la route des ordinateurs quantiques. En raison de sa structure simple, le nouveau circuit quantique est un candidat pour une réalisation expérimentale à court terme d'algorithmes quantiques.