週刊リョーシカ！

2008-10-24掲載
『週刊リョーシカ！』「量子コンピュータ編」も残すところ、あと2回。この「量子コンピュータ編」をもって連載完結となります。慣れ親しんだヒルベルト空間とももうすぐお別れ…… というわけで、今週はさっそくアルゴリズムへ進みたいと思いますよ。量子計算にとってアルゴリズムとは何か？どんなアルゴリズムがあるのか？さあ、基本的なところを押さえてまいりましょう。
	いやー、知らなかったなあ～。
	どうしましたか？
	あのね、「アルゴリズム」って「リズム（rhythm）」と関係あるのかな？　と思うと……
	ないでしょう。
	そうなんです。「algorithm」で、スペルも違うんですよ。
	ふむふむ。
	でもって、なんと！バクダットの数学者・アル・フワーリズミーに由来するんですって。それがなんと9世紀の人だそうで……。

	ふむふむ。
	びっくりしました。アルゴリズムって、神秘的!?
	アルゴリズムは数学的です。どうしたら問題が解けるか、その方法を示すものですね。
	そうでした。
	量子コンピュータで具体的な問題を解こうという場合について考えていくのでしたね。
	すると、問題を解くのにまず必要なのは、アルゴリズム！
	はい。量子コンピュータが量子ならではの高いパフォーマンスを実現するのであれば、量子系の持つあの広い空間をきっと活かしているはずです。
	ふむむ。
	アルゴリズムが示す手順のひとつひとつは「ユニタリー変換」で考えることができます。アルゴリズムに従って各々のユニタリー変換をゲートの組み合わせにしていき量子計算を実行することになります。

	そうかそうか。これまでは、ユニタリー変換がどうなっていて、ということを物理的に理解してきたんだけど今度は、見方を変えると── 同じユニタリー変換も、数学的な手順を担っているものと考えられるわけですね？
	そのようにも言えますね。ここまで来たら、では実際に量子コンピュータ上でアルゴリズムを実行したら、どのくらいの速さでできるかを知ることができます。
	なんでスピードが大事なんですか？
	量子でやるより、古典的なコンピュータのほうが速ければ、古典的なコンピュータで計算したほうがいいと思いませんか？
	なるほど。
	そこでまず、量子系の持つ広い空間を活かしてほんとうに量子計算が行えるのかというところが問題になります。量子の重ね合わせ状態に注目し、これが行えることを最初に示したのが、ドイチェージョサのアルゴリズムです。ドイチェージョサのアルゴリズムは、量子コンピュータのための最初の画期的なアルゴリズムとして大きな注目を集めました。
	ふむむ。すると、このアルゴリズムに基づいて、ゲートへ分解して、量子コンピュータで実行できるようにすればいいわけですね？
	はい。しかし残念ながら、そのようにしてみると、ドイチェージョサのアルゴリズムは期待されたような目覚ましいスピードアップを、実現することはできませんでした。
	うーん、残念！でも量子コンピュータのアルゴリズムといえば、素因数分解を解く有名なのがありますよね？
	はい。ショアのアルゴリズムですね。ドイチェージョサのアルゴリズムの後、素因数分解を解くものとして発表され、世界に大きな衝撃を与えました。

	どうしてそんなに衝撃だったんですか？
	現在のネット社会では、古典的なコンピュータが大きな数の素因数分解を解くのに時間がかかる点にセキュリティの基礎を置いているからです。これを高速に解く新しいコンピュータが出現すれば現在運用中のセキュリティのしくみが成り立たなくなることになります。
	そりゃ、確かに話題になるはずですね。
	ええ。しかも今度は、見事な高速さも実現していました。とはいえ、そのような量子コンピュータはまだまだ実現しませんので、近いうちにセキュリティを脅かすといったことはありません。
	なあんだ。
	ただ、アルゴリズムの中の何が、量子コンピュータにスピードアップをもたらすのか？という点は重要です。しかしそのことは、現在まだ明確にわかっているわけではありません。また量子コンピュータはどのような種類の、どのくらい難しい計算が解けるのか、という問題が、新しいアルゴリズムが登場することで明らかになる可能性もあるわけです。
	アルゴリズムって大事なんですね。
	今後の研究がまさに楽しみな分野です。
（つづく）
今週は「アルゴリズム」をお届けしました。アル・フワーリズミー ↓ アル・コワリズミ ↓ アルゴリズムという語源にはちょっとびっくり！ちなみにアルゴリズムの「アル」はアルハンブル宮殿の「アル」と同じでもとは冠詞なんだそうです。この「アルゴリズム」さえわかればあとは実際のプログラムで問題を解くだけ！　というところまで行けるわけですね。量子コンピュータが潜在的に持つハイ・パフォーマンスな性能を示すには、この「あと一歩！」のアルゴリズムがどうしても欠かせません。さて、というわけで次回はとうとう最終回。どうぞお楽しみに。