Classical Error Correction／古典的な誤り訂正

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

デコヒーレンスは、量子状態やゲート操作に誤りをもたらします。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)だけを訂正できるということです。