NTTの研究チームは、出力が周期性のような「構造」を持たない関数を用いた問題に対し、検証可能な量子コンピューターの優位性（「量子超越性」と呼ぶ）を示す新たな量子アルゴリズムを初めて考案した。「ショア（Shor）の素因数分解アルゴリズム」以来、約30年ぶりの本質的に新しいアイディアに基づく、検証可能な量子超越性を示すアルゴリズムだという。
NTTの研究チームは、出力が周期性のような「構造」を持たない関数を用いた問題に対し、検証可能な量子コンピューターの優位性（「量子超越性」と呼ぶ）を示す新たな量子アルゴリズムを初めて考案した。「ショア（Shor）の素因数分解アルゴリズム」以来、約30年ぶりの本質的に新しいアイディアに基づく、検証可能な量子超越性を示すアルゴリズムだという。 研究チームは、構造を持たないランダムな関数（入力nビット、出力1ビット）の出力が0になる入力を見つける問題に、その入力が誤り訂正符号にもなっているという条件を追加。量子コンピューターでは高速に解けるが、古典コンピューターでは高速に解の探索ができない問題を定義することに成功した。 量子コンピューターが高速に解ける問題として、1994年に示されたShorの素因数分解アルゴリズムがよく知られている。Shorの素因数分解アルゴリズムは、自然数の累乗の剰余が周期性という「構造」を持っていることを利用している。出力に周期性のないハッシュ関数のような「構造」を持たない関数を用いた問題について、検証可能な量子超越性を示す結果はこれまで知られていなかった。 今回の成果により、これまで実用的な量子アルゴリズムを見つけることは難しいと考えられてきた問題に対するアルゴリズムの研究が促進され、量子計算機の適用範囲が広がることが期待される。この研究は、2022月10月31日～11月3日に開催される理論計算機科学の国際会議「IEEE Symposium on Foundations of Computer Science (FOCS) 2022」で発表される。（中條）
