世界初、量子超越性と暗号の安全性が等価であることを証明―従来とは異なるアプローチによる量子計算機の優位性を特徴付ける新たな理論的基盤―

概要
白川雄貴 京都大学基礎物理学研究所博士課程学生、森前智行 同准教授、山川高志 NTT社会情報研究所上席特別研究員（兼: 基礎物理学研究所特任准教授）の研究グループは、量子計算機が古典計算機よりも高速であることの必要十分条件を暗号理論の観点から明らかにしました。量子計算機は古典計算機を凌駕する計算能力が期待されていますが、この量子超越性1が存在するためには何が必要なのか、その条件はこれまで明確にされていませんでした。本研究は量子超越性と暗号の安全性が等価であることを証明し、量子超越性の必要十分条件に対して初めて明確な解答を与えました。さらに興味深いことにこの成果は、量子超越性が存在しない場合、現在安全とされている暗号機能の多くが破られることも意味します。これは、情報セキュリティ分野にとっても重要な意味を持ち、量子超越性の存在そのものが暗号の基盤と密接に結びついていることを示しています。
本研究成果は、2025年6月27日に国際会議「57th Annual ACM Symposium on Theory of Computing (STOC 2025)」にて発表され、国際学術誌「Proceedings of the 57th Annual ACM Symposium on Theory of Computing」にオンライン掲載されます。