量子コンピューターで、高速検索アルゴリズムの実行に成功
メリーランド大学の研究チームが、3キュービットの量子コンピューターで高速検索アルゴリズムの実行に成功した。20年前に考案されたアルゴリズムは、検索対象が増えても比例して計算量が増えないため、飛躍的に検索時間を短くできる。 by Emerging Technology from the arXiv2017.04.06
1996年、ベル研究所(ニュージャージー州)のコンピューター科学者ロブ・グローバー研究員は、データベースを検索するための画期的アルゴリズムを発表した。検索アルゴリズムはコンピューター科学で最も重要な研究対象といってよい。電話帳から番号を探すだけではなく、暗号データを解読するような、高度な処理でも使われる。検索アルゴリズムはコンピューター科学の基礎中の基礎として、あらゆるプログラムで使われている。
したがって、検索処理の速度向上は、プログラム全体の性能を高めることにもなり、極めて重要だ。標準的な検索方法では、検索対象の総件数におおむね比例して一定の時間がかかる。つまり最悪の場合、たったひとつの情報を見つけるために、アルゴリズムは文書全体を最初から最後まで検索することになる。
しかし、グローバーのアルゴリズムは違った。処理時間はO(N1/2)として表現でき、検索対象の総件数の平方根に比例するのだ。コンピューター科学では、わずか数%の速度向上を巡ってアルゴリズムを改善しており、指数的な速度向上は非常に有益であり、超弩級の偉業といえる。
グローバーの方法が画期的だったのは、量子力学的な、奇妙だが強力なアイデアを利用することだった。一般的なコンピューターの場合、1ビットは0か1しか表せない。しかし量子の世界では、ひとつの量子ビット(キュービット)は0と1を同時に表せる。
物理学者が「重ね合わせ状態」と呼ぶキュービットの重ね合わせが鍵だ。重ね合わせ状態では、アルゴリズムは同じ瞬間に0と1の両方を検索できる。同時にひとつ以上の要素を検索できるので、量子アルゴリズムは従来の物理学の遅いペースに制限されたアルゴリズムよりも、非常にすばやくリストを検索できるのだ。
量子アルゴリズムは量子コンピューターで実行する必要があり、グローバーが研究した1996年当時、アイデアの実現は遠い夢にすぎなかった。しかしブレイクスルーはすぐにやってきた。物理学者は1998年に史上初の原始的な量子コンピューターを発表し、同年、グローバーのアルゴリズムを量子コンピューターでどのように実行できるか示したのだ。
ただし、当時の量子コンピューターの機能は非常に制限があり、数個のキュービットで動作するが、それ以上はキュービットを増やせず、理論的にも、より大きな計算処理にスケールアップできなかった。以来、ス …
- 人気の記事ランキング
-
- The winners of Innovators under 35 Japan 2024 have been announced MITTRが選ぶ、 日本発U35イノベーター 2024年版
- Kids are learning how to make their own little language models 作って学ぶ生成AIモデルの仕組み、MITが子ども向け新アプリ
- These companies are creating food out of thin air 大豆・昆虫の次は微生物、 空気からタンパク質を作る 「夢の食品工場」
- The race to find new materials with AI needs more data. Meta is giving massive amounts away for free. メタ、材料科学向けの最大規模のデータセットとAIモデルを無償公開