豆寄席第15回『量子アニーリングと数理最適化』参加レポート

林 沛萱

AI技術チームの林(リン)です。
今回は株式会社Fixstars AmplifyのCEO、平岡卓爾様をお招きして、2022年 2月24日に行われた豆寄席「量子アニーリングと数理最適化」についてレポートします。

 

イベントの講演は数理最適化問題を解く方法の一種である量子アニーリング・イジングマシン及び、産業界の課題へどのように対応するのかについて、以下の流れでご説明いただきました。

  1. 株式会社Fixstars Amplifyの会社紹介
  2. 量子アニーリング・イジングマシンと組み合わせ最適化問題
  3. 量子コンピュータについて
  4. Fixstars Amplifyの技術について

 

組み合わせ最適化問題の例
図(1)組み合わせ最適化問題の例。(出典:講演資料)


現在の産業界において、さまざまな課題が「組み合わせ最適化問題」という問題に帰着します。組み合わせ最適化問題とは、膨大な選択肢から条件を満たすベストな選択肢を探索する問題です。例えば、図(1)のように、バイキングで金額が最も安く、各栄養素が取れる食材の組み合わせが知りたいケースです。問題には、それぞれの選択肢に対して結果となる数値を計算することができます。先ほどの例では合計金額が結果にあたります。様々な入力パターンがある場合は結果を一つ一つのパターンごとに計算し、全パターンを網羅するのは非常に大変です。このような問題を解くには、通常のコンピュータでは計算回数は指数関数的に増えてしまうことが知られており、実際の問題に対し、現実的な時間で解くことができません。今日紹介する量子アニーリング・イジングマシンは、通常のコンピュータより迅速に、ただし近似的な手法でこのような組み合わせ最適化問題を解くことができるマシンの一種です。同社の社名ともなっているAmplifyは、量子アニーリング・イジングマシンを簡単に操作することができ、組み合わせ最適化問題に特化したツールです。
 

組み合わせ最適化問題を解くに統一的なフレームワーク
図(2)組み合わせ最適化問題を解くに統一的なフレームワーク。(出典:講演資料)


組み合わせ最適化問題は図(2)が示しているように、統一的なフレームワークで解くことができます。各選択肢に対する結果値を関数と捉えたものを「目的関数」と呼び、目的関数を最小化(最大化)する選択肢を解と呼びます。これに加え、解が満たすべき条件を「制約条件」と呼びます。目的関数と制約条件の二つを数式で書ければ、Amplifyにより解が得られます。
 

現在の産業界における代表的な組み合わせ最適化問題を挙げると、生産スケジュールの効率化課題があります。工場では、ある製品を作るのに必要な機械の稼働時間は決まっているので、なるべく隙間がないように機械の順番や稼働時間をうまく調整したいという要望があります。このような問題も組み合わせ最適化問題として解くことが可能です。この問題において、「目的関数」はリードタイムであり、「制約条件」は稼働可能な機械です。一方、同じく工場の例ですが、作業員の割り当てを効率化する課題も組み合わせ最適化問題に帰着させることができます。例えば、多くの従業員をチームに割り振るとして、各作業員の勤務希望曜日に合わせた割り当てを考える場合があります。他には、工場の中を走り回る無人搬送車(AGV)のルートを最適化する問題があります。AGVは工場の中に何10台もあり、荷物を搬送する際には渋滞がかなりの頻度で発生します。最適化問題として最適解を計算すると、全体的にAGVの移動を見ながら最適な配置と経路を指示することで、全体の待ち時間を最小化することができます。

量子コンピュータ、イジングマシン、量子アニーリングの関係図
図(3)量子コンピュータ、イジングマシン、量子アニーリングの関係図。(出典:講演資料)


量子コンピュータは、図(3)が示しているようにゲート型とアニーリング型の二種類に大きく分かれています。ゲート型は量子力学的な状態の重ね合わせを利用し、汎用計算の計算速度を上げるものです。量子アニーリングは、組合せ最適化問題の中でも、二次の多変数多項式で表される目的関数の最適化問題 (QUBO)と呼ばれるタイプの最適化問題を、量子焼きなまし法の原理を用いて高速に解くことを目的とします。QUBOを解くための専用機のことをイジングマシンと呼ぶため、量子アニーリングもイジングマシンの一種と言えます。量子アニーリングをはじめとしたイジングマシンは、次世代アクセラレータとして日本のメーカーを中心に提供されています。

 

Amplifyを使用することで、メーカー各社が提供するイジングマシンの操作方法を知らなくてもイジングマシンを利用することが可能です。Amplifyのメリットは、まずイジングマシン利用のプロセスが非常に簡単になることです。通常イジングマシンを使用するためのプログラミングでは問題を数学的に定式化するだけではなく、特有の形式に落とし込む必要があるため習得は簡単ではありません。Amplifyを使えば、その変換を自動的にやってくれるので苦労することはありません。次に、Amplifyが複数のイジングマシンに対応できる点です。Fixstarsが提供したGPUベースのイジングマシンの他に、D-Waveなどのマシンへの対応も可能です。さらに、Amplifyは始めやすいという特徴があります。どんなに便利だとしても、少しだけやってみたいときでもお金がかかるのであればなかなか活用が広がらないかもしれません。それに対して、Amplifyは研究開発用途では無償で利用することができます。Amplifyの公式サイトにも、高校生でも理解できるぐらいわかりやすく書かれている無料のチュートリアルが提供されています。

以上が豆寄席「量子アニーリングと数理最適化」のレポートになります。

 

組合せ最適化問題は現在の産業界において頻繁に発生する課題ですが、簡単に操作できるAmplifyを導入することで、多くの問題が解けるだけではなく、手間や時間を大幅に減らすことで効率も上げることができると思います。例えば、今日紹介した作業員シフト調整の例では、もともとは毎朝30分程度かけてシフト表を作成する工程が不要となり、僅か10秒でAmplifyが自動で作成してくれます。Amplifyを使うことで、生産性と効率がさらに上がることで、ビジネスの現場に新たな可能性が広がると感じました。

今回の講演内容で、組合せ最適化問題を素早く解決するには、単純に新しい数学アルゴリズムを提案するだけでなく、ハードウェアの革新もかかわってくるということを学びました。ただし、ハードウェアも関係してくると、設備の管理や機械の知識といった課題も出てくるので、クラウドサービスとすることで誰でも量子アニーリングを気軽に使えるようになるという点は今回の講演のポイントだと思いました。今回、解決可能な組合せ最適化問題として紹介されたもの以外にも、配達トラックのルートナビや、通勤シフトの路線案内など、様々なソリューションに適用できるではないかと思っています。