量子コンピュータの仕組みをエクセルで理解してみよう ～量子アニーリングの古典版「シミュレーテッドアニーリング」の実装～

ITエンジニアのための量子コンピュータ入門 第2回

シミュレーテッドアニーリングをエクセルで実行してみよう

　以上で説明した解けない問題は、厳密に解くことはできなくても、近似的な解ならば求めることができます。また、実用上厳密に解かなくても、ある程度の精度で解が得られれば十分な場合が多く、そのような近似的な解を効率的に求めるアルゴリズムが日夜開発されています。今回は、そういった近似的なアルゴリズムの一つ「シミュレーテッドアニーリング^[*]」（Simulated Annealing：以後SAと呼ぶ）について説明します。

　SAは、量子アニーリングのベースとなるアルゴリズムであるため、これを理解すれば量子アニーリングがかなり身近に感じられるでしょう。量子アニーリングの最初の研究も、このシミュレーテッドアニーリングに量子力学の効果を導入してみる、という観点で研究されました（参考：東工大・ 西森秀稔教授による量子アニーリングの解説ページ）。量子アニーリングの性能を普通のコンピュータと比較する際には、同じ問題を通常のコンピュータを使ってSAで解いた時の計算時間と比較している場合が多く、通常のコンピュータで解くときのアルゴリズムの代表として用いられるアルゴリズムの一つでもあります。

[*]: シミュレーテッドアニーリング

　アニーリングとは、金属を高温で一度溶かし、その後ゆっくり冷ますことで結晶を成長させて、その欠陥を減らす「焼きなまし」のことです。シミュレーテッドアニーリングは文字通り、この「焼きなまし」をコンピュータ上でシミュレーションすることで問題を解く方法であり、「焼きなまし法」とも呼ばれます。（参考：Wikipedia：焼きなまし法）

　では、まず本記事に添付しているエクセルファイルをダウンロードし、動かしてみましょう。ファイルを開くと、「Ising」ワークシートに「Start!」ボタンがあるので、押してみてください。すると、10×10セルの最適化問題をシミュレーテッドアニーリングで計算し、数秒後に答えにたどり着きます。まずは何度か押して、ちゃんと顔が出るかどうか、美白が出るかガングロが出るか、を楽しんでください。そして興味が出てきたら、以下のアルゴリズムの詳細を読んでください。

解くべき問題の概要

　問題は、「Answer」ワークシートに表示されている10×10＝100セルの0と1の2値画像を、隣り合う各セルの関係だけの情報から復元できるか？という問題です。隣り合う各セルの関係は「Bond_h」と「Bond_v」ワークシートに表示されており、それぞれ横方向と縦方向のセルの関係が、同じ値であれば＋1、反転した値であれば－1として表示されています。各セルの関係が"同じ"か"反転"かの相対的なものであるため、答えは全てが反転した画像も含まれて2通り（美白かガングロ）が存在します。また、一番上のセルの上は一番下、一番右のセルの右は一番左にそれぞれ接続しているドラクエのマップ方式（周期境界条件）を導入しています。「変更可能パラメータ」と記載のある枠線部と「Answer」ワークシートを書き換えることで、計算の条件や答えの絵柄を変更することができます。

　この問題をあらゆる組み合わせをしらみつぶしに計算すると、2¹⁰⁰通りの組み合わせを計算する必要があり、通常のPCではおよそ10²⁰年かかってしまい、厳密に解くことは困難です。しかし、SAを用いると、通常のパソコンで、25秒ほどで解くことができます。その高速性と引き換えに、時々正しい答に行きつかなかったり、問題によって解きやすい問題と解きにくい問題があったり、問題に合わせてアルゴリズムのパラメータ調整が必要だったりします。これが、「近似的に解く」ことの意味です。

問題設定のイメージ