【乗算】量子ゲートでの掛け算回路の実装

Yuichiro Minato

2021/01/16 06:33

#量子ゲート

はじめに

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

２進数の掛け算について

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

00=0 01=0 10=0 11=1

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

例題

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

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

0110=0010。つまり12=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コード

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


from blueqat import Circuit
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})

Counter({'00000000000000': 100})


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

Counter({'11100000001000': 100})


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

Counter({'01010100000100': 100})


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

Counter({'10001010000100': 100})


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

Counter({'00011001000010': 100})


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

Counter({'10011011000110': 100})


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

Counter({'01011101000110': 100})


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

Counter({'11111111111001': 100})

まとめ

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