日本電信電話（以下、NTT）は、出力が周期性のような「構造」を持たない関数を用いた問題に対し、検証可能な量子計算機の優位性（量子優位性）を示す新たな量子アルゴリズムを世界で初めて考案したことを発表した。

これは、Shorの素因数分解アルゴリズム（1994年）以来、約30年ぶりの本質的に新しいアイディアに基づく、検証可能な量子優位性を示すアルゴリズムの提案だという。

同成果により、これまで実用的な量子アルゴリズムを見つけることは難しいと考えられてきた問題に対するアルゴリズムの研究が促進され、将来の量子計算機の適用範囲が広がることが期待されるとのことだ。

なお、同成果は理論計算機科学における最高峰の国際会議であるIEEE Symposium on Foundations of Computer Science（FOCS）2022において発表されるとしている。

■研究の成果

Shorの素因数分解アルゴリズムは、自然数の累乗の剰余が周期性という「構造」を持っていることを利用したアルゴリズム（図1）。一方でハッシュ関数の出力には、周期性のような「構造」はない（図2）。

ハッシュ関数のような「構造」を持たない関数を用いた問題について、検証可能な量子優位性を示す結果はこれまで知られていなかったという。

NTTの山川高志特別研究員は、NTT Research Cryptography & Information Security LabのMark Zandry博士と共著で投稿した論文において、「構造」を持たない関数のみを用いた問題に対し、検証可能な量子優位性を示す量子アルゴリズムを世界で初めて示したとしている。

山川らは、構造を持たないランダムな関数（入力nビット、出力1ビット）の出力が0になる入力を見つけるという問題に、その入力が誤り訂正符号にもなっているという条件を加えることで、量子計算機では高速に解けるが、古典計算機では高速に解の探索ができないという問題を定義することに成功。

この「構造」を持たない問題に対する検証可能な量子優位性を示す量子アルゴリズムの発見により、これまで量子計算機による高速なアルゴリズムが知られていなかった種類の問題に対しても、高速な量子アルゴリズムが発見されることが期待され、将来の量子計算機の適用範囲を広げうる、ブレークスルーといえる研究成果とのことだ。

研究の成果、図1・図2

同成果はarXivに公開された時から注目を集め、山川らへのインタビュー取材をもとに、サイエンス分野の著名なウェブサイトであるQuanta Magazineへの記事掲載もされたという。

また、同成果は理論計算機科学における最高峰の国際会議であるIEEE Symposium on Foundations of Computer Science (FOCS) 2022に採択され、10/31のSession 1Bにおいて発表される予定。

なお、山川特別研究員の論文がFOCSに採択されるのは、昨年度に続き2年連続の快挙となるとのことだ。