はじめに
量子コンピューター Advent Calendar 2020の8日目です．
量子アニーリングでソートアルゴリズムを実装するなら，こうかなというのを作ってみました．
ソースコード
Quantum Sort
量子コンピュータを用いたソートアルゴリズムについては，先行研究がいくつかあるようです．
ただ，量子アニーリングで解く試みは見受けられなかったので，今回試してみました．
ColabでWeb上から実行可能です．こちらに沿って説明していきます．（URL先のColabマークから実行できます）
問題設定
min_number以上，max_number以下の整数をnum_number個だけ用意して，これを降順に並び替えることを考えます．
import random
num_numbers = 4
min_number = 1
max_number = 100
numbers = [random.randint(min_number, max_number) for _ in range(num_numbers)]
print("index : numbers")
for i, x in enumerate(numbers):
print(i, " : ", x)
ここでは，1以上100以下の整数をランダムに，4個用意しています．
index : numbers
0 : 57
1 : 87
2 : 63
3 : 96
量子ビットを定義
$q^v_i$ を numbers[v] が i 番目にあるかどうかを表す量子ビットとして定義します．
例えば，$q^0_0$ は numbers[0] = 57 が 0 番目にあることを意味します．
今回は，この $q^v_i$ すべてが，適切にソートされた状態になるように，量子ビット同士に相互作用を与えていきます．
具体的には，隣り合う整数の差が最小になる時，エネルギー最小となるようにQUBOを作ります．
差分行列の生成
まず，生成した整数の差分行列 $D$ を生成します．
diffs = {
(v, w) : abs(numbers[w] - numbers[v])
for v in range(num_numbers)
for w in range(v+1, num_numbers)
}
print("pair : difference")
for pair, diff in diffs.items():
print(pair, " : ", diff)
差分行列は，整数列のインデックスのペアをキーにとって，次のように表されます．
(0, 1)と(1, 0)のような，(i, j)成分を入れ替えたペアの差分は同じなので，i < j となるペアのみを用います．
pair : difference
(0, 1) : 30
(0, 2) : 6
(0, 3) : 39
(1, 2) : 24
(1, 3) : 9
(2, 3) : 33
隣接行列を生成
今，関係性を表現したいのは，並び替えた時，隣り合う量子ビット同士に対してなので，以下のような無向グラフの隣接行列 $N$ を考えます．
neighbors = [
(i, j)
for i in range(num_numbers)
for j in range(num_numbers)
if abs(j-i) == 1
]
print("neighbor")
for pair in neighbors:
print(pair)
隣接行列の成分は，0か1ですが，隣接していることを表すのは，値が1の時だけなので，この状態のみをタプルでリストに追加しています．
neighbor
(0, 1)
(1, 0)
(1, 2)
(2, 1)
(2, 3)
(3, 2)
ハミルトニアン
目的関数を最小化することで，隣り合う整数の差が最小になります．$H_{objective} = \sum_{v<w} D_{vw}\sum_{\{(i, j)|N_{ij}=1\}}q^v_iq^w_j$
これだけだと，ある整数が，0番目にも1番目にもいるような状態が許されてしまうので，これを防ぐ制約関数を設定します．$H_{constraint} = \sum_{v=0}^{N-1}(1-\sum_{i=0}^{N-1}q^v_i)^2 + \sum_{i=0}^N (1-\sum_{v=0}^{N-1}q^v_i)^2$
目的関数と制約関数をラグランジュの未定乗数法でつなぎます．$H = H_{objective} + \lambda H_{constraint}$
ラグランジュ未定乗数の設定
経験則で，以下のように設定しました．
max_number = max(numbers)
lam = max_number/2
アニーリング
SA（シミュレーティド・アニーリング）で試してみます．
import neal
sampler = neal.SimulatedAnnealingSampler()
# QUBOを渡して，SAを10回実行
response = sampler.sample_qubo(qubo, num_reads=10)
# 得られた回のうち，エネルギー最小のものをsolutionsとして取得
solutions = [
state.tolist()
for i, state in enumerate(response.record['sample'])
if response.record['energy'][i] == min(response.record['energy'])
]
for sol in solutions:
print(sol)
得られた解のうち，エネルギー最小のものを出力します．
[1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0]
重複している解があるので，実際の解を出力してみます．
selected_sols = []
for sol in solutions:
if not sol in selected_sols:
selected_sols.append(sol)
for sol in selected_sols:
print(sol)
[1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0]
解は，2種類ありました．
それぞれ，(0, 2, 1, 3), (3, 1, 2, 0)の並び順になっています．
これを整数列に直すと，それぞれ，(57, 63, 87, 96), (96, 87, 63, 57)です．
昇順と降順に並び替えられていますね．
Qsort の開発
最後に，これらをまとめてQsortの開発を行いました．
Qsortは，https://github.com/kumagaimasahito/Qsort からインストールできます．
pip install git+https://github.com/kumagaimasahito/Qsort.git
実験用にランダムに整数を設定するメソッドを用意しました．また，set_numbers(numbers)メソッドを使えば，好きな整数列を設定することもできます．
from Qsort import Qsort
qsort = Qsort()
qsort.set_random_numbers(
num_numbers = 4,
min_numbers = 1,
max_numbers = 100
)
index : numbers
0 : 95
1 : 75
2 : 96
3 : 9
SAでQsortを解く場合は，次のように実行します．
sorted_numbers = qsort.SASolver()
print(sorted_numbers)
[96, 95, 75, 9]
QA（量子アニーリング）で解く場合は，次のように実行します．
sorted_numbers = qsort.QASolver(
token = "Your API Token",
solver = "Advantage_system1.1",
endpoint = "https://cloud.dwavesys.com/sapi/"
)
[96, 95, 75, 9]
きちんと，ソートができました！
＊ただし，DWave Advantage システムで試した時はエラーで止まってしまいました．何が原因かわかる方がいたら教えていただきたいです．
まとめ
量子アニーリングを用いたソートアルゴリズム Quantum Sort を自分なりに実装し，Qsortの開発を行いました．
急いで作ったので荒削りですが，時間がある時にアップデートしていきたいと思います．
あと，個人的には量子ボゴソートを作ってみたいです．いつかやるかもしれません．
Future Work
- 計算量の導出
- 昇順を防ぐ制約関数の追加
- 量子ボゴソート