変化の激しい世の中にあって、複雑化する課題の解決に取り組む社会や企業では、量子関連の技術が注目されています。量子現象を利用した本格的な量子コンピューターの実現には時間がかかると考えられている中で、東芝では、量子現象から着想を得た量子インスパイアード最適化技術に取り組んでいます。これは、膨大な選択肢の中から最適な解を導き出す「組合せ最適化」に対応する当社独自の技術で、既存のコンピューターを使って高精度な近似解（良解）を短時間で得られる量子インスパイアード最適化ソリューション「SQBM+」として提供しています。ここでは、量子インスパイアード最適化技術について、連載でご説明します。
第1回では、量子コンピューターにおける2つの方式（ゲート方式とイジングマシン方式）と、それに対する量子インスパイアード最適化技術の位置づけや構造について解説しました。第2回では、この技術で重要となる「分岐」と、「高速化・高精度化」、さらにはこの技術の全体像について説明しました。第3回では、「組合せ最適化問題」を中心にご説明します。

第1回では、量子コンピューターには、大きく分けて「ゲート方式」と「イジングマシン方式」の2つの方式があると説明しました。汎用性の高い用途を想定した「ゲート方式」に対して、「イジングマシン方式」は組合せ最適化問題を解くことに特化した方式です。

では、「組合せ最適化」とは何でしょうか。「最適化」について説明し、ひも解いていきます。

最適化とは、「特定の目的のために、事象やシステムを最も適した状態にすること」です。ここで、交通の分野における、自動車の走行ルートの最適化を考えてみます。 

例えば、異なる目的地に向かういくつかの自動車があり、それぞれの運転者は最短の時間で目的地に到着したいと思っているとします。このとき、すべての自動車が最短のルートを進むと、ある道路や交差点に自動車が集中して渋滞が発生し、かえって目的地への到着が遅れてしまうことがあります。こうした場合、何台かの自動車が、必ずしも最短ではないルートを通ることで、渋滞の発生が減り、結果として平均的な到着時間が早くなるかもしれません。 

では、各自動車には、どのようなルートを進んでもらえばよいのでしょうか。ただし、最短ではないルートを選んでもらう自動車は、最小限に抑えるものとします。 

このような、一定の条件（制約）のもとで最適な結果を探すような社会課題や業務課題を、数理モデルを用いて数学的に最適解を求める手法を、「数理最適化」といいます。

数理最適化では、①問題を数理モデルで表現した（数理モデル化）のち、②「目的関数」を設定して問題を数学的に扱えるようにし（定式化）、③目的関数の出力が最小あるいは最大になるような「入力値」を求めます（最小化/最大化）（図1）。

数理最適化の手順

① 数理モデル化
問題を数学的に扱えるように、抽象化したり単純化したりして、数式やグラフの形式に置き換えます。

② 定式化
数理モデル上で、何が良い状態であるかを示す評価尺度を定め、取り得る選択肢を表現する「変数」を決め、その変数によって決まる「入力」と、それに対する良しあしの評価を示す「出力」との対応付けを「目的関数」として定め、さらに、「入力」の取り得る「制約」を設定します。

③ 最小化/最大化
変数に与えられた「制約」の範囲内で、目的関数が最小あるいは最大となる「入力値」を求めます。これが、数理最適化の答えになります。
 

前述した交通の例で考えると、次の手順になります。

① 自動車の流れをグラフ化します。

②「良しあし」を評価する評価尺度として、例えば「混雑度」を考えることにします。それぞれの自動車が選択するルートの組み合せを変数として、選択するルートの組み合わせから道路網の混雑度を計算する式を作り、目的関数とします。このとき、最短ではないルートを選ぶ自動車は、例えば「全体の1%以内にする」というような制約を定めます。

③ 目的関数（混雑度）がもっとも低くなる「入力値」（自動車が選択するルートの組み合わせ）を求めます。

最適化問題には、「線形計画問題」や「２次計画問題」などさまざまな種類があり、これらは先に示した②定式化と③最小化/最大化で登場する、(a)目的関数の種類、(b)制約の有無、そして(c)変数の種類という3つの観点で分類できます。

