Blueqatで128ビット加算器を動かしてみた

# 正気か?
2019年末現在、発表されている量子コンピュータで、128ビット加算器を動かすのに必要な量子ビット数を持っているものはありません。
また、一般に、量子コンピュータを古典コンピュータでシミュレートするには2の量子ビット数乗の複素数が必要で、128ビット加算器を動かすのに必要なメモリを持っているマシンはありません。

じゃあ無理じゃん。そう思うじゃん？

ですが、加算器って、そもそも古典コンピュータでも動くものだから、古典コンピュータでもシミュレートできるんじゃないですか?
それを実際にやってみたのが、この記事です。

古典コンピュータでも効率よくシミュレートできるように、今回は、重ね合わせ状態にない2つの整数同士の加算を行いました。

# よし、やるぞ

まず動かしてみましょう。
今回特別に用意しましたバックエンドをインストールします。

```sh
pip install blueqat_classicalbit_backend
```

続いて、加算するスクリプトを呼び出してみます。

```sh
python -m blueqat_classicalbit_backend
```

乱数を振っているので、何度も動かすと、いろんなのが出てきます。

```shell-session
$ python -m blueqat_classicalbit_backend
152490833597243651881358545928870703965 + 33996090087648457986490234298246419943 = 186486923684892109867848780227117123908
$ python -m blueqat_classicalbit_backend
139074587703179274591376699439261081159 + 39783386593626087826565877334191465788 = 178857974296805362417942576773452546947
$ python -m blueqat_classicalbit_backend
58745633672795689287074762971776980039 + 51662405526747060138580976982415918288 = 110408039199542749425655739954192898327
$ python -m blueqat_classicalbit_backend
121012545071215090940050764453053995080 + 153329068579833955484082870380726056209 = 274341613651049046424133634833780051289
$ python -m blueqat_classicalbit_backend
54303131703632904159538515878735454297 + 12196436579933817990618318210306807844 = 66499568283566722150156834089042262141
$ python -m blueqat_classicalbit_backend
120104303378664039946983633420096905568 + 168495603237786472094127576811319908293 = 288599906616450512041111210231416813861
```

加算結果は、量子回路をシミュレートして出てきたものから取り出して、普通にPythonで加算したものと結果が会うことを確認してから表示しています。

以下、何をやったのかコードを見ながら解説していきます。

