跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

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 QMA\mathsf{QMA} from QCIP\mathsf{QCIP}, we introduce a new problem called Codeword-Hash pairs in Noise (CHN\mathsf{CHN}) and prove that, in the query complexity model, it is in QMA\mathsf{QMA} but hard for the QCMA\mathsf{QCMA} hierarchy QCMAH=⋃d≥1QCMAQCMA⋯QCMA\mathsf{QCMAH} = \bigcup_{d\geq1}\mathsf{QCMA}^{\mathsf{QCMA}^{\cdots^{\mathsf{QCMA}}}}, the classical-witness quantum-verifier analogue of PH=⋃d≥1NPNP⋯NP\mathsf{PH}=\bigcup_{d\ge1}\mathsf{NP}^{\mathsf{NP}^{\cdots^{\mathsf{NP}}}}. Using this problem, we show that there exists a classical oracle O{O} such that PO=BQPO=QCMAO=QCMAHO⊂QMAO but QMAO⊈QCMAHO,\mathsf{P}^{O}=\mathsf{BQP}^{O}=\mathsf{QCMA}^{O} =\mathsf{QCMAH}^{O} \subset \mathsf{QMA}^{O} \text{ but } \mathsf{QMA}^{O}\not\subseteq\mathsf{QCMAH}^{O}, 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 P=QCMA\mathsf{P} = \mathsf{QCMA} and thus neither quantum-computable one-way functions nor (verifiable) quantum computational advantage exist. In particular, relative to a classical oracle O{O} with PO=BQPO=QCMAO=QCMAHO\mathsf{P}^{O}=\mathsf{BQP}^{O}=\mathsf{QCMA}^{O}=\mathsf{QCMAH}^{O}, 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

AI 论文解读

基于摘要 · 非全文审阅

作者构造新问题 CHN,在查询复杂度模型中证明其属于 QMA 但对 QCMA 层级困难,由此给出经典 oracle 下 QMA 严格超出 QCMAH 的分离,并表明即使 P=QCMA 仍可存在多种量子密码原语。

正在读取账号与研究记录…

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 QMA\mathsf{QMA} from QCIP\mathsf{QCIP}, we introduce a new problem called Codeword-Hash pairs in Noise (CHN\mathsf{CHN}) and prove that, in the query complexity model, it is in QMA\mathsf{QMA} but hard for the QCMA\mathsf{QCMA} hierarchy QCMAH=⋃d≥1QCMAQCMA⋯QCMA\mathsf{QCMAH} = \bigcup_{d\geq1}\mathsf{QCMA}^{\mathsf{QCMA}^{\cdots^{\mathsf{QCMA}}}}, the classical-witness quantum-verifier analogue of PH=⋃d≥1NPNP⋯NP\mathsf{PH}=\bigcup_{d\ge1}\mathsf{NP}^{\mathsf{NP}^{\cdots^{\mathsf{NP}}}}. Using this problem, we show that there exists a classical oracle O{O} such that PO=BQPO=QCMAO=QCMAHO⊂QMAO but QMAO⊈QCMAHO,\mathsf{P}^{O}=\mathsf{BQP}^{O}=\mathsf{QCMA}^{O} =\mathsf{QCMAH}^{O} \subset \mathsf{QMA}^{O} \text{ but } \mathsf{QMA}^{O}\not\subseteq\mathsf{QCMAH}^{O}, 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 P=QCMA\mathsf{P} = \mathsf{QCMA} and thus neither quantum-computable one-way functions nor (verifiable) quantum computational advantage exist. In particular, relative to a classical oracle O{O} with PO=BQPO=QCMAO=QCMAHO\mathsf{P}^{O}=\mathsf{BQP}^{O}=\mathsf{QCMA}^{O}=\mathsf{QCMAH}^{O}, 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).

查看此版本解读 →查看此版本原文 ↗