量子コンピューターの「量子超越性」の必要十分条件を世界で初めて証明、京大とNTTが発表

　京都大学基礎物理学研究所の白川雄貴氏（博士課程学生）と森前智行氏（准教授）、および、NTT社会情報研究所の山川高志氏（上席特別研究員兼京都大学基礎物理学研究所特任准教授）の研究グループは、量子コンピューターが従来型の古典コンピューターより高速であることを示す「量子超越性」の必要十分条件について、暗号理論の観点から世界で初めて証明した。日本電信電話株式会社（NTT）が6月23日に発表した。

　量子コンピューターは、量子力学の基本原理である重ね合わせの性質（1つの量子ビットで「1」と「0」を同時に表現できる性質。これにより古典コンピューターには不可能な並列計算が可能で、処理の高速化も期待できる）を活用することで計算を行う技術で、古典コンピューターでは膨大な計算時間が必要だと考えられる困難な問題を高速に解く可能性が期待されている。しかし、全ての問題に対して量子超越性が存在するわけではなく、古典コンピューターの方が短い計算時間となる問題も存在する。

　量子コンピューターの能力を生かすためには、「どのような条件の下で量子超越性が存在するのか」「量子超越性が存在するために何が必要か」といった問いへの明確な答えが不可欠だとされる。これまでにも、素因数分解の困難性などさまざまな条件が提示され、その条件のもとで量子超越性の存在が証明されてきたが、それらはあくまでも十分条件であり、それらの条件が本当に必要なのかについては、明確に理解されてはいなかったという。

　同研究では、量子超越性の理論的な土台をより強固なものとするために、「量子超越性の必要十分条件は何か？」という根本的な問題に取り組んだ。

　そして、量子超越性の必要十分条件を特定することに初めて成功したとしている。特に、近年の量子暗号の分野で提案されている、量子論の性質を活用した情報通信や古典コンピューターだけでは不可能な暗号機能の安全性（後述する非効率検証可能量子性証明）と、量子超越性の存在が等価であることを示しており、暗号機能が安全であれば量子超越性を示すタスクを構成することができ、量子超越性が存在するならば安全な暗号機能が構成できるとしている。

「非効率検証可能量子性証明」（IV-PoQ：Inefficient-Verifier Proofs of Quantumness）

　同研究では、「非効率検証可能量子性証明」（IV-PoQ：Inefficient-Verifier Proofs of Quantumness）と呼ばれる量子計算機を持たない検証者が、量子計算機を持つ証明者とやりとりをすることで、相手が本当に量子計算能力を持っているかを検証できる仕組みに着目した。この仕組みが存在するための必要十分条件が、ある種の暗号機能の安全性に一致することを数学的に証明し、量子超越性と暗号の安全性が等価であることを示したという。

　この成果をもとに、将来的な量子超越性の実証実験やさらなる理論研究が暗号理論的により強固な基盤のもとで進められることが見込まれるとしている。また、「もし量子超越性が存在しないのであれば、現在安全とされている多くの暗号機能の安全性が破綻してしまう」ことも意味しているとしており、量子計算機実現後にも安全に使用できる暗号の構成に向けた基盤理論への貢献も期待されるとしている。

　同研究の成果は、6月27日に国際会議「57th Annual ACM Symposium on Theory of Computing」（STOC 2025）にて発表され、国際学術誌「Proceedings of the 57th Annual ACM Symposium on Theory of Computing」にオンライン掲載される。