NTTは10月31日、出力が周期性のような「構造」を持たない関数を用いた問題に対し、検証可能な量子コンピュータの既存(古典)のコンピュータに対する優位性である「量子超越性」を示す新たな量子アルゴリズムを考案したことを発表した。

同成果は、NTTの山川高志特別研究員、NTT Research Cryptography & Information Security LabのMark Zandry博士の2名によるもの。詳細は、米・コロラド州デンバーで11月3日まで開催中の理論計算機科学の国際会議「IEEE Symposium on Foundations of Computer Science (FOCS) 2022」にて10月31日に発表されたという。

量子コンピュータは、量子化学計算やある種のシミュレーションなど、古典コンピュータでは計算時間が爆発的に増加してしまうために実用的な時間で解くことが困難な問題を、高速に解くことができると期待されている。また、計算機科学の理論面からも、どのような問題であれば量子超越性、すなわち量子コンピュータが古典コンピュータよりも高速に解けることが示されるのか、という研究も進められている。

量子コンピュータが高速に解ける問題として、1994年に示された「Shorの素因数分解アルゴリズム」がよく知られているが、どのような問題であれば量子コンピュータで高速に解けるのかという点については、未解明な点も多くあるという。

Shorの素因数分解アルゴリズムは、自然数の累乗の剰余が周期性という「構造」を持っていることを利用したアルゴリズムだが、ハッシュ関数の出力には周期性のような「構造」がなく、このような関数を用いた問題について、検証可能な量子超越性を示す結果はこれまで知られていなかったという。そこで山川特別研究員とザンドリー博士は今回、「構造」を持たない関数のみを用いた問題に対し、検証可能な量子超越性を示す量子アルゴリズムを定義することにしたという。

  • 自然数の累乗の剰余に見られる周期性という「構造」の例

    自然数の累乗の剰余に見られる周期性という「構造」の例 (出所:NTT Webサイト)

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

  • ハッシュ関数の出力には周期性のような「構造」は見られない

    ハッシュ関数の出力には周期性のような「構造」は見られない (出所:NTT Webサイト)

なお、この「構造」を持たない問題に対する検証可能な量子超越性を示す量子アルゴリズムの発見により、これまで量子コンピュータによる高速なアルゴリズムが知られていなかった種類の問題に対しても、高速な量子アルゴリズムが発見されることが期待されると研究チームでは説明しているほか、将来の量子コンピュータの適用範囲を広げうる、ブレークスルーといえる研究成果としている。