Théorème du seuil

Le dernier sujet de discussion de la leçon est un théorème très important connu sous le nom de théorème du seuil. Voici un énoncé quelque peu informel de ce théorème.

Théorème

Le théorème du seuil : Un circuit quantique de taille $N$ peut être implémenté avec une grande précision par un circuit quantique bruité, à condition que la probabilité d'erreur à chaque position du circuit bruité soit inférieure à une valeur seuil fixe non nulle $p_{\text{th}} > 0.$ La taille du circuit bruité est de l'ordre de $O(N \log^c(N))$ pour une constante positive $c.$

En termes simples, ce théorème dit que si nous avons un circuit quantique de $N$ portes, où $N$ peut être aussi grand que nous le souhaitons, il est alors possible d'implémenter ce circuit avec une grande précision en utilisant un circuit quantique bruité, à condition que le niveau de bruit soit en dessous d'une certaine valeur seuil indépendante de N. De plus, le coût n'est pas trop élevé, en ce sens que la taille du circuit bruité requis est de l'ordre de $N$ fois une puissance constante du logarithme de $N.$

Énoncer le théorème plus formellement nécessite d'être précis sur le modèle de bruit, ce qui ne sera pas fait dans cette leçon. Il peut, par exemple, être prouvé pour le modèle de bruit stochastique indépendant mentionné précédemment, où les erreurs se produisent indépendamment à chaque position possible du circuit avec une probabilité strictement inférieure à la valeur seuil, mais il peut aussi être prouvé pour des modèles de bruit plus généraux où il peut y avoir des corrélations entre les erreurs.

Il s'agit d'un résultat théorique, et la façon la plus typique dont il est prouvé ne se traduit pas nécessairement par une approche pratique, mais il a néanmoins une grande importance pratique. En particulier, il établit qu'il n'y a pas de barrière fondamentale à l'exécution de calculs quantiques en utilisant des composants bruités ; tant que le taux d'erreur de ces composants est en dessous de la valeur seuil, ils peuvent être utilisés pour construire des circuits quantiques fiables de taille arbitraire. Une autre façon d'exprimer son importance est d'observer que, si le théorème n'était pas vrai, il serait difficile d'imaginer que le calcul quantique à grande échelle devienne jamais une réalité.

Il y a de nombreux détails techniques dans les preuves formelles de (des énoncés formels de) ce théorème, et ces détails ne seront pas communiqués ici — mais les idées essentielles peuvent néanmoins être expliquées à un niveau intuitif. Pour rendre cette explication aussi simple que possible, imaginons que nous utilisons le code de Steane à $7$ qubits pour la correction d'erreurs. Ce serait un choix impraticable pour une implémentation physique réelle — comme le refléterait une valeur seuil $p_{\text{th}}$ minuscule — mais il convient bien pour transmettre les idées principales. Cette explication sera également assez cavalière quant au modèle de bruit, avec l'hypothèse qu'une erreur frappe chaque position d'une implémentation tolérante aux fautes indépendamment avec probabilité $p.$

Maintenant, si la probabilité $p$ est supérieure à l'inverse de $N,$ la taille du circuit que nous cherchons à implémenter, il y a de fortes chances qu'une erreur survienne quelque part. Nous pouvons donc tenter d'exécuter une implémentation tolérante aux fautes de ce circuit, en suivant la prescription décrite dans la leçon. Nous pouvons alors nous poser la question suggérée précédemment : Est-ce que cela améliore les choses ou les aggrave ?

Si la probabilité $p$ d'une erreur à chaque position est trop grande, nos efforts n'aideront pas et pourraient même aggraver les choses, tout comme le code de Shor à $9$ qubits n'aide pas si la probabilité d'erreur dépasse environ 3,23 %. En particulier, l'implémentation tolérante aux fautes est considérablement plus grande que notre circuit original, donc il y a beaucoup plus de positions où des erreurs pourraient survenir.

Cependant, si $p$ est suffisamment petit, nous réussirons à réduire la probabilité d'erreur pour le calcul logique que nous effectuons. (Dans une preuve formelle, nous devrions être très prudents à ce stade : les erreurs dans le calcul logique ne seront pas nécessairement décrites avec précision par le modèle de bruit original. Cela motive en fait des modèles de bruit moins indulgents où les erreurs pourraient ne pas être indépendantes — mais nous allons balayer ce détail sous le tapis pour les besoins de cette explication.)

