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

まえがき

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

全加算器

全加算器は 3 入力 2 出力の論理回路です。詳細は Wikipedia 見ましょう。こんなやつです。

図1 全加算器

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

図2 4 ビット 加算回路

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

Q# で全加算器

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

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

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

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 の量子コンピューター は 50 ビットらしいので、この方法だと 16 ビット同士の足し算はできませんね。

全加算器つなぎ合わせ

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

// 与えられた 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 ビットでやってみました！

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

最後に

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