ANDゲートなどの古典論理回路を量子コンピュータのイジング最適化で解いてみる


はじめに

汎用計算機である量子コンピュータでは様々な論理回路を再現できますが、今回は王道ではなくて組合せ最適化を使った古典論理回路の解法をみてみたいと思います。


例題

バイナリの掛け算の論理回路をイジングつかって実現したいと思います。今回は4*3=12をみてみます。


論理回路

使用するのは、いくつかの論理回路ですが、まずはAND回路を含む基本的なものをみてみます。バイナリ値の掛け算で3*4は11*100と表現されます。

  100

* 11
-----
100
100
-----
1100

この際に実現したいのは、

1、100*1で100を再現するAND回路。こちらは11なので、両方の位に必要

2、100と100を足し合わせるための回路。0のくらいはそのまま落とせばOK。

3、桁上がりを保存して足す回路。桁上がりを想定する必要があります。


図に落としてみる

こんな感じ。

895ab4ae6db7fc4e1f2d007d8c9755ef-2.jpg

最初にAND回路で掛け合わせます。次に下のくらいから順番に足していきながら桁上がりを上のくらいの足し算に足し合わせていき、一番上の回路が決まります。


もっとイジングぽくしてみる

上記を頑張って量子ビットで表記した結果。。。

d1be809e8f4f3ac23ba718d991f6af54-2.jpg

こうなりました!39量子ビット使っています!

一番左は入力の3と4に対応。左から二列目はAND回路をイジングで3量子ビットに分解しました。そして桁上がりをしながら3列目は左上から順番に桁上がりを導入した加算器です。

AND回路が6つ。桁上がり対策の特殊回路が3つですね。


もっと減らすと

111.jpg

こんな感じに同じ量子ビットはつけられます。


ANDゲートを例に解いてみる

では、今回は部分的にANDゲートを例にとって解いてみます。


AND回路とは?

AND回路は2つのビットがあって、両方とも1の時に1を出力し、それ以外は0を出力します。

0 0 >>> 0

0 1 >>> 0
1 0 >>> 0
1 1 >>> 1

今回これを最小値問題に落とし込んでみます。

コスト関数

コスト関数を考えてみます。 3量子ビットを考えてみて、一般化したコスト関数を準備します。

E=aA+bB+cC+dAB+eBC+fCA+gABC

を考えた上で、ABに入力ビット。Cに出力ビットを割り当てます。ここで、上記のANDゲートの条件を満たした時だけコスト関数が低くなるように係数を探せばいいことになります。

A B C E(コスト関数)

0 0 0 0
0 1 0 0
1 0 0 0
1 1 1 0
-------
0 0 1 x
0 1 1 y
1 1 0 z
1 0 1 k

まず上から順番にどんどん代入していきます。

#[A,B,C] = [0,0,0]

E = 0

#[A,B,C] = [0,1,0]
E = b = 0

#[A,B,C] = [1,0,0]
E = a = 0

#[A,B,C] = [1,1,1]
E = c+d+e+f+g = 0

ここまでは正解組です。次からはコストがこれよりも高くなる条件を設定します。

#[A,B,C] = [0,0,1]

E = c = x > 0

#[A,B,C] = [0,1,1]
E = c + e = y >0

#[A,B,C] = [1,1,0]
E = d = z >0

#[A,B,C] = [1,0,1]
E = c + f = k >0

これを満たす条件を頑張って探すと、

c=1,e=1,d=1,f=1,g=-4

が見つかります。これを代入するとコスト関数が求まります。

E = C + AB + BC + CA - 4ABC

これがANDゲートのコスト関数です。早速これを使って解いてみましょう。

QAOAで求める

from blueqat import vqe

from blueqat.pauli import qubo_bit as q

hami = q(2)+q(0)*q(1)+q(1)*q(2)+q(2)*q(0)-4*q(0)*q(1)*q(2)

result = vqe.Vqe(vqe.QaoaAnsatz(hami,4)).run()
print(result.most_common(12))

#=>
(((0, 0, 0), 0.519727769221865), ((1, 1, 1), 0.23719281758252192), ((0, 1, 0), 0.11967601213486054), ((1, 0, 0), 0.1196760121348605), ((0, 0, 1), 0.0027571549552323237), ((1, 1, 0), 0.0006430030415655319), ((1, 0, 1), 0.00016361546454752971), ((0, 1, 1), 0.00016361546454752736))

きちんと求めたい値の000,111,010,100が出てきました。確率振幅も十分です。

解いてみる

1つだけやってみます。A=1,B=0で入力をしてCを求めてみるAND回路をしてみます。

この際には-1*q(0)+q(1)を加えてみます。これによってA=1,B=0に固定できます。

hami1 = -1*q(0)+q(1)

hami = q(2)+q(0)*q(1)+q(1)*q(2)+q(2)*q(0)-4*q(0)*q(1)*q(2)

result = vqe.Vqe(vqe.QaoaAnsatz(hami1+hami,4)).run()
print(result.most_common(12))

#=>
(((1, 0, 0), 0.9193795158893359), ((1, 1, 1), 0.03156160130462393), ((0, 0, 0), 0.02058110630291014), ((1, 1, 0), 0.006777171223222024), ((1, 0, 1), 0.006777171223222019), ((0, 1, 0), 0.006257773121487779), ((0, 0, 1), 0.006257773121487756), ((0, 1, 1), 0.0024078878137108292))

高い確率できちんと100が出てきました。これにより10の入力で、出力0を得ることができました。


D-Waveで実行

D-Waveは現在無料時間が設定されており個人で利用することができます。

https://cloud.dwavesys.com/leap/login/?next=/leap/

1111.png


簡単にクリックで実行して試せる。

試すことができます。プログラミングなしで実行できます。

Demo-1-Congratulations-D-Wave-Leap.png