量子情報理論の基本：量子誤り訂正（CSS符号）

$$
\def\bra#1{\mathinner{\left\langle{#1}\right|}}
\def\ket#1{\mathinner{\left|{#1}\right\rangle}}
\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}}
$$

## はじめに

[前回の記事](https://qiita.com/SamN/items/4a02d8bba4f1df46ef2f)で古典線形符号について理解できたので、今回はそれをベースとした量子誤り訂正のクラスである「CSS符号(Calderbank-Shor-Steane code)」について勉強します。さらに、その具体的な符号方式として「Steane符号」についても見ていきます。一通り理解できたところで、量子計算シミュレータ[qlazy](https://github.com/samn33/qlazy)を使って、その「Steane符号」の動作を確認してみます。

ちなみに、「CSS符号」は、より一般的な量子誤り訂正のクラスである「スタビライザー符号(Stabilizer code)」の部分クラスに相当するとのことです。今回の記事は、それへの布石という位置づけでもあります。

参考にさせていただいたのは、以下の文献です。

1. [ニールセン、チャン「量子コンピュータと量子通信（３）」オーム社（2005年）](https://www.ohmsha.co.jp/book/9784274200090/)

## 理論の説明

### CSS符号の定義

$C_1$と$C_2$は古典線形符号$[n,k_1]$と$[n,k_2]$であり、$C_2 \subset C_1$とします。また、$C_1$と$C_{2}^{\perp}$はともに$t$個の誤りに対応可能であるとします。このとき$t$個の誤りに対応できる、$[n, k_1 - k_2]$の量子符号として、CSS符号$CSS(C_1,C_2)$を構築することができます。$x \in C_1$を符号$C_1$における任意の符号語であるとします。このとき量子状態$\ket{x + C_2}$を、

```math
\ket{x+C_2} \equiv \frac{1}{\sqrt{|C_{2}|}} \sum_{y \in C_2} \ket{x+y}  \tag{1}
```

のように定義します。ここで、右辺の$+$は2を法とするビットごとの和を表すものとします（以下同様）。この$\ket{x+C_2}$たちの重ね合わせによって表現される符号がCSS符号です。

イキナリなんのことかわかりません。噛み砕きます。

$x$は$[n,k_1]$符号$C_1$の要素なので、$k_1$次元のすべてのバイナリ・ベクトル（$0$または$1$を要素とするベクトル）から生成される$n$次元のバイナリ・ベクトルです。したがって、$x$の総数$|C_1|$は$2^{k_1}$個です。一方、$y$は$[n,k_2]$符号$C_2$の要素なので、$k_2$次元のすべてのバイナリ・ベクトルから生成される$n$次元のバイナリ・ベクトルです。したがって、$y$の総数$|C_2|$は$2^{k_2}$個です。また、$C_2 \subset C_1$ということなので、$k_2 < k_1$です。[前回の記事](https://qiita.com/SamN/items/4a02d8bba4f1df46ef2f)で「古典線形符号」が理解できていれば、ここまでは全然難しくないですね。

さて、式(1)の右辺は、$C_1$の要素$x$と$C_2$の要素$y$との和を指標とする状態ベクトル$\ket{x+y}$を、すべての$y \in C_2$について足しあげる格好になっています。それを$\ket{x+C_2}$という記号で定義しています。少し別の言い方をすると、$\ket{x+C_2}$は、ある$\ket{x} \space (x \in C_1)$を種にして、それに対してすべての$y \in C_2$を総動員して行った変換（ケットの中身に$y$を加える）を全部を合わせた重ね合わせ状態です。

ここで、線形符号の要素同士を足し合わせても、その同じ線形符号の要素になるので[^1]、右辺のすべてのケットの中身は$C_1$の要素であることに注意しておきましょう。つまり、種になる$x \in C_1$にすべての$y \in C_2 \subset C_1$を加えた結果の各々は、すべて$C_1$に属する符号になります。別の$x^{\prime} \in C_1$を種にしてすべての$y \in C_2$を加えた結果の各々も、すべて$C_1$に属する符号になります。ここで質問です。$x$と$x^{\prime}$を種にして生成された2つの符号の集まり（各々$2^{k_2}$個の集まりですが）に何か関係はありますでしょうか？実は、「全部同じ」または「全部違う」のどちらかであって、部分的に重なっているということはありません。

[^1]: $[n,k]$符号$C$を考え、その生成行列を$G$とします。任意の$x_1,x_2 \in \\{ 0,1 \\}^{k}$に対して、$y_1 = Gx_1, y_2 = Gx_2$とすると、$y_1, y_2 \in C$です。2つの式を足すと、$y_1 + y_2 = G(x_1 + x_2)$となり、$x_1 + x_2 \in \\{ 0,1 \\}^{k}$なので、$y_1+y_2 \in C$が成立ちます。

どういうことでしょうか？

いま考えている集合とは正確には違うのですが、一旦感覚を掴むために、類似した例を上げてみます。$0$から$99$までの整数の集合をイメージしてください。これを集合$C_1$とします。次に、$C_1$の中から$3$の倍数を取り出します。それを$C_2$とします。いま$C_1$の中から、ある特定の整数を取り出し$x$とします。これを種にして、すべての$y \in C_2$を総動員して、その各々を$x$に加えます（ただし$100$を法とした加算にします）。得られた結果は全部$0$から$99$までの整数になるので、$C_1$の要素になっています。例えば、$x=6$としてみましょう。このとき、$y$を加えてできあがった整数は全部$3$の倍数になります。$x^{\prime}=15$を考えて、同じように$y \in C_2$を使って、整数の集合を生成してみます。簡単にわかると思いますが、これも全部$3$の倍数です。つまり、$x=6,x^{\prime}=15$を種にして生成された整数の集合は完全に一致しているということです。別の例として、$x=7,x^{\prime}=31$だとどうでしょうか。生成される整数は、どっちも$3$で割ったら余りが$1$になる集合です。ということで、この場合も両者は完全に一致します。さらに別の例として、$x=11,x^{\prime}=52$だとどうでしょうか。この場合、$x=11$から生成されるのは、$3$で割った余りが$2$の整数集合、$x^{\prime}=52$から生成されるのは、$3$で割った余りが$1$の整数集合です。ということで、両者は完全不一致です。つまり、$x \in C_1$を種に集合$C_2$を使って生成した集合を、$3$で割った余りがいくつになるかで分類することができるということです。もっと言うと、$C_2$によって$x \in C_1$を3つのグループに分類することができます。この分類のことを「剰余類」と呼びます（例えば、「$7$と$31$は同じ剰余類に属している」という言い方をします）。同じ剰余類に属しているかどうかは、いちいち全部生成してみなくても、引き算をしてみればわかります。いまの例でやってみます。$15-6$は$9$、$31-7$は$24$となり、どっちも$3$の倍数です。一方、$52-11$は$41$となり、$3$の倍数ではありません。このように同じ剰余類に属しているかどうかは、引き算をしてみて、それが$C_2$に属しているかどうかで判断できます。

さて、アナロジーはこの辺までにしておきます。前段の$C_1,C_2$の定義は忘れてください。で、改めて、式(1)の定義を見ると、これに類似したことが成り立ちそうな気がしてきます。気がするだけでなく、実際にもそうであるということを以下で示してみます。

まず、同じ剰余類に属している場合、すなわち、$x, x^{\prime} \in C_1$で、$x-x^{\prime} \in C_2$だったとすると、

```math
\ket{x + C_2} = \ket{x^{\prime} + C_2}  \tag{2}
```

が成り立ちます。では、証明してみます。

【証明】

$\ket{x+C_2} - \ket{x^{\prime}+C_2}$が$0$になることを証明します。

```math
\ket{x+C_2} - \ket{x^{\prime}+C_2} = \frac{1}{|C_2|} (\sum_{y \in C_2} \ket{x+y} - \sum_{y \in C_2} \ket{x^{\prime}+y})  \tag{3}
```

$x-x^{\prime}=y^{\prime} \in C_2$とおきます。

```math
\ket{x+C_2} - \ket{x^{\prime}+C_2} = \frac{1}{|C_2|} (\sum_{y \in C_2} \ket{x^{\prime}+y^{\prime}+y} - \sum_{y \in C_2} \ket{x^{\prime}+y})  \tag{4}
```

$y^{\prime\prime} = y^{\prime}+y$とおきます。$y^{\prime}$と$y$は同じ符号$C_2$の要素なので$y^{\prime\prime} \in C_2$であることに注意すると、

```math
\ket{x+C_2} - \ket{x^{\prime}+C_2} = \frac{1}{|C_2|} (\sum_{y^{\prime\prime} \in C_2} \ket{x^{\prime}+y^{\prime\prime}} - \sum_{y \in C_2} \ket{x^{\prime}+y}) = 0 \tag{5}
```

となります。（証明終）

次に、異なる剰余類に属している場合、すなわち、$x, x^{\prime} \in C_1$で、$x-x^{\prime} \notin C_2$だったとすると、

```math
\braket{x + C_2}{x^{\prime} + C_2} = 0 \tag{6}
```

が成り立ちます。では、証明してみます。

【証明】

まず、いかなる2つの$y,y^{\prime} \in C_2$をもってきても、$x+y = x^{\prime}+y^{\prime}$にすることはできません。つまり、

```math
x+y \neq x^{\prime} + y^{\prime}  \tag{7}
```

です。なぜなら、等号が成り立つとすると、$x-x^{\prime} = y^{\prime}-y \in C_2$となり[^2]、前提を否定することになります。したがって、式(7)が成り立ちます。とすると、

[^2]: 2を法とするビットごとの加算は減算に等しいことにご注意。$y^{\prime}-y=y{\prime}+y$となり同じ符号に属するもの同士を足しても同じ符号に属するという線形符号の性質から$y^{\prime}-y \in C_2$が言えます。

```math
\begin{align}
\ket{x+C_2} &= \frac{1}{|C_2|} \sum_{y \in C_2} \ket{x+y} \\
\ket{x^{\prime}+C_2} &= \frac{1}{|C_2|} \sum_{y^{\prime} \in C_2} \ket{x^{\prime}+y^{\prime}} \tag{8}
\end{align}
```

という2つの状態は、互いに全く重なることのない状態の重ね合わせということになるので、

```math
\braket{x+C_2}{x^{\prime}+C_2} = 0 \tag{9}
```

が成り立ちます。（証明終）

$\ket{x+C_2}$の$x$は$C_1$の要素なので、その総数は$2^{k_1}$なのですが、上に示した性質があるので、ケットとしての総数はそれより少なくなります。簡単にわかると思いますが、$y \in C_2$の総数で割り算すれば良いです。つまり、$\ket{x+C_2}$の総数は、$|C_1|/|C_2|=2^{k_1}/2^{k_2}=2^{k_1 - k_2}$です。ということで、このCSS符号は、量子ビット長$k_1 - k_2$の状態から生成される$[n, k_1 - k_2]$符号ということになります。


### ビット反転と位相反転

それでは、このように定義された量子符号で、なぜどのように誤り訂正ができるのかを見ていきます。が、まず、ビット反転と位相反転が加わった状態がどうなるかを確認しておきます。

いま、ビット反転の誤りを表すベクトルをバイナリ値を要素とする、以下のようなベクトルで表すことにします。

```math
e_1 = (0, \cdots , 0,1,0, \cdots, 0,1,0, \cdots, 0)^T  \tag{10}
```

ここで、ベクトルの次元は$n$で、誤りが加わる量子ビット番号に相当した要素のみが$1$で、その他が$0$となっているものと思ってください。また、位相反転の誤りを表すベクトルも同様に、

```math
e_2 = (0, \cdots , 0,1,0, \cdots, 0,1,0, \cdots, 0)^T  \tag{11}
```

と表すことにします。このような誤りによって、先程のCSS符号はどう変化するかと言うと、

```math
\ket{x+C_2} = \frac{1}{|C_2|} \sum_{y \in C_2} (-1)^{(x+y)e_2} \ket{x+y+e_1} \tag{12}
```

となります。ビット反転の効果が、右辺のケットの中身に$e_1$が加えられることによって表現されるのは良いですよね。ちょっとわかりにくいのは位相反転の効果が、$(-1)^{(x+y)e_2}$になっているところかと思いますので、若干説明を加えます。

$x+y$は$n$次元のバイナリ・ベクトルでした。それがケットの中に入っているということなので、

```math
x+y = (q_1, q_2, \cdots , q_n)^{T}  \tag{13}
```

とおいてみると、$\ket{x+y}$は、

```math
\ket{x+y} = \ket{q_1}\ket{q_2} \cdots \ket{q_n}  \tag{14}
```

と書けます。ここで、$\ket{q_i}$は$\ket{0}$か$\ket{1}$のどちらかです。位相反転は$\ket{0}$をそのままにして、$\ket{1}$を$-\ket{1}$にする変換だったので、式(11)の$n$個の成分の中で$1$となっている場所の$q_i$が$1$になっているときに、式(14)の符号が反転します。つまり、$x+y$と$e_2$の内積分だけ$-1$がかかるということなので、式(12)で示されているように、係数$(-1)^{(x+y)e_2}$が状態の前にかかることになります。

### ビット反転誤りの訂正

このように誤りが入った状態をどうやって訂正していくかについて説明します。まず、ビット反転誤りの訂正についてです。式(12)の右辺の$\ket{x+y+e_1}$に注目します。$x+y \in C_1$だったので、$C_1$のパリティ検査行列を$H_1$として、それをケットの中身に適用して誤りシンドロームの計算ができれば、そこにビット反転があった量子ビット番号についての情報が入っているはずです。これを実行するためには、量子誤りシンドロームの結果を格納するためのアンシラが必要になります。すなわち、

```math
\ket{x+y+e_1}\ket{0} \rightarrow \ket{x+y+e_1}\ket{H_1(x+y+e_1)} = \ket{x+y+e_1}\ket{H_1 e_1}  \tag{15}
```

という変換が実現できれば、右辺のアンシラ$\ket{H_1 e_1}$に、誤りビット番号に関する情報が入ることになります。

では、式(15)の変換は、どんな量子回路で実現できるでしょうか。

いきなり一般的に説明するは難しいので、簡単な例で考えてみます。$\ket{x}\ket{0} \rightarrow \ket{x}\ket{Hx}$という変換を実現したいとします。具体的には、$\ket{x}$は3量子ビットの符号語、$H$はパリティ検査行列、

```math
H =
\begin{pmatrix}
1 & 1 & 0 \\
0 & 1 & 1
\end{pmatrix}  \tag{16}
```

とします。このとき、生成行列$G$は、

```math
G =
\begin{pmatrix}
1\\
1\\
1
\end{pmatrix}  \tag{17}
```

です。ということで、これは、1量子ビットを3量子ビットに冗長化する繰り返し符号に他なりません。つまり、$\ket{0} \rightarrow \ket{000}, \ket{1} \rightarrow \ket{111}$のような符号化を実現します。入力ベクトル$x=(x_1, x_2, x_3)^{T}$に$H$を演算した結果が、アンシラに転写されれば良いので、量子回路は以下のようになります。

```
     [1行目]  [2行目]
|x1> --*-------------
|x2> --|--*----*-----
|x3> --|--|----|--*--
       |  |    |  |
 |0> --X--X----|--|--
 |0> ----------X--X--
```

[1行目]と書かれている箇所は$H$の1行目に対応した計算です。1列目と2列目の行列要素が1になっているので、1番目のアンシラが$\ket{x_1+x_2}$となるようにしています。[2行目]と書かれている箇所は$H$の2行目に対応した計算です。2列目と3列目の行列要素が1になっているので、今度は、2番目のアンシラが$\ket{x_2 + x_3}$となるようにしています。

任意の$\ket{x}$に対して任意の$H$が定義されたときも、この考え方は一般化できます。$H$の第$i$行の第$j$列が$1$だったとき、$j$番目の符号量子ビットを制御ビット、$i$番目のアンシラ量子ビットを標的ビットにしたCNOTゲートを配備します。これを行列要素が$1$になっている数分繰り返せば良いです。というわけで、式(15)の変換を実現する量子回路をどう作れば良いかわかったと思います[^3]。

[^3]: [ニールセン、チャン](https://www.ohmsha.co.jp/book/9784274200090/)の「演習問題10.26」です。

元の誤りありの状態は式(12)だったので、量子誤りシンドロームを通した結果は、

```math
\begin{align}
\ket{x+C_2} &= \frac{1}{|C_2|} \sum_{y \in C_2} (-1)^{(x+y)e_2} \ket{x+y+e_1} \\
& \rightarrow \frac{1}{|C_2|} \sum_{y \in C_2} (-1)^{(x+y)e_2} \ket{x+y+e_1} \ket{0} \\
& \rightarrow \frac{1}{|C_2|} \sum_{y \in C_2} (-1)^{(x+y)e_2} \ket{x+y+e_1} \ket{H_1(x+y+e_1)} \\
& \rightarrow \frac{1}{|C_2|} \sum_{y \in C_2} (-1)^{(x+y)e_2} \ket{x+y+e_1} \ket{H_1 e_1} \tag{18}
\end{align}
```

となります。誤りが1量子ビットに限定されている場合は、最後の$\ket{H_1 e_1}$の中で$\ket{0}$となっていないものは1種類しかありません。それを$\ket{z_1}$とします。アンシラが$\ket{z_1}$となっている右辺の項についてのみ、$z_1$に対応した量子ビット番号（つまり、パリティ検査行列の列ベクトルが$z_1$になっていう列番号）を反転させれば、誤り訂正ができます。2量子ビットの誤りがある場合は、$\ket{0}$以外のアンシラ状態が2種類あるということになります。それを$\ket{z_1},\ket{z_2}$とすると、アンシラが$\ket{z_1}$または$\ket{z_2}$になっている右辺の項についてのみ、$z_1$と$z_2$に対応した量子ビット番号を反転するようにすれば、誤り訂正ができます。3量子ビット以上の誤りがあった場合も同様にして誤り訂正ができます。というわけで、ビット反転誤りの訂正が完了します[^4]。ただし、$C_1$は$t$個までの誤りを訂正できる符号だったので、対応できる量子ビット数は$t$個までです。

[^4]: $z_1,z_2, \cdots$の値を得るために測定して、それに応じて符号量子ビットを反転するような回路を組むことは可能です。その場合、条件つきXゲート（測定結果を古典レジスタに格納しておいて、その値が0か1かに応じてオンオフするXゲート）を使う感じになると思います。が、誤り量子ビットが1個以上ある場合は、複数$z_1,z_2, \cdots$を得るために、複数回の測定をしないといけないと思います。というわけで、あまり嬉しくないです。測定をする代わりに$\ket{z_i}$のみに反応するようにXゲートとCNOTゲートを組み合わせて、同じことを実現する回路も可能であって、その場合、量子回路を1回通すだけで、複数量子ビットの誤り訂正ができると思います。記事の後半で示すシミュレーションはこの方向で実装しました。

ビット反転誤りを訂正した結果、状態は以下のようになります。

```math
\frac{1}{|C_2|} \sum_{y \in C_2} (-1)^{(x+y)e_2} \ket{x+y} \tag{19}
```


### 位相反転誤りの訂正

次に、位相反転誤りの訂正について考えます。ヒントはアダマール変換です。

```math
\begin{align}
\ket{+} \rightarrow \ket{-}  \\
\ket{-} \rightarrow \ket{+}  \tag{20}
\end{align}
```

という位相反転は、アダマール変換した世界で考えると

```math
\begin{align}
\ket{0} \rightarrow \ket{1}  \\
\ket{1} \rightarrow \ket{0}  \tag{21}
\end{align}
```

というビット反転となります。ここから、何となくアダマール変換して、ビット反転誤りの訂正をやって、再びアダマール変換をやると、うまく行くような気がします。実際にもそれは正しくて、以下のように、きちんと数式で示すことができます。

まず、$n$量子ビット状態に対するアダマール変換$H^{\otimes n}$は、

```math
H^{\otimes n} \ket{x} = \frac{1}{\sqrt{2^{n}}} \sum_{z} (-1)^{xz} \ket{z}  \tag{22}
```

となります[^5]。これを使うと、式(19)に対するアダマール変換は、

[^5]: 公式として覚えておくと良いと思います。

```math
\begin{align}
& \frac{1}{|C_2|} \sum_{y \in C_2} (-1)^{(x+y)e_2} \ket{x+y} \\
& \rightarrow \frac{1}{|C_2|} \sum_{y \in C_2} (-1)^{(x+y)e_2} H^{\otimes n} \ket{x+y} \\
&= \frac{1}{\sqrt{|C_2| 2^{n}}} \sum_{z} \sum_{y \in C_2} (-1)^{(x+y)e_2} (-1)^{(x+y)z} \ket{z} \\
&= \frac{1}{\sqrt{|C_2| 2^{n}}} \sum_{z} \sum_{y \in C_2} (-1)^{(x+y)(e_2+z)} \ket{z} \tag{23}
\end{align}
```

$z^{\prime}=z+e_2$とおくと、上の式は、

```math
\begin{align}
& \frac{1}{\sqrt{|C2| 2^{n}}} \sum_{z^{\prime}} \sum_{y \in C_2} (-1)^{(x+y)z^{\prime}} \ket{z^{\prime} + e_2} \\
&= \frac{1}{\sqrt{|C2| 2^{n}}} \sum_{z^{\prime}} (-1)^{xz^{\prime}} \sum_{y \in C_2} (-1)^{yz^{\prime}} \ket{z^{\prime} + e_2} \tag{24}
\end{align}
```

と変形できます。ここで、$\sum_{y \in C_2} (-1)^{yz^{\prime}}$に注目して、[前回の記事](https://qiita.com/SamN/items/4a02d8bba4f1df46ef2f)の式(46)のあたりで説明した双対符号の性質を使います。いまの状況に焼き直すと、その性質は、

```math
\begin{align}
& z^{\prime} \in C_{2}^{\perp} \Rightarrow \sum_{y \in C_2} (-1)^{yz^{\prime}} = |C_2| \\
& z^{\prime} \notin C_{2}^{\perp} \Rightarrow \sum_{y \in C_2} (-1)^{yz^{\prime}} = 0 \tag{25}
\end{align}
```

と表されます。これを式(24)に当てはめると、

```math
\sqrt{\frac{|C_2|}{2^{n}}} \sum_{z^{\prime} \in C_{2}^{\perp}} (-1)^{xz^{\prime}} \ket{z^{\prime} + e_2}  \tag{26}
```

となります。つまり、アダマール変換を実行した結果、位相反転$e_2$の効果はケットの中の加算として現れることになります。こうなれば、後は先程と同様、ビット反転の誤り訂正の手続きで$e_2$の効果を消去することができます。結果、

```math
\sqrt{\frac{|C_2|}{2^{n}}} \sum_{z^{\prime} \in C_{2}^{\perp}} (-1)^{xz^{\prime}} \ket{z^{\prime}}  \tag{27}
```

ということになります。再度アダマール変換を実行すると、完全に元に戻るはずです。やってみます。

```math
\begin{align}
& \sqrt{\frac{|C_2|}{2^{n}}} \sum_{z^{\prime} \in C_{2}^{\perp}} (-1)^{xz^{\prime}} \ket{z^{\prime}} \\
& \rightarrow \sqrt{\frac{|C_2|}{2^{n}}} \sum_{z^{\prime} \in C_{2}^{\perp}} (-1)^{xz^{\prime}} \frac{1}{\sqrt{2^{n}}} \sum_{w} (-1)^{z^{\prime} w} \ket{w} \\
&= \frac{\sqrt{|C_2|}}{2^{n}} \sum_{w} \sum_{z^{\prime} \in C_{2}^{\perp}} (-1)^{(x+w)z^{\prime}} \ket{w} \tag{28}
\end{align}
```

再び、$\sum_{z^{\prime} \in C_{2}^{\perp}} (-1)^{(x+w)z^{\prime}}$に対して、双対符号の性質を使います。$x+w \in C_2$のときのみ$|C_2|$となり、その他は$0$なので、以下のように変形できます。

```math
\frac{\sqrt{|C_2|}}{2^{n}} \sum_{w,x+w \in C_2} |C_{2}^{\perp}| \ket{w} \tag{29}
```

ここで、

```math
\begin{align}
& |C_2| = 2^{k_2}, |C_{2}^{\perp}| = 2^{n-k_2} \\
& |C_2| |C_{2}^{\perp}| = 2^{n} \tag{30}
\end{align}
```

が成り立つので、式(29)は、

```math
\frac{1}{\sqrt{|C_2|}} \sum_{w,x+w \in C_2} \ket{w} \tag{31}
```

となります。ここで、$x+w=x-w=y \in C_2$とおくと、結局、

```math
\frac{1}{\sqrt{|C_2|}} \sum_{y \in C_2} \ket{x+y} \tag{32}
```

とできるので、これで元の状態が完全に復元されることになります。

ビット反転や位相反転以外の連続的な誤りがあったときも、これだけで対応できることは、[前々回の記事](https://qiita.com/SamN/items/650549224eb1f9b511fc)で説明していました。ということで、CSS符号がどう構築されて、どんな量子回路を通せば、誤り訂正ができるかの説明は一応完了です。

が、最後にもう一言。

CSS符号には、パラメータ$u,v$をもったバリエーションがあります。

```math
\ket{x+C_2} \equiv \frac{1}{|C_2|} \sum_{y \in C_2} (-1)^{uy} \ket{x+y+v}  \tag{33}
```

で定義され、$CSS_{u,v}(C_1,C_2)$符号と呼ばれています。余計なパラメータが入っているのですが、先程の$CSS(C_1,C_2)$符号と同じ量子回路で誤り訂正ができます。量子鍵配送で有用になるとのことなので、ここで定義だけ掲載し、証明は省略します[^6]。

[^6]: これについて、私は驚くべき証明を見つけたのですが、この余白はそれを書くには狭すぎます、というのは嘘です（笑、一度言ってみたかった。出典ご存知ない方は[こちら](https://ja.m.wikipedia.org/wiki/%E3%83%95%E3%82%A7%E3%83%AB%E3%83%9E%E3%83%BC%E3%81%AE%E6%9C%80%E7%B5%82%E5%AE%9A%E7%90%86)をどうぞ）。[ニールセン、チャン](https://www.ohmsha.co.jp/book/9784274200090/)の「演習問題10.27」です。上でやったのとほぼ同じ式変形を愚直にやる感じだったので、省略しました。


### Steane符号

CSS符号の一般論がわかったので、具体例を上げて、さらに理解を確実にしたいと思います。「Steane符号」というものがあります。これは、$C_1=C, C_2=C^{\perp}$として、$C$をHamming符号にしたCSS符号です。$C_1$のパリティ検査行列を$H_1$、生成行列を$G_1$とします。いま簡単のため、$[7,3]$Hamming符号とすると、$H_1,G_1$は各々、

```math
H_1 =
\begin{pmatrix}
0 & 1 & 1 & 1 & 1 & 0 & 0 \\
1 & 0 & 1 & 1 & 0 & 1 & 0 \\
1 & 1 & 0 & 1 & 0 & 0 & 1
\end{pmatrix}  \tag{34}
```

```math
G_1 =
\begin{pmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
0 & 1 & 1 & 1 \\
1 & 0 & 1 & 1 \\
1 & 1 & 0 & 1
\end{pmatrix}  \tag{35}
```

と表せます（標準形で書きました）。一方、$C_2$は、その双対符号ですので、定義から、

```math
H_2 = G_{1}^{T} =
\begin{pmatrix}
1 & 0 & 0 & 0 & 0 & 1 & 1 \\
0 & 1 & 0 & 0 & 1 & 0 & 1 \\
0 & 0 & 1 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 1 & 1 & 1 & 1
\end{pmatrix}  \tag{36}
```

```math
G_2 = H_{1}^{T} =
\begin{pmatrix}
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0 \\
1 & 1 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{pmatrix}  \tag{37}
```

と書き表せます。

ところで、このように定義した線形符号をベースにした量子符号が確かにCSS符号であるということを言うためには、$C_1$と$C_{2}^{\perp}$が同じ$t$個の誤りに対応できる、つまり符号の距離（最小距離）が等しいということと、$C_2 \subset C_1$であることが必要です。

前者は、定義より$C_1$も$C_{2}^{\perp}$もともに$C$なので自明です。後者は、[前回の記事](https://qiita.com/SamN/items/4a02d8bba4f1df46ef2f)の式(45)あたりで説明したことを使えばわかります。再掲します。

```math
G^{T} G = 0 \Leftrightarrow C \subseteq C^{\perp}  \tag{38}
```

つまり、$G_{2}^{T} G_2 = 0$が示せれば、$C_2 \subseteq C_{2}^{\perp}$、すなわち、$C_2 \subseteq C_1$が証明できたことになります。やってみます。

```math
G_{2}^{T} G_2 =
\begin{pmatrix}
0 & 1 & 1 & 1 & 1 & 0 & 0 \\
1 & 0 & 1 & 1 & 0 & 1 & 0 \\
1 & 1 & 0 & 1 & 0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0 \\
1 & 1 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{pmatrix} =
\begin{pmatrix}
0 & 0 & 0 \\
0 & 0 & 0 \\
0 & 0 & 0
\end{pmatrix}  \tag{39}
```

ということで、$C_2 \subseteq C_{2}^{\perp}$であることが確認できました[^7]。

[^7]: [7,3]Hamming符号の場合は確認できましたが、一般のHamming符号についても成り立っているかどうかは、まだ言えてないです（多分成り立っているのだと思いますが）。一瞬、$HG=0$が使えるかと思ったのですが、勘違いでした。

それでは、ベースとなる古典線形符号がわかったので、これからCSS符号を構築してみます。式(1)を改めて見てみます。

```math
\ket{x+C_2} \equiv \frac{1}{\sqrt{|C_{2}|}} \sum_{y \in C_2} \ket{x+y}  \tag{1}
```

これに従って符号を構築すれば良いです。

いま$C_1$は[7,4]符号、$C_2$は[7,3]符号です。したがって、できあがるCSS符号は[7,1]符号です。1量子ビットを7量子ビットに冗長化する量子符号ということなので、2つの$x$を持ってきて、式(1)の右辺のようにすべての$y$を総動員して重ね合わせれば良いです。$y$の方は[7,3]符号なので、すべての3次元のバイナリ・ベクトルを持ってきて、式(35)の生成行列$G_2$を演算してやれば良いです。さて、問題はどんな$x$を持ってくれば良いかです。同じ剰余類に属する2つのの$x$を持ってきたとすると、右辺は全く同じになるので、意味がありません。違う剰余類に属する2つの$x$を持ってくる必要があります。2つの$x$の差分が$C_2$に属していないようにすれば良いので、エイヤで$x=(0,0,0,0,0,0,0)^{T}$と$x^{\prime} = (1,1,1,1,1,1,1)^{T}$という2つを持ってきます。こうすれば差分が$C_2$の要素になっていなさそうです。$x$を種にして生成される状態を$\ket{0_L}$、$x^{\prime}$を種にして生成される状態を$\ket{1_L}$とすると、

```math
\begin{align}
\ket{0_L} &= \frac{1}{\sqrt{8}} (\ket{0000000} + \ket{1101001} + \ket{1011010} + \ket{0110011} + \ket{0111100} + \ket{1010101} + \ket{1100110} + \ket{0001111}) \\
\ket{1_L} &= \frac{1}{\sqrt{8}} (\ket{1111111} + \ket{0010110} + \ket{0100101} + \ket{1001100} + \ket{1000011} + \ket{0101010} + \ket{0011001} + \ket{1110000}) \tag{40}
\end{align}
```

となり、これで量子符号ができました。実際に、$\ket{\psi} = \alpha \ket{0} + \beta \ket{1}$という1量子ビット状態を符号化する際には、

```math
\ket{\psi}　\rightarrow \ket{\psi_{L}} = \alpha \ket{0_L} + \beta \ket{1_L} \tag{41}
```

を実現するように適当な量子回路を構築します。

次に、この状態に対して誤りが加わる想定で、先程説明したような誤りシンドロームを計算する回路を実行します。つまり、アンシラを追加して、各状態に対して、

```math
\ket{x} \ket{0} \rightarrow \ket{x} \ket{H_1 x}  \tag{42}
```

を実現する量子回路を実行すれば、アンシラに$H_1 e_1$というビット反転誤りの効果が移るのでした。いまの場合、3量子ビット分のアンシラを用意します。先程説明したように、パリティ検査行列の各行に含まれる$1$の場所に注意しながら、CNOTゲートを並べます。

```
|x1> -----------*--------*-------- ...
|x2> --*--------|--------|-*------ ...
|x3> --|-*------|-*------|-|------ ...
|x4> --|-|-*----|-|-*----|-|-*---- ...
|x5> --|-|-|-*--|-|-|----|-|-|---- ...
|x6> --|-|-|-|--|-|-|-*--|-|-|---- ...
|x7> --|-|-|-|--|-|-|-|--|-|-|-*-- ...
       | | | |  | | | |  | | | |       
 |0> --X-X-X-X--|-|-|-|--|-|-|-|-- ...
 |0> -----------X-X-X-X--|-|-|-|-- ...
 |0> --------------------X-X-X-X-- ...
```

次に、アンシラの状態に応じて、ビット反転をします。アンシラの状態がパリティ検査行列$H_1$の列ベクトルの値と一致しているところに対応したビットを反転します。つまり、アンシラが$\ket{011}$なら第1量子ビット、$\ket{101}$なら第2量子ビット、$\ket{110}$なら第3量子ビット…という具合にビット反転すれば、ビット反転誤りは訂正できます。先程の回路に続けて、以下のようにします。

```
|x1> ... ----X--------------------------------------------- ...
|x2> ... ----|------X-------------------------------------- ...
|x3> ... ----|------|------X------------------------------- ...
|x4> ... ----|------|------|------X------------------------ ...
|x5> ... ----|------|------|------|------X----------------- ...
|x6> ... ----|------|------|------|------|------X---------- ...
|x7> ... ----|------|------|------|------|------|------X--- ...
             |      |      |      |      |      |      |
 |0> ... --X-*-X----*------*------*------*----X-*-X--X-*-X-
 |0> ... ----*----X-*-X----*------*----X-*-X----*----X-*-X-
 |0> ... ----*------*----X-*-X----*----X-*-X--X-*-X----*---
```

これで、ビット反転誤りが訂正できたので、次に位相反転誤りに対応します。まず、アダマール変換を使います。同時に、ビット反転誤り訂正用のアンシラは役目が終わったので初期化します。上の回路に続けて、以下を実行します。

```
|x1> ... --H-------------*--------*-------- ...
|x2> ... --H----*--------|--------|-*------ ...
|x3> ... --H----|-*------|-*------|-|------ ...
|x4> ... --H----|-|-*----|-|-*----|-|-*---- ...
|x5> ... --H----|-|-|-*--|-|-|----|-|-|---- ...
|x6> ... --H----|-|-|-|--|-|-|-*--|-|-|---- ...
|x7> ... --H----|-|-|-|--|-|-|-|--|-|-|-*-- ...
                | | | |  | | | |  | | | |       
 |0> ... -------X-X-X-X--|-|-|-|--|-|-|-|-- ...
 |0> ... ----------------X-X-X-X--|-|-|-|-- ...
 |0> ... -------------------------X-X-X-X-- ...
```

誤りシンドロームの計算ができたので、位相反転誤りを訂正して（実際にはビット反転誤りを訂正して）、最後にアダマール変換を実行して、元に戻します。

```
|x1> ... ----X---------------------------------------------H--
|x2> ... ----|------X--------------------------------------H--
|x3> ... ----|------|------X-------------------------------H--
|x4> ... ----|------|------|------X------------------------H--
|x5> ... ----|------|------|------|------X-----------------H--
|x6> ... ----|------|------|------|------|------X----------H--
|x7> ... ----|------|------|------|------|------|------X---H--
             |      |      |      |      |      |      |
 |0> ... --X-*-X----*------*------*------*----X-*-X--X-*-X----
 |0> ... ----*----X-*-X----*------*----X-*-X----*----X-*-X----
 |0> ... ----*------*----X-*-X----*----X-*-X--X-*-X----*------
```

これで、誤り訂正は完了です[^8]。

[^8]: もっと効率の良い回路構成はあるのかもしれませんが、とりあえず初心者コースなので、ご容赦ください。少なくとも連続しているXゲートは消去できます。それから、本当は、7量子ビットのSteane符号を1量子ビット状態から作成したかったのですが、良さげな回路を思いつかなかったので、今回の記事では、それも省略しました。もっと勉強を進めればスッキリしたカッコいい回路が書けるのだと思いますが。


## シミュレーション

### 実装

それでは、上で説明したSteane符号を実装してみます。[qlazy](https://github.com/samn33/qlazy)では、量子回路の計算は、量子状態または密度演算子に相当するクラスのインスタンスを作って、ゲート演算することで実行します。量子状態でも密度演算子でもどちらでも良いのですが、雑音付加に量子チャネル（分極解消とか、振幅ダンピングとか）を利用できる密度演算子の方でやってみます[^9]。

[^9]: 10量子ビットの密度演算子の計算で、かつ、マルチ制御NOT（制御ビットが複数あるCNOT）をふんだんに使っているので、量子状態で実行するのと比べ、処理時間はかかります。

全体のコードは以下です。

【2021.9.5追記】[qlazy](https://github.com/samn33/qlazy)最新版でのソースコードは[ここ](https://github.com/samn33/qlazy/blob/master/example/py/ErrorCorrection/steane_code_1.py)に置いてあります。

```Python
import numpy as np
from qlazypy import QState, DensOp

Hamming   = np.array([[0,1,1,1,1,0,0], [1,0,1,1,0,1,0], [1,1,0,1,0,0,1]])
Hamming_T = Hamming.T

Steane_0 = ['0000000', '1101001', '1011010', '0110011',
            '0111100', '1010101', '1100110', '0001111']
Steane_1 = ['1111111', '0010110', '0100101', '1001100',
            '1000011', '0101010', '0011001', '1110000']

def generate_qstate(qid_C, qid_S):

    a = np.random.rand() + np.random.rand() * 1.j
    b = np.random.rand() + np.random.rand() * 1.j

    print("== quantum state (a |0L> + b |1L>) ==")
    print("- a = {:.4f}".format(a))
    print("- b = {:.4f}".format(b))

    qvec = np.full(2**len(qid_C), 0.+0.j)
    for s in Steane_0: qvec[int(s, 2)] = a
    for s in Steane_1: qvec[int(s, 2)] = b

    norm = np.linalg.norm(qvec)
    qvec = qvec / norm

    qs_C = QState(vector=qvec)
    qs_S = QState(len(qid_S))
    qs = qs_C.tenspro(qs_S)
    de_ini = DensOp(qstate=[qs])
    de_fin = de_ini.clone()

    QState.free_all(qs_C, qs_S, qs)
    return de_ini, de_fin

def noise(self, kind='', prob=0.0, qid=[]):

    print("== noise ({:}) ==".format(kind))
    print("- qubit = {:}".format(qid))
    print("- prob  = {:}".format(prob))
    
    qchannel = {'bit_flip':self.bit_flip, 'phase_flip':self.phase_flip,
                'bit_phase_flip':self.bit_phase_flip,
                'depolarize':self.depolarize, 'amp_dump':self.amp_dump,
                'phase_dump':self.phase_dump}
    [qchannel[kind](i, prob=prob) for i in qid]
    return self

def correct(self, kind, qid_C, qid_S):

    self.reset(qid=qid_S)

    if kind == 'phase_flip': [self.h(q) for q in qid_C]

    # syndrome
    for i, row in enumerate(Hamming):
        [self.cx(qid_C[j], qid_S[i]) if row[j] == 1 else False for j in range(len(row))]

    # correction
    for i, row in enumerate(Hamming_T):
        [self.x(qid_S[j]) if row[j] == 0 else False for j in range(len(row))]
        self.mcx(qid=qid_S+[qid_C[i]])
        [self.x(qid_S[j]) if row[j] == 0 else False for j in range(len(row))]
    
    if kind == 'phase_flip': [self.h(q) for q in qid_C]
        
    return self
    
if __name__ == '__main__':

    # add custom gates
    DensOp.add_method(noise)
    DensOp.add_method(correct)

    # set registers
    qid_C = DensOp.create_register(7) # registers for code space
    qid_S = DensOp.create_register(3) # registers for error syndrome
    DensOp.init_register(qid_C, qid_S)

    # generate initial quantum state (density operator)
    de_ini, de_fin = generate_qstate(qid_C, qid_S)

    # add noise
    de_fin.noise(kind='depolarize', qid=[qid_C[3]], prob=1.0)

    # error correction
    de_fin.correct('bit_flip', qid_C, qid_S)
    de_fin.correct('phase_flip', qid_C, qid_S)

    # print result
    print("== result ==")
    print("- fidelity = {:.6f}".format(de_fin.fidelity(de_ini, qid=qid_C)))

    DensOp.free_all(de_ini, de_fin)
```

何をやっているか、簡単に説明します。基本的には、上で説明したSteane符号による誤り訂正を実行しているだけです。では、メイン処理部を見てください。

```Python
# add custom gates
DensOp.add_method(noise)
DensOp.add_method(correct)
```

で、雑音付加と誤り訂正を各々一つのかたまりとしてカスタムゲートを定義して、メソッドとして設定しています。処理内容は上の方で関数定義されています。

```Python
# set registers
qid_C = DensOp.create_register(7) # registers for code space
qid_S = DensOp.create_register(3) # registers for error syndrome
DensOp.init_register(qid_C, qid_S)
```

で、使用する量子レジスタを定義しています。この程度であれば、こんなクラスメソッドを使わなくても手で書いてしまった方が早いかもしれません。これで、qid_Cは[0,1,2,3,4,5,6]というリストになり、qid_Sは[7,8,9]というリストになります。

```Python
# generate initial quantum state (density operator)
de_ini, de_fin = generate_qstate(qid_C, qid_S)
```

Steane符号を使った量子状態（密度演算子）をランダムに用意します。関数定義を見ていただければわかると思いますが、$a,b$という複素数をランダムに設定して、7量子ビットの量子状態$a \ket{0_L} + b \ket{1_L}$を作成し、3量子ビットのアンシラとのテンソル積を実行することによって10量子ビットの状態を作成します。それに基づき密度演算子を作成してリターンします。複製して２つ全く同じものを作っていますが、これはプログラムの最後で、初期状態と演算結果の状態を比較評価するためです。

```Python
# add noise
de_fin.noise(kind='depolarize', qid=[qid_C[3]], prob=1.0)
```

で、雑音を加えます。[qlazy](https://github.com/samn33/qlazy)に標準搭載されている雑音（量子チャネル）は、「ビット反転(bit_flip)」「位相反転(phase_flip)」「ビット位相反転(bit_phasee_flip)」「分極解消(depolarize)」「振幅ダンピング(amp_dump)」「位相ダンピング(phase_dump)」の6種類であり、各々、適用する量子ビット番号リストと雑音の強度を表す確率を引数に与えるようになっています。関数（カスタムゲート）noiseは、引数にその量子チャネルの種別を表す文字列と量子ビット番号リストと確率を指定して、密度演算子に適用するものです。詳細は関数定義をご覧ください。

```Python
# error correction
de_fin.correct('bit_flip', qid_C, qid_S)
de_fin.correct('phase_flip', qid_C, qid_S)
```

で、ビット反転誤り訂正と位相反転誤り訂正を実行しています。関数（カスタムゲート）correctは、引数にビット反転対応なのか位相反転対応なのかを表す文字列と、符号空間とアンシラに対応した量子ビット番号リストを指定します。correectの中身を見てみます。

```Python
self.reset(qid=qid_S)
```

で、アンシラを初期化します。誤りシンドローム計算のために、まず初期化が必要です。

```Python
if kind == 'phase_flip': [self.h(q) for q in qid_C]
```

位相反転に対応したい場合、アダマールをまず実行しないといけないので、ここでやっています。

```Python
# syndrome
for i, row in enumerate(Hamming):
    [self.cx(qid_C[j], qid_S[i]) if row[j] == 1 else False for j in range(len(row))]
```

で、誤りシンドロームの計算を実行します。上で説明した回路を実行するため、Hamming符号のパリティ検査行列の各行ごとにCNOTを適切にかけるようなループを回しています。

```Python
# correction
for i, row in enumerate(Hamming_T):
    [self.x(qid_S[j]) if row[j] == 0 else False for j in range(len(row))]
    self.mcx(qid=qid_S+[qid_C[i]])
    [self.x(qid_S[j]) if row[j] == 0 else False for j in range(len(row))]

```

で、誤りシンドロームの結果に応じて、ビット反転して元に戻します。Hamming符号のパリティ検査行列の各列に応じて、マルチ制御NOT（mcxメソッド）を適切にかけるようなループを回しています。

```Python
if kind == 'phase_flip': [self.h(q) for q in qid_C]
```    

で、位相反転対応の場合、最後にアダマールをかけて、元に戻すようにします。以上で誤り訂正が完了します。

再度、メイン処理部に戻ります。

```Python
# print result
print("== result ==")
print("- fidelity = {:.6f}".format(de_fin.fidelity(de_ini, qid=qid_C)))
```

で、最初の密度演算子と誤り訂正処理を実行した後の密度演算子とを比較評価するため、fidelityメソッドで両者の忠実度を計算して表示します。引数qidに関心のある量子ビット番号リストを指定することで、該当部分のみの忠実度を計算することができます。

```Python
DensOp.free_all(de_ini, de_fin)
```

で、使用したメモリを開放します。クラスメソッドfree_allに引数として複数のDensOpインスタンスを指定すれば、1行で複数インスタンスのメモリを開放できます（引数に何個インスタンスを指定しても大丈夫です）。


### 動作の確認

実行結果を示します。3番目の量子ビットに対して分極解消チャネルを確率1.0で適用した結果です。

```
== quantum state (a |0L> + b |1L>) ==
- a = 0.4835+0.0654j
- b = 0.2558+0.9664j
== noise (depolarize) ==
- qubit = [3]
- prob  = 1.0
== result ==
- fidelity = 1.000000
```

忠実度が1.0になっているので、誤り訂正は無事成功しました。量子ビット番号や量子チャンネルや確率をいろいろ変えてみましたが、どんな場合でも忠実度は1.0となり、誤り訂正できることがわかりました。

ところが、当然ですが、2つの量子ビットに雑音が入るとダメでした。以下の通りです。

```
== quantum state (a |0L> + b |1L>) ==
- a = 0.4749+0.4393j
- b = 0.5424+0.6672j
== noise (depolarize) ==
- qubit = [3, 4]
- prob  = 1.0
== result ==
- fidelity = 0.864784
```

それから、これも当然ですが、位相反転の誤り訂正を省略した場合もダメでした。

```Python
# error correction
de_fin.correct('bit_flip', qid_C, qid_S)
# de_fin.correct('phase_flip', qid_C, qid_S)
```

という具合に位相反転対応部分をコメントアウトすると、

```
== quantum state (a |0L> + b |1L>) ==
- a = 0.2903+0.1936j
- b = 0.8322+0.4586j
== noise (depolarize) ==
- qubit = [3]
- prob  = 1.0
== result ==
- fidelity = 0.707107
```

となり、これも誤り訂正は失敗します。

というわけで、予想通りの動作が確認できました。


## おわりに

ある条件を満たした古典線形符号を2つ持ってくれば、そこから量子符号を1つ必ず構築できるということがわかりました。つまり、いろんな量子符号を具体的に構築できる強力なツールの一つを手に入れたということになります。しかも、「Steane符号」は7量子ビットで実行できます。「Shorの符号」は9量子ビット必要だったので、2量子ビット削減することができました（3量子ビットのアンシラも必要でしたが）！

「はじめに」で述べたように「CSS符号」は、さらに、より一般的な「スタビライザー符号」の部分クラスに相当するとのことです。次回は、この「スタビライザー符号」について勉強してみたいと思います（予定です）。


以上