Quantum Katas で始める量子コンピュータ入門 |9⟩: quantum error-correction

## 前書き

本記事では、[Quantum Katas の quantum error-correction (QEC) codes](https://github.com/Microsoft/QuantumKatas/tree/master/QEC_BitFlipCode) について解説します。Q# や Quantum Katas って何よという方は [Quantum Katas で始める量子コンピュータ入門 |0⟩](https://qiita.com/stwhabout/items/195b93a194c24ba5fb73) をご参照ください。

さて、勝手にまとめて来た Quantum Katas のまとめも今回で $|9⟩$ 回目となりました。現時点で公開されている Kata は 10 個なので、ようやく終わりが見えてきましたね。今回はアルゴリズムや観測とは一線を画す内容で、誤り検出および訂正について学んでいきます。この Kata では観測の基礎を行った $|3⟩$ や $|8⟩$ の内容をがっつり使いますので、まだやっていない方はそちらを先にご参照ください。

知っている人にとっては当たり前かもしれませんが、誤り検出と誤り訂正という二つは区別して議論する必要があります。名前の通り誤り検出は「なにか間違っていることはわかる、でも何が間違っているかはわからない」という機能を指します。現実世界の利用例でいえば、この Qiita を見ているときにも利用される TCP や IP のチェック サムが該当します。TCP と IP はそれぞれチェック サム （送信したパケットの情報が変わってしまっていないかどうかを判定する）機能を有していて、受信ノードはその情報が正しいかどうか、再送を要求しなければいけないかどうかを判定することができるようになっています。一方誤り訂正は名前の通り、訂正する能力も有する機能のことを指します。これもそのまんまですが、Forward Error Correction (FEC) と呼ばれますね。残念ながら（？）私たちが普段使う TCP や IP は FEC を具備していません。すみません、若干脱線しました。

量子コンピューターは、原理的に常に誤差との闘いを強いられるため、誤りをいかに検出するかが信頼性の高い計算を行う上で非常に重要なポイントとなります。また、可能であれば検出した誤りを訂正できればベストです。今回は最もシンプルな、複数量子ビットを利用した誤りの検出および訂正について学びます。進めていきましょう。

## 各 Task の解説

### Task 1. Parity Measurements

#### 問題

> 入力: 未知の基底状態にある 3 量子ビット

> ゴール: パリティビットを出力せよ。すなわち、$|x_0, x_1, x_2⟩$ に対し $𝑥x_0 \oplus x_1 \oplus x_2$ を出力せよ。

#### 解説

前回の Joint Measurement をやった方からは「見たわ！」という声も聞こえそうですが、パリティ ビットは PauliZ で計算可能なのでした。Joint Measurement を使わずに


```cs
// あえて Joint Measurement を使わないならこうなる
operation MeasureParity (register : Qubit[]) : Result {
    mutable result = false;
    using (qs = Qubit[1]) {
        for(i in 0..Length(register)-1) {
            CNOT(register[i], qs[0]);
        }
        set result = BoolFromResult(M(qs[0]));
        ResetAll(qs);
    }
    if(result) {return One;}
    else {return Zero;}
}
```

なんて書き方もできなくないですが、せっかくなので学んだことは早速つかいましょう。回答は以下です。

```cs
operation MeasureParity (register : Qubit[]) : Result {
    body {
        return MeasureAllZ(register);
    }
}
```

すっきりかけますね。

###  Task 2. Encoding Codewords

#### 問題

> 入力: 3 量子ビット $|\psi⟩ \otimes |00⟩$、ただし $|\psi⟩ = \alpha |0⟩ + \beta |1⟩$

> ゴール: $|\bar \psi⟩ = \alpha |000⟩ + \beta |111⟩$ を作れ。

#### 解説

これは誤りを検出したり訂正したりするための重ね合わせ状態を作る下準備です。省略します。

```cs
operation Encode (register : Qubit[]) : Unit {
    body {
        CNOT(register[0], register[1]);
        CNOT(register[0], register[2]);
    }
}
```

### Task 3. Error Detection I

#### 問題

> 入力: $|\bar \psi⟩ = \alpha |000⟩ + \beta |111⟩$ もしくは先頭ビットが反転した $\alpha |100⟩ + \beta |011⟩$

> 出力: 前者の場合は `Zero` を、後者の場合は `One` を出力せよ。

#### 解説

最初の誤り検出の問題です。今回は先頭ビットに誤りがあるかもしれないということが問題からわかっています。このときはどうすればいいでしょうか？今回の場合は、3 ビットとも観測するのではなく、先頭 2 ビットをパリティ測定してやれば、前者の場合は `Zero` が、後者の場合は `One` が得られそうです。

回答は一行で終わりです。

```cs
    operation DetectErrorOnLeftQubit (register : Qubit[]) : Result {
        body {
    		return MeasureAllZ(register[0..1]);
        }
    }
```


###  Task 4. Error Correction I

#### 問題

> 入力: $|\bar \psi⟩ = \alpha |000⟩ + \beta |111⟩$ もしくは先頭ビットが反転した $\alpha |100⟩ + \beta |011⟩$

> ゴール: 後者の場合は先頭ビットを訂正し、 $|\bar \psi⟩ = \alpha |000⟩ + \beta |111⟩$ 状態とせよ。

#### 解説

最初の誤り訂正の問題です。今回は誤りが生じた箇所もわかっていますし、検出さえできれば先頭ビットを反転するだけで訂正ができそうです。すでに検出は行ったので、 Task 3 のオペレーションをそのまま使えば回答は以下となります。

```cs
operation CorrectErrorOnLeftQubit (register : Qubit[]) : Unit {
    if(BoolFromResult(DetectErrorOnLeftQubit(register))) {
        X(register[0]);
    }
}
```


### Task 5. Error Detection II

#### 問題

> 入力: $|\bar \psi⟩ = \alpha |000⟩ + \beta |111⟩$ もしくはどこか 1 ビットが反転した量子ビット

> 出力: 検出した誤りに応じて、以下の通りに出力せよ。

| Error      | Output |
|------------|--------|
| None       | 0      |
| 1 ビット目 | 1      |
| 2 ビット目 | 2      |
| 3 ビット目 | 3      |

#### 解説

先程は先頭ビットが誤っているかどうかを判定するという問題でしたが、今回はどのビットが誤っているかがわからないため、それを判別するという問題となります。チェック自体は複数行う必要があるため、面倒にはなりますが、さして困難なタスクではありません。

先頭ビットの誤り検出を行ったときは `register[0..1]` の Joint Measurement を行えばよかったですが、今回は併せて `register[1..2]` の観測も行います。1 ビット目がエラーとなったときは、 `MeasureAllZ(register[0..1])`  のみが 1 となりますが、2 ビット目だった場合は  `MeasureAllZ(register[0..1])`  も  `MeasureAllZ(register[1..2])` も 1 になります。一方、3 ビット目がエラーとなったときは `MeasureAllZ(register[1..2])` のみが 1 となりますね。表にまとめると以下となります。



| Error      | register[0..1]の観測結果 | register[1..2]の観測結果 | Output |
|------------|----------------|----------------|--------|
| None       | 0              | 0              | 0      |
| 1 ビット目 | 1              | 0              | 1      |
| 2 ビット目 | 1              | 1              | 2      |
| 3 ビット目 | 0              | 1              | 3      |


あとは上記を実装すれば終了です。簡単ですね。

```cs
operation DetectErrorOnAnyQubit (register : Qubit[]) : Int {
    mutable result = 0;
    let m1 = MeasureAllZ(register[0..1]);
    let m2 = MeasureAllZ(register[1..2]);

    if(m1 == One && m2 == Zero) {
        set result = 1;
    } elif(m1 == One && m2 == One) {
        set result = 2;
    } elif(m1 == Zero && m2 == One) {
        set result = 3;
    }
    return result;
}
```

### Task 6. Error Correction II

#### 問題

> 入力: $|\bar \psi⟩ = \alpha |000⟩ + \beta |111⟩$ もしくはどこか 1 ビットが反転した量子ビット

> 出力: 検出した誤りに応じて、量子ビットを訂正せよ。

#### 解説

コードとしてはとても単純で、先程のタスクで検出したビットを反転するだけで終了です。


```cs
operation CorrectErrorOnAnyQubit (register : Qubit[]) : Unit {
    let result = DetectErrorOnAnyQubit(register);
    if(result != 0) {
        X(register[result - 1]);
    }
}
```

ここまでで、3 量子ビットを使って 1 量子ビットまでの誤りを検出し、訂正することができることを学びました。既にお気づきかとは思いますが、この訂正方法では 2 ビット以上の誤りに対しては効果を発揮しませんし、また、位相のエラーに関しても無力です。

### Task 7. Logical X Gate

#### 問題

> 入力: $|\bar \psi⟩ = \alpha |000⟩ + \beta |111⟩$ もしくはどこか 1 ビットが反転した量子ビット

> ゴール: エラーを含むかもしれない入力を全て反転せよ。すなわち、$|\bar \psi⟩ = \alpha |000⟩ + \beta |111⟩$  が与えられた場合は状態を $\beta |000⟩ + \alpha |111⟩$ に、$\alpha |010⟩ + \beta |101⟩$ が与えられた場合は $\beta |010⟩ + \alpha |101⟩$ にそれぞれ変換せよ。

#### 解説

深く考える必要はありません。3 量子ビットを全く同じように X ゲートで処理すれば終了です。


```cs
operation LogicalX (register : Qubit[]) : Unit {
    for (i in 0..Length(register) - 1) {
        X(register[i]);
    }
}
```

3 量子ビットをまとめて 1 量子ビットと見なす場合、ゲートの処理は全ての量子ビットに対して同じように処理すればよいということになります。

### Task 8. Logical Z Gate

#### 問題

> 入力: $|\bar \psi⟩ = \alpha |000⟩ + \beta |111⟩$ もしくはどこか 1 ビットが反転した量子ビット

> ゴール: エラーを含むかもしれない入力の位相を反転せよ。すなわち、$|\bar \psi⟩ = \alpha |000⟩ + \beta |111⟩$  が与えられた場合は状態を $\alpha |000⟩ - \alpha |111⟩$ に、$\alpha |010⟩ + \beta |101⟩$ が与えられた場合は $\alpha |010⟩ - \beta |101⟩$ にそれぞれ変換せよ。

#### 解説

こちらも深く考える必要はありません。3 量子ビットを全く同じように Z ゲートで処理すれば終了です。


```cs
operation LogicalZ (register : Qubit[]) : Unit {
    for (i in 0..Length(register) - 1) {
        Z(register[i]);
    }
}
```


## まとめ

この記事では、量子ビットの誤り検出/訂正について学んできました。これまでの Kata とは異なり、具体的なアルゴリズムや観測とは違う観点で Q# について学ぶことができたかなと思います。シミュレーションをする上ではこうした誤り訂正/検出は不要かと思いますが、実機を利用するようなケースでは非常に重要となることが想像されます。

次回は Grover algorithm でお会いしましょう。