Dans le monde de l'information, protéger les données contre la corruption est une question de survie. Qu'il s'agisse d'envoyer un message via un canal radio bruyant ou de stocker un fichier sur un disque dur, les ingénieurs utilisent des codes correcteurs d'erreurs. Ce sont des structures mathématiques qui ajoutent de la redondance aux données, permettant à un récepteur de détecter et de corriger les erreurs sans demander de retransmission. Depuis des décennies, les scientifiques savent que trouver la version la plus robuste de ces codes est un puzzle incroyablement difficile. Dans le monde classique, où les données sont composées de bits simples qui sont soit zéro, soit un, il a été prouvé que calculer la force exacte d'un code est une tâche si complexe qu'aucun algorithme informatique efficace ne peut la résoudre pour chaque cas.

Le royaume quantique, cependant, fonctionne selon des règles différentes. Au lieu des bits, les ordinateurs quantiques utilisent des qubits, qui peuvent exister dans des superpositions délicates d'états. Pour protéger cette information fragile, les physiciens utilisent des codes correcteurs d'erreurs quantiques, qui sont bien plus complexes que leurs cousins classiques. Une mesure clé de la force d'un code quantique est sa « distance », un nombre qui nous indique combien d'erreurs le code peut supporter avant que l'information ne soit perdue. Si la distance est petite, le code est fragile ; si elle est grande, le code est robuste. Pendant longtemps, les chercheurs ont cru que si trouver cette distance était difficile, ce n'était peut-être pas aussi difficile que la version classique. Certaines études récentes suggéraient que la difficulté pourrait plafonner à un certain point, créant une barrière où le problème devient plus facile à approximer qu'on ne le pensait auparavant. Cette idée laissait entendre que les codes quantiques pourraient posséder une simplicité cachée dont les codes classiques sont dépourvus.

Une nouvelle étude d'Upendra Kapshikar, de l'Université d'Ottawa, conteste directement cette notion. Le chercheur a démontré que la difficulté d'approximer la distance d'un code quantique est aussi sévère que la version classique, atteignant les limites mêmes de ce que les ordinateurs peuvent faire, à condition que certaines hypothèses fondamentales de complexité soient vérifiées. En construisant un pont spécifique entre les problèmes classiques et quantiques, Kapshikar prouve qu'il n'y a pas de raccourci pour trouver la force de ces codes quantiques. Le travail démontre que tenter de deviner la distance avec une marge d'erreur raisonnable est une tâche qui reste informatiquement impossible pour tout algorithme efficace, à moins que les hypothèses largement acceptées sur la nature du calcul ne s'effondrent. Cela ferme effectivement la porte à l'idée que les codes quantiques possèdent une propriété spéciale, plus facile à résoudre.

Pour comprendre la portée de ce résultat, il faut d'abord saisir la nature du problème. Dans un ordinateur quantique, des erreurs peuvent s'immiscer de l'environnement, inversant l'état d'un qubit ou décalant sa phase. Un code quantique est conçu pour détecter ces erreurs. La « distance » du code est le nombre minimum de qubits qui doivent être affectés par une erreur avant que le code ne parvienne plus à la détecter. Si un code a une distance de dix, il peut détecter toute erreur affectant neuf qubits ou moins. Le défi pour les informaticiens est que, étant donné la description d'un code, calculer ce nombre exact est un cauchemar. Dans le monde classique, il a été prouvé il y a des années que l'on ne peut même pas s'approcher rapidement de la bonne réponse ; le problème est « NP-difficile », ce qui signifie qu'à mesure que le code s'agrandit, le temps requis pour le résoudre croît de manière explosive.

Pour les codes quantiques, la situation semblait plus trouble. Des recherches antérieures avaient réussi à prouver que le problème était difficile, mais seulement jusqu'à un certain point. Ces preuves antérieures pouvaient montrer que trouver la distance était difficile si l'on voulait une réponse dans un intervalle qui croissait avec la racine carrée de la taille du code. Cependant, elles ne pouvaient pas prouver qu'il était difficile de trouver une réponse dans un intervalle qui croît linéairement avec la taille. Imaginez un code de mille qubits. Un intervalle de racine carrée pourrait permettre une réponse erronée de trente, tandis qu'un intervalle linéaire permettrait une erreur de cent. Les résultats précédents laissaient ouverte la possibilité que les codes quantiques puissent être faciles à approximer si l'on acceptait une marge d'erreur plus grande. Le travail de Kapshikar lève cette incertitude.

Le chercheur y est parvenu en construisant un nouveau type de code quantique appelé code « stabilisé par mot-clé » (codeword-stabilized). Cette construction agit comme un traducteur, prenant un problème classique difficile et le transformant en un problème quantique. Le processus implique deux ingrédients principaux : un code classique et un graphe, qui est un réseau de points connectés par des lignes. Le graphe détermine comment les qubits interagissent, tandis que le code classique fournit la structure sous-jacente. L'innovation clé résidait dans la manière dont le graphe était choisi. Les méthodes précédentes reposaient sur des graphes ayant des connexions très spécifiques et éparses, ce qui limitait la force de la preuve. Kapshikar a réalisé qu'en utilisant un graphe aléatoire — un réseau où les connexions sont choisies au hasard — on pouvait obtenir un résultat beaucoup plus fort.

