量子コンピューターで、高速検索アルゴリズムの実行に成功

メリーランド大学の研究チームが、3キュービットの量子コンピューターで高速検索アルゴリズムの実行に成功した。20年前に考案されたアルゴリズムは、検索対象が増えても比例して計算量が増えないため、飛躍的に検索時間を短くできる。 by Emerging Technology from the arXiv2017.04.06

1996年、ベル研究所（ニュージャージー州）のコンピューター科学者ロブ・グローバー研究員は、データベースを検索するための画期的アルゴリズムを発表した。検索アルゴリズムはコンピューター科学で最も重要な研究対象といってよい。電話帳から番号を探すだけではなく、暗号データを解読するような、高度な処理でも使われる。検索アルゴリズムはコンピューター科学の基礎中の基礎として、あらゆるプログラムで使われている。

したがって、検索処理の速度向上は、プログラム全体の性能を高めることにもなり、極めて重要だ。標準的な検索方法では、検索対象の総件数におおむね比例して一定の時間がかかる。つまり最悪の場合、たったひとつの情報を見つけるために、アルゴリズムは文書全体を最初から最後まで検索することになる。

しかし、グローバーのアルゴリズムは違った。処理時間はO(N1/2)として表現でき、検索対象の総件数の平方根に比例するのだ。コンピューター科学では、わずか数%の速度向上を巡ってアルゴリズムを改善しており、指数的な速度向上は非常に有益であり、超弩級の偉業といえる。

グローバーの方法が画期的だったのは、量子力学的な、奇妙だが強力なアイデアを利用することだった。一般的なコンピューターの場合、1ビットは0か1しか表せない。しかし量子の世界では、ひとつの量子ビット（キュービット）は0と1を同時に表せる。

物理学者が「重ね合わせ状態」と呼ぶキュービットの重ね合わせが鍵だ。重ね合わせ状態では、アルゴリズムは同じ瞬間に0と1の両方を検索できる。同時にひとつ以上の要素を検索できるので、量子アルゴリズムは従来の物理学の遅いペースに制限されたアルゴリズムよりも、非常にすばやくリストを検索できるのだ。

量子アルゴリズムは量子コンピューターで実行する必要があり、グローバーが研究した1996年当時、アイデアの実現は遠い夢にすぎなかった。しかしブレイクスルーはすぐにやってきた。物理学者は1998年に史上初の原始的な量子コンピューターを発表し、同年、グローバーのアルゴリズムを量子コンピューターでどのように実行できるか示したのだ。

ただし、当時の量子コンピューターの機能は非常に制限があり、数個のキュービットで動作するが、それ以上はキュービットを増やせず、理論的にも、より大きな計算処理にスケールアップできなかった。以来、ス …

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

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

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

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

人気の記事ランキング