Zenn
🚚

TYTAN SDK で遊んでみる (1) — 入門の入門

2023/06/29に公開
Python
poem
qubo
tech

目的

詳しくないので用語や言い回しは適切ではないかもしれないが、QUBO (Quadratic Unconstrained Binary Optimization) という概念があって、これをソルバで最適化して組合せ最適化問題を解きたい、ということがある (らしい)。

今回、この QUBO の最適化を通じた組合せ最適化について、基本的なところを押さえておきたいという理由でつらつらと記事を書いてみようかと思って、最初の記事を書いてみることにした。今回は、SDK の使いかたを最低限見る程度をゴールとする。

はじめに

QUBO による組合せ最適化が何かということは後に回すとして、そういったことができるものに、D-Wave Ocean SDK とか PyQUBO[1] とかいうものがあるらしい。比較できていないが、たぶんこれらと似たようなものとして TYTAN SDK というのがある。今回これを使ってみたいが、その理由はありがちなもので、よく分からないので、たまたま目にとまって、なおかつチュートリアルが用意されていて何となく良さそうに見えたというくらいの動機である。なお、D-Wave の実機を除いては、恐らく「擬似量子アニーリング」という手法になると思う。

やることはシンプルで、

  1. 解きたい組み合わせ問題を QUBO 式という式で記述してやって、
  2. ソルバに放り込めば、

記述が妥当であって、なおかつ運が良ければ最適解や準最適解が得られるというものになる。

取り組める問題は、典型的なものは

  • 配送経路などの経路最適化
  • 勤務に関するシフト最適化

などが考えられる。

ざっくりと

QUBO を使った組み合わせ問題の解放では、適当な変数を使って問題を解くのだが、かなり厳しい条件がある。

  1. Binary (二値) というだけあって、変数 q_0, q_1, ... は 0 か 1 の 2 値しかとれない。
  2. なおかつ、この変数について使える式の次数は Quadratic (二次) というだけあって、問題を記述する多項式の次数が 2 次までである

つまり、q_0^2 は OK だが、q_0^3 や q_0^4 は NG である。線形結合の類は使えるので

  • OK:
    • H = q_0 + q_1^2,
    • H = (2 q_0 - q_1 + 3 q_2)^2 + 3 q_0 q_1
  • NG:
    • H = q_0 + q_1^3
    • H = (2 q_0 - q_1 + 3 q_2)^3 + 3 q_0 q_1 q_2

みたいな感じである。なお、q_0 \in \{0, 1\} より q_0^2 = q_0 である。つまり、

\begin{align*} H = (q_0^2 + q_1^2) q_2 \end{align*}

は見かけ上は 3 次式だが、整理すると H = q_0 q_2 + q_1 q_2 で 2 次式なので OK となる。

二値性や二次性については、工夫することである程度は緩和可能だと思っているが、それは次回以降の記事にまわす。

簡単な問題

この厳しい条件下で、「足したら 2 になる整数を求めてみたい」。つまり、解きたい問題は、q_0, q_1 \in \{0, 1\} に対して

\begin{align*} q_0 + q_1 = 2 \tag{1} \end{align*}

というものになる。答えは恐らく自明ではあるのだが、それはさて置き、脳内では一瞬のうちに

  • q_0=0, q_1=0
  • q_0=0, q_1=1
  • q_0=1, q_1=0
  • q_0=1, q_1=1

を試しているはずである。ということにする[2]。

なんと、4 回も計算していると！毎回しらみ潰しでそれをするのは面倒くさいので、やりたくない。PC にお任せしたいというのがこういった問題をソルバで解きたい動機であろう。

ところで、いわゆる “最適化問題” として解くので、何かしらコスト関数的なもの —— 何かしらの実数値関数で、最小値をとるケースが最適解を与えるようなもの —— を用意してあげる必要がある。今回のケースであれば 2 つのコスト関数 H_1 と H_2 が考えられそうである。

\begin{align*} H_1(q_0, q_1) = 2 - (q_0 + q_1) \tag{2} \end{align*}

と

\begin{align*} H_2(q_0, q_1) = (q_0 + q_1 - 2)^2 \tag{3} \end{align*}

である。(2) 式は実は案に答えの当たりがついていないとこの形 (特に符号) にはできないので嫌な感じである。(3) 式は符号周りなどは何も考えずに設計できて、頭を使わない。恐らく汎用性が高いのはこちらだ。一方で、2 乗すると、QUBO の 2 次性をすぐに消費してしまうので、カッコ内で 1 次式しか使えなくなる。

