|
|
■URL
http://www.lucent.com/press/0500/000523.bla.html
Lucent Technologiesの研究部門、Bell Labsの研究者が、量子コンピュータを使えば大規模なデータベースの中でたくさんの検索条件を付けても結果を見つけだすことができる新しい量子アルゴリズムを発見した。発見したのはLov Grover氏。この研究結果は、今週開かれる学会「ACM STOC」で発表される。
量子コンピュータとはミクロの世界の量子力学的な効果を用いて超並列的な計算を行なうための新しい計算の枠組み。現在、実用に耐えるだけの量子コンピュータは実現しておらず、多くの科学者が実現に向けて研究を進めている。今回の研究発表は、その量子コンピュータが実現した暁になにができるかを示してくれる好例で、今のところは純理論的なものだ。
この量子コンピュータで実現される新しいアルゴリズムを使うと、ほとんど忘れかけていたような情報でも、たくさんの検索条件を使うことによって見つけだすことができる。Glover氏は、忘れかけていた人の名前を検索することを例に挙げてこのように語る。「例えば彼の姓がJohnだったことは覚えていても名前を思い出せない時に、確かその名前がSmithとかJonesとかMillerとか普通の名前だったことは覚えているとしよう。そのときに、その名前がSmithである可能性が50%、Jonesで有る可能性が30%、Millerが20%であるとする。あなたは、彼がニューヨーク市のLicoln Centerの近くに住んでいてBroadwayがよく見えるアパートに住んでいたことを覚えていたとする。さらに、彼の電話番号の最後の4桁が自分のかかりつけの医者のと同じだったことを思い出したとする。電話帳を見てニューヨーク市に住んでいるすべてのJohn Smith氏（あるいはJones、Miller）を素早く正確に探し出す既存の方法はない。しかし、私の新しいアルゴリズムと量子コンピュータが有ればこうした検索も可能になるのだ」
Grover氏は、以前にもデータベース検索のための量子アルゴリズムを発見しており、この結果は広く知られている。こちらのアルゴリズムを使うとこれまで何百万ものデータが入っている大規模なデータベースでアイテムを見つけだすのに既存の方法では平均して50万ステップを要したのが、たったの1,000ステップで済む。このアルゴリズムは2年前にきわめて原始的な形式の量子コンピュータの原型に実装され、確認された。
このように量子コンピュータの潜在的可能性は大きいが、Bell LabsのRichart Slusher氏は「ほんの少しの量子アルゴリズムしかまだ存在しない。これらは発明するのがとても難しく、まだこの分野の歴史が浅いからだ」と研究の難しさを指摘する。
(2000/5/24)
[Reported by taiga@scientist.com]