京都大学(京大)とNTTの両者は6月23日、これまで明確でなかった量子コンピュータが古典(通常)コンピュータを凌駕する計算能力である「量子超越性」の存在条件について、特定のタスクにおけるその必要十分条件を暗号理論の観点から解明したと共同で発表した。

  • 特定のタスクにおける量子超越性の存在には暗号の安全性の仮定が必要十分であると解明

    今回の研究では、特定のタスクにおける量子超越性(左)の存在には、暗号の安全性(右)を仮定することが、必要十分であると解明された(出所:NTT Webサイト)

同成果は、京大 基礎物理学研究所(YITP)の白川雄貴大学院生、同・森前智行准教授、NTT 社会情報研究所の山川高志上席特別研究員(YITP 特任准教授兼任)らの共同研究チームによるもの。詳細については、6月27日までチェコ・プラハで開催中の理論計算機科学分野の国際会議「STOC 2025」で27日に口頭発表が行われる予定だ。

量子コンピュータの優位性を特徴づける理論的基盤を構築

量子コンピュータは、現在の古典コンピュータに対して性能面で完全に優位であるかのように受け取られがちだ。特定の計算問題において、量子コンピュータが古典コンピュータよりも真に高速であることを量子超越性という。しかし、量子超越性は常に存在するとは限らないため、量子コンピュータの性能を正しく理解し、その能力を活かすには、「どのような条件下で量子超越性が存在するのか」、「そのためには何が必要か」といった疑問への明確な回答が不可欠だ。

量子超越性についてはこれまでにも、例えば素因数分解の困難性などのさまざまな条件が提示され、その条件下で存在が証明されてきた。しかしそれらはあくまで十分条件であり、本当に必要なのかは不明瞭な点だったとのこと。そこで研究チームは今回、量子超越性の理論的な土台をより強固にするため、その必要十分条件の明確化を目指したという。

今回の研究では、量子超越性の必要十分条件として、「暗号が存在するなら量子超越性が存在し、また逆に量子超越性が存在するなら暗号が存在する」という関係を特定。近年、量子暗号の分野で提案されている特定の暗号機能の安全性と量子超越性の存在が等価であることが示された。この等価性は、暗号機能が安全であれば量子超越性を示すタスクを構成でき、量子超越性が存在するなら安全な暗号機能が構成できることを意味する。

  • 従来の研究と今回の内容の比較

    従来の研究と今回の研究の内容の比較(出所:NTT Webサイト)

研究チームによると今回の成果は、量子計算理論と暗号理論の技術と考え方を統合し、一見無関係に見える「量子超越性」と「暗号の安全性」を結びつける新しい枠組みの提案によって実現されたという。特に着目されたのは、「非効率検証可能量子性証明」(IV-PoQ)と呼ばれる対話型プロトコルだ。これは、量子コンピュータを持たない検証者が、量子コンピュータを持つ証明者とやり取りすることで、相手が真に量子計算能力を持つのかを検証できる仕組みだ。このプロトコルが存在するための必要十分条件が、ある種の暗号機能の安全性と一致することが数学的に証明され、量子超越性と暗号の安全性が等価であることが示されたのである。

  • 量子超越性の定義

    量子超越性の定義(出所:NTT Webサイト)

今回の研究は、量子計算理論と暗号理論の密接な関係を明らかにしたといい、これにより両分野に以下のような相互的な影響が期待されるとのこと。まずは、将来的な量子超越性の実証実験や、さらなる理論研究が暗号理論的により強固な基盤の下で進められることが見込まれるとした。

なお今回の成果は、「もし量子超越性が存在しないならば、現在安全とされている多くの暗号機能の安全性が破綻する」ことも意味するという。ここでの安全性が破綻する暗号機能とは、量子暗号だけでなく、現在古典コンピュータで用いられている暗号や、今後の普及が急がれる耐量子コンピュータ暗号も含むため、情報セキュリティ分野にとっても非常に重要な示唆とした。これは、量子コンピュータの優位性と暗号理論の基盤が深く関係していることを明らかにしている。

したがって今回の成果は、量子コンピュータの実現後も安全に使用できる暗号の構成に向けた基盤理論への貢献が期待されるという。また研究チームは、暗号理論に基づいた量子超越性研究の新たな応用を切り拓く可能性を示唆するとしている。