全結合イオントラップ量子コンピュータによる組合せ最適化における量子もつれと2-opt法の実装

離散最適化を考える際に、巡回セールスマン問題をSAなどで解く際には2-opt法と呼ばれる２つの都市を入れ替える方法があると思います。今回はこの2-opt法を量子コンピュータで実行できないかと考えてみました。

2-opt法

こちらは２つの都市を入れ替えて距離を評価します。明示的に都市を入れ替えるという操作をイジングモデルを導入した量子シミュレーションで導入するにはちょっとしたコツが必要です。
./img/210706opt3.jpg
上記ではABCDの順番で巡回することを考えると、イジングモデルでは都市の数Nに対してN*Nの量子ビット数を使って、下記のように実装ができます。2-optを実現するには、BとCの順番を入れ替えるために、4量子ビットを入れ替える必要があります。
./img/210706opt2.jpg
上記の状態を量子回路で表現すると、

|0> --X--RXX--RYY-- 
         |    |
|0> -----RXX--RYY--

|0> -----RXX--RYY--
         |    |
|0> --X--RXX--RYY--

このように、初期状態をXでつくってから、量子ビットをswapすることで実現できます。

from blueqat import Circuit
import math

Circuit(4).x[0,3].m[:].run(shots=100)

Counter({'1001': 100})

まずは1001の状態を作りました。次にswapして、0110になるかどうかみてみます。

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の実機でもやってみましょう。

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)

#タスクが処理されました
print(task.status())

Status.QUEUED

#結果を表示してみます
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量子ビットある場合の量子ビットの取りうる値は、

この16通りですが、明らかに今回の2-optはBとCの入れ替えだけを考える場合には、

0110
1001

この２パターンだけを考えればいいことになります。これは量子もつれにほかなりません。先ほどの回路は1001のパターンを入れ替えただけでした。それだけでは、量子コンピュータの重ね合わせやもつれをうまくつかえていません。2-optを量子コンピュータでうまく使うにはもつれを活用し、2通りのflipを同時に実現することができます。1001を0110にflipするだけでなく、0110を1001にflipする状態を同時に持つことができます。

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})

task2 = api.execute(Circuit(4).x[0,3].rxx(math.pi/2)[0,1].cx[1,2].cx[2,3], Device.IonQDevice, 100)

#結果を表示してみます
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します。

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の実機でも行ってみます。

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)

#結果を表示してみます
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法を使う準備ができましたね。実際にこれを組合せ最適化に応用するのは難解になるのでちょっとずつ説明します。今回は以上です。

全結合イオントラップ量子コンピュータによる組合せ最適化における量子もつれと2-opt法の実装

Yuichiro Minato

2-opt法