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. 各分野のキーパーソンを招いたトークイベント、関連セミナーに優待価格でご招待。
Innovators Under 35 Japan 2020

MITテクノロジーレビューが主催するグローバル・アワード「Innovators Under 35」が2020年、日本に上陸する。特定の分野や業界だけでなく、世界全体にとって重要かつ独創的なイノベーターを発信していく取り組みを紹介しよう。

記事一覧を見る
MITテクノロジーレビュー[日本版] Vol.2/Winter 2020
MITテクノロジーレビュー[日本版] Vol.2/Winter 2020SDGs Issue

今、世界中の企業や機関の技術者・研究者たちが各地で抱える社会課題を解決し、持続可能な世界の実現へ向けて取り組んでいる「SDGs(持続可能な開発目標)」。
気候変動や貧困といった地球規模の課題の解決策としての先端テクノロジーに焦点を当て、解決に挑む人々の活動や、日本企業がSDGsを経営にどう取り入れ、取り組むべきか、日本が国際社会から期待される役割について、専門家の提言を紹介します。

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