量子情報理論の基本：フォールトトレラント量子計算

$$
\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/c4823734c1b994e75da4)までで一通り「誤り訂正符号」について理解できました。これで量子コンピュータに多少のノイズが加わっても誤りを訂正して正しく計算結果を得ることができる！（少なくとも理論的には！）と言いたいところなのですが、実は全然そうではありません！という話をこれからします。ノイズは量子計算プロセスのあらゆる箇所に発生する可能性があって、その各々について特別な手当てをしてあげる必要があります。それらを実施してはじめて誤りがあったとしても正しく動作する誤り耐性のある量子計算＝フォールトトレラント量子計算(fault-tolerant quantum computation)が実現できたと言えます。

この後の節で何を説明しようとしているか最初に言っておきます。まず、「理論説明」ではフォールトトレラントであるとは一体どういうことなのかを述べた後、具体的にフォールトトレラントな量子ゲートや測定や初期状態作成の実現方法を紹介し、連結符号としきい値定理について説明します。「動作確認」では、フォールトトレラント量子計算のとても簡単な例を取り上げて、量子計算シミュレータ[qlazy](https://github.com/samn33/qlazy)を使ってその動作を確認してみます。

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

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


## 理論説明

### フォールトトレラントの定義

誤り訂正符号は量子状態を蓄積・伝送する際に発生するノイズに対応するものでした。実際の量子計算は「初期状態作成」「ゲート演算」「測定」といった一連のプロセスから成り立っていますので、誤り訂正符号だけでは十分ではありません。例えば、ゲート演算はどうやって実行すれば良いでしょうか。符号状態を一旦復号化してゲート演算を実行して完了したらすかさず再度符号化すればいいんじゃない？と思われたかもしれませんが、その考えは良くないです。復号化して符号化するプロセスやゲート演算の最中にノイズが紛れ込む可能性があります。したがって、より良い方法は符号化状態のままゲート演算をすることなのですが、単に復号化しないで済むようにゲートを構成しました、というだけではこれまた不十分です。どこかに発生したノイズが伝搬し増殖しないように構成しないといけません。例えば、制御NOTゲート（CNOTゲート）はあらゆる場面で大活躍するゲートですが、$U_{1,2}$を制御NOT演算とすると$U_{1,2}X_{1}=X_{1}X_{2}U_{1,2}$が成り立つので、入力の制御側に発生したビット反転ノイズは出力の制御側と標的側の両方に伝搬します。一方、$U_{1,2}Z_{2}=Z_{1}Z_{2}U_{1,2}$が成り立つので、入力の標的側に発生した位相反転ノイズは出力の制御側と標的側に伝搬します。図で書くと以下のように伝搬することになります。

```
＜制御側のビット反転[X]は制御・標的に伝搬＞

--[X]--*----     ----*--[X]--
       |      =>     |
-------X----     ----X--[X]--


＜標的側の位相反転[Z]は制御・標的に伝搬＞

-------*----     ----*--[Z]--
       |      =>     |
--[Z]--X----     ----X--[Z]--

```

符号状態に対するゲート演算の中にこのような部品があるととてもマズイです。誤り訂正は一つの符号ブロックの中で高々1回だけ発生するのであれば訂正可能ですが、上記のような構成があると1個のノイズが2個に増えますので、訂正不能となります。したがって、このようなことにならないように構成しないといけません。さらにゲート演算だけでなく、誤り訂正の手続き自体にもノイズが発生する可能性もあるので、この対策も必要です。さらに初期状態作成や測定のプロセスにもノイズが紛れ込む可能性があります。

等々、、ということを考えると、フォールトトレラントなんて不可能なのでは、という気分にだんだんなってきます。だってCNOTがノイズを伝搬させるのですよ。果たしてCNOTを使わないで符号状態に対するCNOTが実現できるでしょうか？またCNOTなしで誤り訂正を実現できるでしょうか？、、でも、ご安心ください。実はCNOTを絶対に使ってはいけないということではありません。ある条件を満たした伝搬であれば問題ないのです。その条件（＝フォールトトレラントの定義）というのは、「量子計算を実行するシステムの中で1個ノイズが発生したときに各符号ブロックの中に高々1個のノイズしか発生しない状態になっている」というものです。各符号ブロックあたり1個のノイズであれば訂正できるので、ノイズが発生したのと同じ符号ブロックへの伝搬はダメですが（ブロックあたりのノイズが2個になるので）、他のブロックへの伝搬であれば許されます（1個のノイズであれば訂正できるので）。そのように量子計算システムが構成されていればフォールトトレラントであると言うことができます。

残念ながら、ノイズは2箇所以上同時に発生する場合があります[^1]。そして、不幸にして、伝搬の結果同じ符号ブロックにノイズが2個紛れ込むことがあります。その場合は計算結果が間違ってしまいます。しかし、その確率は1箇所にノイズが発生する確率を$p$とすると高々$O(p^{2})$にまで抑えられているはずです。誤りに関して何も対策を施さない場合、計算結果が間違う確率は$O(p)$であり、それが$O(p^{2})$になるということなので、これはフォールトトレラントの明白な効果です。すなわち、計算誤り率が高々$O(p^{2})$になっていることが、フォールトトレラント量子計算のひとつの特徴と考えることもできそうです。

[^1]: 「同時に」というのは1個のノイズに対する誤り訂正実行前に、別のノイズが発生することだと思えば良いです（と思います）。


### フォールトトレラント量子計算の構成

それでは、具体的に「ゲート演算」「測定」「初期状態作成」をどのようにフォールトトレラントに構成できるかについて見ていきます。7量子ビットのSteane符号で考えるのがもっともわかりやすいということなので、以降の議論はすべてSteane符号を前提にします[^2]。

[^2]: 5量子ビット符号の場合ゲート演算をフォールトトレラントにするのは結構難しいとのことです。が、$X$も$Z$も後の説明ででてくるトランスバーサル型にできそうですし、それほど難しくないのでは？という気がするのですが、、おそらく自分自身とんでもない勘違いをしているか、まだ理解が及んでいないところに壁ががあるのだと思います。5量子ビットで誤り耐性を考えてみるのは今後の宿題としておきます。

#### ゲート演算

##### パウリゲート:X,Y,Z

まずパウリ$Z$からはじめます。Steane符号の論理$Z$は、6個ある生成元すべてと可換なものとして、

```math
\bar{Z} = Z_{1} Z_{2} Z_{3} Z_{4} Z_{5} Z_{6} Z_{7}  \tag{1}
```

と定義できます。生成元は、

| 生成元 | 演算子                                                    |
|--------|-----------------------------------------------------------|
| $g_1$  | $I \space I \space I \space X \space X \space X \space X$ |
| $g_2$  | $I \space X \space X \space I \space I \space X \space X$ |
| $g_3$  | $X \space I \space X \space I \space X \space I \space X$ |
| $g_4$  | $I \space I \space I \space Z \space Z \space Z \space Z$ |
| $g_5$  | $I \space Z \space Z \space I \space I \space Z \space Z$ |
| $g_6$  | $Z \space I \space Z \space I \space Z \space I \space Z$ |

だったので、式(1)の定義で良いことがわかると思います[^3]。

[^3]: 同じ演算子を$X_{1}Z_{2}X_{3}$と書いたり$X \otimes Z \otimes X$と書いたり$XZX$と書いたりしますが、実体は同じですので混乱しないようにしてください。

6個の生成元に$\bar{Z}$を加えた7個の演算子によってユニークに決まるスタビライザー状態を$\ket{0_L}$とし、$\bar{Z}$を$-\bar{Z}$に変えたときにユニークに決まるスタビライザー状態を$\ket{1_L}$とします。そうすると、

```math
\bar{Z} \ket{0_L} = \ket{0_L}, \space \bar{Z} \ket{1_L} = - \ket{1_L}  \tag{2}
```

となり、$\bar{Z}$を論理基底$\\{ \ket{0_L}, \ket{1_L} \\}$で表現すると、

```math
\bar{Z} = 
\begin{pmatrix}
1 & 0\\
0 & -1
\end{pmatrix}  \tag{3}
```

という具合に見慣れた格好になります。ここまでは誤り訂正符号のときにやったことを思い出すための復習です。ここで注目したいのは式(1)の形です。量子回路で書くと、

```
--Z--
--Z--
--Z--
--Z--
--Z--
--Z--
--Z--
```

となります。見てわかる通り、ビットごとに$Z$演算を実行するという形になっており、どこかのビットにノイズが発生しても符号ブロック内の他のビットに影響を及ぼすことはありません。このように符号化ゲートがビットごとのゲート演算で実現できる性質のことを「トランスバーサル性(transversality)」といい、こうなっていればフォールトトレラントなゲート演算であるということが直ちに言えます。

次にパウリ$X$についてです。

```math
\bar{X} \bar{Z} \bar{X} = -\bar{Z}  \tag{4}
```

を満たすように$\bar{X}$を決めれば良いです。例えば、

```math
\bar{X} = X_{1} X_{2} X_{3} X_{4} X_{5} X_{6} X_{7}  \tag{5}
```

でいけますね。そうすると、

```math
\bar{X} \ket{0_L} = \ket{1_L}, \space \bar{X} \ket{1_L} = \ket{0_L}  \tag{6}
```

なので[^4]、論理基底での行列表現は、

[^4]: $\bar{X}\ket{0_L}=\bar{X}\bar{Z}\ket{0_L}=-\bar{Z}\bar{X}\ket{0_L}$なので$\bar{X}\ket{0_L}$は$\bar{Z}$の固有値$-1$に対する固有状態です。つまり、$\bar{X}\ket{0_L}=\ket{1_L}$です。両辺に$\bar{X}$を演算すると$\bar{X}\ket{1_L}=\ket{0_L}$が得られます。細かいことを言うと$\bar{X}\ket{0_L}=e^{i\alpha}\ket{1_L}$という定義でも良いような気もしますが、$\alpha=0$とするのが習わしということなのだと思います。

```math
\bar{X} =
\begin{pmatrix}
0 & 1\\
1 & 0
\end{pmatrix}  \tag{7}
```

です。式(5)の形を見ればわかる通りこれもトランスバーサル型になっていますので、これでフォールトトレラントなパウリ$X$が実現できたことになります。

パウリ$Y$については、

```math
\bar{Y} = i\bar{X}\bar{Z} = Y_{1} Y_{2} Y_{3} Y_{4} Y_{5} Y_{6} Y_{7}  \tag{8}
```

としておけば万事丸く収まります。すなわち、$\bar{Y}$は$\bar{X}$および$\bar{Z}$と反可換で$\bar{Y}$自身はエルミートになり、

```math
\bar{Y}\ket{0_L} = -i\ket{1_L}, \space \bar{Y}\ket{1_L} = i\ket{0_L} \tag{9}
```

なので、行列表現は、

```math
\bar{Y} =
\begin{pmatrix}
0 & -i\\
i & 0
\end{pmatrix}  \tag{10}
```

となります。式(8)はトランスバーサル型なので、これでフォールトトレラントなパウリ$Y$が実現できたことになります。

##### アダマールゲート:H

$\bar{X},\bar{Y},\bar{Z}$に基づき、符号状態に対するアダマールゲートをフォールトトレラントに構成してみます。

```math
\bar{H} \bar{X} \bar{H} = \bar{Z}, \space \bar{H} \bar{Z} \bar{H} = \bar{X}  \tag{11}
```

を満たす$\bar{H}$を決めれば良いのですが、

```math
\bar{H} = H_{1} H_{2} H_{3} H_{4} H_{5} H_{6} H_{7}  \tag{12}
```

としてみると式(11)を満たすことがわかります。

```math
\begin{align}
\bar{H}\ket{0_L} &= \bar{H}\bar{Z}\ket{0_L} = \bar{X}\bar{H}\ket{0_L} \\
\bar{H}\ket{1_L} &= -\bar{H}\bar{Z}\ket{1_1} = -\bar{X}\bar{H}\ket{1_L} \tag{13}
\end{align}
```

からわかるように、$\bar{H}\ket{0_L}$は$\bar{X}$の固有値$+1$の固有状態で$\bar{H}\ket{1_L}$は$\bar{X}$の固有値$-1$の固有状態です。したがって、各々、

```math
\begin{align}
\bar{H}\ket{0_L} &= \frac{1}{\sqrt{2}} (\ket{0_L} + \ket{1_L}) \\
\bar{H}\ket{1_L} &= \frac{1}{\sqrt{2}} (\ket{0_L} - \ket{1_L}) \tag{14}
\end{align}
```

のように書けて、行列表現は、

```math
\bar{H} = \frac{1}{\sqrt{2}}
\begin{pmatrix}
1 & 1\\
1 & -1
\end{pmatrix}  \tag{15}
```

となります。式(12)からわかるようにトランスバーサル型になっているので、これでフォールトトレラントなアダマールゲートが実現できたことになります。

##### 位相シフトゲート:S

```math
\bar{S}\bar{X}\bar{S}^{\dagger} = \bar{Y}, \space \bar{S}\bar{Z}\bar{S}^{\dagger} = \bar{Z} \tag{16}
```

を満たすように$\bar{S}$を決めます。

```math
\bar{S} = S_{1} S_{2} S_{3} S_{4} S_{5} S_{6} S_{7}  \tag{17}
```

でいけるのではと一瞬思うのですが、これでは式(16)は成り立ちません。

```math
\bar{S} = (Z_{1}S_{1}) (Z_{2}S_{2}) (Z_{3}S_{3}) (Z_{4}S_{4}) (Z_{5}S_{5}) (Z_{6}S_{6}) (Z_{7}S_{7})  \tag{18}
```

とすればＯＫです（簡単に確認できると思います）。式(16)を満たすための行列表現は、

```math
\bar{S} =
\begin{pmatrix}
1 & 0\\
0 & i
\end{pmatrix}  \tag{19}
```

です（これも簡単に確認できると思います）。式(18)からわかるようにトランスバーサル型になっているので、これでフォールトトレラントな位相シフトゲートが実現できたことになります。

間違えないと思いますが、念のため回路図を書くと、

```
--S-Z--
--S-Z--
--S-Z--
--S-Z--
--S-Z--
--S-Z--
--S-Z--

```

です。数式で書いたときの演算子の順番と回路図で書いたときの演算子の順番が左右逆だというのは、この業界の常識ですが、うっかりすると間違って実装してしまいます（自分のことです、汗）。


##### 制御NOTゲート:CNOT

さて、問題の制御NOTゲートです。果たして同一符号ブロック内に伝搬しないようにうまく構成できるのでしょうか、、。符号ブロック$A$を制御ビット、符号ブロック$B$を標的ビットとみなした符号状態に対する制御NOT演算子を$\bar{U}_{A,B}$と書くことにします。このとき、

```math
\begin{align}
\bar{U}_{A,B} \bar{X_A} \bar{U}_{A,B} &= \bar{X_A} \bar{X_B} \\
\bar{U}_{A,B} \bar{X_B} \bar{U}_{A,B} &= \bar{X_B} \\
\bar{U}_{A,B} \bar{Z_A} \bar{U}_{A,B} &= \bar{Z_A} \\
\bar{U}_{A,B} \bar{Z_B} \bar{U}_{A,B} &= \bar{Z_A}\bar{Z_B} \tag{20}
\end{align}
```

を満たすように制御NOT演算を決めることを考えます。符号ブロックAの中に含まれる7個のビット番号を$A_{1},A_{2},A_{3},A_{4},A_{5},A_{6},A_{7}$とおき、符号ブロックBの中に含まれる7個のビット番号を$B_{1},B_{2},B_{3},B_{4},B_{5},B_{6},B_{7}$とおき、$i$番目のビットを制御、$j$番目のビットを標的とする単なる制御NOT演算子を$U_{i,j}$と書くことにします。そうすると、式(18)を満たす$\bar{U}_{A,B}$は、

```math
\bar{U}_{A,B} = U_{A_1,B_1} U_{A_2,B_2} U_{A_3,B_3} U_{A_4,B_4} U_{A_5,B_5} U_{A_6,B_6} U_{A_7,B_7}  \tag{21}
```

であることがわかります。確かめるのは、簡単です。式(20)の1番目の式は、

```math
\begin{align}
\bar{U}_{A,B} \bar{X_A} \bar{U}_{A,B} &= (U_{A_1,B_1} \cdots U_{A_7,B_7}) (X_{A_1} \cdots X_{A_7}) (U_{A_1,B_1} \cdots U_{A_7,B_7}) \\
&= (U_{A_1,B_1} X_{A_1} U_{A_1,B_1}) \cdots (U_{A_7,B_7} X_{A_7} U_{A_7,B_7}) \\
&= (X_{A_1} X_{B_1}) \cdots (X_{A_7} X_{B_7}) \\
&= (X_{A_1} \cdots X_{A_7}) (X_{B_1} \cdots X_{B_7}) = \bar{X_A} \bar{X_B} \tag{22}
\end{align}
```

となるので式(21)でＯＫです。2番目、3番目、4番目も同様に確認できます。ちょっと身構えてしまっていましたが、結局とても簡単な形になりました。回路図で書くと、

```
           A1 --*--------------------
[block A]  A2 --|--*-----------------
           A3 --|--|--*--------------
           A4 --|--|--|--*-----------
           A5 --|--|--|--|--*--------
           A6 --|--|--|--|--|--*-----
           A7 --|--|--|--|--|--|--*--
                |  |  |  |  |  |  |
           B1 --X--|--|--|--|--|--|--
[block B]  B2 -----X--|--|--|--|--|--
           B3 --------X--|--|--|--|--
           B4 -----------X--|--|--|--
           B5 --------------X--|--|--
           B6 -----------------X--|--
           B7 --------------------X--

```

というきれいな形になり、これでフォールトトレラントな制御NOTが実現できたことになります。見ての通り、符号ブロックAに発生したビット反転ノイズは符号ブロックBに伝搬します。が、同じブロック内に伝搬するわけではないので大丈夫です。符号ブロックBに発生した位相反転ノイズは符号ブロックAにも伝搬しますがこれも同じブロックに伝搬するわけではないので大丈夫です（各ブロックで各々誤り訂正が可能です）。


##### 位相シフトゲート:T

以上でCliffordゲートが出揃いました。量子計算をユニバーサルにするためには、もうひとつの位相シフトゲート$T$ゲートが必要です。$T$ゲートは、

```math
T =
\begin{pmatrix}
1 & 0\\
0 & e^{i\pi /4}
\end{pmatrix}  \tag{23}
```

で定義されるので、符号状態$\ket{\psi}=a\ket{0_L} + b\ket{1_L}$を入力して$\ket{\psi^{\prime}}=a\ket{0_L} + b e^{i\pi /4}\ket{1_L}$を出力するような演算をフォールトトレラントに構成できれば良いです。が、これはそれほど簡単ではありません。ちょっとわかりにくい巧妙なやり方[^5]なので、答えを先に言います。回路図は、

[^5]: [ニールセン、チャン](https://www.ohmsha.co.jp/book/9784274200090/)の「演習10.65」「演習10.66」にこの回路をどうやって導いたかが書かれています。この演習をやってみると、なるほど！という感じになります。また、「演習10.68」には、同じような考え方でToffoliゲートをフォールトトレラントに構成する方法が書かれています。

```
               |C>
                v
|0L>  --/--H--T----*----SX-- T|psi>
                   |    |
|psi> --/----------X----M

```

です。1番目の符号ブロックの中にこれから定義しようとしてる$T$が入っているのはどういうこと？と思われたかもしれません。この1番目の符号ブロックの最初のアダマールと$T$ゲートは、このように演算したのと同じような状態を吐き出すなんらかの作用を表していると思ってください。図では$\ket{C}$と書きましたが、

```math
\ket{C} = \frac{1}{\sqrt{2}} (\ket{0_L} + e^{i\pi /4} \ket{1_L})  \tag{24}
```

となります。どうやってこの状態をつくるかはこの後に説明するとして、こういう状態ができた前提でその次の演算について説明します。まず制御NOTを作用させます。これは先ほど構成したフォールトトレラントな制御NOTです。フォールトトレラントな制御NOTは、数式上は基底を論理基底にしたものとして扱えば良いだけなので、単なる制御NOTと同じように、

```math
\ket{0_L} \bra{0_L} \otimes I + \ket{1_L} \bra{1_L} \otimes \bar{X}  \tag{25}
```

と書けます。したがって、$\ket{C}\ket{\psi}$に対するCNOTの効果は、

```math
\begin{align}
\ket{C}\ket{\psi} &\rightarrow \frac{1}{\sqrt{2}} (\ket{0_L} \bra{0_L} \otimes I + \ket{1_L} \bra{1_L} \otimes \bar{X}) \ket{C}\ket{\psi} \\
&= \frac{1}{2} (\ket{0_L} \bra{0_L} \otimes I + \ket{1_L} \bra{1_L} \otimes \bar{X}) (\ket{0_L} + e^{i\pi /4} \ket{1_L}) (a\ket{0_L} + b\ket{1_L}) \\
&= \frac{1}{2} (\ket{0_L} (a\ket{0_L}+b\ket{1_L}) + e^{i\pi /4} \ket{1_L} (a\ket{1_L}+b\ket{0_L})) \\
&= \frac{1}{2} ((a\ket{0_L}+b e^{i\pi /4} \ket{1_L}) \ket{0_L} + (b\ket{0_L}+a e^{i\pi /4} \ket{1_L}) \ket{1_L}) \tag{26}
\end{align}
```

となります。2番目の符号ブロックを測定して測定値が$1(\ket{0_L})$だった場合、何もしないので、1番目の符号ブロックの出力は、

```math
\ket{\psi^{\prime}} = a\ket{0_L}+b e^{i\pi /4} \ket{1_L} = \bar{T} \ket{\psi}  \tag{27}
```

となります。測定値が$-1(\ket{1_L})$だった場合、$SX$を演算するので、同じく式(27)の状態にグローバル位相がかかったものが1番目の符号状態として出力されます。

さて、式(24)のような状態をどうやって吐き出させるかの説明が残っていました。スタビライザー形式で考えると$\ket{0_L}$から$TH\ket{0_L}$への変換は$\bar{Z} \rightarrow \bar{T}\bar{H}\bar{Z}\bar{H}\bar{T}^{\dagger}$と表すことができ、$\bar{T}\bar{H}\bar{Z}\bar{H}\bar{T}^{\dagger}$は、

```math
\begin{align}
\bar{T}\bar{H}\bar{Z}\bar{H}\bar{T}^{\dagger} &= \bar{T}\bar{X}\bar{T}^{\dagger}  \\
&=
\begin{pmatrix}
1 & 0\\
0 & e^{i\pi /4}
\end{pmatrix}
\begin{pmatrix}
0 & 1\\
1 & 0
\end{pmatrix}
\begin{pmatrix}
1 & 0\\
0 & e^{-i\pi /4}
\end{pmatrix} \\
&= e^{-i\pi /4} \bar{S} \bar{X}  \tag{28}
\end{align}
```

のように書き換えることができます。したがって、状態$\ket{C}$は演算子$e^{-i\pi /4} \bar{S} \bar{X}$の固有値$+1$に対する固有状態になります。ということは$e^{-i\pi /4} \bar{S} \bar{X}$を間接測定して、測定値$+1$が得られればそれを$\ket{C}$として良いということになります。もし測定値が$-1$だった場合は、$\bar{Z}$を適用します。そうすると、固有値$+1$の状態に変化します[^6]。

[^6]: $\bar{Z}$は$e^{-i\pi /4} \bar{S}\bar{X}$と反可換なので、$\bar{Z} \frac{1}{2} (I-e^{-i\pi /4} \bar{S}\bar{X})\ket{0_L} = \frac{1}{2} (I+e^{-i\pi /4} \bar{S}\bar{X})\ket{0_L}$となり、固有値を逆転させることができます。

ここで注意事項がひとつあります。$e^{-i\pi /4} \bar{S} \bar{X}$を間接測定すると言いましたが、ちょっとした工夫が必要です。模式的には、

```
|0>  -----H--*--*----*-----------H-- M
             |  |    |
|0L> --/-----X--S--exp(-i pi/4)-----

```

という測定なのですが、制御つきの$e^{-i\pi /4} I$ゲートが問題です。これは、

```
|0>  ----*-----------    ---T+--
         |             = 
|0L> --exp(-i pi/4)--    -------

```

という等式を使って、


```
|0>  -----H--*--*--T+-H-- M
             |  |
|0L> --/-----X--S--------

```

という形に変形するのが良いです。この図における$T$ゲートは単なる$T$ゲートです。

というわけで、これで符号状態に対する$T$ゲートを構成することができました。$CNOT,S,X$というゲートはすべてトランスバーサル型にできるので、全体としてフォールトトレラントであると言えます。ただし、測定については何も配慮していませんでした。本当は測定部分もフォールトトレラントにできてはじめて本当の意味でフォールトトレラントな$T$ゲートが実現できたということができます。

というわけで、次にフォールトトレラントな測定について説明します。

#### 測定

符号状態に働く演算子$ABC$の間接測定は、

```
|0> --H--*--*--*--H-- M
         |  |  |
    -----A--|--|-----
    --------B--|-----
    -----------C-----

```

とやればできます（Steane符号前提なので本当は符号ブロックには線が7本必要なのですが、説明を簡単にするため省略して3本にしています）。ところが、フォールトトレラントを実現する観点からするとこれは非常にマズイやり方です。補助ビットにノイズが発生した場合、符号ブロックを構成するすべてのビットにそのノイズが伝搬する可能性があります。これを避けるため、以下のような構成にすれば良いということがわかっています。

```
|0> --H--*----*----------*--H-- M
    -----X----|--*-------X-----
    -----X----|--|--*----X-----
              |  |  |
    ----------A--|--|----------
    -------------B--|----------
    ----------------C----------

```

補助ビットを3ビットにして、

```
|0> --H--*--
    -----X--
    -----X--

```

この回路で、いわゆるcat状態$(\ket{000}+\ket{111})/\sqrt{2}$を作ります。こうすると間接測定が実現できますし、補助ビットにノイズが発生したとしても、符号ブロックのどれか1個のビットにしかノイズが伝搬しません。

これはこれで良いのですが、最初のcat状態を作成する際にノイズが発生する可能性があります。補助ビット3ビットのどれかにノイズが発生すると簡単にブロック内をノイズが伝搬します。さて、どうしましょう？というわけで、こんな場合はcat状態を作成したら正しくできているかをどうか検査して正しくなかったらその状態を捨てて、もう一回作成をトライするという方針でいくしかないです。具体的には、cat状態を作成した直後にパリティ検査の回路を入れます。

```
       パリティ検査
      |0> --X--X-- M
            |  |
|0> --H--*--*--|--*----------*--H-- M
    -----X-----*--|--*-------X-----
    -----X--------|--|--*----X-----
                  |  |  |
    --------------A--|--|----------
    -----------------A--|----------
    --------------------A----------

```

こんな具合です。簡単のためパリティ検査は1つしか書いていませんが、すべてのビットの組み合わせで確認すべきなので、2番目と3番目のビットのパリティ検査も必要です。すべてのパリティが偶パリティになるまでcat状態の作成を繰り返します。

ちょっと大変ですがこれでフォールトトレラントになりました！と言いたいところなのですが、もうひとつ問題があります。パリティ検査のために追加した補助ビットに位相反転ノイズが発生することも考えておかないといけません。この場合間接測定のための3ビットブロックの2つのビットに伝搬してしまいます。これでは誤り訂正できないです。結果として、一番右の測定は間違った結果を出力することになります。この場合も仕方ないので、測定を3回繰り返して多数決をとるようにします。そうすると、誤り発生率を$O(p^2)$に抑えることができます（ノイズ発生の確率を$p$とすると）。

これで誤り耐性のある測定を構成することができました。測定は単に計算結果を取得するときだけでなく、誤り訂正のためのシンドローム測定や先ほど説明した$T$ゲート作成にも必要な部品ですし、次に説明する初期状態を作成する際にも必要になるものです。


#### 初期状態作成

というわけで、初期状態作成をフォールトトレラントに構成する方法について説明します。[前回](https://qiita.com/SamN/items/c4823734c1b994e75da4)、[前々回](https://qiita.com/SamN/items/41b56da69cc029fb36e3)の記事で5量子ビット符号の初期状態（論理基底状態$\ket{0_L}$）を作成する方法について詳細に述べました。それをSteane符号に置き換えて、間接測定の部分をたったいま説明したフォールトトレラントな測定に置き換えるだけです。

Steane符号の6個の生成元と論理$Z$演算子は先ほど提示していました。初期状態作成にはこの７個の演算子を順に測定していき固有値$+1$の固有空間への射影を次々に行っていくのですが、固有値$-1$の固有空間に射影されてしまう場合もあるので、その時は当該生成元と反可換で他の生成元と可換な演算子を適用すれば良かったです。Steane符号の場合、以下の7個の演算子になります[^7]。後の動作確認の際に必要になるので、ここに掲載しておきます。

[^7]: これ以外にも選択肢はあると思いますが、簡単に思いついたものを一つの例として並べてみました。

|             | 演算子                                                    |
|-------------------|-----------------------------------------------------------|
| $g_{1}^{\prime}$  | $Z \space Z \space Z \space Z \space I \space I \space I$ |
| $g_{2}^{\prime}$  | $Z \space Z \space I \space I \space Z \space Z \space I$ |
| $g_{3}^{\prime}$  | $I \space I \space Z \space I \space Z \space I \space Z$ |
| $g_{4}^{\prime}$  | $X \space X \space X \space X \space I \space I \space I$ |
| $g_{5}^{\prime}$  | $X \space X \space I \space I \space X \space X \space I$ |
| $g_{6}^{\prime}$  | $I \space I \space X \space I \space X \space I \space X$ |
| $g_{7}^{\prime}$  | $X \space X \space X \space X \space X \space X \space X$ |

これで量子計算に必要な一連のプロセス（初期状態作成、ゲート演算、測定）のすべてをフォールトトレラントに構成する方法がわかりました。

さて、次に気になるのは、その量子計算の誤り率をどの程度まで小さくできるかということです。システムを構成する各部品が誤る確率を$p$とすると、計算結果の誤り率は高々$O(p^2)$に抑えることができるということでしたが、それをどの程度にまで小さくできるのかということです。実は、$p$があるしきい値以下であれば、いくらでも小さくできる方法があります。それについて以下で説明します。


### 連結符号としきい値定理

量子計算システムを構成する部品としては、量子ビット、それを制御する制御デバイス、量子状態を測定するための測定デバイス等々があり、その各々が動作不良や外界からの雑音を受ける等で、所定の動作をしないことが一定の確率で発生します。非常に単純にその平均的な確率を$p$としてみます。前節までで説明したように、各符号ブロックあたり高々1個の誤りであれば訂正することができます。問題は2箇所に同時に誤りが発生して、伝搬することによって特定の符号ブロックに2つの誤りが入り込む場合です。その確率は$p^2$に比例していて$cp^2$となります。この比例係数$c$は「特定の符号ブロックに2つの誤りをもたらす」という場合の数です。[ニールセン、チャン](https://www.ohmsha.co.jp/book/9784274200090/)には、簡単な量子回路を例に非常に大雑把な見積もりとして$c \approx 10^{4}$という値が掲載されています。

この誤り率をもっと小さくするために符号ブロックや誤り訂正のための補助ブロックを構成する各量子ビットをさらに符号化することを考えます。もとのシステムの1ビットがSteane符号によって7倍+$\alpha$になっていたので、さらにその7倍+$\alpha$になります。システムの規模は大きくなるのですが、このお陰で誤り率は$c(cp^2)^2=c^{3}p^{4}$になります。もう一度、各ビットをSteane符号で符号化するとさらにシステム規模はその7倍+$\alpha$となり、誤り率は$c(c(cp^2)^2)^2=c^{7}p^{8}$になります。この操作を$k$回繰り返すと、システムの規模（必要なビット数）は、元のシステム規模を$d$としたとき$d^k$になり、誤り率は$(cp)^{2^k}/c$となります。このように符号化を階層的に構成することを「連結符号(concatenated code)」と呼びます。

いま考えている量子計算システムに$p(n)$個のゲートが元々あったとします。ここで$n$はある問題の大きさを表しており$p(n)$は$n$についての多項式関数であるとします。最終的に達成したい誤り率を$\epsilon$とすると、

```math
\frac{(cp)^{2^k}}{c} \leq \frac{\epsilon}{p(n)}  \tag{29}
```

という関係が成り立っていなければなりません。これを見てわかる通り、$p$がある閾値$p_{th} < 1/c$を満たしているなら$k$の値を十分大きくすることで、いくらでも誤り率を小さくできます。大雑把な見積もりとして$c \approx 10^{4}$だったので、$p_{th} \approx 10^{-4} = 0.01\%$ということになります。

では、誤り率$\epsilon$を達成するために必要なシステムの規模（ビット数）$d^k$はどの程度になるでしょうか。式(27)の不等号を近似に置き換えて、以下のように変形することでわかります。

```math
d^k \approx (\frac{\log(p(n)/c\epsilon)}{\log(1/pc)})^{\log d} = O(poly(\log p(n)/\epsilon))  \tag{30}
```

この中に含まれるゲート数は、

```math
O(poly(\log p(n)/\epsilon) p(n))  \tag{31} 
```

と見積もることができます。つまり、$p(n)$個のゲートを含む量子回路は、部品の誤り確率が高々$p$であるハードウェアによる、

```math
O(poly(\log p(n)/\epsilon) p(n))  \tag{32} 
```

個のゲートを用いて$\epsilon$の誤り率を達成することができます。ただし、$p$はある一定の閾値より小さくなっている必要があります。これを「しきい値定理」と呼んでいます。


## 動作確認

理論がわかったところで、フォールトトレラント量子計算の非常に簡単な例を取り上げて、量子計算シミュレータ[qlazy](https://github.com/samn33/qlazy)で動作確認してみたいと思います。$T$ゲートをフォールトトレラントに実現する方法について上で説明しましたが、ちょっとトリッキーな回路構成になっていると感じたので、これが本当に正しい働きをするものなのか確認してみます。$\ket{0_L}$状態に対して$T$ゲートを作用させても$\ket{0_L}$のままで全然面白くないので前後にアダマールをかけて、$\bar{H}\bar{T}\bar{H}\ket{0_L}$という演算を実施して最後に$\bar{Z}$基底で測定してみます。一応すべてのゲート演算と測定をフォールトトレラントに構成しました。が、何らかのノイズを加えて誤り訂正を行うような処理は省略しました（前回やったので）。さらに、cat状態が正しくできているか検査するパリティ検査や何度も測定して多数決をとるという方式も省略しました。とにかく、今回は、符号状態に対する演算および測定がフォールトトレラントな構成で正しく実現できていることの確認のみに注力しました。

### 実装

それでは、全体のPythonコードを示します。

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

```Python
from qlazypy import QState

def logical_zero():

    anc = [0,1,2,3,4,5,6]     # registers for ancila
    cod = [7,8,9,10,11,12,13] # registers for steane code
    qs_total = QState(14)

    # g1
    qs_total.h(anc[0])
    [qs_total.cx(anc[0], anc[i]) for i in range(1,4)]
    qs_total.cx(anc[0], cod[3]).cx(anc[1], cod[4]).cx(anc[2], cod[5]).cx(anc[3], cod[6])
    [qs_total.cx(anc[0], anc[i]) for i in range(1,4)]
    qs_total.h(anc[0])
    mval = qs_total.m(qid=[anc[0]]).last
    if mval == '1': qs_total.z(cod[0]).z(cod[1]).z(cod[2]).z(cod[3])
    qs_total.reset(qid=anc)

    # g2
    qs_total.h(anc[0])
    [qs_total.cx(anc[0], anc[i]) for i in range(1,4)]
    qs_total.cx(anc[0], cod[1]).cx(anc[1], cod[2]).cx(anc[2], cod[5]).cx(anc[3], cod[6])
    [qs_total.cx(anc[0], anc[i]) for i in range(1,4)]
    qs_total.h(anc[0])
    mval = qs_total.m(qid=[anc[0]]).last
    if mval == '1': qs_total.z(cod[0]).z(cod[1]).z(cod[4]).z(cod[5])
    qs_total.reset(qid=anc)

    # g3
    qs_total.h(anc[0])
    [qs_total.cx(anc[0], anc[i]) for i in range(1,4)]
    qs_total.cx(anc[0], cod[0]).cx(anc[1], cod[2]).cx(anc[2], cod[4]).cx(anc[3], cod[6])
    [qs_total.cx(anc[0], anc[i]) for i in range(1,4)]
    qs_total.h(anc[0])
    mval = qs_total.m(qid=[anc[0]]).last
    if mval == '1': qs_total.z(cod[2]).z(cod[4]).z(cod[6])
    qs_total.reset(qid=anc)

    # g4
    qs_total.h(anc[0])
    [qs_total.cx(anc[0], anc[i]) for i in range(1,4)]
    qs_total.cz(anc[0], cod[3]).cz(anc[1], cod[4]).cz(anc[2], cod[5]).cz(anc[3], cod[6])
    [qs_total.cx(anc[0], anc[i]) for i in range(1,4)]
    qs_total.h(anc[0])
    mval = qs_total.m(qid=[anc[0]]).last
    if mval == '1': qs_total.x(cod[0]).x(cod[1]).x(cod[2]).x(cod[3])
    qs_total.reset(qid=anc)
    
    # g5
    qs_total.h(anc[0])
    [qs_total.cx(anc[0], anc[i]) for i in range(1,4)]
    qs_total.cz(anc[0], cod[1]).cz(anc[1], cod[2]).cz(anc[2], cod[5]).cz(anc[3], cod[6])
    [qs_total.cx(anc[0], anc[i]) for i in range(1,4)]
    qs_total.h(anc[0])
    mval = qs_total.m(qid=[anc[0]]).last
    if mval == '1': qs_total.x(cod[0]).x(cod[1]).x(cod[4]).x(cod[5])
    qs_total.reset(qid=anc)

    # g6
    qs_total.h(anc[0])
    [qs_total.cx(anc[0], anc[i]) for i in range(1,4)]
    qs_total.cz(anc[0], cod[0]).cz(anc[1], cod[2]).cz(anc[2], cod[4]).cz(anc[3], cod[6])
    [qs_total.cx(anc[0], anc[i]) for i in range(1,4)]
    qs_total.h(anc[0])
    mval = qs_total.m(qid=[anc[0]]).last
    if mval == '1': qs_total.x(cod[2]).x(cod[4]).x(cod[6])
    qs_total.reset(qid=anc)

    # g7
    qs_total.h(anc[0])
    [qs_total.cx(anc[0], anc[i]) for i in range(1,7)]
    [qs_total.cz(anc[i], cod[i]) for i in range(7)]
    [qs_total.cx(anc[0], anc[i]) for i in range(1,7)]
    qs_total.h(anc[0])
    mval = qs_total.m(qid=[anc[0]]).last
    if mval == '1': [qs_total.x(q) for q in cod]
    qs_total.reset(qid=anc)

    qs = qs_total.partial(qid=cod)
    qs_total.free()

    return qs

def faulttolerant_t(qs_in):

    A = [0,1,2,3,4,5,6]         # registers for ancila
    B = [7,8,9,10,11,12,13]     # registers for output quantum state
    C = [14,15,16,17,18,19,20]  # registers for input quantum state
    qs_A = QState(7)
    qs_B = logical_zero()
    qs_AB = qs_A.tenspro(qs_B)
    qs_ABC = qs_AB.tenspro(qs_in)

    # -H-T-
    qs_ABC.h(A[0])
    [qs_ABC.cx(A[0], A[i]) for i in range(1,7)]
    # [qs_ABC.cx(A[i],B[i]).cs(A[i],B[i]).cz(A[i],B[i]).t_dg(A[i]) for i in range(7)]
    [qs_ABC.cx(A[i],B[i]).cs(A[i],B[i]).cz(A[i],B[i]) for i in range(7)]

    [qs_ABC.cx(A[0], A[i]) for i in range(1,7)]
    # qs_ABC.h(A[0])
    qs_ABC.t_dg(A[0]).h(A[0])
    mval = qs_ABC.m(qid=[A[0]]).last
    if mval == '1': [qs_ABC.z(q) for q in B]
    qs_ABC.reset(qid=A)

    # -CNOT-
    [qs_ABC.cx(B[i], C[i]) for i in range(7)]
    
    # -M-, -SX-
    qs_ABC.h(A[0])
    [qs_ABC.cx(A[0], A[i]) for i in range(1,7)]
    [qs_ABC.cz(A[i],C[i]) for i in range(7)]
    [qs_ABC.cx(A[0], A[i]) for i in range(1,7)]
    qs_ABC.h(A[0])
    mval = qs_ABC.m(qid=[A[0]]).last
    if mval == '1': [qs_ABC.x(q).s(q).z(q) for q in B]

    qs_out = qs_ABC.partial(qid=B)
    QState.free_all(qs_A, qs_B, qs_AB, qs_ABC)

    return qs_out

def faulttolerant_m(qs_in):

    anc = [0,1,2,3,4,5,6]      # ancila
    cod = [7,8,9,10,11,12,13]  # steane code
    qs_anc = QState(7)
    qs_total = qs_anc.tenspro(qs_in)

    qs_total.h(anc[0])
    [qs_total.cx(anc[0], anc[i]) for i in range(1,7)]
    [qs_total.cz(anc[i], cod[i]) for i in range(7)]
    [qs_total.cx(anc[0], anc[i]) for i in range(1,7)]
    qs_total.h(anc[0])
    md = qs_total.m(qid=[0], shots=10000)
    QState.free_all(qs_anc, qs_total)

    return md

if __name__ == '__main__':

    qs = QState(1).h(0).t(0).h(0)    # not fault-tolerant -HTH-
    qs.show()
    
    qs_ini = logical_zero()          # make initial state (logical zero)
    [qs_ini.h(i) for i in range(7)]  # operate fault-tolerant H
    qs_fin = faulttolerant_t(qs_ini) # operate fault-tlerant T
    [qs_fin.h(i) for i in range(7)]  # operate fault-tolerant H
    md = faulttolerant_m(qs_fin)     # execute fault-tolerant measurement
    print(md.frequency)

    QState.free_all(qs, qs_ini, qs_fin)
```

何をやっているか簡単に説明します。まず、メイン処理部を見てください。

```Python
qs_ini = logical_zero()          # make initial state (logical zero)
```

で、Steane符号の論理基底状態$\ket{0_L}$を作成しています。詳細は関数logical_zeroの中身なのですが、とても長くてわかりにくいかもしれません。が、基本は簡単で、

```Python
# g1
qs_total.h(anc[0])
[qs_total.cx(anc[0], anc[i]) for i in range(1,4)]
qs_total.cx(anc[0], cod[3]).cx(anc[1], cod[4]).cx(anc[2], cod[5]).cx(anc[3], cod[6])
[qs_total.cx(anc[0], anc[i]) for i in range(1,4)]
qs_total.h(anc[0])
mval = qs_total.m(qid=[anc[0]]).last
if mval == '1': qs_total.z(cod[0]).z(cod[1]).z(cod[2]).z(cod[3])
qs_total.reset(qid=anc)
```

のようなコードの繰り返しになっています。補助ビットをcat状態にして生成元を間接測定します。測定結果が1（つまり$\ket{1_L}$）だった場合、当該生成元と反可換な演算子を適用します。7個の演算子についてすべて完了したらば、その状態を（補助ビットを除いて）リターンします。ここで、測定値を得るためのメソッドlastは2進数の文字列を得るためのものです(v0.0.41で追加)。次に、

```Python
[qs_ini.h(i) for i in range(7)]  # operate fault-tolerant H
```

で、フォールトトレラントなアダマールを適用しています。トランスバーサル型なので簡単です。

```Python
qs_fin = faulttolerant_t(qs_ini) # operate fault-tlerant T
```

で、フォールトトレラントな$T$ゲートを実行しています。関数faulttolerant_tの中身を見てみます。上で説明した1番目の符号ブロックをB、2番目の符号ブロックをCと名付け、測定に必要となる補助ブロックをAと名付けています。各々7個のビットから成り立っています。という前提で見ていただければと思います。

```Python
# -H-T-
qs_ABC.h(A[0])
[qs_ABC.cx(A[0], A[i]) for i in range(1,7)]
[qs_ABC.cx(A[i],B[i]).cs(A[i],B[i]).cz(A[i],B[i]).t_dg(A[i]) for i in range(7)]
[qs_ABC.cx(A[0], A[i]) for i in range(1,7)]
qs_ABC.h(A[0])
mval = qs_ABC.m(qid=[A[0]]).last
if mval == '1': [qs_ABC.z(q) for q in B]
qs_ABC.reset(qid=A)
```

で、$H$と$T$を適用したのと同じ符号状態を作成しています。補助ビットをcat状態にして、演算子$e^{-i \pi /4}SX$を測定するのですが$S$のトランスバーサル型は$ZS$だったので$ZSX$を制御化するようにします。さらに、位相$e^{-i \pi /4}$は制御側の$T$ゲートに等しいということだったので、その演算も忘れず入れています。

```Python
# -CNOT-
[qs_ABC.cx(B[i], C[i]) for i in range(7)]
```

で、トランスバーサルなCNOTを実行して、

```Python
# -M-, -SX-
qs_ABC.h(A[0])
[qs_ABC.cx(A[0], A[i]) for i in range(1,7)]
[qs_ABC.cz(A[i],C[i]) for i in range(7)]
[qs_ABC.cx(A[0], A[i]) for i in range(1,7)]
qs_ABC.h(A[0])
mval = qs_ABC.m(qid=[A[0]]).last
if mval == '1': [qs_ABC.x(q).s(q).z(q) for q in B]
```

で、符号ブロックCを測定して測定結果が1であれば、符号ブロックAに$SX$を適用します。このときも$S$のトランスバーサル型が$ZS$だったことを忘れずに考慮しています。結果は符号ブロックBに入っているはずなので、

```Python
qs_out = qs_ABC.partial(qid=B)
```

で、符号ブロックBに対応した部分系をpartialメソッドで取り出しています。これをリターンします。

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

$T$ゲートの結果に対して、

```Python
[qs_fin.h(i) for i in range(7)]  # operate fault-tolerant H
```

で、再びアダマールをフォールトトレラントに演算して、最後に、

```Python
md = faulttolerant_m(qs_fin)     # execute fault-tolerant measurement
print(md.frequency)
```

で、測定を実施します。詳細は関数faulttolerant_mの中身を見てください。補助ビットをcat状態にして間接測定しているだけです。測定結果を変数md(MDataクラスのインスタンス)として取得し、frequencyメソッド(v0.0.41で追加)で頻度データをCounter形式で得るようにしています。以上です。

### 結果

実行結果を以下に示します。

```
c[0] = +0.9239-0.0000*i : 0.8536 |++++++++++
c[1] = +0.0000-0.3827*i : 0.1464 |++
Counter({'0': 8524, '1': 1476})
```

最初の2行はフォールトトレラントではない普通の-H-T-H-の結果です。これが答えになります。つまり$\ket{0_L}$状態と$\ket{1_L}$状態の確率は各々0.8536と0.1464になるということです。3行目のCounterがフォールトトレラントの-H-T-H-を実行して10000回測定シミュレーションした結果になります。答えの確率に大体一致していると思います（思ってください！）。


## おわりに

フォールトトレラント量子計算というのは、いろんなテクニックを駆使しながら実現するとても大変な技術だということがわかりました。本当に実用的な量子コンピュータをつくるには、やはりこのような地道な蓄積が大事なのですね。しきい値定理は、その努力がきっと必ず報われるということを保証してくれる心の支えとも言える超重要な理論成果でありました。それにしても$10^{-4}=0.01\%$という誤り率は厳しい要求です。スタビライザー符号のような誤り訂正符号と連結符号を想定すると、どうしてもこのくらいの精度が必要なのです。が、もっと別の符号化方式を使えば、このしきい値を上げることができるようです。次回は、そんな符号方式のひとつである「トポロジカル符号（表面符号）」について勉強してみたいと思います。


以上