common.title
Cloud support

Nobisuke

Dekisugi

RAG

autoQAOA
RAG for dev
Fortune telling app
Annealing
DEEPSCORE
Translation
Overview
Service overview
Terms of service

Privacy policy

Contact
Research
Sign in
Sign up
common.title

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

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を上書きするなどして減らす必要もありそうです。しかし回路も実行できましたのでいったんこれで。

© 2024, blueqat Inc. All rights reserved