2008-10-24掲載
『週刊リョーシカ!』
「量子コンピュータ編」も
残すところ、あと2回。
この「量子コンピュータ編」をもって
連載完結となります。
慣れ親しんだ
ヒルベルト空間
とも
もうすぐお別れ……
というわけで、今週はさっそく
アルゴリズムへ進みたいと思いますよ。
量子計算にとってアルゴリズムとは何か?
どんなアルゴリズムがあるのか?
さあ、基本的なところを
押さえてまいりましょう。
いやー、知らなかったなあ~。
どうしましたか?
あのね、「アルゴリズム」って
「リズム(rhythm)」と
関係あるのかな? と思うと……
ないでしょう。
そうなんです。
「algorithm」で、
スペルも違うんですよ。
ふむふむ。
でもって、なんと!
バクダットの数学者・
アル・フワーリズミーに
由来するんですって。
それがなんと9世紀の人だそうで……。
ふむふむ。
びっくりしました。
アルゴリズムって、神秘的!?
アルゴリズムは数学的です。
どうしたら問題が解けるか、
その方法を示すものですね。
そうでした。
量子コンピュータで
具体的な問題を解こう
という場合について
考えていくのでしたね。
すると、問題を解くのに
まず必要なのは、
アルゴリズム!
はい。量子コンピュータが
量子ならではの高いパフォーマンスを
実現するのであれば、
量子系の持つあの広い空間を
きっと活かしているはずです。
ふむむ。
アルゴリズムが示す
手順のひとつひとつは
「ユニタリー変換」で
考えることができます。
アルゴリズムに従って
各々のユニタリー変換を
ゲートの組み合わせにしていき
量子計算を実行することになります。
そうかそうか。
これまでは、ユニタリー変換が
どうなっていて、ということを
物理的に理解してきたんだけど
今度は、見方を変えると──
同じユニタリー変換も、
数学的な手順を担っているもの
と考えられるわけですね?
そのようにも言えますね。
ここまで来たら、
では実際に量子コンピュータ上で
アルゴリズムを実行したら、
どのくらいの速さでできるか
を知ることができます。
なんでスピードが大事なんですか?
量子でやるより、古典的な
コンピュータのほうが速ければ、
古典的なコンピュータで計算したほうが
いいと思いませんか?
なるほど。
そこでまず、
量子系の持つ広い空間を活かして
ほんとうに量子計算が行えるのか
というところが問題になります。
量子の重ね合わせ状態に注目し、
これが行えることを最初に示したのが、
ドイチェージョサのアルゴリズムです。
ドイチェージョサのアルゴリズムは、
量子コンピュータのための
最初の画期的なアルゴリズムとして
大きな注目を集めました。
ふむむ。
すると、このアルゴリズムに基づいて、
ゲートへ分解して、
量子コンピュータで実行できるように
すればいいわけですね?
はい。しかし残念ながら、
そのようにしてみると、
ドイチェージョサのアルゴリズムは
期待されたような目覚ましい
スピードアップを、
実現することはできませんでした。
うーん、残念!
でも量子コンピュータの
アルゴリズムといえば、
素因数分解を解く
有名なのがありますよね?
はい。ショアのアルゴリズムですね。
ドイチェージョサのアルゴリズムの後、
素因数分解を解くものとして発表され、
世界に大きな衝撃を与えました。
どうしてそんなに衝撃だったんですか?
現在のネット社会では、
古典的なコンピュータが
大きな数の素因数分解を解くのに
時間がかかる点に
セキュリティの基礎を置いているからです。
これを高速に解く
新しいコンピュータが出現すれば
現在運用中のセキュリティのしくみが
成り立たなくなることになります。
そりゃ、確かに
話題になるはずですね。
ええ。しかも今度は、
見事な高速さも実現していました。
とはいえ、そのような
量子コンピュータは
まだまだ実現しませんので、
近いうちにセキュリティを脅かす
といったことはありません。
なあんだ。
ただ、アルゴリズムの中の何が、
量子コンピュータに
スピードアップをもたらすのか?
という点は重要です。
しかしそのことは、現在まだ
明確にわかっているわけではありません。
また量子コンピュータはどのような種類の、
どのくらい難しい計算が解けるのか、
という問題が、
新しいアルゴリズムが登場することで
明らかになる可能性もあるわけです。
アルゴリズムって大事なんですね。
今後の研究がまさに楽しみな分野です。
(つづく)
今週は「アルゴリズム」をお届けしました。
アル・フワーリズミー
↓
アル・コワリズミ
↓
アルゴリズム
という語源には
ちょっとびっくり!
ちなみにアルゴリズムの「アル」は
アルハンブル宮殿の「アル」と同じで
もとは冠詞なんだそうです。
この「アルゴリズム」さえわかれば
あとは実際のプログラムで
問題を解くだけ!
というところまで行けるわけですね。
量子コンピュータが潜在的に持つ
ハイ・パフォーマンスな性能を示すには、
この「あと一歩!」のアルゴリズムが
どうしても欠かせません。
さて、というわけで
次回はとうとう最終回。
どうぞお楽しみに。