blueqatで積の計算

## この記事に関して
ここではpythonライブラリのblueqatを用いて量子プログラミングを行っていこうと思います。
内容は[公式のチュートリアル](https://github.com/Blueqat/Blueqat-tutorials/tree/master/tutorial-ja)を元に作成しています。
今回は2進数の積を実装していきます。

## 乗算器

ビットは 0, 1 をとるので 2進数の掛け算を考えます。
組み合わせは

``` math
0 \times 0 = 0, \ 0 \times 1 = 0, \ 1 \times 0 = 0, \ 1 \times 1 = 1
```
となります。
これは[加算器の1桁目](https://qiita.com/KeiichiroHiga/items/239aef7694842056ce6e#%E5%9B%9E%E8%B7%AF%E3%81%AE%E4%BD%9C%E6%88%901%E6%A1%81%E7%9B%AE)と同じCCXゲートで表せます。

#### 実装
[量子の重ね合わせ](https://qiita.com/KeiichiroHiga/items/239aef7694842056ce6e#%E9%87%8D%E3%81%AD%E5%90%88%E3%82%8F%E3%81%9B%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E5%8A%A0%E7%AE%97%E5%99%A8)を用いて上の4パターンを実装します。

``` python:sample.ipynb
from blueqat import Circuit

c = Circuit().h[0,1].ccx[0,1,2]
c.m[:].run(shots=1000)

結果
Counter({'111': 242, '010': 253, '100': 260, '000': 245})
```
4つのパターンを同時に出力させることができました。

## 乗算器 (2桁×2桁)
次は応用で2桁×2桁の乗算を考えてみます。

組み合わせは

``` math
00 \times 00 = 0000, \ 00 \times 01 = 0000, \ 00 \times 10 = 0000, \ 00 \times 11 = 0000 \\
01 \times 00 = 0000, \ 01 \times 01 = 0001, \ 01 \times 10 = 0010, \ 01 \times 11 = 0011 \\
10 \times 00 = 0000, \ 10 \times 01 = 0010, \ 10 \times 10 = 0100, \ 10 \times 11 = 0110 \\
11 \times 00 = 0000, \ 11 \times 01 = 0011, \ 11 \times 10 = 0110, \ 11 \times 11 = 1001
```
の16通りとなります。

### 考え方
まず試しに 11 × 10 を筆算で考えてみます。

``` math
\hspace{24px} 11 \\
\underline{\times \ \ 10} \\
\hspace{60px} 00 ← 1\\
\hspace{34px} \underline{\ \ \ 11 \ \ } ← 2\\
0110
```
1 と 2 の行を合わせた4回の計算をそれぞれ考えます。
1行目 は 11 × 0 , 2行目は 11 × 1 となります。 
各項4つの計算はそれぞれ 1桁の積でできるので全て CCXで実装できます。

1 と 2 の和に関しては繰り上がりを考えないといけないので[加算器](https://qiita.com/KeiichiroHiga/items/239aef7694842056ce6e#%E5%9B%9E%E8%B7%AF%E3%81%AE%E4%BD%9C%E6%88%90-%E5%85%A8%E4%BD%93)で実装します。

### 回路の作成 (1, 2行目)
今回は 1 行目だけ考えます。
11 × 0 を CCX ゲートを用いて以下の回路を考えます。

``` math
\begin{array}{ccccccc}
\left|1\right> &-&-&-&*&-& \\
\left|1\right> &-&*&-&|&-& \\
\left|0\right> &-&*&-&*&-& \\
&&|&&|&\\
\left|0\right> &-&|&-&X&-&←出力_1 \\
\left|0\right> &-&X&-&-&-&←出力_2 \\
\end{array}
```
上から 2 つのビットは 11 の部分で次の 1 ビットは 0 の部分となります。
出力_1 ,出力_2 は 1 × 0 を表しています。
これで 1 行目が出力されました。
2 行目も同様にしてできます。

#### 実装
上の回路を実装します。

``` python:sample.ipynb
from blueqat import Circuit

c = Circuit().x[0,1].ccx[1,2,4].ccx[0,2,3]
c.m[:].run(shots=1000)

結果
Counter({'11000': 1000})
```
きちんと 00 が出力されました。

### 回路の作成 (1, 2行目の和)
11 × 10 の 1, 2 行目を考えます。
これらの和を以下の回路で表します。

``` math
\begin{array}{ccccccc}
\left|0\right> &-&-&-&*&-&*&-&-&-&-&-&-&-& \\
\left|0\right> &-&*&-&|&-&|&-&-&-&-&-&-&-& \\
\left|1\right> &-&|&-&|&-&|&-&*&-&*&-&-&-& \\
\left|1\right> &-&|&-&|&*&*&-&|&-&|&-&-&-& \\
&&&&&&& \\
\left|0\right> &-&|&-&|&|&|&-&|&-&X&-&*&-&←繰り上がり_1 \\
\left|0\right> &-&|&-&|&|&X&-&|&*&*&-&|&-&←繰り上がり_2 \\
&&&&&&& \\
\left|0\right> &-&|&-&|&|&-&-&|&|&-&-&X&-&←出力_1 \\
\left|0\right> &-&|&-&|&|&-&-&X&X&-&-&-&-&←出力_2 \\
\left|0\right> &-&|&-&X&X&-&-&-&-&-&-&-&-&←出力_3 \\
\left|0\right> &-&X&-&-&-&-&-&-&-&-&-&-&-&←出力_4 \\
\end{array}
```
上の4つには 1行目の 0, 0 と2行目の 1, 1 をそれぞれ入れます。
繰り上がり\_1 は一番上のくらいの繰り上がりの有無を判別します。
繰り上がり\_2 は上から二番目のくらいへの繰り上がりの有無を判別します。
出力は高いくらいから出力\_1, 出力\_2, 出力\_3, 出力\_4 となっています。

下のくらいから考えます。
1\. 1の位はそのままなのでCXで出力\_4 に渡しています。

2\. 次のくらいの値は 1, 2 の該当する値を足した値なのでCXを 2 つ出力\_3 に渡しています。
続けてCCXは該当する値が両方 1 ならば繰り上がりが起こるので繰り上がり\_2 に渡しています。

3\. 次のくらいの値は 2 の該当する値と繰り上がり\_2 を足した値なのでCXを 2 つ出力\_2 に渡しています。
CCXは該当する値が両方 1 ならばさらに繰り上がりが起こるので繰り上がり\_1 に渡しています。

4\. 一番上のくらいは繰り上がった数のみがくるのでCXで繰り上がり\_1 を出力\_1 に渡しています。

#### 実装
上パターンを実装します。

``` python:sample.ipynb
from blueqat import Circuit

c = Circuit().x[2,3]
c.cx[1,9] # 1
c.cx[0,8].cx[3,8].ccx[0,3,5] # 2
c.cx[2,7].cx[5,7].ccx[2,5,4] # 3
c.cx[4,6] # 4
c.m[:].run(shots=1000)

結果
Counter({'0011000110': 1000})
```
最後の4桁を見ると答えが取れたことがわかります。

### 回路の作成 (全体)
11 × 10 を計算します。
上の2つの回路を組み合わせて以下の回路を作ります。

``` math
\begin{array}{ccccccc}
\left|1\right> &-&*&-&*&-&-&-&-&-&-&-&-&-&-& \\
\left|1\right> &*&|&*&|&-&-&-&-&-&-&-&-&-&-& \\
\left|1\right> &|&|&*&*&-&-&-&-&-&-&-&-&-&-& \\
\left|0\right> &*&*&|&|&-&-&-&-&-&-&-&-&-&-& \\
&&&&&&& \\
\left|0\right> &|&X&|&|&-&-&*&-&*&-&-&-&-&-&←1 \\
\left|0\right> &X&-&|&|&-&*&|&-&|&-&-&-&-&-&←1 \\
\left|0\right> &-&-&|&X&-&|&|&-&|&*&-&*&-&-&←2 \\
\left|0\right> &-&-&X&-&-&|&|&*&*&|&-&|&-&-&←2 \\
&&&&&&& \\
&&&&&\left|0\right>&|&|&|&|&|&-&X&*&-&←繰り上がり_1 \\
&&&&&\left|0\right>&|&|&|&X&|&*&*&|&-&←繰り上がり_2 \\
&&&&&&& \\
&&&&&\left|0\right>&|&|&|&-&|&|&-&X&-&←出力_1 \\
&&&&&\left|0\right>&|&|&|&-&X&X&-&-&-&←出力_2 \\
&&&&&\left|0\right>&|&X&X&-&-&-&-&-&-&←出力_3 \\
&&&&&\left|0\right>&X&-&-&-&-&-&-&-&-&←出力_4 \\
\end{array}
```
左上の操作は 1, 2 行目を計算しています。
右下は 1, 2 行目の和を計算しています。

#### 実装
上パターンを実装します。

``` python:sample.ipynb
from blueqat import Circuit

c = Circuit().x[0,1,2]

# 左上
c.ccx[1,3,5].ccx[0,3,4].ccx[1,2,7].ccx[0,2,6]

# 右下
c.cx[4,13].cx[4,12].cx[7,12].ccx[4,7,9].cx[6,11].cx[9,11].ccx[6,9,8].cx[8,10]

c.m[:].run(shots=1000)

結果
Counter({'11100011000110': 1000})
```
最後の4桁を見ると答えが取れたことがわかります。

## まとめ
今回はblueqatを用いて2進数の積を実装しました。
次回は量子テレポーションをblueqatで実装してみます。