量子コンピューターを使ったことを、普通のコンピューターとのやり取りで確かめられる。そんな「量子性の証明」ができれば、古典計算の難しさについても強い結論を引き出せそうです。ところが、2026年11月3日に公開された理論研究は、外部の計算装置を仮定した世界では、量子性の証明とP＝NPが両立すると示しました。現実のP対NP問題を解いたという意味ではなく、量子性の証明から何を導けるか、その推論に限界を与える結果です。［1］
簡単にまとめると？
- 量子性の証明は、効率的な量子計算機なら通過でき、効率的な古典計算機では通過しにくい対話型の検査です。
- 研究チームは、同じオラクルを使う計算世界で、P＝NPと量子性の証明が両立する構成を示しました。
- 古典側が検査する場合、やり取りの回数を一定に抑えられるとは限りません。実機の高速化や既存暗号の破綻を示した研究ではありません。
答えを出す力と、答えを確かめる力
Pは、入力が大きくなっても計算時間を多項式の範囲に抑えて解ける判定問題の集合です。NPは、正解を裏付ける証拠を渡されれば、多項式時間で確認できる判定問題の集合です。たとえば、ある論理式を満たす変数の割り当てがあるかを探す作業と、渡された割り当てで本当に式が満たされるかを確かめる作業は、異なる負担を持ちます。
P＝NPなら、この種の「証拠を確かめやすい問題」は、証拠なしでも効率的に解けることになります。ただし、NPがあらゆる計算問題を含むわけではありません。量子計算の能力を表すBQPも、NPと同じ定義で作られた集合ではありません。
一方、量子性の証明では、検査する側と計算する側がメッセージを交換します。正直な量子計算機は高い確率で合格でき、古典計算機が量子計算をしたふりをしても、問題の大きさに対して効率的な計算では合格確率を十分小さく抑えられる、という条件を課します。単に量子計算機が速く答えを出すだけでなく、検査する側も結果を扱えることが要点です。
同じ外部装置を加えて、推論を試す
プリンストン大学のEli Goldin、Alex Lombardi、京都大学のTomoyuki Morimaeによる研究は、「オラクル」を使います。オラクルは、決められた問い合わせに答える外部装置を数学的に仮定したものです。その内部を普通の計算機でどう実装するかは、ここでは問題にしません。
古典計算と量子計算の両方に同じオラクルOへのアクセスを与え、その条件でできることを比較します。量子計算側は、オラクルに重ね合わせの状態で問い合わせることができます。「古典オラクル」という呼び名は、入出力が古典的な関数として定まることを指し、量子側の問い合わせまで古典計算に制限するという意味ではありません。
著者らの構成では、PO＝NPOが成立する一方、BQPO＝PSPACEOとなります。PSPACEは、使う記憶領域を多項式の範囲に抑えて解ける問題の集合です。さらに、古典計算では平均的な入力に対しても解きにくく、量子計算では答えを出して対話的に正しさを示せる問題が残るように、オラクルを組み立てています。
これは、古典計算にできることを広げても、その広がり方だけで量子側との違いが消えるとは限らない、という構成です。すべてのオラクルでそうなるという主張ではなく、条件を同時に満たすオラクルが存在することが結果の中心です。
やり取りの回数と、検査する側の能力が変わる
検査の流れは、検査者が入力を選び、計算する側が答えを返し、その答えが正しいことを対話で確かめる、というものです。量子側は、答えの計算だけでなく、その対話で必要な処理も効率的に進められます。古典側が誤った答えを出すと対話の検査で拒否され、正しい答えを繰り返し返そうとすると、もとの計算の難しさが効いてきます。
ただし、ここで認めるやり取りの回数は、問題の大きさとともに多項式の範囲で増えてよいものです。同じオラクル世界では、古典計算機が検査し、通信も古典的で、やり取りが一定回数で終わる量子性の証明は存在しない、と論文は示しています。この条件では、古典側が十分よい応答を計算でき、量子計算機だけを合格させる差が保てなくなるためです。
| 検査の条件 | 同じオラクル世界での結果 |
|---|---|
| 古典計算で検査。回数は多項式の範囲で増えてよい | 量子性の証明が成り立つ |
| 古典計算で検査。回数を入力サイズによらない一定値に抑える | 量子性の証明は成り立たない |
| 検査する側も量子計算を使う | 二つのメッセージで量子性を確かめる構成が成り立つ |
最後の二メッセージの結果を、「普通のコンピューターから一往復するだけで検査できる」と読むことはできません。短いやり取りを可能にする代わりに、検査する側の能力も量子計算へ変わっています。通信回数だけを比べると、この違いを落としてしまいます。
暗号や実機について、ここから何が言えるか
オラクルを加えても成り立つ形の証明は、「相対化する証明」と呼ばれます。もし量子性の証明からP≠NPを導く一般的な議論がその形で作れれば、今回のオラクル世界にも適用できるはずです。ところが、その世界では両立しています。この食い違いから、その方法だけでは狙った結論に届かないと分かります。
論文は同じ考え方を使い、多項式回数の量子性の証明から一定回数の検査へ変換する方法や、さまざまな暗号機能を構成する方法にも制約を与えています。制約の対象は、オラクルを加えても通用する構成と証明です。別の性質を使う方法まで、すべて不可能だと証明したわけではありません。
今回の結果は、計算量理論のモデルについてのものです。新しい量子プロセッサーの性能測定、実際の通信遅延の短縮、既存の暗号を解読した報告ではありません。研究を比べる際には、どの計算能力を検査者に認めるか、通信回数をどう数えるか、オラクルや計算困難性を何として仮定するかを見る必要があります。量子性を確かめられることと、その検査から別の難しさを導けることの間にある条件を、具体的に整理する研究といえます。
出典
- Eli Goldin, Alex Lombardi, Tomoyuki Morimae, Quantum Advantage has Few Complexity Implications, arXiv:2611.05303v1, 2026年11月3日公開。第1節、2.1節、定義3.26、定理4.1、系4.13〜4.17。本記事は公開原稿の第一のオラクル構成と、その検証条件を紹介しています。