計算手順
さて、具体的な計算手順を見ていきましょう。まず、初期状態をランダムなスピン配置とします。そして、まずランダムにスピン1つを選び、そのスピンを反転してみます。そして、反転した場合のエネルギーの増減を計算します。エネルギーの変化分ΔEは、スピン反転後のエネルギー引くスピン反転前のエネルギーで計算できるため、先ほどの式を使って、
と計算します。ここで、エネルギー変化に寄与するのは、反転させたスピンと隣接スピン4つだけのため、計算はこの部分だけで行うことができます。
エネルギーの変化分ΔEを計算したら、このスピン反転を受け入れる「受理」か、受け入れない「棄却」かを判定します。スピンを反転したことで、エネルギーが小さくなっていれば、当初の目的は、エネルギーを最小することなので、文句なしに受理します。そして、エネルギーが大きくなってしまっていた場合は、確率的に受理します。エネルギーが大きくなってしまったのだから必ず棄却すれば良いと思われるかもしれませんが、ここであえて受理する可能性を残すことで最終的な到達エネルギーを小さくできるのがSAの面白いところです。
受理確率rは、温度Tを用いて、以下の式で表します。
この判定基準はメトロポリス法と呼ばれており、これをグラフにすると以下のようになります。
つまり、温度Tが高い時はΔE>0でエネルギーが上がる場合も受け入れて、温度Tが低い時は、受け入れなくなっていきます。高温ではチャレンジングな提案も受け入れ、低温では冷静に地に足着いた判断を下すというわけです。
以下、計算フローを図示します。
量子コンピュータの得意な問題、苦手な問題
以上、シミュレーテッドアニーリング(Simulated Annealing:SA)について解説しました。SAは、通常のコンピュータで計算すると、スピン1つずつを反転させていくために非常に計算効率が悪いです。これを、量子状態を用いて物理的に実装したのが、量子アニーリング(Quantum Annealing:QA)です。SAで温度に対応するものは、QAでは横方向の磁場(横磁場)で、これを弱くしていくことで、上向きと下向きの重ね合わせ状態の各スピンが、あらかじめ設定された相互作用を満たすように、最適な組み合わせに到達していきます。重ね合わせ状態は、「観測」すると壊れてしまうのですが、十分横磁場を弱めたあとで観測すれば、各スピンは重ね合わせ状態から抜けて古典的な状態になっているため、解の組み合わせを得られるわけです。
この「観測」によって状態が壊れることは量子コンピュータにとって非常に重要な問題で、“デコヒーレンス”と呼ばれています。量子コンピュータには、現在、大きく分けて2種類あります。その一つが今回扱った量子アニーリング方式(量子イジングマシン方式とも呼ばれる)で、もう一つは“量子ゲート方式”と呼ばれているものです。量子ゲート方式は、現在のコンピュータの正統な量子版と呼ぶべきもので、1990年代から盛んに研究されており、素因数分解や検索問題を古典コンピュータより高速に解くことが可能です。しかし、現在実用化に近いのは“量子アニーリング方式”のほうで、“量子ゲート方式”の開発は難航しています。開発が遅れている理由は、まさにこのノイズにより意図しない観測が発生して量子状態が壊れるデコヒーレンスの問題があるからなのです。
以上から、量子コンピュータは、未だすべての問題を高速に解くことができる段階にはないことが分かります。量子アニーリング方式では、イジングモデルにマッピング可能な最適化問題だけを扱うことができ、また、量子ゲート方式では、素因数分解などの一部の問題に限り、通常のコンピュータより高速に解くことができます。このように、量子コンピュータには得意な問題と苦手な問題が存在するため、苦手な問題は古典コンピュータの力を借りる必要があるでしょう。量子コンピュータが実現しても古典コンピュータが無くなるわけではなく、2つのコンピュータは共存し、社会の問題解決をしていく未来を描くことができます。