# バックエンドの作成
バックエンドの作成方法については、以前に触れた
[Blueqatのバックエンドを作る 〜 その1](https://qiita.com/gyu-don/private/104c5565cdc0f6da1986)と[Blueqatのバックエンドを作る 〜 その2](https://qiita.com/gyu-don/private/2bd354a9999201b5463d)もご参照ください。今回の内容は、とくに「その2」で触れられています。

## Context

```py
@dataclass
class _ClassicalBitBackendContext:
    shots: int
    bits: List[bool]
    measured: List[bool]
```

[Blueqatのバックエンドを作る 〜 その2](https://qiita.com/gyu-don/private/2bd354a9999201b5463d)で詳細を解説したのですが、Blueqatのバックエンドを作るときの流れは

- `_preprocess_run`メソッドで実行のための準備をする。とくに`ctx`とよばれるオブジェクトを用意する
- ゲートの適用は、`ctx`を更新し、`ctx`を返すメソッドの呼び出し
- `_postprocess_run`メソッドで`ctx`を最終的に返したい結果に変換する

でした。

量子回路を実行する間に持っていないといけない情報は

- shot数
    - 何回、この量子回路を動かしたことにするか
    - 実機では、実際にその回数だけ、同じ回路を動かす
    - シミュレータでは、実際にその回数だけ動かしてもいいし、そうしたら返ってくるであろう結果を返してもいい
    - 今回、古典ビットなので、何回動かしても結果は同じ
        - なので、1度だけ計算して「xx回やったら全部xxxでした」という結果を返す
- 現在の「状態」
    - 量子状態を保持しようと思ったら、普通は膨大なメモリが必要
    - 今回、古典ビットの「状態」なので、単なるビット列
- 測定結果
    - 測定しない場合や、測定してから状態をいじる場合もあるので、別で取っておく
- (回路のビット数)
    - 必要ではあるが、「状態」の長さを見ると分かるので、特に保存しない

です。これらを`_ClassicalBitBackendContext`で保持します。

## `_preprocess_run`と`_postprocess_run`

```py
class ClassicalBitBackend(Backend):
    def _preprocess_run(self, gates, n_qubits, args, kwargs):
        shots = kwargs.get('shots', 100)
        return gates, _ClassicalBitBackendContext(shots, [False] * n_qubits, [False] * n_qubits)

    def _postprocess_run(self, ctx):
        return Counter({
            ''.join('1' if b else '0' for b in ctx.bits): ctx.shots
        })
```

`_preprocess_run`は、`_ClassicalBitBackendContext`を初期化して返して終わりです。

ゲートは後で見ますが、それらが終わった後に呼ばれる`_postprocess_run`では、測定結果を`Counter`型に変換して「`ctx.shots`回試したら、全部この結果だったよ」と返します。

`ctx`が単にビット列になっているのを見ると分かるように、このバックエンドは、一般の量子コンピュータシミュレータと違い、メモリをほとんど使いません。
Pythonのbool型やリストがどれくらいメモリを食うかは詳しくないのですが、100万程度なら、メモリ使用量としては全然余裕なのではないでしょうか。

## ゲートと測定
```py
    def gate_x(self, gate, ctx):
        bits = ctx.bits
        for idx in gate.target_iter(len(bits)):
            bits[idx] = not bits[idx]
        return ctx

    def gate_cx(self, gate, ctx):
        bits = ctx.bits
        for (c, t) in gate.control_target_iter(len(bits)):
            if bits[c]:
                bits[t] = not bits[t]
        return ctx

    def gate_ccx(self, gate, ctx):
        bits = ctx.bits
        c0, c1, t = gate.targets
        if bits[c0] and bits[c1]:
            bits[t] = not bits[t]
        return ctx
```

Xゲートはビットを反転します。CX (CNOT)ゲートは、もしcontrolビットが1ならばtargetビットを反転して、そうでなければ何もしません。CCX (Toffoli)ゲートは、もしc0, c1ビットがともに1ならばtargetビットを反転して、そうでなければ何もしません。
プログラミング初心者が生まれて初めてif文を書いたときのような、ごくごく素直なコードです。

```py
    def gate_measure(self, gate, ctx):
        bits = ctx.bits
        meas = ctx.measured
        for idx in gate.target_iter(len(bits)):
            meas[idx] = bits[idx]
        return ctx
```

測定も極めて単純で、単に、測定されたビットを、`ctx.measured`にコピーしているだけです。
古典ビットなので、測定しても状態が壊れることはありません。

以上で、バックエンドの実装は終了です。

# 加算器の実装
加算器の実装は「[元号が平成か令和かを判定する量子回路組んでみた](https://qiita.com/gyu-don/items/4b72dd31e0212ea0721a)」で作ったものを流用しています。

https://arxiv.org/pdf/quant-ph/9511018.pdf に書かれているものを素直に実装した形です。
この論文のFigure 2のようにやっています。
![Fig2](https://qiita-image-store.s3.amazonaws.com/0/88256/20f92c4a-14ce-a2fe-38fa-afaed4ff2e26.png)

コードについては[こちら](https://github.com/gyu-don/blueqat-classicalbit-backend/blob/master/blueqat_classicalbit_backend/__main__.py)に乗せてますので、ご参照ください。

# まとめ
今回は、古典ビットをシミュレートするバックエンドを実装し、Blueqat上で動かしてみました。
結果、量子コンピュータのシミュレータなら、膨大すぎるメモリが必要な128ビット加算器を、ご家庭のパソコンでらくらく動かすことができました。

今回作ったコードは
https://github.com/gyu-don/blueqat-classicalbit-backend
に置いています。