「量子コンピュータは本当に古典コンピュータを超えるのか？」この長年の問いに、全く新しい角度から光が当てられた。NTTと京都大学の研究グループが、量子コンピュータの優位性、すなわち「量子超越性」と、現代社会を支える「暗号の安全性」が、数学的にコインの裏表の関係にあることを世界で初めて証明したのだ。この発見は、もし量子コンピュータが期待外れに終わるなら、私たちのデジタル社会の安全基盤そのものが崩壊しかねない、という衝撃的な結論を突きつけている。
長年の謎「量子超越性」とは何だったのか
量子コンピュータ。それは、私たちの日常的な直観が通用しないミクロの世界、「量子力学」の原理を計算に応用する、まったく新しいコンピュータだ。特に、量子ビットが「0」と「1」の状態を同時に取りうる「重ね合わせ」という性質を利用することで、従来の古典コンピュータでは天文学的な時間がかかる問題を、現実的な時間で解き明かす可能性を秘めている。
この、量子コンピュータが古典コンピュータを圧倒する能力を「量子超越性（Quantum Advantage）」と呼ぶ。GoogleやIBMなどが開発競争を繰り広げ、特定のタスクにおいてその実証が報告されるたびに、世界中のメディアが沸き立ったことは記憶に新しい。
しかし、科学の世界は常に冷静だ。一つの大きな疑問が、理論家たちの頭を悩ませてきた。それは、「一体、どのような条件が満たされれば、量子超越性は存在するのか？」という根源的な問いである。
これまでの研究は、いわば「十分条件」を示すものだった。例えば、「もし素因数分解が古典コンピュータにとって難しい問題であり続けるなら、量子コンピュータはそれを高速に解くことで超越性を示すことができる」といった具合だ。これはショアのアルゴリズムとして有名だが、あくまで「素因数分解の困難性」という一つの仮定の上に成り立つ話に過ぎない。もし、素因数分解を古典コンピュータで効率的に解くアルゴリズムが発見されれば、この論理は崩れてしまう。
本当に量子超越性が存在するために「必要」な条件は何か。その根本的な土台は、これまで砂上の楼閣のように不確かなものだったのだ。
計算理論の地殻変動、NTT・京大のブレークスルー
この長年の謎に終止符を打ったのが、NTT社会情報研究所の山川高志上席特別研究員、京都大学基礎物理学研究所の森前智行准教授、そして同研究所博士課程学生の白川雄貴氏による研究グループだ。彼らは、2025年6月27日に理論計算機科学のトップ国際会議「STOC 2025」で発表される論文において、量子超越性の「必要十分条件」を世界で初めて特定した。
その驚くべき結論とは、「ある種の量子超越性が存在すること」と「ある種の暗号が安全であること」が、数学的に等価である、というものだ。
これはつまり、以下の二つが同時に成り立つことを意味する。
- もし、その暗号が安全であるならば、量子超越性を示すタスクを必ず作り出せる。
- もし、量子超越性が存在するならば、その安全な暗号を必ず作り出せる。
まるで無関係に見えた二つの概念が、実は分かちがたく結びついていたことが、数学的に厳密に証明された瞬間である。
鍵は「IV-PoQ」と「一方向性パズル」
この証明を理解するために、二つの重要な専門用語を少しだけ覗いてみよう。どちらも、今回の研究で「量子超越性」と「暗号の安全性」を厳密に定義するために用いられた概念だ。
- 非効率検証可能量子性証明（IV-PoQ: Inefficient-Verifier Proofs of Quantumness）
これは、今回の研究で採用された「量子超越性」の定義だ。ある証明者（Prover）が「私は量子計算能力を持っています」と主張するのを、検証者（Verifier）が対話を通じて確かめる手続き（プロトコル）を考える。この「IV-PoQ」が特徴的なのは、検証者（古典コンピュータ）が、証明者とのやり取りは素早く行うが、最終的にその主張が正しいかどうかの検証には無制限に時間を使って良い点にある。
この定義は非常に巧妙だ。例えば、量子コンピュータが得意とする「サンプリング問題」のように、生成された答えが正しいかどうかの検証自体が難しいタスクも、この「時間をかければ検証できる」という枠組みの中に含めることができる。これにより、これまで研究されてきた様々なタイプの量子超越性を統一的に扱えるようになった。 - 一方向性パズル（OWPuzzs: One-way Puzzles）
こちらは「暗号の安全性」を定義するために用いられた暗号部品（プリミティブ）だ。その名の通り、「パズル（puzz）」とその「答え（ans）」のペアを生成するアルゴリズムを考える。
このパズルの性質は、「パズルと答えのペアを作るのは簡単だが、パズルだけ渡されて答えを見つけるのは非常に難しい」というもの。これは暗号の基本である「一方向性関数」と似ているが、それよりも条件が緩く、より基礎的な部品だと考えられている。論文によれば、この一方向性パズルが存在すれば、量子デジタル署名など様々な量子暗号技術を構成できることが知られている。
研究グループは、この「IV-PoQが存在すること」と、「古典コンピュータには解読できない一方向性パズル（classically-secure OWPuzzs）が存在すること」が、完全に同値であることを数学的に証明してみせたのだ。
一見無関係な二つを結んだエレガントな証明戦略
どうやって彼らは、この二つの全く異なる世界の概念を結びつけたのか。arXivで公開されている論文を紐解くと、その証明戦略のエレガントさに驚かされる。
彼らは直接 IV-PoQ ⇔ OWPuzzs を証明したわけではない。「QAS/OWF condition」という、新たな中間的な概念を導入したのだ。これは非常に大まかに言えば、「量子コンピュータの出力は古典的に模倣困難である」か、あるいは「古典的に安全な一方向性関数が存在する」という条件である。
研究チームはこの中間地点をハブとして、
- IV-PoQが存在すること ⇔ QAS/OWF conditionが成り立つこと
- OWPuzzsが存在すること ⇔ QAS/OWF conditionが成り立つこと
という二つの等価性をそれぞれ証明した。これにより、論理的に「IV-PoQ ⇔ OWPuzzs」が導き出される。異なる山脈にトンネルを掘るため、まず両方の山からアクセス可能な共通の地下ステーションを建設したような、見事な証明アプローチと言えるだろう。
「もし量子超越性がなかったら？」──情報社会に突きつけられたパラドックス
この研究成果の真の衝撃は、その論理的な帰結にある。等価であるということは、片方が成り立たなければ、もう片方も成り立たないことを意味する。つまり、こうだ。
「もし、量子超越性が存在しないのであれば、古典的に安全な一方向性パズルも存在しない」
これは、単なる学術的な話では終わらない。なぜなら、この「一方向性パズル」は、より多くの、より複雑な暗号技術の安全性を支える基礎的な部品だからだ。もしこの土台が崩れれば、その上に建てられたビルもろとも崩壊してしまう。
研究グループは、このインパクトを次のように指摘している。
「もし量子超越性が存在しないのであれば、現在安全とされている多くの暗号機能の安全性が破綻してしまう」
驚くべきことに、ここで破綻の危機に瀕するのは、量子技術を応用した「量子暗号」だけではない。論文によれば、この論理は、現在私たちがインターネットバンキングや電子メールで日常的に利用している古典的な暗号や、量子コンピュータの攻撃に耐えられるように設計されたはずの「耐量子計算機暗号（PQC）」の安全性にも影響を及ぼすという。
これは、私たちの常識を覆すパラドックスを突きつけている。
これまで私たちは、「量子コンピュータが完成すれば、今の暗号は破られてしまう。だから新しい暗号（PQC）が必要だ」と考えてきた。これは、「量子コンピュータは脅威」という見方だ。
しかし今回の発見は、「もし量子コンピュータが（期待されたほどの）脅威でなかったとしたら、それはそれで別の理由で暗号は安全ではないかもしれない」という、全く新しいシナリオを示唆している。
量子超越性の存在そのものが、我々の情報社会の安全性の根幹と、予想もしない形で深く結びついていたのだ。
量子研究と暗号理論、交差点から生まれる新たな地平
この画期的な成果は、量子計算と暗号理論という二つの分野に、大きな波及効果をもたらすだろう。
まず、量子コンピュータ研究にとっては、自分たちの進むべき道を照らす強力な灯台となる。量子超越性の存在を証明するという困難な目標が、「暗号の安全性を仮定する」という、より確かな理論的基盤の上で進められるようになるからだ。
一方で、暗号理論や情報セキュリティ分野にとっては、自らの足元を見つめ直す重要なきっかけとなる。量子超越性の有無という、物理学と計算機科学の境界領域の問題が、自分たちの構築するシステムの安全性に直結していることが明らかになったからだ。安全な暗号の設計は、より深い理論的考察を必要とすることになる。
論文の筆頭著者である白川氏は、次のようにコメントしている。
「本研究では、量子超越性の必要十分条件を暗号理論的観点から特徴づけることに成功しました。証明のテクニックは暗号理論的なアイデアと量子計算のアイデアをうまく組み合わせたものであり、個人的には面白い手法を提案できたと思っています。今後は、さらに広範な量子超越性の特徴づけを目指していきたいです。」
今回の発見は、単一の技術的ブレークスルーではない。それは、計算とは何か、安全とは何か、そして量子と古典の世界がどのように関わり合っているのか、という科学の根源的な問いに、新たな光を当てた知的なマイルストーンだ。量子超越性の探求は、我々が築き上げてきたデジタル文明の土台そのものを問い直す旅でもあるのかもしれない。
論文
参考文献
