フラッシュ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 you may have missed about GPT-5 肩透かしだったGPT-5、オープンAIの方針転換に危うさ
  2. Promotion MITTR Emerging Technology Nite #34 【9/10開催】伝説の玩具「アームトロン」開発者が誕生秘話を語る
  3. Five ways that AI is learning to improve itself 迫る「知能爆発」の兆し、 AIによるAIの進化は 5つの領域で起きている
  4. The greenhouse gases we’re not accounting for 見過ごされた気候フィードバック効果、温暖化が数年早まる可能性も
  5. It’s pretty easy to get DeepSeek to talk dirty 「お堅い」Claude、性的会話に応じやすいAIモデルは？