NTTは2022年10月31日、量子計算機が従来の計算機よりも高速で解を求めることができることを示す新たなアルゴリズムを考案したと発表した。同社によると世界初の考案となる。
量子計算機は、量子化学計算や特定のシミュレーションなど、既存の古典計算機では計算量が極端に多くなってしまうために解くことが難しい問題を、高速に解くことが可能になることが期待されている。同時に、どのような問題であれば従来型よりも量子計算機がより高速に解けるのかという研究も進められている。
これまで量子計算機がより優位性を示す問題として、Shorの素因数分解アルゴリズムが知られていた。同アルゴリズムは、自然数の累乗が周期性という「構造」を持つことを利用したアルゴリズムである（冒頭の左図）。一方、ハッシュ関数（任意のデータから、別の短い値を得る、電子署名などに使われる関数）の出力には、周期性のような「構造」はなく（冒頭の右図)、これら関数を用いた問題について、検証可能な量子優位性を示す結果は知られていなかった。
今回、「構造を持たないランダムな関数（入力nビット、出力1ビット）の出力が0になる入力を見つける」という問題に、「その入力が誤り訂正符号（データの記録や伝送の際に誤りが発生しても元の正しい符号を復元できる特徴を持つ符号）にもなっている」という条件を付け加えることで、従来の計算機よりも量子計算機が高速に解を探索できる問題を定義することに成功した。
今回の発見は、これまで知られていなかった種類の問題に対しても、高速な量子アルゴリズムが発見されることが期待され、将来の量子計算機の適用範囲を広げうる研究成果といえよう。
