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

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

　前回は、量子コンピュータの基本的な考え方である、0と1の重ね合わせ状態を使って高速計算を実現する方法と、量子コンピュータの一方式である「量子アニーリング」の動作原理について簡単に説明しました。今回は、量子コンピュータの動作をより直感的に理解することをめざして、エクセルVBAを用い、量子アニーリングの古典版である「シミュレーテッドアニーリング」というアルゴリズムを作ってみます。

普通のコンピュータが解けない問題とは？

　第1回において、機械学習などの分野では、普通のコンピュータでは現実的な時間で解くことができない問題が多く存在し、そういった問題を解くことができる可能性を量子コンピュータに見出している、と説明しました。今回のテーマであるエクセルによる実装の前に、まずはこの“解けない問題”についてもう少し詳しく説明し、普通のコンピュータが“できないこと”とは何かを明確にしましょう。

　まず、ここで言う“解けない問題”とは、正確には「多項式時間での解法が知られていない」問題と定義されます。「多項式時間ってなんですのん？」と思う人多数でしょう。順を追って説明しましょう。まず、下の図を見てください。

解ける問題と解けない問題のイメージ

　どんな問題にも、必ず入力があります。プログラムでいうところの“引数”です。そして、解ける問題とは、入力（引数）の数（入力サイズ）に対して計算しなければならない回数がそれほど多くならない問題のことです。例えば「入力の数の中から最大値を求めよ」という問題は、入力の数が6個の場合、1つずつ大小関係を比較するという計算をしていくとおよそ6回の計算で解が求まります。入力の数が10個なら10回、100個なら100回ですから、問題「最大値を求めよ」の計算回数は入力サイズNに対してN回の計算回数が必要です。

　他にも「入力の数の合計を求めよ」もN回、「入力の数の中から剰余が最大となる2つのペアを選び出せ」は、総当たり戦のように2つのペアをすべて計算すればよいのでおよそN²回など、我々の身の回りにある問題の多くはN^k（k：整数）の多項式で計算回数を見積もることができます。こういった、およそN^k回の計算回数となるような問題を、Nの多項式で計算時間を見積もることができることから、「多項式時間で解ける問題」と呼びます。

　一方、「多項式時間での解法が知られていない問題」とはどんな問題でしょうか。例えば「入力の数において、積が40に最も近い組み合わせを求めよ」という問題があったとします。どう解けばよいでしょう。普通に考えると、入力の数のすべての組み合わせを書き出して、積を計算し、40に最も近いものを探すことになるでしょう。組み合わせは、入力の数が6個であれば、2⁶＝64個あります。つまり、64回掛け算の計算をして40に最も近い組み合わせを探す必要があります。この問題は、入力の数が10個の時は2¹⁰＝1,024回、20個の時は2²⁰＝1,048,576回、30個の時は2³⁰＝1,073,741,824とどんどん増えていきます。

　入力サイズNに対して、k^N（k：整数）回の計算回数を必要とする、つまり指数関数的に計算回数が増加していくような問題を「多項式時間での解法が知られていない問題」と言って、普通のコンピュータで“解けない問題”と呼んでいるのです。実際には、入力サイズが小さければ指数関数的な計算回数でも解くことができるので、くどさをいとわず言えば、「普通のコンピュータで“入力サイズが大きくなってくると、急激に計算回数が増加して”解けない問題」となります（下図参照）。こういった問題に対して量子コンピュータの出番となるわけです。

解ける問題と解けない問題の入力サイズ（引数の数）Nに対する計算回数（Oは計算回数のオーダーを表す記号）