[レビュー]HOBO＋QAOAで巡回セールスマン問題の必要量子ビットがN*logNに！10都市なら100から40量子ビットに激減！

前回はQUBOならぬHOBOをみました。巡回セールスマンにHOBOを適用することで、必要量子ビット数をN^2からN*logNに減らせる方法について確認します！

https://blueqat.com/yuichiro_minato2/5108c201-23c6-4522-97b1-f630521f9559
こちらです！
Space-efficient binary optimization for variational quantum computing

通常TSPを解くにはN^2だけ量子ビットが必要です。都市数と回る順序のmatrixを使ってone-hotエンコーディングをしますが、ここではhigh-orderエンコーディングでかなり量子ビット数を減らせるようになりました！そのため、順位を表現する量子ビットが減りNからlogNですみます。
いままで、は4都市の場合には16量子ビットを使って、該当する順序を1、その他を0にするエンコーディングを行っていました。

\ 1 2 3 4
A 1 0 0 0
B 0 0 1 0
C 0 1 0 0
D 0 0 0 1

今回は普通に自然数を使ってエンコーディングしますので、

A 0 0
B 0 1
C 1 0
D 1 1

なんと8量子ビットですみます！

しかし、そこへいたる道はまだ長そうですので、今回は概観してみます。まずはTSPを8量子ビットで実行するためには条件があります。ABCDの4都市の順序をエンコードしますが、順番なので、0123の4つの数字をエンコードする必要があります。これは、00,01,10,11とできます。同じ数字が二回出ないような条件は量子もつれを用いたり、ソフト制約を用いた方法があります。

また、距離は単純にコスト関数なので、都市間の距離を用いて求めることができます。今回の計算は結構重たいので、コスト関数はいったんわきに置いておいて、4都市の順番のエンコードが重ならない条件を決めてみます。

0123ですが、Aの0は固定でいいので、実際は123がキチンとエンコードされて探索されればよいと考えます。mixerはXを利用してみます。

from blueqat import vqe
from blueqat import Circuit
from blueqat.pauli import *
from blueqat.pauli import qubo_bit as q

xA = 0
xB = 2*q(2) + q(3)
xC = 2*q(4) + q(5)
xD = 2*q(6) + q(7)

#dAB = dCD = 5
#dAC = dAD = dBC = dBD = 1
#hamiltonian = dAB*(4-(xA-xB)**2)/3 + dAC*(4-(xA-xC)**2)/3 + dAD*(4-(xA-xD)**2)/3 + dBC*(4-(xB-xC)**2)/3 + dBD*(4-(xB-xD)**2)/3 + dCD*(4-(xC-xD)**2)/3

hamiltonian = (xB*xC*xD-6)**2
step = 4

result = vqe.Vqe(vqe.QaoaAnsatz(hamiltonian, step)).run()
print(result.most_common(4))

(((0, 0, 1, 1, 1, 0, 0, 1), 0.015998139395079478), ((1, 0, 1, 1, 1, 0, 0, 1), 0.015998139395079478), ((0, 1, 1, 1, 1, 0, 0, 1), 0.015998139395079478), ((1, 1, 1, 1, 1, 0, 0, 1), 0.015998139395079478))

このように、少ない量子ビットでエンコードをHOBOにすることで、QUBOで必要だった量子ビット数を減らすことができました。なかなか条件を満たすものを作るのは大変そうですが、量子ビットの多体計算が量子ゲートではシミュレートできるので、HOBOを使うことでdepthは増えますが、量子ビット数を減らせることが分かりました（量子アニーリングマシンだとHOBOをQUBO分解するときに量子ビットが増えるためできない）。TSPではこれまでN^2必要だった量子ビット数がN*logNとなります。10都市のTSPでは、100量子ビットから40量子ビットに減ることになります。まだ計算に課題はあるものの、mixerを工夫するなどもつれの併用によって部分空間の探索にTSPを押し込めることが以前よりも容易になりそうです。

課題はdepthが深くなるので計算時間が増えます。高速に計算できる手法などを今後は考察したいと思います。以上です。