量子回路 (Q#) で足し算をやってみたら死ぬほど遅かった

# まえがき

[Interface の 2019 年 3 月号](https://interface.cqpub.co.jp/magazine/201903/)に量子ビット (ブロッホ球) を PIC で大雑把にシミュレートするという~~狂気を感じる~~**大変楽しい**特集がありました。電子工作ガチ勢の Interface が量子回路に乗り込んで来るなら、量子コンピューター側が電子工作に乗り込んでもよかろうと思ったのです。電子工作の最初の一歩といえば加算器かカウンタですよね。というわけで加算器を量子回路(というか Q#) で実装してみました。

## 全加算器

全加算器は 3 入力 2 出力の論理回路です。詳細は [Wikipedia](https://ja.wikipedia.org/wiki/%E5%8A%A0%E7%AE%97%E5%99%A8) 見ましょう。こんなやつです。

![fa.png](https://qiita-image-store.s3.amazonaws.com/0/59544/d23b7945-4908-badf-ef79-5a21d5cb3e2a.png)
図1  全加算器

入力 A、B と下位からの桁上げ Cin が与えられると、結果 S と上位への桁上げ Cout を出力します。これを N 段つなげると任意桁数の足し算ができるようになります。実際には桁上げ先見が必要になりますが、例えば 4 bit の加算器は以下です。

![4bit_fa.png](https://qiita-image-store.s3.amazonaws.com/0/59544/b0b1fcbb-4710-66c0-7a41-5decfca1ea31.png)
図2  4 ビット 加算回路

早速 Q# で実装しましょう。

## Q# で全加算器

まずは上記の全加算器 (FullAdder) を実装します。それほど難しくはありません。

- $S= A \oplus B \oplus C_{\text{in}}$
- $C_{\text{out}}$  は A, B, Cin の多数決

なので、S の計算はパリティ観測で、多数決は CCNOT ゲートで実現できます。(なんで Q# でこんなふうに書けるかは、それぞれ[ここ](https://qiita.com/tehishik/items/770b3d894b1850b4c703)や[このあたり](https://qiita.com/tehishik/items/1e68c6e2ee0605b3cd16)で解説しているので、ご興味ある方はご参照ください。)

```cs
operation fulladder (a: Qubit, b: Qubit, cin: Qubit, s: Qubit, cout: Qubit): Unit {
    // パリティ観測で "a + b + cin" を実行
    let m0 = MeasureAllZ([a, b, cin]);
    if (m0 == One) {
        X(s);
    } 

    // CCNOT ゲートの処理を Cout に適用して "[a, b, cin]" の多数決を実現
    CCNOT(a, b, cout);
    CCNOT(a, cin, cout);
    CCNOT(b, cin, cout);
}
```

これで 1 ビットの計算はできるようになりました。あとはこれをつないでいくだけです。

ここで 1 つ注意点があります。量子ビットは今のコンピューターのビットとは異なり、途中で状態を複製したり、分岐させることができません。そのため、入力も出力も事前に用意する必要があります。具体的に言うなら、図1の全加算器だけを実行する場合でも最初から 5 量子ビットを用意しておく必要がある、ということになります。愚直に考えれば、N ビットの加算を計算するとすれば A、B、S でそれぞれ N ビット、C で N+1 ビットが必要となるので、合計は 4N+1 ビットです。4 ビット同士の値の足し算をするために、17 ビットも必要になる計算です。C 言語は `short` でも 16 ビットなので、この方法だと量子コンピューターでは 65 ビット必要です。[先日発表された IBM の量子コンピューター](https://www.technologyreview.jp/s/62657/ibm-raises-the-bar-with-a-50-qubit-quantum-computer/) は 50 ビットらしいので、この方法だと 16 ビット同士の足し算はできませんね。

## 全加算器つなぎ合わせ

つなぎ合わせて見ましょう。

```cs
// 与えられた Bool のビット列に従って量子ビットをセットする
operation SetQubit(qs: Qubit[], target: Bool[]): Unit {
    for (i in 0..Length(qs) - 1) {
        if(target[i]) {
            X(qs[i]);
        }
    }
}

// 加算器
operation QuantumAdder (intA: Int, intB: Int, N: Int) : Int {
    let boolA = BoolArrFromPositiveInt(intA, N);
    let boolB = BoolArrFromPositiveInt(intB, N);
    mutable result =  0;

    // 4N+1 個の量子ビット用意
    using (qs = Qubit[N * 4 + 1]) {

        // a, b, c(in と out は共通) , s を準備
        let a = qs[0..N-1];
        let b = qs[N..2*N-1];
        let carry = qs[2*N..3*N];
        let sum = qs[3*N+1..4*N];

        let res = sum[0..N-1] + [carry[N]];
        
        // 与えられた値に基づいて量子ビットを初期化
        SetQubit(a, boolA);
        SetQubit(b, boolB);

        // 全加算器を使って桁上げしながら順番に処理
        for(i in 0..N -1) {
            fulladder(a[i], b[i], carry[i], sum[i], carry[i+1]);
        }

        // 計算結果の観測
        set result = MeasureInteger(LittleEndian(res));

        // 量子ビットの開放
        ResetAll(qs);


    }
    return result;
}
```

やったー！これで足し算ができるようになりました。あとは C# のドライバを適当に書けば実行できます。

## 結果

とりあえず 6 ビットでやってみました！

![GIF2.gif](https://qiita-image-store.s3.amazonaws.com/0/59544/9851f6ad-aeb3-5b3d-1353-a6a0e41daa72.gif)

…**くっそ遅いですね**。ちなみに 16 ビットとかにすると、仮想メモリが数十 GB を超えたうえ、Exception を吐いて死にます。流石に非効率的過ぎましたかね。とはいえ、量子コンピューターの動作を現在のコンピューターがシミュレートして動いているということを考慮しても、こうした処理があまり得意ではなさそう (というか今のコンピューターで十分効率的) だなという感じは見て取れるかなと思いました。


## 最後に

人類が量子コンピューターで足し算をするのは早すぎた (一生来ない？) ようです。 [この辺の論文](https://arxiv.org/pdf/quant-ph/0410184.pdf)にゲート数削減の考察があるようです。気が向いたら実装してみます。