新発見：量子アルゴリズム「グローバー探索」は自然現象だった？

1996年、米ニュージャージー州にあるベル研究所の量子物理学者が、N個のデータをもつデータベースを探索する新しいアルゴリズムを発表した。コンピューター科学界では長い間、この探索プロセスには約Nステップかかると考えられてきた。探索しているデータは、最悪の場合、リストの最後にある可能性があるからだ。

しかし、このアルゴリズムを開発した物理学者のロブ・グローバーは、量子力学の見慣れない法則を使ってNの平方根ステップ（√N回）で探索を実行できることを示した。

これは重大な発見だった。データベースの探索は、コンピューター科学の基本的なタスクであり、電話番号の検索から暗号コードの解読に至るまであらゆるものに使用されるからだ。探索の高速化は間違いなく大きな進歩をもたらす。

量子力学はさらなる展開をもたらした。発表当時、グローバーのアルゴリズムは、古典アルゴリズムと比較して高速なことが証明された2番目の量子アルゴリズムにすぎなかった（最初のものは1994年にピーター・ショアが考案した量子因数分解アルゴリズム）。しかし、グローバーの研究は、現在も進行中の量子コンピューティング革命の下地を作る重要な要素となったのだ。

グローバーのアルゴリズムには大きな関心が寄せられたが、実装に難しい技術的課題がともなうため時間がかかっている。グローバーのアルゴリズムを実装可能な最初の量子コンピューターは1998年に登場したが、スケーラブルな量子コンピューターは2017年まで登場せず、それも3キュービットでしか動作しなかった。そのため、グローバーのアルゴリズムを実装する新しい方法が切実に求められている。

最近、このことは広く考えられているより簡単かもしれないと、フランスのツーロン大学のステファン・ギレ博士の研究チームが発表した。同研究チームは、グローバーの探索アルゴリズムが自然的に発生する現象である証拠を得たという。「特定の条件下において、電子がグローバーの探索アルゴリズムに自然に従って、材料内の欠陥を探索することを示す初の証拠を得ました」。

ギレ博士らの研究チームの発見が量子コンピューティングに影響を及ぼすのは明らかだが、それよりもはるかに深い意味を持つものかもしれない。かねてより、量子探索が生命の起源に関する最大の謎を説明できるかどうか、理論家の間で議論されてきた。グローバーの探索アルゴリズムが自然界で発生するという考え方は、この難問を解決に導く可能性がある。

まず基礎知識を少し説明しよう。グローバーのアルゴリズムは非常に基本的なものなので、応用の幅が広い。その1つに、量子粒子が表面上のある位置から別の位置にランダムに移動する様子を示す量子ウォークがある。

…