Une nouvelle preuve frappante de la complexité du calcul quantique pourrait être mieux comprise avec une expérience de pensée ludique. Faites couler un bain, puis jetez un tas d'aimants flottants dans l'eau. Chaque aimant inversera son orientation d'avant en arrière, essayant de s'aligner avec ses voisins. Il poussera et tirera sur les autres aimants et sera poussé et tiré en retour. Essayez maintenant de répondre à ceci : quel sera l'arrangement final du système ?
Ce problème et d'autres semblables, il s'avère, sont incroyablement compliqués. Avec rien de plus que quelques centaines d'aimants, les simulations informatiques prendraient un temps fou pour cracher la réponse.
Maintenant, rendez ces aimants quantiques - des atomes individuels soumis aux règles byzantines du monde quantique. Comme vous pouvez le deviner, le problème devient encore plus difficile. "Les interactions deviennent plus compliquées", a déclaré Henri Yuen de l'Université de Columbia. "Il y a une contrainte plus compliquée sur le moment où deux 'aimants quantiques' voisins sont heureux."
Ces systèmes apparemment simples ont fourni des informations exceptionnelles sur les limites du calcul, dans les versions classique et quantique. Dans le cas des systèmes classiques ou non quantiques, un théorème historique de l'informatique nous emmène plus loin. Appelé théorème PCP (pour "preuve probabiliste vérifiable"), il dit que non seulement l'état final des aimants (ou les aspects qui y sont liés) est incroyablement difficile à calculer, mais que de nombreuses étapes y conduisent. La complexité de la situation est encore plus drastique, c'est-à-dire avec l'état final entouré d'une zone de mystère.
Une autre version du théorème PCP, non encore prouvée, traite spécifiquement du cas quantique. Les informaticiens soupçonnent que la conjecture du PCP quantique est vraie, et le prouver changerait notre compréhension de la complexité des problèmes quantiques. Il est sans doute considéré comme le problème ouvert le plus important de la théorie de la complexité computationnelle quantique. Mais jusqu'à présent, il est resté inaccessible.
Il y a neuf ans, deux chercheurs ont identifié un objectif intermédiaire pour nous aider à y arriver. Ils sont venus avec une hypothèse plus simple, connue sous le nom de conjecture "pas d'état trivial à basse énergie" (NLTS), qui devrait être vraie si la conjecture PCP quantique est vraie. Le prouver ne faciliterait pas nécessairement la preuve de la conjecture PCP quantique, mais cela résoudrait certaines de ses questions les plus intrigantes.
Puis le mois dernier, trois informaticiens prouvé la conjecture NLTS. Le résultat a des implications frappantes pour l'informatique et la physique quantique.
"C'est très excitant", a déclaré Dorit Aharonov de l'Université hébraïque de Jérusalem. "Cela encouragera les gens à se pencher sur le problème plus difficile de la conjecture PCP quantique."
Pour comprendre le nouveau résultat, commencez par imaginer un système quantique tel qu'un ensemble d'atomes. Chaque atome a une propriété, appelée spin, qui est quelque peu similaire à l'alignement d'un aimant, en ce sens qu'il pointe le long d'un axe. Mais contrairement à l'alignement d'un aimant, le spin d'un atome peut être dans un état qui est un mélange simultané de différentes directions, un phénomène connu sous le nom de superposition. De plus, il peut être impossible de décrire le spin d'un atome sans prendre en compte les spins d'autres atomes de régions éloignées. Lorsque cela se produit, on dit que ces atomes interdépendants sont dans un état d'intrication quantique. L'enchevêtrement est remarquable, mais aussi fragile et facilement perturbé par les interactions thermiques. Plus il y a de chaleur dans un système, plus il est difficile de l'emmêler.
Imaginez maintenant que vous refroidissez un tas d'atomes jusqu'à ce qu'ils approchent du zéro absolu. Au fur et à mesure que le système se refroidit et que les schémas d'intrication deviennent plus stables, son énergie diminue. L'énergie la plus faible possible, ou « énergie du sol », fournit une description concise de l'état final compliqué de l'ensemble du système. Ou du moins il le serait, s'il pouvait être calculé.
À partir de la fin des années 1990, les chercheurs ont découvert que pour certains systèmes, cette énergie au sol ne pouvait jamais être calculée dans un laps de temps raisonnable.
Cependant, les physiciens pensaient qu'un niveau d'énergie proche de l'énergie du sol (mais pas tout à fait là) devrait être plus facile à calculer, car le système serait plus chaud et moins intriqué, et donc plus simple.
Les informaticiens n'étaient pas d'accord. Selon le théorème PCP classique, les énergies proches de l'état final sont tout aussi difficiles à calculer que l'énergie finale elle-même. Et donc la version quantique du théorème PCP, si elle est vraie, dirait que les énergies précurseurs de l'énergie du sol seraient tout aussi difficiles à calculer que l'énergie du sol. Puisque le théorème PCP classique est vrai, de nombreux chercheurs pensent que la version quantique devrait également être vraie. "Sûrement, une version quantique doit être vraie", a déclaré Yuen.
Les implications physiques d'un tel théorème seraient profondes. Cela signifierait qu'il existe des systèmes quantiques qui conservent leur intrication à des températures plus élevées, ce qui contredit totalement les attentes des physiciens. Mais personne ne pourrait prouver que de tels systèmes existent.
En 2013, Michael Freedman et Matthew Hastings, tous deux travaillant à la Station Q de Microsoft Research à Santa Barbara, en Californie, ont cerné le problème. Ils ont décidé de rechercher des systèmes dont les énergies les plus basses et presque les plus basses sont difficiles à calculer selon une seule métrique : la quantité de circuits qu'il faudrait à un ordinateur pour les simuler. Ces systèmes quantiques, s'ils pouvaient les trouver, devraient conserver de riches schémas d'intrication à toutes leurs énergies les plus basses. L'existence de tels systèmes ne prouverait pas la conjecture PCP quantique - il pourrait y avoir d'autres mesures de dureté à considérer - mais cela compterait comme un progrès.
Les informaticiens ne connaissaient pas de tels systèmes, mais ils savaient où aller les chercher : dans le domaine d'étude appelé correction d'erreur quantique, où les chercheurs créent des recettes d'intrication conçues pour protéger les atomes des perturbations. Chaque recette est connue sous le nom de code, et il existe de nombreux codes de stature plus ou moins importante.
Fin 2021, les informaticiens fait une percée majeure dans la création de codes de correction d'erreurs quantiques de nature essentiellement idéale. Au cours des mois suivants, plusieurs autres groupes de chercheurs se sont appuyés sur ces résultats pour créer différentes versions.
Les trois auteurs du nouvel article, qui avaient collaboré à des projets connexes au cours des deux dernières années, se sont réunis pour prouver que l'un des nouveaux codes possédait toutes les propriétés nécessaires pour créer un système quantique du type que Freedman et Hastings avaient émis l'hypothèse. . Ce faisant, ils ont prouvé la conjecture NLTS.
Leur résultat démontre que l'intrication n'est pas nécessairement aussi fragile et sensible à la température que le pensaient les physiciens. Et cela soutient la conjecture PCP quantique, suggérant que même loin de l'énergie du sol, l'énergie d'un système quantique peut rester pratiquement impossible à calculer.
"Cela nous dit que la chose qui semblait peu probable d'être vraie est vraie", a déclaré Isaac Kim de l'Université de Californie, Davis. "Bien que dans un système très étrange."
Les chercheurs pensent que différents outils techniques seront nécessaires pour prouver la conjecture PCP quantique complète. Cependant, ils voient des raisons d'être optimistes quant au fait que le résultat actuel les rapprochera.
Ils sont peut-être plus intrigués par la question de savoir si les systèmes quantiques NLTS nouvellement découverts – bien que possibles en théorie – peuvent réellement être créés dans la nature, et à quoi ils ressembleraient. Selon le résultat actuel, ils nécessiteraient des schémas complexes d'intrication à longue distance qui n'ont jamais été produits en laboratoire, et qui ne pourraient être construits qu'en utilisant des nombres astronomiques d'atomes.
"Ce sont des objets hautement techniques", a déclaré Chinmay Nirkhé, informaticien à l'Université de Californie à Berkeley, et co-auteur du nouvel article avec Anurag Anshu de l'Université de Harvard et Nicolas Breuckmann de l'University College de Londres.
"Si vous avez la capacité de coupler des qubits très éloignés, je pense que vous pourriez réaliser le système", a déclaré Anshu. "Mais il y a un autre chemin à parcourir pour vraiment passer au spectre à basse énergie." Breuckmann a ajouté: «Peut-être qu'il y a une partie de l'univers qui est NLTS. Je ne sais pas."
