フラッシュ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. An ancient man’s remains were hacked apart and kept in a garage 切り刻まれた古代人、破壊的発掘から保存重視へと変わる考古学
  2. AI reasoning models can cheat to win chess games 最新AIモデル、勝つためなら手段選ばず　チェス対局で明らかに
  3. This startup just hit a big milestone for green steel production グリーン鉄鋼、商業化へ前進　ボストン・メタルが1トンの製造に成功
  4. This artificial leaf makes hydrocarbons out of carbon dioxide 人工光合成が次段階へ、新型人工葉が炭化水素合成に成功