Ist eine Fehlerkorrektur notwendig?

20

Warum brauchen Sie eine Fehlerkorrektur? Nach meinem Verständnis werden durch die Fehlerkorrektur Fehler aus dem Rauschen entfernt, aber das Rauschen sollte sich selbst ausmitteln. Um zu verdeutlichen, wonach ich frage, warum können Sie nicht einfach, anstatt eine Fehlerkorrektur durchzuführen, die Operationen beispielsweise hundertmal ausführen und die durchschnittliche / häufigste Antwort auswählen?

Heide
quelle

Antworten:

18

Das skaliert nicht gut. Nach einer mäßig langen Berechnung haben Sie im Grunde genommen den maximal gemischten Zustand oder welchen festen Punkt Ihr Rauschen hat. Um auf beliebig lange Berechnungen zu skalieren, müssen Sie Fehler korrigieren, bevor sie zu groß werden.

Hier ist eine kurze Berechnung für die oben angegebene Intuition. Betrachten Sie das einfache Modell des weißen Rauschens (depolarisierendes Rauschen): wobeiρder ideale Zustand ist (es gilt dieStandardnotation). Wenn Siensolche verrauschten Prozesseverketten, ist der neue Rauschparameterε=1-(

ρ(ε)=(1ε)ρ+εItrI,
ρn , was in der Anzahl der Gatter (oder anderer Fehlerquellen) exponentiell zunimmt. Wenn Sie das Experiment m- malwiederholenund annehmen, dass der Standardfehler auf 1 skaliertε=1(1ε)nm Sie sehen, dass die Anzahl der Läufemin der Länge Ihrer Berechnung exponentiell wäre!1mm
M. Stern
quelle
11

Wenn die Fehlerrate niedrig genug wäre, könnten Sie eine Berechnung hundertmal ausführen und die häufigste Antwort verwenden. Dies funktioniert beispielsweise, wenn die Fehlerrate so niedrig ist, dass die erwartete Anzahl von Fehlern pro Berechnung sehr gering ist. Das bedeutet, dass die Funktionsweise dieser Strategie davon abhängt, wie lange und kompliziert eine Berechnung sein soll, die Sie durchführen möchten.

Sobald die Fehlerrate oder die Länge Ihrer Berechnung ausreichend hoch ist, können Sie nicht mehr sicher sein, dass das wahrscheinlichste Ergebnis null Fehler ist: Ab einem bestimmten Punkt ist es wahrscheinlicher, dass Sie einen oder zwei haben, oder mehr Fehler, als dass Sie Null haben. In diesem Fall hindert nichts die meisten Fälle daran, Ihnen eine falsche Antwort zu geben. Was dann?

Diese Probleme sind für die Quantenberechnung nicht besonders: Sie gelten auch für die klassische Berechnung. Es kommt lediglich vor, dass fast alle unsere Technologien in einem ausreichend fortgeschrittenen Zustand sind, sodass uns diese Probleme in der Praxis nicht beschäftigen. Möglicherweise besteht eine größere Wahrscheinlichkeit, dass Ihr Computer während der Berechnung von einem Meteoriten getroffen wird (oder der Akku fast leer ist oder Sie ihn ausschalten), als dass ein Hardwarefehler vorliegt. Das (vorübergehende) Besondere an der Quantenberechnung ist, dass die Technologie noch nicht ausgereift genug ist, um hinsichtlich der Möglichkeit von Fehlern so gelassen zu sein.

In jenen Zeiten, in denen das klassische Rechnen hatIn einem Stadium, in dem die Fehlerkorrektur sowohl praktisch als auch notwendig war, konnten wir bestimmte mathematische Techniken anwenden - die Fehlerkorrektur -, die es ermöglichten, die effektive Fehlerrate zu unterdrücken und im Prinzip so niedrig zu machen, wie wir es wollten. Die gleichen Techniken können überraschenderweise für die Quantenfehlerkorrektur verwendet werden - mit ein wenig Erweiterung, um den Unterschied zwischen Quanten- und klassischer Information auszugleichen. Vor Mitte der neunziger Jahre wurde zunächst angenommen, dass eine Quantenfehlerkorrektur aufgrund der Kontinuität des Raums der Quantenzustände unmöglich sei. Es stellt sich jedoch heraus, dass durch die richtige Anwendung klassischer Fehlerkorrekturtechniken auf die verschiedenen Arten, wie ein Qubit gemessen werden kann (üblicherweise als "Bit" und "Phase" bezeichnet), Sie können im Prinzip auch viele Arten von Rauschen auf Quantensystemen unterdrücken. Diese Techniken sind auch nicht speziell für Qubits: Dieselbe Idee kann für Quantensysteme beliebiger endlicher Dimensionen verwendet werden (obwohl sie bei Modellen wie der adiabatischen Berechnung möglicherweise die tatsächliche Durchführung der von Ihnen gewünschten Berechnung behindert).

Zum Zeitpunkt, an dem ich dies schreibe, sind einzelne Qubits so schwierig zu bauen und zu verteilen, dass die Leute hoffen, mit der Durchführung von Proof-of-Principles-Berechnungen ohne jegliche Fehlerkorrektur davonzukommen. Das ist in Ordnung, aber es wird begrenzen, wie lange ihre Berechnungen dauern können, bis die Anzahl der akkumulierten Fehler groß genug ist, dass die Berechnung nicht mehr aussagekräftig ist. Es gibt zwei Lösungen: Verbesserung der Rauschunterdrückung oder Anwendung der Fehlerkorrektur. Beide sind gute Ideen, aber es ist möglich, dass die Fehlerkorrektur mittel- und langfristig einfacher durchzuführen ist als die Unterdrückung von Rauschquellen.

Niel de Beaudrap
quelle
Als schnelle Korrektur leidet moderne Hardware unter nicht zu vernachlässigenden Fehlerraten, und es werden Fehlerkorrekturmethoden verwendet. Das heißt, natürlich ist Ihr Standpunkt zu den Problemen, die auf aktuellen Quantencomputern noch viel schlimmer sind, zutreffend.
Nat
@Nat: interessant. Mir ist vage bewusst, dass dies derzeit bei GPUs der Fall sein kann, und (in einem Kontext, in dem keine aktiven Berechnungen erforderlich sind) RAID-Arrays sind ebenfalls ein offensichtliches Beispiel. Aber können Sie andere Hardwareplattformen beschreiben, für die die klassische Berechnung während einer Berechnung auf einer Fehlerkorrektur beruhen muss?
Niel de Beaudrap
Scheint, dass Fehler am häufigsten in Netzwerkkontexten auftreten, gefolgt von Festplattenspeicher, gefolgt von RAM. Netzwerkprotokolle und Festplatten implementieren routinemäßig Tricks zur Fehlerkorrektur. RAM ist eine gemischte Tasche; Server- / Workstation-RAM verwendet in der Regel Fehlerkorrekturcode (ECC), Consumer-RAM jedoch häufig nicht. Bei CPUs würde ich mir vorstellen, dass sie implementierungsspezifischere Taktiken haben, aber das wären wahrscheinlich Herstellergeheimnisse. Fehlerraten in CPUs und GPUs werden in einigen Fällen auf einem beobachtbaren Niveau relevant, z. B. bei Übertaktungs- und Hersteller-Core-Locking-Entscheidungen.
Nat
Eigentlich ein bisschen neugierig auf CPU-Typ-Fehlerkorrektur .. Ich meine, der Cache scheint anfällig für die gleichen Probleme zu sein wie normaler RAM (es sei denn, er ist irgendwie mit mehr Leistung gepuffert oder so?), Was auf Servern vermutlich inakzeptabel wäre. Workstation-Kontexte. Aber auf Registerebene? Das wäre etwas Ordentliches, worüber man lesen könnte. Ich habe nichts sofort bei Google gesehen, obwohl ich annehme, dass solche Informationen wahrscheinlich ein Geschäftsgeheimnis sind.
Nat
8

Nun zu M. Sterns Antwort :

Der Hauptgrund, warum für Quantencomputer eine Fehlerkorrektur erforderlich ist, liegt darin, dass Qubits ein Kontinuum von Zuständen aufweisen (der Einfachheit halber betrachte ich derzeit nur Qubit-basierte Quantencomputer).

α|0+β|1α|0+βeiϕ|1 but actually becomes α|0+βei(ϕ+δ)|1. The actual state is close to the correct state but still wrong. If we don't do something about this the small errors will build up over the course of time and eventually become a big error.

Moreover, quantum states are very delicate, and any interaction with the environment can cause decoherence and collapse of a state like α|0+β|1 to |0 with probability |α|2 or |1 with probability |β|2.

In a classical computer if say a bit's value is being replicated n-times as follows:

000000...n times
and
111111...n times

In case after the step something like 0001000100 is produced it can be corrected by the classical computer to give 0000000000 because majority of the bits were 0s and most probably the intended aim of the initial operation was replicating the 0-bit 10 times.

But, for qubits such a error correction method won't work, because first of all duplicating qubits directly is not possible due to the No-Cloning theorem. And secondly, even if you could replicate |ψ=α|0+β|1 10-times it's highly probably that you'd end up with something like (α|0+β|1)(αeiϵ|0+βeiϵ|1)(αeiϵ2|0+βeiϵ2|1)... i.e. with errors in the phases, where all the qubits would be in different states (due to the errors). That is, the situation is no-longer binary. A quantum computer, unlike a classical computer can no longer say that: "Since majority of the bits are in 0-state let me convert the rest to 0 !", to correct any error which occurred during the operation. That's because all the 10 states of the 10 different qubits might be different from each other, after the so-called "replication" operation. The number of such possible errors will keep increasing rapidly as more and more operations are performed on a system of qubits. M. Stern has indeed used the right terminology in their answer to your question i.e. "that doesn't scale well".

So, you need a different breed of error correcting techniques to deal with errors occurring during the operation of a quantum computer, which can deal not only with bit flip errors but also phase shift errors. Also, it has to be resistant against unintentional decoherence. One thing to keep in mind is that most quantum gates will not be "perfect", even though with right number of "universal quantum gates" you can get arbitrarily close to building any quantum gate which performs (in theory) an unitary transformation.

Niel de Beaudrap mentions that there are clever ways to apply classical error correction techniques in ways such that they can correct many of the errors which occur during quantum operations, which is indeed correct, and is exactly what current day quantum error correcting codes do. I'd like to add the following from Wikipedia, as it might give some clarity about how quantum error correcting codes deal with the problem described above:

Classical error correcting codes use a syndrome measurement to diagnose which error corrupts an encoded state. We then reverse an error by applying a corrective operation based on the syndrome. Quantum error correction also employs syndrome measurements. We perform a multi-qubit measurement that does not disturb the quantum information in the encoded state but retrieves information about the error. A syndrome measurement can determine whether a qubit has been corrupted, and if so, which one. What is more, the outcome of this operation (the syndrome) tells us not only which physical qubit was affected, but also, in which of several possible ways it was affected. The latter is counter-intuitive at first sight: Since noise is arbitrary, how can the effect of noise be one of only few distinct possibilities? In most codes, the effect is either a bit flip, or a sign (of the phase) flip, or both (corresponding to the Pauli matrices X, Z, and Y). The reason is that the measurement of the syndrome has the projective effect of a quantum measurement. So even if the error due to the noise was arbitrary, it can be expressed as a superposition of basis operations—the error basis (which is here given by the Pauli matrices and the identity). The syndrome measurement "forces" the qubit to "decide" for a certain specific "Pauli error" to "have happened", and the syndrome tells us which, so that we can let the same Pauli operator act again on the corrupted qubit to revert the effect of the error.

The syndrome measurement tells us as much as possible about the error that has happened, but nothing at all about the value that is stored in the logical qubit—as otherwise the measurement would destroy any quantum superposition of this logical qubit with other qubits in the quantum computer.


Note: I haven't given any example of actual quantum error correcting techniques. There are plenty of good textbooks out there which discuss this topic. However, I hope this answer will give the readers a basic idea of why we need error correcting codes in quantum computation.


Recommended Further Readings:

Recommended Video Lecture:

Mini Crash Course: Quantum Error Correction by Ben Reichardt, University of Southern California

Sanchayan Dutta
quelle
3
I'm not sure the fact that there is a continuum of states plays any role. Classical computation with bits would also have the same problems if our technology were less mature, and indeed it did suffer meaningfully from noise at various times in its development. In both the classical and quantum case, noise doesn't conveniently average away under normal circumstances
Niel de Beaudrap
@NieldeBeaudrap It does play a big role. In classical computation you know that you'd have to deal only with two states, beforehand. Just consider an example: In classical computation if a signal of 5 mV represents "high" (or 1-state) while 0 mV theoretically represents the "low" (or 0-state), if your operation ended up with something like 0.5 mV it would be automatically be rounded off to 0 mV because it is much closer to 0 mV than 5 mV. But in case of qubits there are an infinite number of possible states and such rounding off doesn't work.
Sanchayan Dutta
Of course you're not wrong when you say that even classical computation suffered from the problem of noise. There's a well established theory of classical error correcting codes too! However, the situation is much more dire in case of quantum computation due to the possibility of infinite number of states of existence of a single qubit.
Sanchayan Dutta
1
The techniques used for quantum error correction does not involve the fact that the state-space is infinite in any way. The arguments you are making seem to be drawing an analogy between quantum computing and analog computing --- while there is a similarity, it would imply that quantum error correction would be impossible if it were a sound analogy. In contrast, the state-space of many qubits is also like a probability distribution on bit-strings, of which there is also a continuum; and yet just doing error correction on definite bit-strings suffices to suppress error.
Niel de Beaudrap
1
@glS I have removed the first sentence. You're right. I was interpreting computation in an unrelated way.
Sanchayan Dutta
2

Why do you need error correction? My understanding is that error correction removes errors from noise, but noise should average itself out.

If you built a house or a road and noise was a variance, a difference, with respect to straightness, to direction, it's not solely / simply: "How would it look", but "How would it be?" - a superposition of both efficiency and correctness.

If two people calculated the circumference of a golf ball given a diameter each would get a similar answer, subject to the accuracy of their calculations; if each used several places of decimal it would be 'good enough'.

If two people were provided with identical equipment and ingredients, and given the same recipe for a cake, should we expect identical results?

To make clear what I'm asking, why can't you, instead of involving error correction, simply run the operations, say, a hundred times, and pick the average/most common answer?

You're spoiling the weighing, tapping your finger on the scale.

If you're at a loud concert and try to communicate with the person next to you do they understand you the first time, everytime?

If you tell a story or spread a rumor, (and some people communicate verbatim, some add their own spin, and others forget parts), when it gets back to you does it average itself out and become essentially (but not identically) the same thing you said? - unlikely.

It like crinkling up a piece of paper and then flattening it out.

All those analogies were intended to offer simplicity over exactness, you can reread them a few times, average it out, and have the exact answer, or not. ;)


