1. 組み合わせ最適化問題とは
組み合わせ最適化問題では、あるの制約条件下において多数の選択肢がある中で、目的とする指標を最も価値が高くする組み合わせを求めることを指している。例として、巡回セールスマン問題がある。これはセールスマンが複数の地点を経由した場合の最短距離で巡回できる経路を求める問題である。
この問題では全経路を計算する場合、通常地点の数nの順列分（n!）だけ計算を行う必要がある。例えば5地点の巡回であれば5!=120通りであり、簡単に計算ができそうである。しかし、10地点で3628800通り、20地点では2.4 × 10^18通り、50地点では3.0 × 10^64通りと直感に反して天文学的数字となっていき、すべての組み合わせを計算することが困難になってきます。このように指数関数的また階乗に比例して計算規模が大きくなり、総当たりの計算では有限時間内に解けない問題を組み合わせ爆発と呼ぶ。
この他にも、ナップサック問題、最大マッチング問題、整数計画問題など様々な組み合わせ最適化問題があり、実社会と繋がりをもつため量子コンピュータ（特に組み合わせ最適化問題では量子アニーリング）を基盤とした量子アルゴリズムによる解決が求められている*。
2. 量子コンピュータの種類
量子コンピュータは2種類に分けられる。イジングモデル方式（アニーリングマシン）では「量子焼きなまし法/焼きなまし法」の原理に基づいている。物体のある安定した高いエネルギーをもった初期状態から操作を加え、徐々に状態を変化させることでエネルギーが最小となる状態をつくる。この原理を最適解の探索に用いる。現時点での量子ビット数はD-wave社のAdvantageが5000量子ビット*2を搭載したマシンを既に提供しており、量子ゲート方式と比較してより大きな計算を行うことができる。イジングマシンでは用途は最適化問題を解くことに特化しておりその他用途もあるが限定的な利用となる*3, 4。
また、量子ゲート方式は超電導・イオントラップなど技術をもとに量子状態の素子を組み合わせて回路を作る。これにより古典コンピュータと同様に汎用的な計算を行うことができるため、この方式の未来には万能量子コンピュータの登場が期待されている。しかし量子ビットの仕組み上イジングマシンより干渉（ノイズ）を受けるため、現時点で提供されているマシンは最大でも数十量子ビット数しかないため、用途はかなり限定されている。
本記事では主に組み合わせ最適化問題に特化しているイジングモデル方式にて簡単な最適化問題を解く。なお、量子ゲート方式においても量子近似最適化アルゴリズム（QAOA: Quantum Approximate Optimization Algorithm）によって組み合わせ最適化問題を解くことができる。
3. イジング形式とQUBO形式
アニーリングマシンにおけるイジングモデルとは、統計物理学上で用いられる抽象的な格子状の物理モデルであり、世の中の様々な最適化問題をこのモデルに定式化する。イジングモデルのエネルギーを推移させて、基底状態（最もエネルギーが低い状態）を作ることで、その値をとりうる組み合わせの変数値を得ることができる*5。
二次形式二値変数最適化問題におけるイジングモデルは以下で表現される。
左辺のHはハミルトニアンでコスト関数（エネルギー）であり、最適化問題ではこのエネルギーの最小となるような二値変数（スピン変数）
を目指していく。
イジングモデルにおける+1, -1のスピン変数を0, 1のバイナリ変数にすることで、以下のようなQUBO(Quadratic unconstraited binary optimization、制約なし二次形式二値変数最適化問題)型へと変換しハミルトニアンを考える。
イジングモデルとQUBOモデルは相互に変換可能なので、対象問題によってどちらを利用するか決定する必要があるが、本記事ではQUBOモデルを利用して問題を解いていく。
4. 最適化問題を解く手順
最適化問題問題ではまず課題を定式を行う。現実で起きている問題や課題をイジングマシンで実行可能な数式で表現する必要がある。次に表現した数式を目的関数や制約条件それぞれをイジングモデルまたはQUBOの論理モデルで表現する。次に選択するソルバーの仕様に従った物理モデルへ再度変換する。更にソルバーのAPI仕様に従って物理モデルのデータに変換し、その後ソルバーにて計算を行い結果を得る*6。
既にソルバー別に汎用的な量子コンピュータ/イジングマシンのSDKが用意されており、アニーリング手法やソルバーの特性によって選択し最適化問題を解いていく。（以下SDKの一部を掲載する。*7）
名称 | 提供元 | 開発言語 |
Ocean | D-wave社 | Python |
Fixstars Amplify SDK | Fixstars社 | Python |
PyQUBO | リクルートコミュニケーションズ | Python |
Openjij | Jij社 | Python |
注釈
“D-Wave Japan.” D-Wave Japan, 2022, dwavejapan.com/system/. Accessed 9 Sept. 2022.
“量子コンピュータの歴史＜その他のコンピュータ＜コンピュータの歴史＜歴史＜木暮仁.” Kogures.com, 2014, www.kogures.com/hitoshi/history/quantum-computer/index.html. Accessed 9 Sept. 2022.
野澤 哲生＝日経クロステック／日経エレクトロニクス. “イジングマシンは占い装置！？ 量子アニーリングが競争の口火に.” 日経クロステック（XTECH）, 日経xTECH, 25 Aug. 2021, xtech.nikkei.com/atcl/nxt/column/18/01755/00002/. Accessed 9 Sept. 2022.
“1-OpenJij 入門 — OpenJij Tutorial 0.3.0 Documentation.” Openjij.org, 2021, tutorial.openjij.org/build/html/ja/001-Introduction.html. Accessed 9 Sept. 2022.
“Amplify SDK - Fixstars Amplify - 量子コンピューティングクラウド.” Fixstars Amplify - 量子コンピューティングクラウド, 2022, amplify.fixstars.com/ja/sdk. Accessed 9 Sept. 2022.
izey0306. “量子ミドルウェアの有名どころをまとめてみた.” Qiita, Qiita, 2 Dec. 2021, qiita.com/izey0306/items/e9e6b1a5b7d4ed698956. Accessed 9 Sept. 2022.