Théorie des codes correcteurs d'erreur : des résultats fondamentaux pour aller vers l’ordinateur quantique

Plus proche du rêve que de la réalité il y a encore quelques années, l’ordinateur quantique devient aujourd’hui de plus en plus concret. Pourtant, sa construction repose encore sur de nombreux défis à relever, à commencer par la fragilité de l’information encodée sur un ordinateur quantique, entrainant toutes sortes d’erreurs dans les calculs.

Alors que les ordinateurs classiques manipulent des valeurs binaires conventionnelles de 0 ou 1 pour effectuer des calculs, les ordinateurs quantiques utilisent en effet ce que l'on appelle des "qubits" (ou "bits quantiques"), capables d’interagir beaucoup plus efficacement que les bits. Ces propriétés conduisent en principe à des accélérations exponentielles pour certaines tâches de calculs, mais le manque de fiabilité de ces qubits reste aujourd’hui un obstacle majeur.

Les qubits sont très bruités, c’est-à-dire fragiles. L’ordre de grandeur, c’est qu’une opération sur 1000 va être fausse. Sachant que certains calculs quantiques nécessitent 100 milliards d’opérations, avec ce taux d’erreur, le résultat sera forcément faux à la fin.

                                                                                                                                   Anthony Leverrier

À partir de la fin des années quatre-vingt-dix, des chercheurs ont commencé à réfléchir à la manière de réduire les erreurs possibles dans les calculs quantiques. Parmi les solutions trouvées : les codes correcteurs d’erreur, qui offrent la possibilité de corriger les erreurs en exploitant de la redondance : « Le code correcteur d’erreurs va répartir l’information sur un grand nombre de qubits, de manière redondante, de manière à ce que s’il y a un peu de "bruit", on puisse corriger les erreurs et ainsi protéger l’information utile au calcul », détaille Anthony Leverrier, avant d’ajouter « C’est quelque chose qui n’existe pas vraiment dans le calcul classique car les transistors sont très fiables, mais qui est nécessaire dans le quantique. »

Partant de cela, le défi a été, pour les chercheurs, de trouver les meilleurs codes correcteurs quantiques à mettre en œuvre, capables de réduire le nombre de qubits redondants nécessaires pour protéger l’information. Par exemple, l’algorithme quantique de factorisation (permettant de lire des communications chiffrées, par exemple) requiert seulement quelques milliers de qubits en théorie, mais ce nombre monte à plusieurs dizaines de millions en incluant les qubits redondants si on utilise les codes correcteurs quantiques connus. Une problématique fondamentale dans le développement de l’ordinateur quantique.

La qualité d’un code correcteur est mesurée par sa distance, c’est-à-dire le nombre d’erreurs qu’il peut corriger. Après plus de vingt ans sans aucun progrès sur cette question, les premiers codes avec une distance meilleure que la racine carrée de la longueur ont été découverts en 2020, et ce n'est que très récemment, en novembre 2021, que les chercheurs russes Pavel Panteleev et Gleb Kalachev ont réussi à montrer que, du moins en théorie, les informations quantiques peuvent être protégées des erreurs aussi bien que les informations classiques. Un travail révolutionnaire, récompensé par le Best Paper Award au 54^e Symposium on Theory of Computing (STOC 2022).

Une découverte suivie, en mars dernier, par la publication par les chercheurs français Anthony Leverrier (Inria – équipe-projet COSMIQ) et Gilles Zémor (Institut Mathématique de Bordeaux) d’une construction différente (mais apparentée) de bons codes LDPC quantiques : les codes de Tanner quantiques. Cette famille de codes, conceptuellement beaucoup plus simple à analyser que les codes de Panteleev et Kalachev, a été le principal nouvel outil menant à la résolution de la conjecture NLTS en théorie de la complexité quantique. Un résultat qui a suscité beaucoup d’intérêt de la part de la communauté, et qui sera présenté le 3 novembre lors de FOCS 2022.

Mais pour être utile à la construction d’un ordinateur quantique, il ne suffit pas d'avoir de bons codes quantiques : il faut aussi être capable de corriger efficacement les erreurs, en temps réel. En juin dernier, trois articles ont montré comment ces récents codes LDPC quantiques peuvent être décodés en temps linéaire, dont un signé par Anthony Leverrier et Gilles Zémor, et qui sera présenté en janvier à SODA 2023.

Bien que cela soit déjà remarquable, c'est encore probablement beaucoup trop lent pour être utile à un ordinateur quantique à grande échelle puisque les erreurs continuent de s'accumuler pendant le processus de décodage

                                                                                                            Anthony Leverrier

Une problématique que les deux chercheurs français abordent dans un article dévoilé en août dernier, en présentant un décodeur parallèle qui corrige de manière prouvée les erreurs arbitraires de poids linéaire en temps logarithmique. « C’était une question qui restait ouverte dans le papier des chercheurs russes, et avec Gilles nous avons montré comment décoder ces nouveaux codes, de manière rapide », conclut Anthony Leverrier.

Des résultats qui placent la France parmi les nations les plus avancées dans le domaine de l’ordinateur quantique. Un sujet que l’État français suit de près, et soutient. La France s’est ainsi dotée, en janvier 2021, d’une "stratégie nationale quantique". Le PEPR Technologies quantiques, doté de 150 millions d’euros et piloté scientifiquement par le CEA, le CNRS et Inria, constitue le volet recherche amont de cette stratégie. Anthony Leverrier travaille, à ce titre, sur l’un des dix projets issus de ce PEPR, NISQ2LSQ, qui vise à améliorer et développer de nouvelles stratégies de correction d’erreurs nécessaires pour mettre en œuvre des ordinateurs quantiques tolérants aux fautes.