A more technical explanation of why quantum error correction is difficult but neccessary is explained on Wikipedia's webpage: "Quantum Error Correction":

"Quantum error correction (QEC) is used in quantum computing to protect quantum information from errors due to decoherence and other quantum noise. Quantum error correction is essential if one is to achieve fault-tolerant quantum computation that can deal not only with noise on stored quantum information, but also with faulty quantum gates, faulty quantum preparation, and faulty measurements.".

"Classical error correction employs redundancy. " ...

"Copying quantum information is not possible due to the no-cloning theorem. This theorem seems to present an obstacle to formulating a theory of quantum error correction. But it is possible to spread the information of one qubit onto a highly entangled state of several (physical) qubits. Peter Shor first discovered this method of formulating a quantum error correcting code by storing the information of one qubit onto a highly entangled state of nine qubits. A quantum error correcting code protects quantum information against errors of a limited form.".

Rob
quelle
2

noise should average itself out.

Noise doesn't perfectly average itself out. That's the Gambler's Fallacy. Even though noise tends to meander back and forth, it still accumulates over time.

For example, if you generate N fair coin flips and sum them up, the expected magnitude of the difference from exactly N/2 heads grows like O(N). That's quadratically better than the O(N) you expect from a biased coin, but certainly not 0.

Even worse, in the context of a computation over many qubits the noise doesn't cancel itself nearly as well, because the noise is no longer along a single dimension. In a quantum computer with Q qubits and single-qubit noise, there are 2Q dimensions at any given time for the noise to act on (one for each X/Z axis of each qubit). And as you compute with the qubits, these dimensions change to correspond to different subspaces of a 2Q dimensional space. This makes it unlikely for later noise to undo earlier noise, and as a result you're back to O(N) accumulation of noise.

run the operations, say, a hundred times, and pick the average/most common answer?

As computations get larger and longer, the chance of seeing no noise or of the noise perfectly cancelling out rapidly becomes so close to 0% that you can't expect see the correct answer even once even if you repeated the computation a trillion times.

Craig Gidney
quelle