例えば、目的関数が１次式（線形）で表現される場合は「線形計画問題」と呼ばれ、目的関数が２次式で、かつ制約が１次式の場合は「２次計画問題」と呼ばれます。また、線形計画問題のうち、変数が-2や-1、0、1、2のような整数だけの場合は「整数計画法」と呼ばれます。変数として、整数と、数直線上のあらゆる点に連続的に対応するいわゆる実数の双方を扱う場合は、「混合整数計画法」と呼ばれます（図2）。

組合せ最適化は、離散的な変数の組み合わせを対象とします。例えばグラフの頂点をひと筆書きですべて通る経路があるかどうかを判定する「ハミルトン経路問題」や、重量や容量に制限のある容器（ナップサック）に複数の品物を詰めて価値の最大化を図る「ナップサック問題」、製造工程を最適化する「ジョブショップスケジューリング問題」などが該当します。

旅先でいくつかの観光スポットを最も短い時間で巡るルートを探索するなど、現実世界のさまざまなところで登場します。交通の例では、例えば各自動車が選択するルートの候補を2個に制限すると、目的関数の「入力」は、自動車ごとに2個の選択肢という離散的なものの組み合わせになるため、組合せ最適化問題になります。

組合せ最適化は、入力できる数が有限なため、入力の候補を一つひとつ目的関数に当てはめて計算し、結果を比べて、目的関数の出力がもっとも小さな値になる入力値を探すという、いわゆる総当たりの方法で答えを出すことができます。しかし、変数の数が増えると、入力値の候補の数が指数関数的に増えていくため、限られた時間内に、総当たり法で解くことは現実的ではありません。

例えば交通の例でいうと、エリア内を走っている自動車が1000台で、それぞれの自動車が通るルートを2個の選択肢から選んだ場合、目的関数の入力値の候補は2¹⁰⁰⁰通りになります。これはオーダーとして10の300乗を超え、例えば全宇宙にある原子の数が10の80乗程度ということからも、非常に大きな数であることがわかります。この規模の組み合せ数になると、現時点でもっとも速いコンピューターを使っても、とてもすべてのパターンを調べ尽くすことはできません。

そのため、組合せ最適化問題には、総当たりで解くのではなく、別の効率的な解法が求められます。これについてはさまざまな工夫が行われ、特定の問題では効率的な求解アルゴリズムが見つかっています。しかし、組合せ最適化問題には、いわゆるNP困難あるいはNP完全^※と呼ばれる極めて難しい問題のクラスに属する問題も多く、厳密に最適解を求める場合には、効率的でかつ、汎用的な解法は存在しないと考えられています。

※NP困難あるいはNP完全：コンピューターで解を得られる問題は、計算量理論による計算クラスで分類できます。このうち、「NP困難（non-deterministic polynomial-time hardness）」「NP完全（nondeterministic polynomial-time complete）」に属する問題は、現在のコンピューターで効率よく解く解法は存在しないと予想されています。
 

これに対して、現実の世界では、厳密に最適解を求めるのでなく、実用的なレベルで評価関数の値が低い入力パターン（準最適解）を求められれば十分とされるケースもあります。このようなケースのために、理論的な保証はないものの、総当たりではない方法で、効率的に解を求めるアルゴリズムが提案されています。SQBM+は、こうしたソルバー^※の一つです。

※ソルバー：数学の問題を「解決」するソフトウェアライブラリーをソルバーと呼びます。

組合せ最適化問題を解くためのイジングマシンの多くは、「QUBO^※」という特定の種類の組合せ最適化問題を解くためのインターフェースを提供しています。

※QUBO（Quadratic Unconstrained Binary Optimization）：二次制約なし二値最適化を意味します。
 

QUBOは、組合せ最適化の中にある特定のパターンの一つであるため、QUBOのインターフェースではすべての組合せ最適化問題に対応することはできません。そのため、多くのイジングマシンでは、一般的な組合せ最適化問題に対して、QUBOのインターフェースをもとにしながら、以下のような工夫をして対応しています（図3）。

（1）2次式以外も含む「目的関数」への対応

