新発見:量子アルゴリズム「グローバー探索」は自然現象だった?
グローバーのアルゴリズムは高速探索が可能だが、量子プロセスを利用するため実装が難しいことで知られている。しかし、同アルゴリズムが、電子の振る舞いに見られる通常の現象であることを示す証拠が発見された。量子コンピュータ開発の突破口になるだけでなく、生物における遺伝暗号の謎を解明できるかもしれない。 by Emerging Technology from the arXiv2019.09.25
1996年、米ニュージャージー州にあるベル研究所の量子物理学者が、N個のデータをもつデータベースを探索する新しいアルゴリズムを発表した。コンピューター科学界では長い間、この探索プロセスには約Nステップかかると考えられてきた。探索しているデータは、最悪の場合、リストの最後にある可能性があるからだ。
しかし、このアルゴリズムを開発した物理学者のロブ・グローバーは、量子力学の見慣れない法則を使ってNの平方根ステップ(√N回)で探索を実行できることを示した。
これは重大な発見だった。データベースの探索は、コンピューター科学の基本的なタスクであり、電話番号の検索から暗号コードの解読に至るまであらゆるものに使用されるからだ。探索の高速化は間違いなく大きな進歩をもたらす。
量子力学はさらなる展開をもたらした。発表当時、グローバーのアルゴリズムは、古典アルゴリズムと比較して高速なことが証明された2番目の量子アルゴリズムにすぎなかった(最初のものは1994年にピーター・ショアが考案した量子因数分解アルゴリズム)。しかし、グローバーの研究は、現在も進行中の量子コンピューティング革命の下地を作る重要な要素となったのだ。
グローバーのアルゴリズムには大きな関心が寄せられたが、実装に難しい技術的課題がともなうため時間がかかっている。グローバーのアルゴリズムを実装可能な最初の量子コンピューターは1998年に登場したが、スケーラブルな量子コンピューターは2017年まで登場せず、それも3キュービットでしか動作しなかった。そのため、グローバーのアルゴリズムを実装する新しい方法が切実に求められている。
最近、このことは広く考えられているより簡単かもしれないと、フランスのツーロン大学のステファン・ギレ博士の研究チームが発表した。同研究チームは、グローバーの探索アルゴリズムが自然的に発生する現象である証拠を得たという。「特定の条件下において、電子がグローバーの探索アルゴリズムに自然に従って、材料内の欠陥を探索することを示す初の証拠を得ました」。
ギレ博士らの研究チームの発見が量子コンピューティングに影響を及ぼすのは明らかだが、それよりもはるかに深い意味を持つものかもしれない。かねてより、量子探索が生命の起源に関する最大の謎を説明できるかどうか、理論家の間で議論されてきた。グローバーの探索アルゴリズムが自然界で発生するという考え方は、この難問を解決に導く可能性がある。
まず基礎知識を少し説明しよう。グローバーのアルゴリズムは非常に基本的なものなので、応用の幅が広い。その1つに、量子粒子が表面上のある位置から別の位置にランダムに移動する様子を示す量子ウォークがある。
…
- 人気の記事ランキング
-
- Kids are learning how to make their own little language models 作って学ぶ生成AIモデルの仕組み、MITが子ども向け新アプリ
- These companies are creating food out of thin air 大豆・昆虫の次は微生物、 空気からタンパク質を作る 「夢の食品工場」
- The winners of Innovators under 35 Japan 2024 have been announced MITTRが選ぶ、 日本発U35イノベーター 2024年版
- Google DeepMind is making its AI text watermark open source AI生成テキストを見抜く「電子透かし」、グーグルが無償公開