KADOKAWA Technology Review
×
ニュース Insider Online限定
Quantum Computing Now Has a Powerful Search Tool

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

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

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

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

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

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

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

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

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

こちらは有料会員限定の記事です。
有料会員になると制限なしにご利用いただけます。
有料会員にはメリットがいっぱい!
  1. 毎月120本以上更新されるオリジナル記事で、人工知能から遺伝子療法まで、先端テクノロジーの最新動向がわかる。
  2. オリジナル記事をテーマ別に再構成したPDFファイル「eムック」を毎月配信。
    重要テーマが押さえられる。
  3. 各分野のキーパーソンを招いたトークイベント、関連セミナーに優待価格でご招待。
人気の記事ランキング
  1. The winners of Innovators under 35 Japan 2024 have been announced MITTRが選ぶ、 日本発U35イノベーター 2024年版
  2. Kids are learning how to make their own little language models 作って学ぶ生成AIモデルの仕組み、MITが子ども向け新アプリ
  3. The race to find new materials with AI needs more data. Meta is giving massive amounts away for free. メタ、材料科学向けの最大規模のデータセットとAIモデルを無償公開
日本発「世界を変える」U35イノベーター

MITテクノロジーレビューが20年以上にわたって開催しているグローバル・アワード「Innovators Under 35 」。2024年受賞者決定!授賞式を11/20に開催します。チケット販売中。 世界的な課題解決に取り組み、向こう数十年間の未来を形作る若きイノベーターの発掘を目的とするアワードの日本版の最新情報を随時発信中。

特集ページへ
MITTRが選んだ 世界を変える10大技術 2024年版

「ブレークスルー・テクノロジー10」は、人工知能、生物工学、気候変動、コンピューティングなどの分野における重要な技術的進歩を評価するMITテクノロジーレビューの年次企画だ。2024年に注目すべき10のテクノロジーを紹介しよう。

特集ページへ
フォローしてください重要なテクノロジーとイノベーションのニュースをSNSやメールで受け取る