Ist eine Fehlerkorrektur notwendig?

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?

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-

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.

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).

$\alpha|0\rangle+\beta|1\rangle$$\alpha|0\rangle + \beta e^{i\phi}|1\rangle$ but actually becomes $\alpha|0\rangle+\beta e^{i(\phi+\delta)}|1\rangle$. 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 $\alpha|0\rangle+\beta|1\rangle$ to $|0\rangle$ with probability $|\alpha|^2$ or $|1\rangle$ with probability $|\beta|^2$.

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

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 $0's$ 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 $|\psi\rangle = \alpha |0\rangle +\beta |1\rangle$ 10-times it's highly probably that you'd end up with something like $(\alpha|0\rangle + \beta |1\rangle)\otimes (\alpha e^{i\epsilon}|0\rangle + \beta e^{i\epsilon'}|1\rangle)\otimes (\alpha e^{i\epsilon_2}|0\rangle + \beta e^{i\epsilon_2'}|1\rangle)\otimes ...$ 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:

• An Introduction to Quantum Error Correction and Fault-Tolerant Quantum Computation - Daniel Gottesman

• Scheme for reducing decoherence in quantum computer memory - Peter Shor

Recommended Video Lecture:

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

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.".

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(\sqrt 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 $2^Q$ 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.