フラッシュ2022年11月1日

• NTT、量子超越性を示す新たなアルゴリズムを30年ぶりに考案

  by MITテクノロジーレビュー編集部 [MIT Technology Review Japan]

  NTTの研究チームは、出力が周期性のような「構造」を持たない関数を用いた問題に対し、検証可能な量子コンピューターの優位性（「量子超越性」と呼ぶ）を示す新たな量子アルゴリズムを初めて考案した。「ショア（Shor）の素因数分解アルゴリズム」以来、約30年ぶりの本質的に新しいアイディアに基づく、検証可能な量子超越性を示すアルゴリズムだという。

  研究チームは、構造を持たないランダムな関数（入力nビット、出力1ビット）の出力が0になる入力を見つける問題に、その入力が誤り訂正符号にもなっているという条件を追加。量子コンピューターでは高速に解けるが、古典コンピューターでは高速に解の探索ができない問題を定義することに成功した。

  量子コンピューターが高速に解ける問題として、1994年に示されたShorの素因数分解アルゴリズムがよく知られている。Shorの素因数分解アルゴリズムは、自然数の累乗の剰余が周期性という「構造」を持っていることを利用している。出力に周期性のないハッシュ関数のような「構造」を持たない関数を用いた問題について、検証可能な量子超越性を示す結果はこれまで知られていなかった。

  今回の成果により、これまで実用的な量子アルゴリズムを見つけることは難しいと考えられてきた問題に対するアルゴリズムの研究が促進され、量子計算機の適用範囲が広がることが期待される。この研究は、2022月10月31日～11月3日に開催される理論計算機科学の国際会議「IEEE Symposium on Foundations of Computer Science (FOCS) 2022」で発表される。

  （中條）

  • 4

• 人気の記事ランキング

  1. What is vibe coding, exactly? バイブコーディングとは何か？ AIに「委ねる」プログラミング新手法
  2. A Google Gemini model now has a “dial” to adjust how much it reasons 推論モデルは「考えすぎ」、グーグルがGeminiに調整機能
  3. Meet the researchers testing the “Armageddon” approach to asteroid defense 惑星防衛の最終戦略 科学者たちが探る 「核爆発」研究の舞台裏
  4. Anthropic can now track the bizarre inner workings of a large language model 大規模言語モデルは内部で 何をやっているのか？ 覗いて分かった奇妙な回路