この記事について
アドベントカレンダもついに17日目となりました！
これまでは、アルゴリズムを中心に扱っていきましたが、FTQCに向けては、
量子系の誤りを如何に訂正するか？も重要な論点となります。
そこで、17日目、18日目は量子誤り訂正を扱ってみたいと思います。
まずは、比較的簡単な、Shorの符号です。
- Shor's 9-bit Quantum Error Collection Code1
また、他の量子コンピュータ関係の他の記事は、下記で紹介しています。
なお、本記事は、下記を再編集したもので、既読の方には重複の内容となります。
マウスで量子誤り訂正（①ビットフリップ）
マウスで量子誤り訂正(②フェーズフリップ)
マウスで量子誤り訂正(③Shorの符号)
% basic braket
\newcommand{\bra}[1]{\left\langle #1 \right|}
\newcommand{\ket}[1]{\left| #1 \right\rangle}
\newcommand{\bracket}[2]{\left\langle #1 \middle| #2 \right\rangle}
\newcommand{\ketbra}[2]{\left| #1 \right\rangle \left\langle #2 \right|}
\newcommand{\ketbraket}[3]{\left| #1 \right\rangle \left\langle #2 \middle| #3 \right\rangle}
% small-size
\newcommand{\bras}[1]{\left\langle {\scriptsize #1} \right|}
\newcommand{\kets}[1]{\left| {\scriptsize #1} \right\rangle}
\newcommand{\brackets}[2]{\left\langle {\scriptsize #1} \middle| {\scriptsize #2} \right\rangle}
\newcommand{\ketbras}[2]{\left| {\scriptsize #1} \right\rangle \left\langle {\scriptsize #2} \right|}
\newcommand{\ketbrakets}[3]{\left| {\scriptsize #1} \right\rangle \left\langle {\scriptsize #2} \middle| {\scriptsize #3} \right\rangle}
% Matrix
\newcommand{\tate}[2]{\begin{bmatrix} #1 \\ #2 \end{bmatrix}}
\newcommand{\yoko}[2]{\begin{bmatrix} #1 & #2 \end{bmatrix}}
\newcommand{\mtrx}[4]{\begin{bmatrix} #1 & #2 \\ #3 & #4 \end{bmatrix}}
説明のアウトライン
かなり長い記事となるので、先に説明のアウトラインを示します。
- 最初に量子誤り訂正がなぜ困難なのか？について確認します。
- 量子状態の誤りには、どんな種類があるのかを見ていきます。
- ビットフリップの訂正回路を確認します
- フェーズフリップの訂正回路を確認します
- 最後に、ビット／フェーズフリップの訂正回路を組み合わせてShorのコードを組み立てます
①量子誤り訂正の難しさ
Nielsen & Chuang, Quantum Computation and Quantum Information2 は、量子誤り訂正では、
下記３点が課題だと指摘しています。
- No cloning
- Errors are continuous
- Measurement destroys quantum information
一個ずつ見ていきましょう。
No cloning
「量子状態は、コピー・複製ができない」という量子複製不能定理が存在します。
誤りを訂正したい対象がコピーできるのであれば、量子状態をコピーし処理してから突き合わせを行えばエラーが訂正できますが、コピーそのものが不可能という点が、誤り訂正を困難にします。
Errors are continuous
ブロッホ球を想像いただくとわかりやすいですが、量子状態は連続的であるため、エラーも連続的で様々なパターン発生します。
| 古典ビット | 量子ビット |
|---|---|
| 0か1なので、誤りのバリエーションも少ない | 単位球上の様々な位置を取るので、 誤りのパターンも連続的で訂正が難 |
 
|
 
|
Measurement destroys quantum information
古典ビットにおける誤り訂正は、誤り対象対象データとパリティ等の誤り訂正符号を比較し、訂正を行います。これは、古典ビットにおいては誤り訂正データにいつでもアクセスできることが前提に成り立ちます。
一方、量子ビットの誤り訂正では、量子状態が測定により破壊される性質を持つため、量子状態を測定することなく（中身を知ることなく）誤りだけを、訂正する必要がある。
困難さ。伝わったでしょうか。
②古典ビットと量子ビットの「誤り方」
誤り訂正の議論に入る前に、量子ビットではどんな種類の「誤り」が発生するのかを確認しておきます
古典ビット
下記のように符号反転（ビットフリップ）による誤りが、古典ビットでの「誤り方」です。
- 本来0だったものが、ノイズにより1になってしまった（0→1）
- 本来1だったものが、ノイズにより0になってしまった（1→0）
量子ビット
量子ビットでは、符号反転（ビットフリップ）に加え、位相反転(フェーズフリップ)が発生します。
具体的には下記に示すよう、パウリの$X,Z$ゲート相当の反転（フリップ）を想定します。
| 符号反転 ビットフリップ |
位相反転 フェーズフリップ |
|
|---|---|---|
| 説明 | 古典ビットと同様の0,1の逆転です | 古典には無い位相の逆転です 水平方向に反転します |
| イメージ | |
|
| 「誤り方」 | $\ket{0}→\ket{1}$ $\ket{1}→\ket{0}$ |
$\ket{+}→\ket{-}$ $\ket{-}→\ket{+}$ |
| パウリゲート でいうと |
$pauli \ X$相当のエラー | $pauli \ Z$相当のエラー |
③ ビットフリップエラーを訂正
まずは、符号が反転するビットフリップのエラー訂正から考えていきます。
Shorの誤り訂正符号は、下記のように複雑な形をしているのですが、これは、
-
１量子ビット目の$\ket{\psi}$を、残りの8個の補助ビット$\ket{0}$を使って誤り訂正する回路です
-
誤りの種類として、上述のビットフリップ／フェーズフリップの両者を想定しています。
-
上記背景で、複雑な回路となっていますが、ビットフリップだけであれば３量子ビットで実現できます
-
Shor's 9-bit Quantum Error Collection Code1
まずは、ビットフリップの訂正回路を見ていきましょう。
ビットフリップ訂正回路
まずは、触っていただくのが良いと思います。下記リンクでシミュレータを起動できます。
下記は、ビットフリップエラーを想定して、ノイズとして$X$ゲートを適用しています。
上記、確認いただきたいのは、下記２点です。
- 誤り訂正が無い１量子ビット目は影響が出ます（ブロッホ球が反転します）
- 一方、誤り訂正がされた２量子ビット目は、誤り訂正されノイズ影響が無く処理できます
では、回路を細かく見ていきます。まず、量子ビットの使い方ですが、
- 1ビット目は、誤り訂正のは関係無い、説明用の量子ビットです。
- 2ビット目が、誤り訂正対象です。このビットを守るために誤り訂正回路を作ります。
- 3,4ビット目は、誤り訂正を実装するための、補助量子ビットです。
| # | 機能 | 回路 | 説明 |
|---|---|---|---|
| 1 | エンコード |  |
誤り訂正対象に、補助ビットをかけ合わせます。 下記のように、ノイズに強い状態をつくります。 この点については、詳細後述します。 $(a\ket{0}+b\ket{1})\otimes\ket{00} → a\ket{000}+b\ket{111}$ |
| 2 | デコード |  |
元の1ビット＋補助2ビットの状態に戻します。 3量子ビットのいずれかにノイズが発生した場合 デコード後の補助量子ビットに情報が保存されます $a\ket{000}+b\ket{111} → (a\ket{0}+b\ket{1})\otimes\ket{00}$ |
| 3 | 誤り訂正 |  |
補助量子ビットのパターンで、誤りが発生した 量子ビットが特定できます。 補助が11のときに保護対象のビットに パウリ$X$のノイズが乗っているので訂正します |
何をエンコード、デコードしているか
エンコード回路
保護したい量子状態$\ket{\psi_{org}}$とした場合に、この$\ket{\psi_{org}}$は脆弱です。
\ket{\psi_{org}} = a\ket{0} + b\ket{1}
例えば、1ビットのパウリ$X_1$の反転が発生すると下記のようにビットが反転してしまいます。
X_1\ket{\psi_{org}} = a\ket{1} + b\ket{0} = b\ket{0} + a\ket{1}
と、$\ket{0}$と$\ket{1}$の確率振幅$a,b$が逆転してしまいました。
１量子ビット相当の情報（確率振幅$a,b$）を保全するための量子ビットとして、
- １量子ビットを用いて、１量子ビット相当の情報を扱うのは脆弱なので
- ３量子ビットを用いて、１量子ビット相当の情報を扱い、パウリ$X$への誤り耐性を高める
これがデコードです。
要は、３本の矢ですね。１本だと折れるが、３本なら折れない。
１量子ビット相当の情報（つまり、上記の$a,b$）を、あえて３量子ビットの$\ket{000},\ket{111}$を使って表現するためにはどうすれば良いでしょうか？
\ket{\psi_{enc}} = a\ket{000} + b\ket{111}
そうです。
$\ket{\psi_{org}}$を上記エンコード回路で処理することにより、上記の３本の矢の状態を作ることができます。
a\ket{000} + b\ket{100} \xrightarrow[]{CX12、13}a\ket{000} + b\ket{111} =\ket{\psi_{enc}}
この３本の矢の状態では、１ビットのビットフリップエラー（$X_1$)が発生すると、
X_1\ket{\psi_{enc}} = a\ket{000} + b\ket{111} \xrightarrow[]{X_1}a\ket{\color{red}{1}00} + b\ket{\color{red}{0}11}
と、赤いビットがフリップしますが、残り２ビットで、誤りを訂正可能です。
デコード回路
３本の矢状態の量子ビットにて、どのビットがエラーでフリップしたか？
誤りの場所を特定するのがデコード回路です。
エンコードされた量子状態$\ket{\psi_{enc}}$について、誤り訂正回路の1ビット目～3ビット目に、
パウリ$X$のエラーフリップが発生した状況を想定し、デコード回路を見ていきたいと思います。
エラー無しの状態をデコード回路($CX_{13,12}$)でデコードすると、下記のように、
- 保護したい量子状態$\ket{\psi_{org}}=a\ket{0} + b\ket{1}$と
- 補助ビット$\ket{00}$が取り出せます。
a\ket{000} + b\ket{111}
\xrightarrow[]{CX13、12}a\ket{000} + b\ket{100}
\
=
\ a\ket{0} + b\ket{1} \ \otimes \ \ket{00}
次に誤り訂正回路の各ビットにパウリ$X$のエラーが発生した状況を整理します。
| # | パウリ$X$エラーが 発生したビット |
エラー発生後 デコード前の状態 |
デコード後の状態 （$CX_{13,12}$後） |
補助ビットの状態 |
|---|---|---|---|---|
| 1 | エラー無し ※上記の式 |
$a\ket{000} + b\ket{111}$ | $a\ket{0} + b\ket{1} \ \otimes \ \ket{00}$ | $\ket{00}$ |
| 2 | １ビット目 (保護対象) |
$a\ket{\color{red}{1}00} + b\ket{\color{red}{0}11}$ | $a\ket{\color{red}{1}} + b\ket{0} \ \otimes \ \ket{11}$ | $\ket{\color{red}{11}}$ |
| 3 | ２ビット目 (補助①) |
$a\ket{0\color{red}{1}0} + b\ket{1\color{red}{0}1}$ | $a\ket{0} + b\ket{1} \ \otimes \ \ket{10}$ | $\ket{10}$ |
| 4 | ３ビット目 (補助②) |
$a\ket{00\color{red}{1}} + b\ket{11\color{red}{0}}$ | $a\ket{0} + b\ket{1} \ \otimes \ \ket{01}$ | $\ket{01}$ |
保護対象の量子ビットでの、パウリ$X$エラーによるビットフリップの検知を検討します。
補助量子ビットに着目すると状態が$\ket{11}$のとき、1ビット目は$a\ket{1}+b\ket{0}$と、
ビットフリップした状態となっています。（上記#2）
つまり、誤り訂正では、
- 補助量子ビットが、$\ket{11}$のときに（これを条件として）
- パウリ$X$にて、ビットフリップを誤り訂正する
という操作が必要になります。２つの補助量子ビットを条件としてパウリ$X$ゲートを適用する。
そうです。誤りの訂正には、トフォリゲートを用います。
誤り訂正
上記の#2のときに、トフォリゲートにより誤り訂正で、どういった状態となるかを計算で確認しておきたいと思います。デコード後の状態から計算すると、
\displaylines{
a\ket{\color{red}{1}} + b\ket{0} \ \otimes \ \ket{11}
\xrightarrow[]{CCX_{23→1}}
X(a\ket{\color{red}{1}} + b\ket{0}) \ \otimes \ \ket{11}
\\
=a\ket{0}+b\ket{1} \ \otimes \ \ket{11}
\ \
=
\ \
\color{red}{\ket{\psi_{org}}} \otimes \ket{11}
}
となり、トフォリゲート適用で、保護対象ビットの元の状態$\ket{\psi_{org}}$を取り出すことができました。
④ フェーズフリップ訂正回路
次にフェーズフリップの訂正回路を見ていきます。
まずは、触っていただくのが良いと思います。下記リンクでシミュレータを起動できます。
下記は、フェーズフリップエラーを想定して、ノイズとして$Z$ゲートを適用しています。
ビットフリップ訂正と同様に、
- 誤り訂正が無い１量子ビット目は影響が出ます（ブロッホ球が反転します）
- 一方、誤り訂正がされた２量子ビット目は、誤り訂正されノイズ影響が無く処理できます
では、回路を細かく見ていきます。まず、量子ビットの使い方ですが、
- 1ビット目は、誤り訂正のは関係無い、説明用の量子ビットです。
- 2ビット目が、誤り訂正対象です。このビットを守るために誤り訂正回路を作ります。
- 3,4ビット目は、誤り訂正を実装するための、補助量子ビットです。
ビットフリップ訂正との差分
ビットフリップ訂正回路との違いは、エンコード、デコード処理です。
比較すると下記の通りで、すべての量子ビットに対してエンコード／デコードともに
$H$（アダマール）を掛けている点が違いです。
| エンコード | デコード | |
|---|---|---|
| フェーズフリップ 訂正 |
 |
 |
| ビットフリップ 訂正 |
|
|
なぜ、Hを掛けるのか？
それは、3本の矢の作り方が違うからです。
ビットフリップ訂正は、パウリ$X$エラー（$\ket{0}→\ket{1}$とその逆）に強いエンコードを考えました。
\ket{\psi_{enc}} = a\ket{000} + b\ket{111}
$\ket{0}$が１本よりは、３本のほうが誤りにも強いだろうという考え方です。
では、フェーズフリップのパウリ$Z$エラー（$\ket{+}→\ket{-}$とその逆）訂正に向け
- どういったエンコードにすれば良いでしょうか？言い方をかえると、、
- 守りたい確率振幅（$a,b$）はどういった状態ベクトルに持たせるべきでしょうか？
パウリ$Z$エラー（$\ket{+}→\ket{-}$とその逆）に耐えるためには、
下記のようにアダマール基底を用いたエンコードが必要です。
\ket{\psi_{enc}} = a\ket{{\scriptsize +++}}
\
+
\
b\ket{{\scriptsize ---}}
つまり、エンコード後の状態が上記の様なアダマール基底を用いたエンコードとなるように、$H$を適用するのがフェーズフリップ訂正回路です。
保護対象の量子ビットの状態を$\ket{\psi}$とすると、下記のようにエンコード回路を用いてアダマール基底を用いたエンコード状態を作ることができます。
\ket{\psi} \otimes \ket{00}
\xrightarrow[]{CX_{12、13}}
a\ket{000} + b\ket{111}
\xrightarrow[]{H_{123}}
a\ket{{\scriptsize +++}}
\
+
\
b\ket{{\scriptsize ---}}
= \ket{\psi_{enc}}
デコード回路
一応、ビットフリップと同様にデコードの過程と、誤り訂正の適用条件を確認しておきますが、エンコードされた状態の基底が変わるだけで、デコード後の状態や誤り訂正の適用条件も同様です。
| # | パウリ$Z$エラーが 発生したビット |
エラー発生後 デコード前の状態 |
デコード後の状態 （$H_{123}CX_{13,12}$後） |
補助ビットの状態 |
|---|---|---|---|---|
| 1 | エラー無し ※上記の式 |
$a\ket{{\scriptsize +++}} + b\ket{{\scriptsize ---}}$ | $a\ket{0} + b\ket{1} \ \otimes \ \ket{00}$ | $\ket{00}$ |
| 2 | １ビット目 (保護対象) |
$a\ket{{\scriptsize \color{red}{-}++}} + b\ket{{\scriptsize \color{red}{+}--}}$ | $a\ket{\color{red}{1}} + b\ket{0} \ \otimes \ \ket{11}$ | $\ket{\color{red}{11}}$ |
| 3 | ２ビット目 (補助①) |
$a\ket{{\scriptsize +\color{red}{-}+}} + b\ket{{\scriptsize -\color{red}{+}-}}$ | $a\ket{0} + b\ket{1} \ \otimes \ \ket{10}$ | $\ket{10}$ |
| 4 | ３ビット目 (補助②) |
$a\ket{{\scriptsize ++\color{red}{-}}} + b\ket{{\scriptsize --\color{red}{+}}}$ | $a\ket{0} + b\ket{1} \ \otimes \ \ket{01}$ | $\ket{01}$ |
⑤ ビット、フェーズの両方の誤りに対応する
Shorの量子誤り訂正回路@Quirk
上記の２回路を組み合わせたのがShorの量子誤り訂正回路です。
ビットフリップ、フェーズフリップの両方の誤りに対し、エラー訂正が可能です。
構成を見ていくと、
- まず、エンコードに$H$が係るフェーズフリップ訂正のエンコードを行います。
- フェーズフリップ訂正は３量子ビットで行いますが、この３つのビットそれぞれにビットフリップ訂正のエンコード、デコード、訂正を行います。
- そして、ビットフリップの訂正終了後に、最後にフェーズフリップのデコード、訂正を行います。
- 上記見ていただくとわかるのですが、
- パウリ$X$エラー、パウリ$Z$エラーどちらが発生しても誤り訂正が行えます
- そして、１量子系の任意角度(パウリ$XZ$)エラーを訂正を行うことができます（※次節で後述）
- まさに、Nielsen & Chuang2が指摘する「Errors are continuous」に対処しています
任意のエラーに対応できるか？
補足として、上記の※を扱っておきます。
任意のエラーとは、ブロッホ球を想像していただくとわかりやすいのですが、元の状態$\ket{\psi_{org}}$に対して、X軸回転、Z軸回転、Y軸回転と任意軸の任意角度の回転が発生することを意味します。
この１量子系に対する任意角度の回転によるノイズ$\varepsilon_1$は、パウリゲートを用いると下記のように表現できます。
（下記４つのパウリゲートにて任意角度の回転が実現できるため。）
\varepsilon_1 = e_0I + e_1X_1 + e_2Z_1 + e_3X_1Z_1
\ \ \ \ \
e_n \in \mathbb{C}
上記式は、ノイズ$\varepsilon_1$が状態$\ket{\psi_{org}}$に発生すると、$\varepsilon_1\ket{\psi_{org}}$となり、ノイズ発生後の状態が、$I,X,Z,XZ$の重ね合わせ状態として表現されます。
この重ね合わせ状態は、測定により$I,X,Z,XZ$のいずれかに収縮し、これらのパウリ操作で訂正が可能された離散化されたエラー状態に収縮します。
つまり、パウリ$X$とパウリ$Z$に対するエラー訂正ができれば任意の$\varepsilon_1$に対する誤り訂正が可能となり、これを実現するのがShorの誤り訂正符号となります。
まとめ
Shorの9-bit Quantum Error Collection Codeを扱いました。
- 1量子ビットの量子状態（つまり確率振幅$a,b$）を保護するために、補助量子ビット8ビットを用いてビットフリップ、フェーズフリップに耐性を持つ誤り訂正回路を構成しました。
- 量子ビットは、コピーできない、観測で破壊されるという背景から、補助量子ビットはフリップに対する耐性を増すための３本の矢として活用し、誤り耐性を実現しました。
- Stabilizer符号等のより効率性が高い符号も存在しますが、量子誤り訂正のアウトラインを理解する意味では、Shor's Codeは良い題材だと思います。今後、他の誤り訂正符号も紹介したいと思います。
で、
明日も量子誤り訂正ですが、ちょっと**レベルアップしたStabilizer code(スタビライザ符号)**を扱います。
代数学と群論がでてきてしまうのですが、なるべくわかりやすく書いてみようと思いますので、ご興味ある方は明日チェックいただければと。
おまけ
上記の誤り訂正回路が、冒頭の課題をどのように解消しているかを確認しておきます。
9bitコード見てもよいのですが、複雑なので、ビットフリップ訂正回路で見ていきます
No cloning
保護対象$\ket{\psi}$をコピーすることはできません。
ですので、$\ket{\psi}$のパウリ$X$エラー耐性を高める目的で補助ビットを用います。
Errors are continuous
実をいうと、180度回転以外の回転角度のエラーにも対応しています。
シミュレータで、ノイズとして、$X$だけでなく、$X^{\frac{1}{2}}$,$X^{\frac{1}{4}}$等を適用しても誤り訂正可能です
Measurement destroys quantum information
3量子ビット全てを測定すると、量子状態は破壊されますが、
補助ビットのみ測定することで、量子状態を破壊しない誤り訂正が可能です。
おまけのおまけ(ノイズX^1/2の計算）
下記のノイズがX^(1/2)のパターンに関して、計算過程を下記に整理します。
計算方法は、ある勉強会で、お詳しい方に伺ったものです。ありがとうございます
$X$は下記のようにアダマール基底で書き下す事ができます
X = \ketbras{+}{+}-\ketbras{-}{-}
また、$X^{1/2}$を計算すると下記となります。
詳細は、分数ゲート? の計算方法をご確認ください。
X^{\frac{1}{2}}=\frac{1 \pm i}{2}\ketbra{0}{0}+\frac{1 \mp i}{2}\ketbra{0}{1}+\frac{1 \mp i}{2}\ketbra{1}{0}+\frac{1 \pm i}{2}\ketbra{1}{1}
よって、
\displaylines{
X^{\frac{1}{2}}\ket{0} = \frac{1 \pm i}{2}\ket{0} + \frac{1 \mp i}{2}\ket{1}
\\
X^{\frac{1}{2}}\ket{1} = \frac{1 \mp i}{2}\ket{0} + \frac{1 \pm i}{2}\ket{1}
}
ビットフリップ訂正回路を計算すると、
\displaylines{
\ket{\psi_{org}} = a\ket{0} + b\ket{1}
\xrightarrow[]{CX12,13(Encode)}
a\ket{000}+b\ket{111}
\\
\xrightarrow[]{X^{\frac{1}{2}}(Noize)}
\frac{1}{2}\left[\
a(1 \pm i)\ket{000} +
a(1 \mp i)\ket{100} +
b(1 \mp i)\ket{011} +
b(1 \pm i)\ket{111}
\right]
\\
\xrightarrow[]{CX_{12, 13}(Decode)}
\frac{1}{2}\left[\
a(1 \pm i)\ket{000} +
a(1 \mp i)\ket{111} +
b(1 \mp i)\ket{011} +
b(1 \pm i)\ket{100}
\right]
\\
\xrightarrow[]{CCX_{23→1}(Collect)}
\frac{1}{2}\left[\
a(1 \pm i)\ket{000} +
a(1 \mp i)\ket{011} +
b(1 \mp i)\ket{111} +
b(1 \pm i)\ket{100}
\right]
}
上記式を整理すると、下記の通り誤り訂正により$\ket{\psi_{org}}$を取り出すことができました。
(a\ket{0}+b\ket{1})(\frac{1 \pm i}{2}\ket{00}+\frac{1 \mp i}{2}\ket{11})
= \ket{\psi_{org}} \otimes (\frac{1 \pm i}{2}\ket{00}+\frac{1 \mp i}{2}\ket{11})