An important quantum algorithm may actually be a property of nature

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

グローバーのアルゴリズムは高速探索が可能だが、量子プロセスを利用するため実装が難しいことで知られている。しかし、同アルゴリズムが、電子の振る舞いに見られる通常の現象であることを示す証拠が発見された。量子コンピュータ開発の突破口になるだけでなく、生物における遺伝暗号の謎を解明できるかもしれない。 by Emerging Technology from the arXiv2019.09.25

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

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

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

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

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

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

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

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

…

こちらは有料会員限定の記事です。 有料会員になると制限なしにご利用いただけます。

有料会員にはメリットがいっぱい！

毎月120本以上更新されるオリジナル記事で、人工知能から遺伝子療法まで、先端テクノロジーの最新動向がわかる。
オリジナル記事をテーマ別に再構成したPDFファイル「eムック」を毎月配信。
重要テーマが押さえられる。
各分野のキーパーソンを招いたトークイベント、関連セミナーに優待価格でご招待。

【冬割】実施中！年間購読料20％オフ！

人気の記事ランキング