Une étude prouve la difficulté de simuler des circuits quantiques aléatoires pour les ordinateurs classiques.

6 septembre 2023 fonctionnalité

Cet article a été examiné selon le processus éditorial et les politiques de Science X. Les éditeurs ont souligné les attributs suivants tout en garantissant la crédibilité du contenu :

• vérification des faits
• publication évaluée par des pairs
• source fiable
• correction

par Ingrid Fadelli, Phys.org

Les ordinateurs quantiques, des technologies qui effectuent des calculs en exploitant des phénomènes de la mécanique quantique, pourraient éventuellement surpasser les ordinateurs classiques sur de nombreux problèmes de calculs complexes et d'optimisation. Bien que certains ordinateurs quantiques aient obtenu d'excellents résultats sur certaines tâches, leur avantage par rapport aux ordinateurs classiques reste à démontrer de manière concluante et cohérente. 

Ramis Movassagh, chercheur chez Google Quantum AI, qui était auparavant chez IBM Quantum, a récemment réalisé une étude théorique visant à démontrer mathématiquement les avantages notables des ordinateurs quantiques. Son article, publié dans Nature Physics, montre mathématiquement que la simulation de circuits quantiques aléatoires et l'estimation de leurs sorties est ce que l'on appelle un problème #P-hard pour les ordinateurs classiques (c'est-à-dire que c'est extrêmement difficile).

"Une question clé dans le domaine de l'informatique quantique est la suivante : les ordinateurs quantiques sont-ils exponentiellement plus puissants que les ordinateurs classiques ?" a déclaré Ramis Movassagh, auteur de l'étude, à Phys.org. "La conjecture de suprématie quantique (que nous avons renommée conjecture de primauté quantique) dit oui. Cependant, mathématiquement, il s'agit d'un problème ouvert majeur à établir rigoureusement."

Récemment, les chercheurs ont cherché à démontrer les avantages des ordinateurs quantiques par rapport aux ordinateurs classiques de différentes manières, tant par des études théoriques qu'expérimentales. Prouver mathématiquement que les ordinateurs classiques ont du mal à obtenir les résultats des ordinateurs quantiques avec une grande précision et une faible marge d'erreur serait une clé pour démontrer cela.

"En 2018, un collègue a donné une conférence au MIT sur, à l'époque, un résultat récent qui tentait de fournir des preuves de la difficulté de l'échantillonnage de circuits aléatoires (ECA)", explique Movassagh. "L'ECA consiste à prélever des échantillons à partir de la sortie d'un circuit quantique aléatoire et Google venait de le proposer comme candidat principal pour démontrer la primauté quantique. J'étais dans le public et je n'avais jamais travaillé sur la complexité quantique auparavant ; en fait, je me souviens même que lorsque j'étais étudiant en doctorat, je me suis même promis de ne jamais travailler dans ce domaine !"

La démonstration mathématique présentée par le collègue de Movassagh au MIT en 2018 n'a pas résolu de manière concluante le problème ancien de la démonstration de la primauté quantique, mais elle a constitué une avancée considérable vers cet objectif. La preuve a été obtenue grâce à une série d'approximations et de troncature de séries ; elle était donc quelque peu indirecte et introduisait des erreurs inutiles.

"J'aime faire le lien entre les mathématiques et la résolution de grands problèmes ouverts, en particulier si les mathématiques sont directes, peu connues des experts dans ce domaine et sont belles", explique Movassagh. "Dans ce cas, j'ai senti que je pourrais probablement trouver une meilleure preuve et j'ai naïvement pensé que si je résolvais le problème correctement, je pourrais résoudre le grand problème ouvert. J'ai donc entrepris de travailler dessus."

La preuve mathématique présentée par Movassagh diffère considérablement de celles introduites jusqu'à présent. Elle repose sur un nouvel ensemble de techniques mathématiques qui montrent collectivement que les probabilités de sortie d'un cas moyen (c'est-à-dire un circuit quantique aléatoire) sont aussi difficiles que le pire des cas (c'est-à-dire le plus artificiel).

"L'idée est que vous pouvez utiliser le chemin Cayley proposé dans l'article pour interpoler entre deux circuits arbitraires, qui dans ce cas sont pris entre le pire des cas et le cas moyen", explique Movassagh. "Le chemin Cayley est une fonction algébrique de faible degré. Étant donné que le pire des cas est connu pour être #P-hard (c'est-à-dire un problème très difficile), en utilisant le chemin Cayley, on peut interpoler vers le cas moyen et montrer que les circuits aléatoires sont essentiellement aussi difficiles que le pire des cas avec une probabilité élevée."

Contrairement aux autres preuves mathématiques dérivées par le passé, la preuve de Movassagh n'implique aucune approximation et est assez directe. Cela signifie qu'elle permet aux chercheurs de limiter explicitement les erreurs impliquées et de quantifier sa robustesse (c'est-à-dire sa tolérance aux erreurs).

Depuis que Movassagh a présenté la preuve, son groupe de recherche et d'autres équipes l'ont testée et améliorée pour en renforcer la robustesse. Elle pourrait donc bientôt orienter d'autres études visant à améliorer la preuve ou à mettre en évidence le potentiel des ordinateurs quantiques.

'We realized direct proofs of the hardness of estimating the output probabilities of quantum circuits,' Movassagh said, 'These provide computational barriers for the classical simulation of quantum circuits. The new techniques such as the Cayley path and rational function version of Berlekamp-Welch are of independent interest for quantum cryptography, computation and complexity, and coding theory. Currently, this is the most promising path toward eventual refutation of Extended-Church Turing thesis, which is an imperative goal of quantum complexity theory.'

The recent work by Movassagh greatly is a key contribution to ongoing research efforts exploring the advantages of quantum computers over classical computers. In his future studies, he plans to build on his current proof to mathematically demonstrate the huge potential of quantum computers for tackling specific problems.

'In my next studies, I hope to bridge this work to the hardness of other tasks to better map out the (in)tractability of quantum systems,' Movassagh added. 'I am investigating the applications of this work in quantum cryptography among others. And last but not least, I hope to prove the quantum primacy conjecture and prove that the Extended Church-Turing thesis is false!'

Journal information: Nature Physics

© 2023 Science X Network