21-37. QUBOアニーリング「TYTAN」に高速GPUサンプラーが追加

量子コンピュータ

2024/02/12

やること
TYTANについて
ベンチマーク問題
実行マシン
SASamplerで求解（CPU）
ArminSamplerのCPU版で求解
ArminSamplerのGPU版で求解
スコア比較
おわりに

やること

QUBOアニーリングでお世話になっている「TYTAN」パッケージに、なんとGPUサンプラーが追加されました。バージョン0.0.22からです。

その名も「ArminSampler」

待ってください。TYTANのサンプラーには巨人の名前が付けられる慣習のはず。まるでアルミンが巨人になるかのようなネーミングじゃないか。え？（←アニメ１期しか見てない）

アルミンサンプラーの使い方は？どれくらい速いの？彼女はいる？結婚してる？

~~調べてみた結果、公開されていませんでした。いかがでしたか？~~

比較してみました。

TYTANについて

「TYTAN」はOSSのアニーリングSDKです。

GitHub - tytansdk/tytan: Python SDK for large QUBO problems

Python SDK for large QUBO problems. Contribute to tytansdk/tytan development by creating an account on GitHub.

チュートリアル教材はこちら。また、毎週木曜日22時にオンライン勉強会もやっています（2024年2月現在）。

GitHub - tytansdk/tytan_tutorial

Contribute to tytansdk/tytan_tutorial development by creating an account on GitHub.

discordコミュニティもあるので気軽に質問できます。

https://discord.gg/qT5etstPW8

ベンチマーク問題

180量子ビットの生産計画最適化問題（ジョブスケジューリング問題）を用意しました。

5台の機械（単位時間あたりの処理能力1, 1, 2, 2, 3）と36個のタスク（処理時間1, 2, …, 35, 36）があり、最短ですべてのタスクを終わらせる割り振りを見つける問題です。

import time
import numpy as np
from tytan import *

# 機械数
M = 5

# 単位時間あたりの処理能力
machine_power = np.array([1, 1, 2, 2, 3])
print(machine_power)

# タスク数
T = 36

# 各タスクの必要処理量
task = np.arange(1, T + 1)
print(task)

[1 1 2 2 3]
[ 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
 25 26 27 28 29 30 31 32 33 34 35 36]

この問題の最適解（大域解）は74時間で、複数パターンあります。

実行マシン

CPU：Ryzen 5 5600G

GPU：RTX 2070（※ColabのTesla T4より性能は高い）

SASamplerで求解（CPU）

サンプリングが10秒程度で終わるようにパラメータを調整しています。デフォルトの shots=100, T_num=2000 から shots=1000, T_num=4000 に上げています。

#量子ビットを用意
q = symbols_list([M, T], 'q{}_{}')

#制約条件（ワンホット）
H = 0
for i in range(T):
    H += 100 * (sum(q[:, i]) - 1)**2

#コスト（処理時間が74に近い）
for i in range(M):
    H += (sum(task*q[i]) / machine_power[i] - 74)**2

#コンパイル
qubo, offset = Compile(H).get_qubo()
print(f'offset={offset}')

#サンプラー選択
solver = sampler.SASampler(seed=None)

#サンプリング
s = time.time()
result = solver.run(qubo, shots=1000, T_num=4000)
e = time.time()
print(round(e - s, 3), 's')

#結果（上位1件）
for r in result[:1]:
    print(f'Energy={r[1]}, Occurrence={r[2]}')
    arr, subs = Auto_array(r[0]).get_ndarray('q{}_{}')
    print(arr)

    #ワンホット確認
    print(np.sum(arr, axis=0))

    #割り振りを確認
    for i in range(M):
        task_select = task[np.where(arr[i]==1)[0]]
        t = np.sum(task_select) / machine_power[i]
        print(f'機械{i} タスク {task_select} 時間 {t}')

offset=30980.0
11.128 s
Energy=-30977.88888888889, Occurrence=1
[[0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0]
 [0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0]
 [0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0]
 [0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0]
 [1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 1]]
[1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]
機械0 タスク [ 2  8 31 34] 時間 75.0
機械1 タスク [ 4 10 11 17 32] 時間 74.0
機械2 タスク [ 3 14 15 18 19 20 26 33] 時間 74.0
機械3 タスク [ 5  6  7 21 23 25 29 30] 時間 73.0
機械4 タスク [ 1  9 12 13 16 22 24 27 28 35 36] 時間 74.33333333333333

10回中もっとも良かった結果を載せました。最良解のエネルギーは理想値+2.1でした。

ArminSamplerのCPU版で求解

ArminSamplerにはCPUモードとGPUモードがありますが、いずれもpytorchのインストールが必須で、ない場合はこのような警告が出ます。pytorchはTYTANパッケージの標準装備ではないため、別途適当にインストールしてください。

=======================
= A T T E N T I O N ! =
=======================
ArminSampler requires PyTorch installation.
Use "pip install torch" (or others) and ensure
-------
import torch
torch.cuda.is_available()
#torch.backends.mps.is_available() #if Mac
-------
outputs True to set up the environment.

こちらもサンプリングが10秒程度で終わるようにパラメータを調整しています。ArminSampler() はデフォルトで mode=’GPU’ です。shots=2000, T_num=4000 に上げています。

#サンプラー選択
solver = sampler.ArminSampler(seed=None, mode='CPU')

#サンプリング
result = solver.run(qubo, shots=2000, T_num=4000, show=True)

offset=30980.0
MODE: CPU
DEVICE: cpu
11.716 s
Energy=-30977.890625, Occurrence=1
[[0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1]
 [0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0]
 [1 1 0 0 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0]]
[1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]
機械0 タスク [ 3  6 19 20 27] 時間 75.0
機械1 タスク [ 8 11 23 32] 時間 74.0
機械2 タスク [12 17 24 26 31 36] 時間 73.0
機械3 タスク [ 4  7 13 18 21 22 28 35] 時間 74.0
機械4 タスク [ 1  2  5  9 10 14 15 16 25 29 30 33 34] 時間 74.33333333333333

10回中もっとも良かった結果を載せました。こちらも最良解のエネルギーは理想値+2.1程度でした。

ArminSamplerのGPU版で求解

こちらもサンプリングが10秒程度で終わるようにパラメータを調整しています。ArminSampler() のGPUモードではサンプリング数を増やしても計算時間があまり伸びません。shots=15000まで上げました。

#サンプラー選択
solver = sampler.ArminSampler(seed=None, mode='GPU')

#サンプリング
result = solver.run(qubo, shots=15000, T_num=8000, show=True)

offset=30980.0
MODE: GPU
DEVICE: cuda:0
11.03 s
Energy=-30980.0, Occurrence=1
[[0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0]
 [1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0]
 [0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1]
 [0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 0]
 [0 0 1 0 0 1 1 0 1 0 1 0 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 1 0]]
[1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]
機械0 タスク [13 16 18 27] 時間 74.0
機械1 タスク [ 1  2 10 12 21 28] 時間 74.0
機械2 タスク [ 4  8 20 23 25 32 36] 時間 74.0
機械3 タスク [ 5 19 26 31 33 34] 時間 74.0
機械4 タスク [ 3  6  7  9 11 14 15 17 22 24 29 30 35] 時間 74.0

10回中1回だけ大域解が見つかりました。（え）