Quantum Sort 作ってみた【量子ソート】

# はじめに

[量子コンピューター Advent Calendar 2020](https://qiita.com/advent-calendar/2020/quantum)の8日目です．

量子アニーリングでソートアルゴリズムを実装するなら，こうかなというのを作ってみました．
[ソースコード](https://github.com/kumagaimasahito/Qsort)

# Quantum Sort
量子コンピュータを用いたソートアルゴリズムについては，先行研究がいくつかあるようです．
ただ，量子アニーリングで解く試みは見受けられなかったので，今回試してみました．
ColabでWeb上から実行可能です．こちらに沿って説明していきます．（[URL先のColabマークから実行できます](https://github.com/kumagaimasahito/Qsort/blob/main/quantum-sort.ipynb)）

## 問題設定
min_number以上，max_number以下の整数をnum_number個だけ用意して，これを降順に並び替えることを考えます．

```python

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$ を生成します．

```python

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$ を考えます．
![neighbor.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/496581/57b66a2e-e984-5219-77c2-55cc8a49df42.png)

```python

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


### ラグランジュ未定乗数の設定
経験則で，以下のように設定しました．

```python
max_number = max(numbers)
lam = max_number/2
```

## アニーリング
SA（シミュレーティド・アニーリング）で試してみます．

```python

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]
```

重複している解があるので，実際の解を出力してみます．

```python

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 からインストールできます．

```shell
pip install git+https://github.com/kumagaimasahito/Qsort.git
```

実験用にランダムに整数を設定するメソッドを用意しました．また，set_numbers(numbers)メソッドを使えば，好きな整数列を設定することもできます．

```python
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を解く場合は，次のように実行します．

```python
sorted_numbers = qsort.SASolver()
print(sorted_numbers)
```

```
[96, 95, 75, 9]
```

QA（量子アニーリング）で解く場合は，次のように実行します．

```python
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
- 計算量の導出
- 昇順を防ぐ制約関数の追加
- 量子ボゴソート