Nobisuke
Dekisugi
RAG
Privacy policy
2021/07/06 03:09
1
離散最適化を考える際に、巡回セールスマン問題をSAなどで解く際には2-opt法と呼ばれる2つの都市を入れ替える方法があると思います。今回はこの2-opt法を量子コンピュータで実行できないかと考えてみました。
こちらは2つの都市を入れ替えて距離を評価します。明示的に都市を入れ替えるという操作をイジングモデルを導入した量子シミュレーションで導入するにはちょっとしたコツが必要です。
上記ではABCDの順番で巡回することを考えると、イジングモデルでは都市の数Nに対してN*Nの量子ビット数を使って、下記のように実装ができます。2-optを実現するには、BとCの順番を入れ替えるために、4量子ビットを入れ替える必要があります。
上記の状態を量子回路で表現すると、
|0> --X--RXX--RYY--
| |
|0> -----RXX--RYY--
|0> -----RXX--RYY--
| |
|0> --X--RXX--RYY--
このように、初期状態をXでつくってから、量子ビットをswapすることで実現できます。
Copy from blueqat import Circuit import math Circuit(4).x[0,3].m[:].run(shots=100)
Counter({'1001': 100})
まずは1001の状態を作りました。次にswapして、0110になるかどうかみてみます。
Copy Circuit(4).x[0,3].rxx(math.pi/2)[0,1].rxx(math.pi/2)[2,3].ryy(math.pi/2)[0,1].ryy(math.pi/2)[2,3].m[:].run(shots=100)
Counter({'0110': 100})
2-optを実現できました。4量子ビットをflipさせることで、イジングモデルでも都市の入れ替えができました。
IonQの実機でもやってみましょう。
Copy from bqcloud import load_api from bqcloud import Device #apiキーを読み込みます api = load_api() task = api.execute(Circuit(4).x[0,3].rxx(math.pi/2)[0,1].rxx(math.pi/2)[2,3].ryy(math.pi/2)[0,1].ryy(math.pi/2)[2,3], Device.IonQDevice, 100)
Copy #タスクが処理されました print(task.status())
Status.QUEUED
Copy #結果を表示してみます result = task.wait(timeout=3600) if result: print(result.shots()) else: print("timeout")
Counter({'0110': 80, '0010': 7, '0100': 4, '0101': 4, '1110': 2, '1010': 1, '1001': 1, '0111': 1})
多少のばらつきありますが、IonQの実機でも実行できました。
実はここからが本番です。量子コンピュータの特性を生かしたハード制約をやってみましょう。上記は4量子ビットのflipを行いました。4量子ビットある場合の量子ビットの取りうる値は、
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
この16通りですが、明らかに今回の2-optはBとCの入れ替えだけを考える場合には、
0110
1001
この2パターンだけを考えればいいことになります。これは量子もつれにほかなりません。先ほどの回路は1001のパターンを入れ替えただけでした。それだけでは、量子コンピュータの重ね合わせやもつれをうまくつかえていません。2-optを量子コンピュータでうまく使うにはもつれを活用し、2通りのflipを同時に実現することができます。1001を0110にflipするだけでなく、0110を1001にflipする状態を同時に持つことができます。
Copy Circuit(4).x[0,3].rxx(math.pi/2)[0,1].cx[1,2].cx[2,3].m[:].run(shots=100)
Counter({'1001': 51, '0110': 49})
Copy task2 = api.execute(Circuit(4).x[0,3].rxx(math.pi/2)[0,1].cx[1,2].cx[2,3], Device.IonQDevice, 100)
Copy #結果を表示してみます result2 = task2.wait(timeout=3600) if result2: print(result2.shots()) else: print("timeout")
Counter({'0110': 52, '1001': 40, '0101': 3, '1000': 2, '1110': 2, '1011': 1})
もつれができた状態で同様に2量子ビットを2-optします。
Copy Circuit(4).x[0,3].rxx(math.pi/2)[0,1].cx[1,2].cx[2,3].rxx(math.pi/2)[0,1].rxx(math.pi/2)[2,3].ryy(math.pi/2)[0,1].ryy(math.pi/2)[2,3].m[:].run(shots=100)
Counter({'0110': 53, '1001': 47})
わかりづらいですが、flipすると2つの状態が同時にflipします。IonQの実機でも行ってみます。
Copy task3 = api.execute(Circuit(4).x[0,3].rxx(math.pi/2)[0,1].cx[1,2].cx[2,3].rxx(math.pi/2)[0,1].rxx(math.pi/2)[2,3].ryy(math.pi/2)[0,1].ryy(math.pi/2)[2,3], Device.IonQDevice, 100)
Copy #結果を表示してみます result3 = task3.wait(timeout=3600) if result3: print(result3.shots()) else: print("timeout")
Counter({'1001': 54, '0110': 33, '0101': 4, '0010': 2, '1010': 2, '1000': 1, '1110': 1, '1101': 1, '1011': 1, '0111': 1})
実機でもできました。これで量子もつれを活用して、2-opt法を使う準備ができましたね。実際にこれを組合せ最適化に応用するのは難解になるのでちょっとずつ説明します。今回は以上です。
© 2024, blueqat Inc. All rights reserved