組み合わせ最適化問題を手軽に解く

従来のコンピューティング環境の演算では時間が掛かりすぎて、解くのが難しい問題。こうした問題を解くために量子コンピューティングは生まれました。量子コンピューティングは一言で言うと「特定の条件下で複数の解を同時に探索できるパワフルな方法」です。しかしながら現時点で量子コンピューティングを本格的に実用運用するには手間とコストが膨大にかかるものです。

Qalmo®は、「量子力学を使わずに、特定の条件下で複数の解を同時に手軽に専用PC１つで探索」することができます。

Qalmo®で求解できる問題は「組み合わせ最適化問題」と一般的に言われていてます。ある制約条件化での組み合わせが多すぎて、従来のコンピュータでは計算時間が掛かりすぎ解けない、下記のような問題です。

• 渋滞の解消：VRP（Vehicle Routing Problem）

  渋滞の解消に関連する最適化問題の一つが、VRP（Vehicle Routing Problem）です。この問題は、複数の顧客に商品を配達する際に、運転手が最も効率的なルートを決定することを目的としています。現実の例として、食品デリバリーサービスが挙げられます。効率的なルートを計画することで、配達時間を短縮し、コストを削減することが可能となります。

• 積載順の問題解決

  配送トラックの荷物の積載順を探します。大きさや重さ、積み下ろしの順番が異なる荷物を最も効率よく積載する方法を探します。配送業者では配送台数の削減など生産性向上が期待できます。

• 訪問順の問題解決:TSP（Traveling Salesman Problem）

  距離の異なる事務所をどういう順番で訪れればもっとも時間効率よく帰社できるのか、その訪問順を探します。最適化問題の一種であり、ある都市の集合を訪れた後、出発点に戻る最短経路を求めることを目的としています。ビジネスでは移動コスト削減と移動効率ＵＰによる生産性の向上を、配送業者では燃費や時間節約することが可能です。

• 人員配置の最適化：シフトスケジューリング

  この問題は、小売店や病院などで、スタッフのシフトをどのように組むかを決定するものです。例えば、病院では、医師や看護師の必要な数を確保しつつ、各スタッフの勤務希望や労働時間制限にも配慮する必要があります。これにより、効率的な人員配置が実現し、サービスの質が向上します。

• 教室の割り当て：タイムテーブルの最適化

  大学などで、授業に必要な教室を各コースに適切に割り当てることは、「タイムテーブルの最適化」として知られています。例えば、限られた教室の中で、異なる科目が重複しないようにスケジュールを組む必要があります。これにより、学生が必要な授業を受けやすくなるだけでなく、教室の資源を最大限に活用することが可能になります。

たとえば、訪問順の問題解決（TSP）を例にとりますと、拠点が20か所に増えるだけで、経路総数がなんと約121京回と天文学的な回数が必要になるのです！

このレベルは汎用PCで解くことは難しいですが、Qalmo®であればエッジ環境で探索可能です。

量子コンピュータでは、量子力学の特性を利用して、最適化問題の複数の解を同時に探索し、最適解へと至る技術ですが、このアプローチでは、量子を扱うため冷却装置など計算機の規模が大きくなり手軽ではありません。

Qalmo®は、独自アルゴリズムをFPGAに実装しており、パソコンで手軽に動作するため、特別な設備を必要とせず、オンプレミスでの使用が可能です。これにより、企業や研究機関は、高価な量子コンピュータを購入することなく、組み合わせ最適化問題を効率的に解くことができます。

下図は従来の最適化問題の探索方法をイメージしたグラフです。エネルギーが最も低い位置のビット状態が目指す最適解ですが、探索を開始後、途中でビットがエネルギーの低い解の１つに落ちると、そこから抜け出して、新たに大域最適解を探しに行けなくなります（局所解：図1）。

この課題を克服するため、Qalmo®は探索エネルギー領域が違う、広域探索モード(FAST)・中域探索モード(RATE)・狭域探索モード(DEEP)の3つの探索モードを自由に切り替えることができます。モードを切り替えて探索を継続することで、局所解を避け、効率よく最適解に達することができるのです。（図２）

ディー・クルーのシステムソリューション技術を駆使した「Qalmo」は、初号機が2022年3月に完成。その後も研究開発を続け、現在、演算性能を倍増した2048spin版をレンタルサービス中です。

手軽に「Qalmo」お試しいただけますよう、リーズナブルなレンタルプランをご用意しています。是非この機会にこちらからお申し込みください。

組み合わせ最適化問題を短時間で求解できる、手軽なソリューションをお求めの研究者様にぜひご体感ください。