組合せ最適化問題の目的関数が、例えば3次式などの高次の多項式だった場合、そのままでは2次式を対象とするQUBOのインターフェースでは解けません。そこで、変数の数を増やして高次式を2次式に書き替える手法を使い、QUBOとして解けるようにします。こうした工夫によってQUBOのインターフェースを拡張した「PUBO（Polynomial Unconstrained Boolean Optimization）」というインターフェースを提供しているソルバーもあります。

なお、SQBM+が採用しているSBアルゴリズム（シミュレーテッド分岐アルゴリズム）では、もともと目的関数を2次式に限定していないため、問題によっては、高次の多項式を2次式に変換する手法は使わず、直接3次式以上の多項式などを扱うことも可能です。
 

（2）「制約」への対応

組合せ最適化では、多くの場合に「制約」がつきます。例えば、先に挙げた交通の例では、「最短ルート以外を選択する自動車の比率を1%以内とすること」が、制約にあたります。

制約がある場合、そのままでは、制約がないことを前提とするQUBOのインターフェースで解くことはできません。そのため、事前に「ペナルティ法」などの手法を用います。ペナルティ法では、まず、制約を満たすときに0になり、制約を満たさない場合は0より大きくなる「関数C」を作ります。次に、制約と目的関数との間のバランスを調節する「パラメーターk」を使って、元の目的関数FとkCの和である「Ｆ’（＝F＋kC）」を作り、Ｆ’を新たな目的関数として設定します。適切なパラメーターkを設定すれば、新たな目的関数F‘を最小化することで、元の目的関数Fを最小化しながらCを０にすることができます。これは、つまり、制約を満たしながら元の目的関数Fを最小化することができるということになるので、これにより、問題が、制約なしの組合せ最適化問題に変換され、QUBOで解けるようになります。
 

（3）バイナリ（0と1）以外の変数への対応

QUBOは、バイナリ（0と1）を変数とするため、整数を変数とする「整数計画問題」などは扱えません。そこでこのような問題を解きたい場合には、整数を2進数に変換し、２進表示の各桁の0あるいは1をバイナリ変数とみなすことで、問題をQUBOの形式にすることができます。この考え方は、小数を含むような問題にも適用できます。

現実に現れる多くの問題を解くには、バイナリや整数の値を取る変数だけではなく、連続した値を取る変数も同時に扱う必要があります。こうした場合に、SBアルゴリズムの工夫で対応する場合もありますが、バイナリの部分をSQBM+で扱い、連続した変数の部分をSQBM+以外の従来手法で扱うような、ハイブリッドで処理する手法もあります。一般的に、イジングマシンはQUBOを高速で解くことができますが、それ以外のパターンは不得意な場合もあり、さまざまなケースで、イジングマシンと従来の数理最適化技術をうまく組み合わせて、全体として効率的に問題を解くハイブリッド・アルゴリズムが研究されています。

現在は、さまざまな問題をQUBOで扱う研究が進んでおり、関連する経験やノウハウも蓄積されてきています。しかし、新しい問題にQUBOインターフェースで取り組むには、まだ難しいところがあるのが実情です。

ただし、QUBOインターフェースでプログラムを書いておくことで、将来、超高性能な量子コンピューターが実現したときに、プログラムをそのまま載せ替えるだけで性能の向上が期待できるということは、魅力的なアイデアです。その一方で、現時点でさまざまな問題を解くには、もう少し使いやすいインターフェースも必要だと考えられます。

SQBM+では、QUBOインターフェースに限らず、「充足最大化問題」や「巡回セールスマン問題」、「シフト最適化問題」といったそれぞれの問題に対して専用のインターフェースを装備し、QUBOに慣れていなくても組合せ最適化問題を解けるソルバーを用意しています。

最近では、イジングマシンを利用するためのミドルウェアのレイヤーも進歩し、ミドルウェアを上手に使うことによって、より効率的にソルバーを活用できるようになってきました。

今回は、最適化編として、「最適化とは何か？」「どのようにして組合せ最適化問題を解いているのか？」について、説明しました。次回の第4回では、SQBM+で具体的に問題を解いた事例をご紹介します。ご期待ください。

• 量子インスパイアード最適化ソリューション「SQBM+」