SHOEISHA iD

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

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

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

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

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

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

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

 以上で説明した解けない問題は、厳密に解くことはできなくても、近似的な解ならば求めることができます。また、実用上厳密に解かなくても、ある程度の精度で解が得られれば十分な場合が多く、そのような近似的な解を効率的に求めるアルゴリズムが日夜開発されています。今回は、そういった近似的なアルゴリズムの一つ「シミュレーテッドアニーリング[*]」(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」ワークシートを書き換えることで、計算の条件や答えの絵柄を変更することができます。

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

問題設定のイメージ
問題設定のイメージ

次のページ
解き方の概要

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

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

もっと読む

この記事の著者

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

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

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

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

この記事をシェア

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

おすすめ

アクセスランキング

アクセスランキング

イベント

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

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

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

メールバックナンバー

アクセスランキング

アクセスランキング