A couple of times so far in this course, we have alluded to the decoherence of quantum states caused by noise and imperfections in our control systems. We can mitigate this problem using error correction.

Decoherence results in errors in our states or gates. We saw when we discussed Shor’s algorithm that our systems need to be nearly perfect in order to be useful, with error rates of (10^{-13}) or better – that is, less than one error in every (10^{13}) gates that we execute. However, the hardware we have talked about this week has error rates that range from (10^{-3}) to perhaps (10^{-5}), depending on experimental conditions and the particular technology. So is computation simply beyond our technical capabilities for the foreseeable future?

Our hope lies in quantum error correction. First, let’s review the basic idea of error correction, then look at the behavior of quantum errors in this article, before studying the mechanisms used in the next article.

Error Correction Concepts

Classical computers depend heavily on error correcting codes, the core ideas of which were developed originally by Richard W. Hamming back in 1947. Today, there are many different known choices of error correcting code. Fundamentally, error correcting codes add redundancy to the information in a message, then use that redundancy to detect and correct errors that occur in transmission or storage of data.

The simplest approach is simply to repeat information: if you want to send a 0, send 00 instead; if you want to send a 1, send 11. With two copies of the data, it is easy to detect an error. If the receiver receives 01 or 10, she knows that an error has occurred. Unfortunately, she doesn’t know which the correct state is, since the result is now ambiguous. The minimum number of copies necessary to be able to recover the original state is three: a single error then results in a state such as 001 or 010, from which it is easy to infer that the most likely original message was intended to be 000 (or just 0, once decoded). Such an error is called a bit flip.

In this simple repetition code, we refer to 000 and 111 as our code words. The code words associated with a particular choice of error correcting code are the legitimate states. Collectively, they make up the code space. The code rate in this case is (1/3), since it takes three bits to transmit a one-bit message. More generally, if the code uses (n) bits to encode (k) bits of message, then the rate is (k/n).

The number of bits that must be flipped to move from one code word to another is the code distance. With our triple repetition code, all three bits must be flipped, (000rightarrow 001rightarrow 011rightarrow 111), so the code distance is three.

Code Words, Distance and Error Probability

The code distance for a particular error correcting code (whether quantum or classical) is known as the Hamming distance. It’s the number of bit flips required to move from one code word to another. If the code distance is (d = 3), then three bits must be flipped to move from 000 to 111 or vice versa. If this happens, the errors go completely undetected; it is impossible to recognize that anything untoward has happened. If the probability of any individual bit being in error is (p), then the probability of this happening is (p^d = p^3). For example, if (p = 10^{-3}), then (p^3 = 10^{-9}). Our error rate has suddenly dropped from one in a thousand to one in a billion.

However, it’s not quite that simple. If two errors occur, e.g. (000rightarrow 001rightarrow 101), then we have a state that’s not one of the code words, and recognize that at least one error has occurred. We say that we are outside of the code space, and must decide how to correct the state. With (n) bits, the probability of (e) errors occurring is (binom{n}{e}p^e(1-p)^{n-e}). ((binom{n}{e}) is the binomial coefficient from basic probability and statistics, also sometimes written (_n C_e).) If we are holding (101), the probability that we started with 000 and two errors occurred (what actually happened) is (p^2(1-p)), but the probability that we started with 111 and only error occurred is (p(1-p)^2). The latter appears to be more likely, so we will choose to “correct” back to 111, perpetuating an error and ruining our data. The fundamental rule is that an error correcting code can only correct errors less than half of the code distance, (e < d/2).

古典的な誤り訂正

これまでにこのコースで何回か、制御システムのノイズや不完全さに起因する量子状態のデコヒーレンスを述べてきました。 誤り訂正を使用してこの問題を緩和することができます。