Dans un graphe aléatoire, les connexions sont denses et imprévisibles. L'étude montre que pour presque n'importe quel graphe aléatoire choisi, le code quantique résultant aura une distance étroitement liée à la distance du code classique original. Si le code classique est fort, le code quantique est fort. Si le code classique est faible, le code quantique est faible. Ce lien est si étroit que si vous pouviez facilement approximer la distance du code quantique, vous pourriez également approximer facilement la distance du code classique. Puisque nous savons que le problème classique est impossible à résoudre efficacement, le problème quantique doit l'être aussi, en supposant que les hypothèses de complexité standard comme l'Hypothèse du Temps Exponentiel (SETH) et l'Hypothèse du Gap-Temps Exponentiel (Gap-ETH) soient vérifiées. La preuve établit qu'aucun ordinateur ne peut approximer la distance quantique dans un intervalle linéaire, à moins que ces hypothèses fondamentales sur la nature du calcul ne s'effondrent.

L'étude va plus loin, examinant le problème à travers le prisme de la complexité « fine ». Cette approche ne demande pas seulement si un problème est difficile, mais précisément à quel point il l'est. Elle considère le temps nécessaire pour résoudre le problème à mesure que la taille de l'entrée augmente. La recherche montre que même si vous permettez à un algorithme de s'exécuter pendant très longtemps — plus longtemps que n'importe quel polynôme mais plus court qu'une recherche exponentielle complète — il ne pourra toujours pas résoudre le problème, à condition que les hypothèses SETH et Gap-ETH soient vraies. Plus précisément, l'article prouve qu'aucun algorithme ne peut résoudre le problème en un temps significativement inférieur au temps qu'il faudrait pour vérifier chaque motif d'erreur possible. Cela reste vrai pour les ordinateurs théoriques puissants, à condition qu'ils opèrent selon les règles standards de la logique et de la probabilité et que les hypothèses susmentionnées restent valides.

L'un des aspects les plus frappants de cette découverte est sa robustesse. Le résultat est valable même lorsque le code quantique est restreint à un type spécifique et populaire connu sous le nom de code CSS. Ces codes sont largement utilisés dans les conceptions pratiques de l'informatique quantique car ils sont plus faciles à mettre en œuvre. Le chercheur a montré que la difficulté s'applique également à eux, ce qui signifie que la difficulté n'est pas un artefact d'une conception de code étrange ou exotique, mais une propriété fondamentale de la correction d'erreurs quantiques elle-même. La preuve traite également la question de la « dégénérescence », une caractéristique unique des codes quantiques où certaines erreurs sont inoffensives car elles agissent de manière triviale sur l'information. L'étude tient compte de ce point avec soin, montrant que même avec cette particularité quantique, le problème reste insoluble.

Les implications de ce travail sont profondes pour l'avenir de l'informatique quantique. Elles confirment que la barrière de la conception et de l'analyse des codes quantiques n'est pas un obstacle temporaire qui sera surmonté par de meilleurs algorithmes. Au contraire, la difficulté est intrinsèque aux mathématiques du problème, en supposant que les conjectures de complexité standard soient vraies. Cela signifie que les ingénieurs concevant des ordinateurs quantiques ne peuvent pas compter sur un calcul rapide pour vérifier la force de leurs codes. Ils doivent soit accepter que trouver la distance exacte est informatiquement prohibitif pour les grands systèmes, soit s'appuyer sur des constructions spécifiques où la distance est connue par conception. L'étude trace ainsi une ligne de démarcation, montrant que la quête de compréhension des limites de la correction d'erreurs quantiques doit se poursuivre avec la compréhension que les mathématiques sous-jacentes sont aussi obstinées que possible.

L'article aborde également la nature de l'aléatoire dans le calcul. La preuve repose sur l'idée qu'un choix de graphe aléatoire est suffisant pour créer une instance difficile. Bien que la preuve initiale utilise un processus aléatoire, le chercheur montre également comment supprimer cet aléa sous une hypothèse largement acceptée concernant la puissance des circuits informatiques. Cela signifie que la difficulté n'est pas seulement un coup de chance statistique dû au hasard, mais une réalité déterministe. Il existe des codes quantiques spécifiques et fixes qui sont garantis d'être difficiles à analyser, et ces codes peuvent être générés par un ordinateur sans avoir besoin de lancer des dés. Cela renforce la conclusion, la faisant passer d'une déclaration probabiliste à une garantie ferme sur les limites du calcul.

En fin de compte, cette recherche comble un fossé qui était ouvert depuis un certain temps. Elle prend la difficulté connue des codes classiques et l'étend pleinement dans le domaine quantique, supprimant la barrière de la racine carrée rencontrée par les études précédentes. Le résultat offre une image claire du paysage computationnel : le problème de trouver la distance d'un code quantique est aussi difficile que les problèmes les plus durs de l'informatique, à condition que les hypothèses de complexité standard soient vérifiées. Pour l'observateur curieux, cela signifie que le monde quantique, bien que rempli de phénomènes étranges et merveilleux, n'offre pas d'échappatoire aux limites fondamentales de la logique. La complexité de la protection de l'information quantique est réelle, profonde et, pour l'instant, inéluctable.