【乗算】量子ゲートでの掛け算回路の実装について考えてみる。


はじめに

足し算引き算はたくさんありますが、掛け算があまり出てきません。具体的な実装もあまりみないのでやってみます。簡単な回路から今後に一般化していきます。足し算引き算は下記にまとめてあります。


2進数の掛け算について

考えてみましたが、シンプルです。2つの数をくらいごとにかけてずらして足し合わせます。その際にキャリービットとして桁上がりを考慮します。

0*0=0

0*1=0
1*0=0
1*1=1

つまり、11のときに1となる回路を作れば良さそうです。これはccx(toffoli)なのでなんとかなりそうです。あとは各くらいを足し合わせれば大丈夫でしょう。


例題

習うより慣れろでいきます。まずは、1*2=?をときます。2は2進数で10ですので、

    01

* 10
-------
00
01
-------
0
0
-------
0010

01*10=0010。つまり1*2=2となります。


では、実装へ

僕は論理回路博士ではないので、より効率的な回路を思いついた人はぜひ発表してくださいませ。まずは2進数の数を2つ用意します。a*bを考えますが、aの0のくらいとaの2のくらいを用意して、それぞれa0とa2とします。bも同様です。

今回最終的に実現するのは|a,b,x> => |a,b,a*b>ととりあえず目標を置いてみます。求めたいのはx0,x2,x4,x8です。cは途中の計算用のビット。zは桁上がりビットを想定します。

a0  0--

b0 0--
c0 0--
a2 0--
b2 0--
c21 0--
c22 0--
c4 0--
z4 0--
z8 0--

x0 0--
x2 0--
x4 0--
x8 0--


まずは掛け算

簡単な桁の掛け算はCCXでできました。まずは、途中の計算用のビットに計算結果を格納していきます。

a0  0--*---*---

b0 0--*-*-|---
c0 0--X-|-|---
a2 0----*-|-*-
b2 0----|-*-*-
c21 0----X-|-|-
c22 0------X-|-
c4 0--------X-
z4 0----------
z8 0----------

x0 0----------
x2 0----------
x4 0----------
x8 0----------

この時点で結構大変そう。。。


桁上がりを実装

実装します。桁上がりビットはz4とz8があります。

a0  0--*---*-------

b0 0--*-*-|-------
c0 0--X-|-|-------
a2 0----*-|-*-----
b2 0----|-*-*-----
c21 0----X-|-|-*---
c22 0------X-|-*---
c4 0--------X-|-*-
z4 0----------X-*-
z8 0------------X-

x0 0--------------
x2 0--------------
x4 0--------------
x8 0--------------


全部足し合わせる

桁を足し合わせます。足し合わせはCXを使うことでできます。

#0  a0  0--*---*-------------------

#1 b0 0--*-*-|-------------------
#2 c0 0--X-|-|-------*-----------
#3 a2 0----*-|-*-----|-----------
#4 b2 0----|-*-*-----|-----------
#5 c21 0----X-|-|-*---|-*---------
#6 c22 0------X-|-*---|-|-*-------
#7 c4 0--------X-|-*-|-|-|-*-----
#8 z4 0----------X-*-|-|-|-|-*---
#9 z8 0------------X-|-|-|-|-|-*-
| | | | | |
#10 x0 0--------------X-|-|-|-|-|-
#11 x2 0----------------X-X-|-|-|-
#12 x4 0--------------------X-X-|-
#13 x8 0------------------------X-

みた感じもっとシンプルにできそう(量子ビットを節約できそう)ですが、今回はこれで。早速コードに落として挙動を見てみます。


Blueqatコード

こちらがコードです。上記の回路をただ実装しただけです。

C1 = Circuit().ccx[0,1,2].ccx[1,3,5].ccx[0,4,6].ccx[3,4,7].ccx[5,6,8].ccx[7,8,9].cx[2,10].cx[5,11].cx[6,11].cx[7,12].cx[8,12].cx[9,13] 

(ここにデータ入力 +C1).m[:].run(shots=100)
実際に、ちなみに桁の読み方は後ろから4桁を順番に読みます。

#00 * 00 = 0000
(Circuit() + C1).m[:].run(shots=100)
Counter({'00000000000000': 100})

#01 * 01 = 0001
(Circuit().x[0].x[1] + C1).m[:].run(shots=100)
Counter({'11100000001000': 100})

#10 * 01 = 0010
(Circuit().x[3].x[1] + C1).m[:].run(shots=100)
Counter({'01010100000100': 100})

#01 * 10 = 0010
(Circuit().x[0].x[4] + C1).m[:].run(shots=100)
Counter({'10001010000100': 100})

#10 * 10 = 0100
(Circuit().x[3].x[4] + C1).m[:].run(shots=100)
Counter({'00011001000010': 100})

#11 * 10 = 0110
(Circuit().x[0].x[3].x[4] + C1).m[:].run(shots=100)
Counter({'10011011000110': 100})

#10 * 11 = 0110
(Circuit().x[1].x[3].x[4] + C1).m[:].run(shots=100)
Counter({'01011101000110': 100})

#11 * 11 = 1001
(Circuit().x[0].x[1].x[3].x[4] + C1).m[:].run(shots=100)
Counter({'11111111111001': 100})


まとめ

結構量子ビットを消費してしまいましたので、工夫してbを上書きするなどして減らす必要もありそうです。しかし回路も実行できましたのでいったんこれで。