デコヒーレンスは、量子状態やゲート操作に誤りをもたらします。Shorのアルゴリズムについては、エラー率が(10^{13})以上、つまり実行する(10^{13})ゲートごとに1つ未満の誤差で、システムをほぼ完璧にする必要があることがわかりました。しかし、私たちが今週話したハードウェアは、実験条件や特定の技術に応じて、(10^{-3})からおそらく(10^{-5})までのエラー率を持っています。 近い将来に、この技術的限界を超えた計算が実現できるのでしょうか？

私たちの希望は量子誤り訂正にあります。 この記事では、（次の記事で使用する仕組みを調べる前に、）誤り訂正の基本的な考え方を確認してから、量子エラーの動作を見てみましょう。

エラー修正の概念

従来型のなコンピュータの動作は誤り訂正符号に大きく依存しており、その中核となる考え方は1947年にRichard W. Hammingによって最初に開発されました。現在、誤り訂正符号の選択肢は数多く知られています。基本的には、誤り訂正符号はメッセージ内の情報に冗長性を追加し、その冗長性を使用してデータの送信または格納時に発生するエラーを検出して訂正します。

最も単純な符号化の方法は、単に情報を繰り返すことです：0を送る場合は00を代わりに送ります。あなたは1を送信したい場合は、11を送信します。データの2つのコピーで、エラーを検出するのは簡単です。受信者が01または10を受信すると、エラーが発生したことがわかります。残念ながら、結果はあいまいであるため、正しい状態がどれか分かりません。元の状態を回復するために必要な最小コピー数は3です。1つのエラーが001または010のような状態になり、最も可能性の高い元のメッセージが000であることが容易に推測されます(もしく１回だけデコードされ、結果は0です)。このような誤り訂正はビットフリップと呼ばれます。

この簡単な反復コードでは、000と111を符号語（コードワード）と呼びます。 誤り訂正符号の特定の選択に関連する符号語は正当な状態である。 集合的に、それらは符号空間を構成します。この場合の符号レートは、1ビットのメッセージを送信するのに3ビットかかるので、 (⅓)です。より一般化すると、(k)ビットのメッセージを符号化するために(n)ビットを使用する場合、レートは(k/n)です。

ある符号語から別の符号語に移動するために反転されなければならないビット数を符号距離と言います。私たちの３回反復符号では、3つのビットはすべて反転されなければなりません。(000rightarrow 001rightarrow 011rightarrow 111)よって符号距離は3です。

コードワード、距離およびエラー確率

特定の誤り訂正符号（量子または古典）の符号距離は、ハミング距離として知られています。ある符号語から別の符号語に移動するのに必要なビットフリップの数です。符号距離が(d=3)の場合、000から111へまたはその逆に移動するには、3ビットを反転する必要があります。この場合、エラーは完全に検出されません。不都合なことが起こったことを認識することは不可能です。個々のビットが誤っている確率が(p)ならば、この確率は(p^d = p^3)となります。たとえば、(p = 10^{-3})の場合、(p^3 = 10^{-9})です。 私たちのエラー率は、突然1000分の１から1億分の１に低下しました。

しかし、それほど単純ではありません。2つのエラーが発生した場合、例えば、 (000rightarrow 001rightarrow 101)の場合、符号語に当てはまらない状態があり、少なくとも1つのエラーが発生したことを認識します。我々は符号空間の外にいると言って、状態を訂正する方法を決めなければなりません。(n)ビットでは、(e)エラーが発生する確率は(binom{n}{e}p^e(1-p)^{n-e})になります。((binom{n}{e})は基本確率と統計からの二項係数で、(_n C_e)と書かれている場合もあります。) 先程の101の場合、実際には000で開始して(p^2(1-p))の確率で2つのエラーが発生しました。一方で111で始まり１つのエラーが発生して101となった確率は(p(1-p)^2)です。後者はより可能性が高いと思われるので、私たちは111への「訂正」を選択し、エラーを永続させ、データは壊れてしまいます。原則として誤り訂正符号は、符号距離の半分未満の誤り、すなわち、(e < d/2)だけを訂正できるということです。