← 研踪 PaperTrailarXiv:2611.26574 · v1
Classical Oracle Separation of QMA from the QCMA Hierarchy and Quantum Cryptography Even When P = QCMA
QMA 与 QCMA 层级在经典 oracle 下的分离及 P=QCMA 时的量子密码学
首次提交 2026-11-20 02:40
版本更新 2026-11-20 02:40
雷达观测 2026-11-20 12:52
摘要
Remark: This work is in submission at STOC'27 and thus the full manuscript has been publicly posted on the conference website since November 3rd, 2026. Inspired by the Codeword-Hash Structure problem recently introduced by Cakan (arXiV, 2026) to separate from , we introduce a new problem called Codeword-Hash pairs in Noise () and prove that, in the query complexity model, it is in but hard for the hierarchy , the classical-witness quantum-verifier analogue of . Using this problem, we show that there exists a classical oracle such that thus showing that quantum state or quantum proof advantage could exist even if classical computers can efficiently solve any problem that can be quantumly verified with a classical proof. Further, using our problem, we show that various quantum cryptographic primitives can exist even when and thus neither quantum-computable one-way functions nor (verifiable) quantum computational advantage exist. In particular, relative to a classical oracle with , there exist pseudorandom states with classical keys and public-key encryption with copy-protected quantum decryption keys and classical public keys and ciphertexts, among other primitives, answering an open question of Kretschmer, Qian, and Tal (STOC 2025).
作者备注:In submission at STOC'27
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-20 02:40 · 最新观测版本
Classical Oracle Separation of QMA from the QCMA Hierarchy and Quantum Cryptography Even When P = QCMA
Remark: This work is in submission at STOC'27 and thus the full manuscript has been publicly posted on the conference website since November 3rd, 2026. Inspired by the Codeword-Hash Structure problem recently introduced by Cakan (arXiV, 2026) to separate from , we introduce a new problem called Codeword-Hash pairs in Noise () and prove that, in the query complexity model, it is in but hard for the hierarchy , the classical-witness quantum-verifier analogue of . Using this problem, we show that there exists a classical oracle such that thus showing that quantum state or quantum proof advantage could exist even if classical computers can efficiently solve any problem that can be quantumly verified with a classical proof. Further, using our problem, we show that various quantum cryptographic primitives can exist even when and thus neither quantum-computable one-way functions nor (verifiable) quantum computational advantage exist. In particular, relative to a classical oracle with , there exist pseudorandom states with classical keys and public-key encryption with copy-protected quantum decryption keys and classical public keys and ciphertexts, among other primitives, answering an open question of Kretschmer, Qian, and Tal (STOC 2025).
查看此版本解读 →查看此版本原文 ↗