SHOEISHA iD

※旧SEメンバーシップ会員の方は、同じ登録情報(メールアドレス&パスワード)でログインいただけます

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

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

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

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

  • X ポスト
  • このエントリーをはてなブックマークに追加

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

  • X ポスト
  • このエントリーをはてなブックマークに追加

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

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

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

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

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

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

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

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

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

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

この記事は参考になりましたか?

  • X ポスト
  • このエントリーをはてなブックマークに追加
ITエンジニアのための量子コンピュータ入門連載記事一覧

もっと読む

この記事の著者

宇津木 健(ウツギ タケル)

 「量子情報勉強会」主催。東京工業大学大学院物理情報システム専攻卒業後、メーカーの研究所にて光学関係の研究開発を行っています。 また、中野付近でお芝居をしています! Twitter:@utsugitakeru

※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です

この記事は参考になりましたか?

この記事をシェア

  • X ポスト
  • このエントリーをはてなブックマークに追加
CodeZine(コードジン)
https://codezine.jp/article/detail/9491 2016/06/24 14:00

おすすめ

アクセスランキング

アクセスランキング

イベント

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

新規会員登録無料のご案内

  • ・全ての過去記事が閲覧できます
  • ・会員限定メルマガを受信できます

メールバックナンバー

アクセスランキング

アクセスランキング