チュートリアルを パクる 参考にする

さて、TYTAN SDK のチュートリアルは tytan_tutorial にあって、結構頻繁に更新されている。TYTAN SDK 自体は、公式的にも main ブランチの最新のものを使ってくれという運用なので、そうしたい。但し、今回は今の瞬間に CI が通っている最新版とする:

問題を解く

!pip install -q git+https://github.com/tytansdk/tytan.git@69d2415

SDK の更新が早いので書き方も多少変化していく。基本的に新しい簡便な書き方は新しいチュートリアルに載っている。ここでは TYTAN tutorial おすすめ10（線形回帰） を参考にする。

必要なモジュールを import する。

from tytan import symbols, Compile, sampler

さて、コスト関数をそれぞれ定義してみよう:

q0 = symbols('q0')
q1 = symbols('q1')

H1 = 2 - q0 - q1
H2 = (q0 + q1 - 2)**2

自明な形でコスト関数が定義できたが、この段階まで到達することを「QUBO の定式化をする」と呼ぶらしい。

さて、これらを API に放り込めるようにするためにそれぞれコンパイルする:

qubo1, offset1 = Compile(H1).get_qubo()
qubo2, offset2 = Compile(H2).get_qubo()

最適化の際に定数項は省いても問題がないので、offset 変数として省かれる。H_1 の式では定数項は 2 なので、offset1 = 2 になっており、H_2 の式は展開すると定数項は 4 なので、offset2 = 4 となる。

print 関数で見ると多少違う出力になるのだが、本質的には定数項を除く形で qubo1 = -q0 -q1 と qubo2 = -3*q0 -3*q1 + 2*q0*q1 が得られている。どこから -3 が来たのか！？という感じであるが、展開した式において q_0^2 = q_0 に注意すると q0**2 - 4*q0 = q0 -4*q0 = -3*q0 として出てくるのである。

H1 = qubo1 + offset1, H2 = qubo2 + offset2 といった感じになる。

これで準備ができたので、深く考えずにソルバに放り込んで問題を解く:

solver = sampler.SASampler()

result = solver.run(qubo1)

for r in result[:2]:
    print(r)

[{'q0': 1, 'q1': 1}, -2.0, 100]

よって、q_0 = 1 と q_1 = 1 が最適解を与えていることになる。「-2.0」は最適解での H_1 の値であり、qubo1 = -q0 -q1 であったので、-2 であることが分かる。「100」の部分はその結果が得られた回数である。SASampler.run のオプションに shots という引数があって、アニーリング実験を何回試行するか？の指定になる。現在のデフォルト値は 100 である。よって、100 回の試行をした結果、すべて q_0 = 1 と q_1 = 1 が得られたということである。[3]

H1 = qubo1 + offset1 であって、offset1 = 2 であったので、H_1(1, 1) = (2 - q_0 -q_1) \big|_{q_0=1,q_1=1} = 0 が得られた形である。

H_2 についても解いてみよう:

result = solver.run(qubo2)

for r in result[:2]:
    print(r)

[{'q0': 1, 'q1': 1}, -4.0, 100]

同じく、q_0 = 1 と q_1 = 1 が最適解を与えていることが分かる。「-4.0」は最適解での H_2 の値であり、qubo2 = -3*q0 -3*q1 + 2*q0*q1 であったので、-4 であることが分かる。こちらも H_2(1, 1) = (q_0 + q_1 -2)^2 = 0 が得られた形である。

まとめ

とても簡単な問題設定で、最適化技術を用いて簡単な計算を実行してみた。最低限の API の使い方と、QUBO の定式化について 2 通り見てみた。

脚注

  1. 量子アニーリングマシンなどで「組合せ最適化問題」を解くためのQUBOを自動で構築するドメイン固有言語『PyQUBO』を開発 ↩︎

  2. 生物学や脳科学は知らないのでよく分からない。 ↩︎

  3. 例えば H3 = (q0 + q1 - 1)**2 という QUBO 式の場合、q_0 = 0 と q_1 = 1 および q_0 = 1 と q_1 = 0 の 2 つが最適解を与える。この場合、どちらで最適値が達成されるかは確率的に定まり、概ね 50:50 くらいになる。例えばの実測では 54:46 であった。 ↩︎

GitHubで編集を提案

Discussion