Plus en détail, pour qu'une erreur logique survienne dans le circuit original, au moins deux erreurs doivent tomber dans le même bloc de code dans l'implémentation tolérante aux fautes, étant donné que le code de Steane peut corriger toute erreur unique dans un bloc de code. En gardant à l'esprit qu'il y a de nombreuses façons différentes d'avoir deux erreurs ou plus dans le même bloc de code, on peut argumenter que la probabilité d'une erreur logique à chaque position du circuit original est au plus $C p^2$ pour un certain nombre réel positif fixe $C$ qui dépend du code et des gadgets que nous utilisons, mais pas de $N,$ la taille du circuit original. Si $p$ est inférieur à $1/C,$ qui est la valeur que nous pouvons prendre comme valeur seuil $p_{\text{th}},$ cela se traduit par une réduction des erreurs.

Cependant, ce nouveau taux d'erreur pourrait encore être trop élevé pour permettre au circuit entier de fonctionner correctement. Une chose naturelle à faire à ce stade est de choisir un meilleur code et de meilleurs gadgets pour faire baisser le taux d'erreur à un point où l'implémentation est susceptible de fonctionner. Théoriquement, une façon simple d'argumenter que c'est possible est de concaténer. C'est-à-dire que nous pouvons penser à l'implémentation tolérante aux fautes du circuit original comme à n'importe quel autre circuit quantique, puis implémenter ce nouveau circuit de manière tolérante aux fautes, en utilisant le même schéma. Nous pouvons alors le faire encore et encore, autant de fois que nécessaire pour réduire le taux d'erreur à un niveau permettant au calcul original de fonctionner.

Pour avoir une idée approximative de la façon dont le taux d'erreur diminue grâce à cette méthode, considérons son fonctionnement pour quelques itérations. Notons qu'une analyse rigoureuse devrait prendre en compte divers détails techniques que nous omettons ici.

Nous commençons avec la probabilité d'erreur $p$ pour les positions du circuit original. En supposant que $p < p_{\text{th}} = 1/C,$ le taux d'erreur logique peut être borné par $Cp^2 = (Cp) p$ après la première itération. En traitant l'implémentation tolérante aux fautes comme n'importe quel autre circuit et en l'implémentant de manière tolérante aux fautes, nous obtenons une borne sur le taux d'erreur logique de

$$C \bigl((Cp) p \bigr)^2 = (Cp)^3 p.$$

Une autre itération réduit encore la borne sur les erreurs, à

$$C \bigl((Cp)^3 p \bigr)^2 = (Cp)^7 p.$$

En continuant ainsi pour un total de $k$ itérations, on obtient un taux d'erreur logique (pour le circuit original) borné par

$$(Cp)^{2^k - 1} p,$$

ce qui est doublement exponentiel en $k.$

Cela signifie que nous n'avons pas besoin de trop d'itérations pour rendre le taux d'erreur extrêmement petit. Pendant ce temps, les circuits augmentent en taille avec chaque niveau de concaténation, mais la taille n'augmente que simplement exponentiellement avec le nombre de niveaux $k.$ C'est parce qu'avec chaque niveau de tolérance aux fautes, la taille augmente d'au plus un facteur déterminé par la taille maximale des gadgets utilisés. Lorsque tout est mis ensemble, et qu'un choix approprié pour le nombre de niveaux de concaténation est fait, nous obtenons le théorème du seuil.

Alors, quelle est cette valeur seuil en réalité ? La réponse dépend du code et des gadgets utilisés. Pour le code de Steane avec la distillation d'états magiques, elle est minuscule et probablement peu susceptible d'être atteinte en pratique. Mais, en utilisant des codes de surface et des gadgets de pointe, le seuil a été estimé à l'ordre de 0,1 % à 1 %.

À mesure que de nouveaux codes et méthodes sont découverts, il est raisonnable de s'attendre à ce que la valeur seuil augmente, tandis que simultanément le niveau de bruit dans les composants physiques réels diminuera. Atteindre le point où de grands calculs quantiques peuvent être implémentés de manière tolérante aux fautes ne sera pas facile et ne se produira pas du jour au lendemain. Mais ce théorème, combiné aux avancées en codes quantiques et en matériel quantique, nous donne de l'optimisme alors que nous continuons à avancer vers l'objectif ultime de construire un ordinateur quantique tolérant aux fautes à grande échelle.

Sondage post-cours

Félicitations pour avoir complété ce cours ! Prends un moment pour nous aider à améliorer notre cours en remplissant le sondage rapide suivant. Ton retour servira à améliorer notre offre de contenu et l'expérience utilisateur. Merci !