デジタルで豊かな社会の実現を目指す東芝デジタルソリューションズグループの
最新のデジタル技術とソリューションをお届けします。

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


シミュレーテッド分岐アルゴリズムにおける「分岐」とは


第1回において、量子インスパイアード最適化ソリューション「SQBM+」は、東芝が独自に研究している量子コンピューター「量子分岐マシン」を「古典化」したものを「シミュレーション」しているものであると説明しました。このシミュレーション(数値計算)により、組合せ最適化問題に対して良い解が得られることが確認できています。しかし、その理由はまだ明らかではなく、現時点では量子分岐マシンのもとにある「分岐」というアイデアが効いていると考えられます。

「分岐」というのは、自動車の台数が一定量を超えると突然交通渋滞が発生するなど、ある瞬間にシステムの状態が大きく変化する現象のことです。シミュレーション(数値計算)などで、その対象を連続的に変化させるとき、ある段階でシミュレーションの振る舞いが突然質的に変化することも「分岐」といいます。ここでは、シミュレーテッド分岐アルゴリズム(以下、SBアルゴリズム)の2019年に公開された論文(https://www.science.org/doi/10.1126/sciadv.aav2372)で使われた「y= x2(x2+p) 」というタイプの4次関数を用いて解説します。ここでは、pはパラメーターで、パラメーターpを連続的に変化させることで、シミュレーションの対象が連続的に変化することを表現します。SBアルゴリズムでは、パラメーターpを変化させ、シミュレーション(数値計算)していく中で発生する「分岐現象」をうまく使って、精度の高い組合せ最適化を実現しています。

4次関数「y= x2(x2+p) 」について調べてみます。

  • 4次関数「y= x2(x2+p) 」を微分すると、「y’=2x(2x2+p)」となります
  • 関数の極値を求めるためにy’=0となるxを探すと、2x(2x2+p)=0から以下であることがわかります
    ① p≧0のときの極値は、x=0という1つ
    ② p<0のときの極値は、x=0とその左右に1つずつで合計3つ

ここから考察すると、「y=x2(x2+p)」という4次関数は、p≧0のときには原点x=0に1つだけ谷がある形であり、またp<0のときには原点x=0は山となり、その左右に谷が2つある形になることがわかります(図1)。

SBアルゴリズムのハミルトン方程式では、システムのエネルギー量を示す関数「ハミルトニアン」の位置エネルギーに相当する部分に、前述した「y=x2(x2+p)」という4次関数が含まれています。SBアルゴリズムは、このハミルトン方程式に従って、4次関数が定める位置エネルギーの等高線(グラフの形状)を意識しながら不規則に飛び回る粒子の運動の軌道計算をしています。

SBアルゴリズムにおいては、例えば、パラメーター(p)を1から-1まで徐々に変えて数値計算していきます(ここでは、パラメーターの変え方を単純化して説明します)。この数値計算の過程で、p=0を境に、4次関数による位置エネルギーの地形は谷が1つの状態から2つの状態に突然変化します。これによって、それまで原点x=0の谷の周辺で安定的に運動していた粒子が不安定になります。粒子は、原点x=0の左右に新しくできた2つの谷のいずれかに近づいていき、やがて落ち着きます(図2)。


多次元空間の中で次々に起こる分岐現象


SQBM+などのイジングマシンでは、経路探索問題など、組合せ最適化問題に対して、特定の形式の関数を対応付け、この関数の最小化問題に帰着させて解を求めます。SBアルゴリズムでは、この組合せ最適化問題に対応した関数に、さらに分岐を起こすための4次関数を加え、両者をあわせた位置エネルギーの等高線を設定して、この上で不規則に飛び回る粒子を想定し、軌道計算を行います。

この際、例えば経路探索問題であれば、訪問する多数の頂点やその間の辺の情報を表現する必要があるなど、問題に応じて、最小化する関数には多数の入力変数が必要になります。SQBM+では、ハミルトン力学の考え方に基づき、組合せ最適化問題に対応する関数の入力変数1つに対して「位置」と「運動量」を示す2つの変数を対応させるため、例えば、入力変数が2000個の問題の場合は、4000次元の空間内で動き回る粒子の軌道を計算することになります。

SQBM+では、この多次元の空間内でパラメーター(p)を少しずつ変えながら数値計算を行い、「位置」に相当する次元のうち、最小化に対する効果がより大きい変数から順に分岐を起こします。数値計算が進むにつれて順次起こる分岐によって、各次元の「位置」に相当する変数がプラスあるいはマイナスに決まり、プラスとマイナスを多少変えながら、すべての次元で分岐が起こります。そして最後に、「位置」の座標を読み取って組合せ最適化の解とします。

各次元で順に分岐を起こしていく動作が、SBアルゴリズムが組合せ最適化問題として良い解を得られるところに関係していると考えられます。


GPUを駆使して高速に計算し多数の解から最も良いものを選択


第1回において、SBアルゴリズムは、各計算ステップが極めてシンプルで、また時間のかかる行列計算が各ステップ内で1回で済むこと、さらに全体として並列性が高く、かつ短時間で良い解を返せることを説明しました。SQBM+では、このSBアルゴリズムの特性を生かしながら、GPU(Graphics Processing Unit)上で実装し、画像の拡大縮小や回転、平行移動などの行列計算を、並列・高速に実行できるGPUの能力を駆使することで、さらなる高速化と高精度化を実現しています。

SBアルゴリズムの中で最も時間がかかる計算は、各ステップでの行列計算です。なぜなら行列計算には、位置を示す変数の全次元の情報が必要となるからです。この行列計算は、GPUが得意としています。そのため、GPUで動作できるSQBM+は、高速に行列計算をすることができるのです。行列計算以外の部分は、高い並列性を持つSBアルゴリズムの性質によって、各次元の計算を独立して実行できることから、SQBM+は、全体として非常に速く計算を終わらせることができます。

さらに、SQBM+は、行列計算が得意なGPUの特性をうまく使ってSBアルゴリズムを高速に計算するだけでなく、GPUに備わった大量の計算リソースをフルに使ってSBアルゴリズムを複数個並列に走らせることで、精度を向上させています。ユーザーの設定によっては、この並列処理を何回も繰り返して、その中で一番良い解を採用することでさらに解の精度を高めることもできます。

SBアルゴリズムは、いわゆる確率論的なアルゴリズムである「シミュレーテッドアニーリング(SA)」とは異なり、確定論的なアルゴリズムであるため、初期値を決めた後は確率的な操作が一切入らず、同じ経路をたどります。つまり、同じ初期値を設定したときには、常に同じ答えを返すということです。このようなSBアルゴリズムの性質を踏まえ、いろいろな解から良い解を見つけられるように、SQBM+ではSBアルゴリズムを並列に走らせたり、それを繰り返したりする際に、初期値を決めるときだけ確率的な操作を行い、初期値をランダムに振って多様な解が得られるようにしています。SQBM+では、この並列と繰り返しの動きで多様な状態が統計的に現れていく動きを模倣し、解の精度をより高めています。(図3)


サービスの実用化に向けたアルゴリズムの改良


ここまでは、2019年に公開された論文で示されたアルゴリズムに基づいて説明しました。論文で示されたアルゴリズムを、現在は「断熱的シミュレーテッド分岐アルゴリズム(aSB:adiabatic Simulated Bifurcation)」と呼んでいます。その後、このaSBを生かしたサービスを実用化する際に、アルゴリズムのさらなる改良をしています。それが、「弾道的シミュレーテッド分岐アルゴリズム(bSB:ballistic Simulated Bifurcation)」と「離散的シミュレーテッド分岐アルゴリズム(dSB:discrete Simulated Bifurcation)」という2つのアルゴリズムです。現在、Azure Quantumなどで提供しているSQBM+のサービスは、この2つのアルゴリズムを活用しているものです。

bSBでは、分岐現象を起こすために「y=x2(x2+p)」という4次関数の代わりに、「y=px2」という単純な2次関数を使います(pはパラメーターです)。例えば、この2次関数でpを1から-1に変えていくと、p=0を境に、原点が谷から山に変化します(図4)。このため、この関数を使って位置エネルギーの等高線を描くと、最初は原点の周りで安定した運動を行っていた粒子が、p=0を境に原点から「転がり落ちる」ことになるのです。

この現象に対してbSBでは、無限遠にまで粒子が転がり落ちないように「x=-1」と「x=1」に壁を設け、粒子の位置を壁と壁の間に制限しています。bSBは、2次関数による分岐と壁を併用し、aSBと同じように高次元の空間内で最小化に対する効果がより大きい次元から順に分岐を起こしながら数値計算を進めていきます。なお、dSBでもbSBと同じ2次関数を使いますが、dSBでは、離散的な性質を持つ問題である組合せ最適化を解くためにより適した計算になるように、粒子の進行方向を決めるときに離散的な性質を考慮した方向付けの工夫を加えています。

これらの新しいアルゴリズムで、SQBM+はさらなる性能の向上を実現しています。これについては、2021年の論文(https://www.science.org/doi/10.1126/sciadv.abe7953)で公開されています。


量子ハードウェアの世界から飛び出した自由なソフトウェア


SQBM+は、「量子分岐マシン」という東芝独自の量子コンピューターから生まれたことから、「量子インスパイアード」と呼んでいるイジングマシン方式のシミュレータ(以下、イジングシミュレータ)です。現在市場にあるイジングシミュレータの多くは、量子力学の原理を使って組合せ最適化を行う「量子アニーリング」に触発されて登場したことから、「量子インスパイアード」と呼ばれています。量子アニーリングは、1980年代に古典物理学の一分野である統計物理から発想された最適化手法であるシミュレーテッドアニーリング(SA)を参照して1990年代に発明された技術で、量子インスパイアードのイジングシミュレータの多くはSAに基づいています。これに対して、SQBM+は、最初から量子で考えた量子分岐マシンを出発点としていますので、「ネイティブ量子」インスパイアードといえます。(図5)

SQBM+は、量子分岐マシンを「古典化」した方程式から出発していますが、最初のaSBの段階で既に古典化した方程式をかなり見直していました。また、その後の改良の際に、さらに大胆に方程式を変形し、bSBとdSBという、より高性能なアルゴリズムを実現しました。このような改良は、SQBM+が、量子ハードウェアの「もの」の世界から離れ、数式の世界で自由に発想を広げたことによって可能になったものです。量子の世界におけるシュレディンガー方程式に対応する、古典の世界におけるハミルトン方程式という枠組みの中で、ソフトウェアおよび数学・物理学の自由な発想に基づいて高性能化を追求すること。これが、SQBM+の良さであると考えています。

第1回のイジングマシンを中心としたSQBM+で重要な役割を果たす「量子インスパイアード最適化技術」の構造解説に続き、第2回ではシミュレーテッド分岐アルゴリズムにおける「分岐」をひも解くとともに、量子インスパイアード最適化技術の全体像について解説しました。第3回では「最適化」編として、最適化とはなにか、どのようにして組合せ最適化問題を解いているのかについて、具体的な例を交えて詳しく説明していきます。

岩崎 元一(IWASAKI Motokazu)

東芝デジタルソリューションズ株式会社
ICTソリューション事業部 データ事業推進部 新規事業開発担当 シニアエキスパート


東芝に入社後、オフィスサーバの基本ソフトウェア開発やミドルウェア開発、プラットフォームの商品企画に従事。現在は量子インスパイアード最適化ソリューション「SQBM+」の事業開発に取り組んでいる。

  • この記事に掲載の、社名、部署名、役職名などは、2023年5月現在のものです。

>> 関連情報

関連記事