Une correction d'erreur est-elle nécessaire?

20

Pourquoi avez-vous besoin d'une correction d'erreur? Ma compréhension est que la correction d'erreurs supprime les erreurs du bruit, mais le bruit devrait se compenser. Pour clarifier ce que je demande, pourquoi ne pouvez-vous pas, au lieu d'impliquer la correction d'erreurs, exécuter simplement les opérations, disons, cent fois, et choisir la réponse moyenne / la plus courante?

bruyère
la source

Réponses:

18

Ça ne va pas bien. Après un calcul modérément long, vous vous retrouvez avec l'état mélangé maximal ou le point fixe de votre bruit. Pour évoluer vers des calculs arbitraires, vous devez corriger les erreurs avant qu'elles ne deviennent trop importantes.

Voici un petit calcul pour l'intuition donnée ci-dessus. Considérons le modèle de bruit blanc simple (bruit dépolarisant), ρest l'état idéal (la notation standards'applique). Si vous concaténeznprocessus bruyants, le nouveau paramètre de bruit est, ce qui augmente exponentiellement le nombre de portes (ou d'autres sources d'erreur). Si vous répétez l'expériencefois et supposez que l'erreur standard évolue en tant quevous voyez que le nombre d'exécutionsserait exponentiellement dans la longueur de votre calcul!

ρ(ε)=(1ε)ρ+εItrI,
ρn m 1ε=1(1ε)nm m1mm
M. Stern
la source
11

Si le taux d'erreur était suffisamment faible, vous pourriez exécuter un calcul cent fois et prendre la réponse la plus courante. Par exemple, cela fonctionnerait si le taux d'erreur était suffisamment bas pour que le nombre d'erreurs attendu par calcul soit quelque chose de très petit - ce qui signifie que le fonctionnement de cette stratégie dépendrait de la durée et de la complexité d'un calcul que vous aimeriez faire.

Une fois que le taux d'erreur ou la longueur de votre calcul est devenu suffisamment élevé, vous ne pouvez plus avoir la certitude que le résultat le plus probable est qu'il n'y a eu aucune erreur: à un certain point, il devient plus probable que vous en ayez une ou deux, ou plus d'erreurs que de zéro. Dans ce cas, rien n'empêche la majorité des cas de vous donner une réponse incorrecte. Et alors?

Ces problèmes ne sont pas particuliers au calcul quantique: ils s'appliquent également au calcul classique - il se trouve que la quasi-totalité de notre technologie est à un stade de maturité suffisamment avancé pour que ces problèmes ne nous concernent pas dans la pratique; qu'il y a plus de chances que votre ordinateur soit frappé par un calcul moyen de météorite (ou qu'il soit à court de batterie ou que vous décidiez de l'éteindre) que d'une erreur matérielle. La particularité (temporaire) du calcul quantique est que la technologie n'est pas encore suffisamment mûre pour que nous soyons si détendus quant à la possibilité d'erreur.

En ces temps où le calcul classique aétant à un stade où la correction d'erreurs était à la fois pratique et nécessaire, nous avons pu utiliser certaines techniques mathématiques - la correction d'erreurs - qui ont permis de supprimer le taux d'erreur effectif, et en principe de le rendre aussi bas que nous le voulions. Les mêmes techniques peuvent étonnamment être utilisées pour la correction d'erreur quantique - avec un peu d'extension, pour tenir compte de la différence entre l'information quantique et classique. Au début, avant le milieu des années 1990, on pensait que la correction d'erreur quantique était impossible en raison de la continuité de l'espace des états quantiques. Mais il s'avère que, en appliquant les techniques classiques de correction d'erreur de la bonne manière aux différentes façons dont un qubit pourrait être mesuré (généralement décrit comme "bit" et "phase"), vous pouvez en principe supprimer également de nombreux types de bruit sur les systèmes quantiques. Ces techniques ne sont pas non plus spécifiques aux qubits: la même idée peut être utilisée pour des systèmes quantiques de toute dimension finie (bien que pour des modèles tels que le calcul adiabatique, cela peut alors entraver la réalisation du calcul que vous souhaitez effectuer).

Au moment où j'écris ceci, les qubits individuels sont si difficiles à construire et à rassembler que les gens espèrent pouvoir faire des calculs de preuve de principe sans aucune correction d'erreur. C'est bien, mais cela limitera la durée de leurs calculs jusqu'à ce que le nombre d'erreurs accumulées soit suffisamment grand pour que le calcul cesse d'être significatif. Il existe deux solutions: améliorer la suppression du bruit ou appliquer une correction d'erreur. Les deux sont de bonnes idées, mais il est possible que la correction d'erreurs soit plus facile à effectuer à moyen et à long terme que la suppression des sources de bruit.

Niel de Beaudrap
la source
En tant que correction rapide, le matériel moderne souffre de taux d'erreur non négligeables et des méthodes de correction d'erreur sont utilisées. Cela dit, bien sûr, votre argument selon lequel les problèmes sont bien pires sur les ordinateurs quantiques actuels est valable.
Nat
@Nat: intéressant. Je suis vaguement conscient que cela peut être actuellement le cas pour les GPU, et (dans un contexte n'impliquant pas de calcul actif) les matrices RAID sont également un exemple évident. Mais pourriez-vous décrire d'autres plates-formes matérielles pour lesquelles le calcul classique doit s'appuyer sur la correction d'erreurs lors d'un calcul?
Niel de Beaudrap
Il semble que les erreurs surviennent le plus souvent dans des contextes de mise en réseau, suivies du stockage sur disque, puis de la RAM. Les protocoles de mise en réseau et les disques implémentent régulièrement des astuces de correction d'erreurs. RAM est un sac mixte; la RAM du serveur / poste de travail a tendance à utiliser le code correcteur d'erreurs (ECC), bien que la RAM grand public ne le fasse pas souvent. Dans les CPU, j'imagine qu'ils ont des tactiques plus spécifiques à l'implémentation, mais ce sont probablement des secrets de fabricant. Les taux d'erreur dans les CPU et les GPU deviennent pertinents à un niveau observable dans quelques cas, par exemple dans les décisions d'overclocking et de verrouillage du cœur du fabricant.
Nat
En fait, un peu curieux de la correction d'erreurs de type CPU maintenant .. Je veux dire, le cache semblerait sujet aux mêmes problèmes que la RAM normale (à moins qu'il ne soit en quelque sorte tamponné avec plus de puissance ou quelque chose?), Ce qui serait probablement inacceptable sur le serveur / contextes des postes de travail. Mais au niveau du registre? Ce serait quelque chose de bien à lire; n'a rien vu immédiatement sur Google, même si je suppose que de telles informations seraient probablement un secret commercial.
Nat
8

Maintenant, en ajoutant à la réponse de M. Stern :

La raison principale pour laquelle la correction d'erreurs est nécessaire pour les ordinateurs quantiques est que les qubits ont un continuum d'états (je ne considère les ordinateurs quantiques basés sur des qubits que pour le moment pour des raisons de simplicité).

Dans les ordinateurs quantiques, contrairement aux ordinateurs classiques, chaque bit n'existe pas dans seulement deux états possibles. Par exemple, une source d'erreur probable est la rotation excessive: pourrait être censé devenir a | 0 + β e i & phiv | 1 , mais elle devient a | 0 + β e i ( φ + δ ) | 1 α|0+β|1α|0+βejeϕ|1α|0+βeje(ϕ+δ)|1. L'état réel est proche de l'état correct mais toujours faux. Si nous ne faisons rien à ce sujet, les petites erreurs s'accumuleront au fil du temps et finiront par devenir une grosse erreur.

De plus, les états quantiques sont très délicats et toute interaction avec l'environnement peut provoquer la décohérence et l'effondrement d'un état comme à | 0 avec une probabilité | α | 2 ou | 1 avec une probabilité | β | 2 .α|0+β|1|0|α|2|1|β|2

Dans un ordinateur classique, disons que la valeur d'un bit est répliquée n fois comme suit:

et 1 11111 ... n fois

000000 ...n fois
111111 ...n fois

En cas après l'étape quelque chose comme est produit , il peut être corrigé par l'ordinateur classique pour donner 0000000000 parce que la majorité des bits étaient 0 ' s et très probablement le but recherché de l'opération initiale reproduisait les 0 -bit 10 fois.000100010000000000000s0dix

Mais, pour les qubits, une telle méthode de correction d'erreur ne fonctionnera pas, car tout d'abord la duplication directe des qubits n'est pas possible en raison du théorème de non-clonage . Et deuxièmement, même si vous pouviez répliquer 10 fois il est très probable que vous finiriez avec quelque chose comme ( α | 0 + β | 1 ) ( α e i ε | 0 + β e i ε|ψ=α|0+β|1c'est-à-dire avec des erreurs dans les phases, où tous les qubits seraient dans des états différents (en raison des erreurs). Autrement dit, la situation n'est plus binaire. Un ordinateur quantique, contrairement à un ordinateur classique, ne peut plus dire que: "Puisque la majorité des bits sont en état0,permettez-moi de convertir le reste en0(α|0+β|1)(αejeϵ|0+βejeϵ|1)(αejeϵ2|0+βejeϵ2|1)...00! ", pour corriger toute erreur survenue pendant l'opération. En effet, tous les états des 10 qubits différents peuvent être différents les uns des autres, après l'opération dite de" réplication ". Le nombre d'erreurs possibles continuera d'augmenter rapidement que de plus en plus d'opérations sont effectuées sur un système de qubits, M. Stern a en effet utilisé la bonne terminologie dans sa réponse à votre question c'est-à-dire "ça ne va pas bien ".dixdix

Ainsi, vous avez besoin d'une race différente de techniques de correction d'erreurs pour traiter les erreurs survenant pendant le fonctionnement d'un ordinateur quantique, qui peuvent traiter non seulement les erreurs de basculement de bits mais également les erreurs de décalage de phase. De plus, il doit être résistant à la décohérence involontaire. Une chose à garder à l'esprit est que la plupart des portes quantiques ne seront pas "parfaites", même si avec le bon nombre de "portes quantiques universelles", vous pouvez vous rapprocher arbitrairement de la construction de toute porte quantique qui effectue (en théorie) une transformation unitaire.

Niel de Beaudrap mentionne qu'il existe des moyens intelligents d'appliquer les techniques classiques de correction d'erreurs de manière à ce qu'elles puissent corriger bon nombre des erreurs qui se produisent pendant les opérations quantiques, ce qui est effectivement correct, et c'est exactement ce que font les codes correcteurs d'erreurs quantiques actuels. Je voudrais ajouter ce qui suit de Wikipedia , car cela pourrait donner une certaine clarté sur la façon dont les codes de correction d'erreur quantique traitent le problème décrit ci-dessus:

Les codes de correction d'erreur classiques utilisent une mesure de syndrome pour diagnostiquer quelle erreur corrompt un état codé. Nous inversons ensuite une erreur en appliquant une opération corrective basée sur le syndrome. La correction d'erreur quantique utilise également des mesures du syndrome. Nous effectuons une mesure multi-qubit qui ne perturbe pas les informations quantiques à l'état codé mais récupère des informations sur l'erreur. Une mesure du syndrome peut déterminer si un qubit a été corrompu et, le cas échéant, lequel. De plus, le résultat de cette opération (le syndrome) nous dit non seulement quel qubit physique a été affecté, mais aussi, de plusieurs façons possibles, il a été affecté. Ce dernier est contre-intuitif à première vue: le bruit étant arbitraire, comment l'effet du bruit peut-il être l'une des rares possibilités distinctes? Dans la plupart des codes, l'effet est soit un flip bit, soit un flip signe (de la phase), soit les deux (correspondant aux matrices de Pauli X, Z et Y). La raison en est que la mesure du syndrome a l'effet projectif d'une mesure quantique. Ainsi, même si l'erreur due au bruit était arbitraire, elle peut être exprimée comme une superposition d'opérations de base - la base d'erreur (qui est donnée ici par les matrices de Pauli et l'identité). La mesure du syndrome "force" le qubit à "décider" qu'une "erreur Pauli" spécifique "s'est produite", et le syndrome nous le dit, afin que nous puissions laisser le même opérateur Pauli agir à nouveau sur le qubit corrompu pour revenir l'effet de l'erreur.

La mesure du syndrome nous en dit autant que possible sur l'erreur qui s'est produite, mais rien du tout sur la valeur qui est stockée dans le qubit logique - sinon la mesure détruirait toute superposition quantique de ce qubit logique avec d'autres qubits du quantum ordinateur.


Remarque : Je n'ai donné aucun exemple de techniques réelles de correction d'erreurs quantiques. Il existe de nombreux bons manuels qui traitent de ce sujet. Cependant, j'espère que cette réponse donnera aux lecteurs une idée de base de la raison pour laquelle nous avons besoin de codes de correction d'erreur dans le calcul quantique.


Lectures complémentaires recommandées:

Conférence vidéo recommandée:

Mini Crash Course: Correction d'erreurs quantiques par Ben Reichardt, Université de Californie du Sud

Sanchayan Dutta
la source
3
Je ne suis pas sûr que le fait qu'il y ait un continuum d'États joue un rôle. Le calcul classique avec des bits aurait également les mêmes problèmes si notre technologie était moins mature, et en effet il souffrait significativement de bruit à différents moments de son développement. Dans le cas classique et quantique, le bruit ne fait pas la moyenne dans des circonstances normales
Niel de Beaudrap
51000,5005
Bien sûr, vous ne vous trompez pas lorsque vous dites que même le calcul classique souffrait du problème du bruit. Il existe également une théorie bien établie des codes de correction d'erreurs classiques! Cependant, la situation est beaucoup plus grave en cas de calcul quantique en raison de la possibilité d'un nombre infini d'états d'existence d'un seul qubit.
Sanchayan Dutta
1
Les techniques utilisées pour la correction d'erreur quantique n'impliquent en aucun cas que l'espace d'état est infini. Les arguments que vous faites semblent faire une analogie entre l'informatique quantique et l'informatique analogique --- bien qu'il y ait une similitude, cela impliquerait que la correction d'erreur quantique serait impossible s'il s'agissait d'une analogie solide. En revanche, l'espace d'état de nombreux qubits est également comme une distribution de probabilité sur des chaînes de bits, dont il existe également un continuum; et pourtant, il suffit de corriger les erreurs sur des chaînes de bits définies pour supprimer l'erreur.
Niel de Beaudrap
1
@glS J'ai supprimé la première phrase. Tu as raison. J'interprétais le calcul d'une manière indépendante.
Sanchayan Dutta
2

Pourquoi avez-vous besoin d'une correction d'erreur? Ma compréhension est que la correction d'erreurs supprime les erreurs du bruit, mais le bruit devrait se compenser.

Si vous construisez une maison ou une route et que le bruit est un écart, une différence, par rapport à la rectitude, à la direction, ce n'est pas seulement / simplement: "A quoi cela ressemblerait-il", mais "Comment serait-ce?" - une superposition à la fois d'efficacité et de justesse.

Si deux personnes calculaient la circonférence d'une balle de golf en fonction d'un diamètre, chacune obtiendrait une réponse similaire, sous réserve de l'exactitude de leurs calculs; si chacun utilisait plusieurs décimales, ce serait «assez bien».

Si deux personnes recevaient un équipement et des ingrédients identiques et recevaient la même recette pour un gâteau, devrions-nous nous attendre à des résultats identiques?

Pour clarifier ce que je demande, pourquoi ne pouvez-vous pas, au lieu d'impliquer la correction d'erreurs, exécuter simplement les opérations, disons, cent fois, et choisir la réponse moyenne / la plus courante?

Vous gâtez la pesée en tapant du doigt sur la balance.

Si vous assistez à un concert bruyant et essayez de communiquer avec la personne à côté de vous, vous comprend-elle la première fois, à chaque fois?

Si vous racontez une histoire ou répandez une rumeur (et certaines personnes communiquent textuellement, certaines ajoutent leur propre spin et d'autres oublient des parties), quand cela vous revient, cela se fait-il en moyenne et devient essentiellement (mais pas à l'identique) le même chose que tu as dit? - peu probable.

C'est comme froisser un morceau de papier puis l'aplatir.

Toutes ces analogies étaient destinées à offrir plus de simplicité que d'exactitude, vous pouvez les relire plusieurs fois, les calculer en moyenne et avoir la réponse exacte, ou non. ;)


Une explication plus technique des raisons pour lesquelles la correction d'erreurs quantiques est difficile mais nécessaire est expliquée sur la page Web de Wikipedia: " Correction d'erreurs quantiques ":

"La correction d'erreurs quantiques (QEC) est utilisée dans l'informatique quantique pour protéger les informations quantiques contre les erreurs dues à la décohérence et à d'autres bruits quantiques . La correction d'erreurs quantiques est essentielle si l'on veut obtenir un calcul quantique tolérant aux pannes qui peut traiter non seulement le bruit sur le informations quantiques, mais aussi avec des portes quantiques défectueuses, une préparation quantique défectueuse et des mesures défectueuses. ".

"La correction d'erreur classique utilise la redondance ." ...

"La copie d'informations quantiques n'est pas possible en raison du théorème de non-clonage . Ce théorème semble présenter un obstacle à la formulation d'une théorie de la correction d'erreurs quantiques. Mais il est possible de diffuser les informations d'un qubit sur un état fortement enchevêtré de plusieurs ( physique). Peter Shor a découvert pour la première fois cette méthode de formulation d'un code de correction d'erreurs quantiques en stockant les informations d'un qubit dans un état fortement enchevêtré de neuf qubits. Un code de correction d'erreurs quantiques protège les informations quantiques contre les erreurs de forme limitée. ".

Rob
la source
2

le bruit devrait se résorber.

Le bruit ne se calcule pas parfaitement. C'est le sophisme du joueur. Même si le bruit a tendance à serpenter d'avant en arrière, il s'accumule toujours avec le temps.

Par exemple, si vous générez N tours de pièces justes et les additionnez, l’amplitude attendue de la différence N/2 les têtes poussent comme O(N). C'est quadratique mieux que leO(N) vous attendez d'une pièce biaisée, mais certainement pas 0.

Pire encore, dans le contexte d'un calcul sur de nombreux qubits, le bruit ne s'annule presque pas aussi bien, car le bruit n'est plus le long d'une seule dimension. Dans un ordinateur quantique avecQ qubits et bruit à qubit unique, il existe 2Qdimensions à tout moment pour que le bruit agisse (un pour chaque axe X / Z de chaque qubit). Et lorsque vous calculez avec les qubits, ces dimensions changent pour correspondre à différents sous-espaces d'un2Qespace dimensionnel. Il est donc peu probable que le bruit ultérieur annule le bruit précédent et, par conséquent, vous revenez àO(N) accumulation de bruit.

exécuter les opérations, disons, cent fois, et choisir la réponse moyenne / la plus courante?

Au fur et à mesure que les calculs deviennent plus grands et plus longs, la probabilité de ne pas voir de bruit ou d'annuler parfaitement le bruit devient si proche de 0% que vous ne pouvez pas vous attendre à voir la bonne réponse même une fois, même si vous avez répété le calcul un billion de fois.

Craig Gidney
la source