betaFeedback

WorksPhysics and Astronomy

Classical Oracle Separation of QMA from the QCMA Hierarchy and Quantum Cryptography Even When P = QCMA

Abstract

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).

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.

  • Pseudorandom states (PRS) with classical keys.

  • Pseudorandom functions (PRF) with (copy-protected) quantum secret keys, and thus also pseudorandom unitaries (PRU) with quantum secret keys,

  • Public-key encryption (PKE) with a (copy-protected) quantum decryption key, classical public keys and ciphertexts,

  • Signature schemes with quantum signing keys and either classical verification keys and quantum signatures or quantum verification keys and classical signatures,

  • Collusion-resistant public-key quantum money (PKQM) with classical verification keys.

Introduction

The QMA versus QCMA question asks whether quantum proofs are more powerful than classical ones, and has been a central question in quantum complexity since the introduction of these classes [13]. Aaronson and Kuperberg [AK07] gave the first evidence for such an advantage for quantum proofs by separating these classes relative to a quantum unitary oracle. After many attempts [40, 71, 61, 21, 84, 63, 38], recently the breakthrough work of Bostanci, Haferkamp, Nirkhe, and Zhandry [23] finally showed the first classical oracle separation. Later, a simpler classical oracle separation was shown by Bostanci, Huang, and Vaikuntanathan [24].

However, a fundamental question still remains open: whether QMA is contained in the QCMA hierarchy

QCMAH=⋃d≥1QCMAQCMA⋯QCMA\mathrm{QCMAH} = \bigcup_{d \ge1} \mathrm{QCMA}^{\mathrm{QCMA}^{\cdots^{\mathrm{QCMA}}}}

the classical-witness quantum-verifier analogue of the polynomial hierarchy PH=⋃d≥1NPNP⋯NP\mathrm{PH} = \bigcup_{d \ge1} \mathrm{NP}^{\mathrm{NP}^{\cdots^{\mathrm{NP}}}}.

Even more importantly, whether QMA is larger even when BQP = QCMA. In other terms, can quantum state advantage or quantum proof advantage exist even if every problem that admits a classical proof can also be efficiently solved? Thus, we ask2:

Is QMA in the QCMA hierarchy? Can quantum state/proof advantage exist (QMA ⊈\not\subseteq QCMA) even if BQP = QCMA, or even if P = QCMA?

The languages3 L∈L \in QMA constructed in [23] and [24] both lie in AM, which is contained in the second level QCMAQCMA\mathrm{QCMA}^{\mathrm{QCMA}} of the QCMA hierarchy. So, they do not obtain a QMA separation from QCMAH, or QMA advantage when BQP = QCMA.

Thus, this question was left open and indeed answering it requires a substantial strengthening of their results: Drawing a parallel to quantum computational advantage4, we note that an oracle separation of BQP from NP has been known since 2000 [79], but a separation of BQP from PH, and separation of BQP from P when P = NP was obtained much later by the celebrated works of Raz and Tal [74] and Aaronson, Ingram, Kretschmer [11], respectively.

Cryptography Aside from its complexity-theoretic interest, the question above also has an important connection to quantum cryptography. Initiated by Kretschmer [58], the study of MicroCrypt, a fruitful major line of research in quantum cryptography [14, 67, 20, 56, 59, 68, 35, 25, 45, 57, 19, 26], has shown evidence for the tantalizing possibility that quantum cryptography can exist even if there is no classical cryptography.

While earlier oracle separations in this area, including [58], used quantum unitary oracles, Kretschmer, Qian, Sinha, and Tal [56] finally showed a classical oracle relative to which P = NP yet single-copy pseudorandom states (PRS) exist. Later, Kretschmer, Qian, and Tal [57] showed that there is a classical oracle relative to which P = NP but quantum-computable one-way functions (OWFs), public-key encryption (PKE), and multi-copy PRS can still exist, and left open the question of cryptography when P=QCMAP = \mathrm{QCMA}.

Further, we note that the results of [57] necessarily have that quantum computational advantage exists relative to their oracle: Indeed, observe that existence of quantum-computable one-way functions implies BQP≠QCMA\mathrm{BQP} \ne\mathrm{QCMA}, and since they also have P=NPP = \mathrm{NP}, their oracle world has P≠BQPP \ne\mathrm{BQP}. Thus, we ask:

Can quantum cryptography exist even if P=QCMAP = \mathrm{QCMA}, that is, without quantum-computable one-way functions (OWF) or quantum computational advantage?

We believe this is an important question given that there have been many examples of quantum algorithms later being de-quantized [78, 37, 55], whereas there is more concrete evidence for quantum state advantage in the standard model [42, 72, 64, 30].

Our results

In this work we answer both of the questions affirmatively, through a new problem called Codeword-Hash pairs in Noise (CHN) that we introduce. Briefly, the problem is to decide if the constant-1 function have been planted on top of a string of sparse Bernoulli noise, at locations that are codewords and their symbol-wise hashes (i.e. Yamakawa–Zhandry hashes [80]).

Complexity

We use the prefix BB- (for black-box) to distinguish classes in the query complexity model from the usual time-bounded classes. We first prove the following query complexity result for CHN.5

Theorem 1 (Informal, Theorems 8 and 10). In the query complexity model,

\mathrm{CHN} \in\mathrm{BB\mathchar`-QMA} \setminus\mathrm{BB\mathchar`-QCMAH}.

Then, with a small extension of our query complexity argument, we construct a classical oracle relative to which QCMAH\mathrm{QCMAH} collapses to PP while QMA\mathrm{QMA} remains strictly larger.

Theorem 2 (Informal, Theorem 11). There exist a classical oracle O:{0,1}∗→{0,1}O : \{0,1\}^{*} \to\{0,1\} and a unary language LL such that

PO=QCMAO=QCMAHO⊂QMAO,L∈QMAO∖QCMAHO.P^{O} = \mathrm{QCMA}^{O} = \mathrm{QCMAH}^{O} \subset\mathrm{QMA}^{O}, \qquad L \in\mathrm{QMA}^{O} \setminus\mathrm{QCMAH}^{O}.

We note that our cryptography theorem below (with small caveats) subsumes this oracle separation theorem. In fact, we show the stronger separation where PromisePO=PromiseQCMAO=PromiseQCMAHO\mathrm{PromiseP}^{O} = \mathrm{PromiseQCMA}^{O} = \mathrm{PromiseQCMAH}^{O}, but there is a language in QMAO\mathrm{QMA}^{O} that is hard even on average for QCMAHO\mathrm{QCMAH}^{O} machines (Corollary 3). However, note that they do not subsume the query complexity result (Theorem 1) regarding CHN.

Quantum State/Proof Advantage Our result shows that quantum state advantage, or quantum proof advantage, can exist even when classical computers can efficiently solve every problem that admits quantum verification with a classical witness (P = QCMA). While our problem itself has no direct connection to the Forrelation problem [4, 2], in some sense it can be thought of as a quantum-state analogue of it, since Forrelation has been used to show that quantum computational advantage can exist even when P = NP [74, 11].

Cryptography

We use CHN to construct quantum cryptographic primitives in a world where P = QCMA = QCMAH, and hence there is no quantum computational advantage, quantum-computable one-way functions or even efficiently verifiable one-way puzzles [35]; answering an open question of Kretschmer, Qian, and Tal [57].

Theorem 3 (Informal, Theorem 19). There exists a classical oracle O:{0,1}∗→{0,1}O : \{0,1\}^{*} \to\{0,1\} such that

PO=QCMAO=QCMAHO,\mathrm{P}^{O} = \mathrm{QCMA}^{O} = \mathrm{QCMAH}^{O},

and relative to OO the following primitives exist with correctness and security:

  • Pseudorandom states (PRS) with classical keys, secure for any polynomial number of copies.

  • Copy-protected public-key encryption (PKE) with quantum decryption keys and classical public keys and ciphertexts.

  • Copy-protected pseudorandom functions (PRF) with quantum secret keys, pseudorandom against quantum evaluation queries.

  • Signature schemes with quantum signing keys and either classical verification keys and quantum signatures or quantum verification keys and classical signatures.

We emphasize that, unlike [57], our PKE construction also satisfies copy-protection, a stronger security requirement that has been extensively studied [3, 12, 48, 39, 34].

Corollaries Through the known black-box constructions in cryptography, we also obtain that the following exist relative to the same oracle:

  • Collusion-resistant public-key quantum money (PKQM) with classical verification keys [10],

  • Bounded-collusion-resistant copy-protected PKE and PRF schemes [36],

  • Pseudorandom unitaries with a quantum key [65],

  • (Inefficient-verifier) one-way puzzles [59],

  • One-way state generators with a classical key [67],

  • Signature scheme with quantum verification keys and classical signing keys and signatures, secure against a bounded number of signing queries [68].

We refer the reader to the Microcrypt Zoo [75] for more implications of these primitives.

Quantum State Advantage in Cryptography It is not hard to see that when P=QCMAP = \mathrm{QCMA}, there is no quantum computational advantage: Any problem that can be solved efficiently by a quantum computer can also be solved efficiently classically, and any efficient quantum computational (even interactive) process that holds no quantum memory can be efficiently simulated by a classical computer6. Thus, we obtain cryptography from quantum state advantage even if there is no quantum computational advantage. Note that this is in contrast to the results of [56, 57], which, as discussed, necessarily require quantum computational advantage (P≠BQPP \ne\mathrm{BQP}).

Aside from [58, 56, 57], very recently, Gulati, Khurana, and Tomer [43] ruled out fully black-box constructions of quantum-computable one-way functions from PRUs. However, they do not show that PRUs can exist even if quantum-computable one-way functions do not exist, or if P=QCMAP = \mathrm{QCMA}.7

Organization

In § 2, we give a technical overview of the paper. See § 2.11 for the detailed organization and § 2.14 for the AI methodology.

In § 2.12 we discuss some future directions and in § 2.13 we discuss some more related work.

Technical Overview

In this section, we give a technical overview of our work, explaining our techniques and providing some intuition. Formal definitions, statements, and proofs can be found in the relevant sections.

Complexity In this overview, we focus on our query complexity8 result about CHN to highlight the main techniques that also underlie our cryptographic results. Through (somewhat) routine techniques, such query complexity results can be converted to oracle separations (see, e.g., [74, 11, 84, 23, 24]). Indeed, our oracle separation showing that QMAO\mathrm{QMA}^{\mathcal{O}} is strictly larger than PO=QCMAHO\mathrm{P}^{\mathcal{O}} = \mathrm{QCMAH}^{\mathcal{O}} relative to some fixed oracle O\mathcal{O} (Theorem 11), follows from this with small additions (which we provide for reference in Appendix § 14.4.1). As mentioned before, our cryptography results actually subsume this oracle separation, but not the query complexity result for CHN.

In § 2.1, we briefly recall the model. Then § 2.2 we introduce our problem CHN and state our query complexity result. We then give an overview of its proof in § 2.3.

Cryptography We introduce our function encoding, PKE construction and collapse oracle in § 2.6. We then give the proof overview in § 2.7, first assuming that the required states are supplied and then explaining their preparation using classical oracles.

Detailed Organization and Further Discussion We give a detailed map of the paper in § 2.11. Then we discuss future directions in § 2.12, and review further related work in § 2.13.

Model

We now briefly recall the query complexity model, the familiar readers may skip. See § 3.2 for formal definitions.

Algorithms and Machines An algorithm is a classical or quantum procedure whose output may be probabilistic, whereas a machine specifies a partial decision function with values in {0,1,⊥}\{0,1,\perp\}. We call an algorithm or machine query-efficient if it makes polynomially many queries in total to its oracles, each on an address (also called a query input) of polynomial length. We allow unbounded computation outside oracle queries. Usually, we will use the word algorithm for query-efficient ones.

Query Complexity Model An algorithm or machine accesses its input as a finite Boolean oracle

O:{0,1}p(λ)→{0,1},\mathcal{O}:\{0,1\}^{p(\lambda)} \to\{0,1\},

where pp is a fixed polynomial and N=2p(λ)N=2^{p(\lambda)} is size of the oracle’s truth table. Resource bounds, such as the number of queries and the witness size, are measured in λ\lambda rather than in NN, so polynomial means polynomial in λ\lambda. We also consider oracles with domain Xλ\mathcal{X}_{\lambda}, writing O:Xλ→{0,1}\mathcal{O}:\mathcal{X}_{\lambda}\to\{0,1\}. Besides its input oracle, an algorithm or machine may have oracle access to another machine and receive a classical auxiliary input zz, supplied directly rather than through oracle access.9 Unless otherwise specified, witnesses and auxiliary inputs have polynomial size. We use the prefix BB- (for black-box), as in BB-QMA and BB-QCMAH, to distinguish these query-model classes from their usual time-bounded counterparts.

BB-QCMA and BB-QCMAH in Query Complexity Model A BB-QCMA machine MM is specified by a query-efficient quantum algorithm VV, called the verifier that additionally receives classical witness ww, and is defined as

MO(z)={1,∃w:Pr⁡[VO(z,w)=1]≥2/3,0,∀w:Pr⁡[VO(z,w)=1]≤1/3,⊥,otherwise.M^{O}(z)= \begin{cases} 1, & \exists w:\Pr[V^{O}(z,w)=1]\ge2/3,\\ 0, & \forall w:\Pr[V^{O}(z,w)=1]\le1/3,\\ \perp, & \text{otherwise.} \end{cases}

Following Agarwal and Ben-David [8], we define the BB-QCMA hierarchy using completions of partial functions.10 For f:{0,1}∗→{0,1,⊥}f:\{0,1\}^{*}\to\{0,1,\perp\}, we define its set of Boolean completions by

Comp⁡(f)={f~:{0,1}∗→{0,1}∣∀z, f(z)≠⊥⟹f~(z)=f(z)}.\operatorname{Comp}(f)=\left\{\widetilde{f}:\{0,1\}^{*}\to\{0,1\}\mid\forall z,\ f(z)\ne\perp\mathrel{\Longrightarrow}\widetilde{f}(z)=f(z)\right\}.

Starting with BB-QCMAH1=BB-QCMA\mathrm{BB\text{-}QCMAH}_{1}=\mathrm{BB\text{-}QCMA}, for d≥2d\ge2 a BB-QCMAHd\mathrm{BB\text{-}QCMAH}_{d} machine MdM_{d} is specified by a query-efficient quantum verifier VdV_{d} and a BB-QCMAHd−1\mathrm{BB\text{-}QCMAH}_{d-1} machine Md−1M_{d-1}, and is defined as

MdO(z)={1,∀f~∈Comp⁡(Md−1O) ∃w:Pr⁡[VdO,f~(z,w)=1]≥2/3,0,∀f~∈Comp⁡(Md−1O) ∀w:Pr⁡[VdO,f~(z,w)=1]≤1/3,⊥,otherwise.M_{d}^{O}(z)= \begin{cases} 1, & \forall\widetilde{f}\in\operatorname{Comp}(M_{d-1}^{O})\ \exists w:\Pr[V_{d}^{O,\widetilde{f}}(z,w)=1]\ge2/3,\\ 0, & \forall\widetilde{f}\in\operatorname{Comp}(M_{d-1}^{O})\ \forall w:\Pr[V_{d}^{O,\widetilde{f}}(z,w)=1]\le1/3,\\ \perp, & \text{otherwise.} \end{cases}

We define the BB-QCMA hierarchy BB-QCMAH as union of constant levels dd,

BB-QCMAH=⋃d≥1BB-QCMAHd.\mathrm{BB\text{-}QCMAH}=\bigcup_{d\ge1}\mathrm{BB\text{-}QCMAH}_{d}.

The CHN Problem and Our Query Complexity Result

Starting point: CHS Problem Our starting point is the Codeword-Hash Structure (CHS) problem recently introduced by Cakan [29], to separate BB-QMA from BB-QCIP, which in turn is based on the Code Intersection Subset Size problem introduced by the elegant classical-oracle QMA–QCMA separation of Bostanci, Huang and Vaikuntanathan [24]. Both problems build on the Yamakawa-Zhandry code intersection problem [80] where we consider the symbol-wise hash function H(a)=H1(a1)∥⋯∥Hq(aq)H(a)=H_{1}(a_{1})\mathbin\Vert\cdots\mathbin\Vert H_{q}(a_{q}) and a suitable linear code C∈ΣqC\in\Sigma^{q}, and the task is to, for a given image y∈{0,1}qy\in\{0,1\}^{q}, find a codeword v∈Cv\in C such that H(v)=yH(v)=y. Indeed, many QMA–QCMA separations rely on this same problem [61, 21, 31]. In particular, [24, 31, 29] use the biased version introduced in [GGJL25].

More precisely, CHS is defined as follows. Let Cλ⊆Σλq(λ)C_{\lambda}\subseteq\Sigma_{\lambda}^{q(\lambda)} be a suitable linear code, q(λ)=poly⁡(λ)q(\lambda)=\operatorname{poly}(\lambda) and we sample each value of the predicates Hi:Σλ→{0,1}H_{i}:\Sigma_{\lambda}\to\{0,1\} independently as

Hi(a)←Bernoulli⁡(λ−4)(i∈[qλ], a∈Σλ),H_{i}(a)\leftarrow\operatorname{Bernoulli}(\lambda^{-4})\qquad(i\in[q^{\lambda}],\ a\in\Sigma_{\lambda}),

We then define the codeword-hash relation over Xλ=Σλqλ×{0,1}λ\mathcal{X}_{\lambda}=\Sigma_{\lambda}^{q^{\lambda}}\times\{0,1\}^{\lambda} by

References

  1. [2]Scott Aaronson and Andris Ambainis. Forrelation: A problem that optimally separates quantum from classical computing. In Rocco A. Servedio and Ronitt Rubinfeld, editors, 47th Annual ACM Symposium on Theory of Computing, pages 307–316, Portland, OR, USA, June 14–17, 2015. ACM Press.
  2. [3]Scott Aaronson. Quantum copy-protection and quantum money, 2009. CCC 2009. arXiv:1110.5353, version 1.
  3. [4]Scott Aaronson. BQP and the polynomial hierarchy, 2010. STOC 2010. Full version: arXiv:0910.4698, version 1.arxiv.org/abs/0910.4698
  4. [5]Scott Aaronson. Impossibility of succinct quantum proofs for collision-freeness. Quantum Information and Computation, 12(1–2):21–28, 2012.arxiv.org/abs/1101.0403
  5. [6]Scott Aaronson. The equivalence of sampling and searching. Theory of Computing Systems, 55(2):281–298, 2014.
  6. [7]Prabhanjan Ananth and Amit Behera. A modular approach to unclonable cryptography. In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology – CRYPTO 2024, Part VII, volume 14926 of Lecture Notes in Computer Science, pages 3–37, Santa Barbara, CA, USA, August 18–22, 2024. Springer, Cham, Switzerland.arxiv.org/abs/2311.11890
  7. [8]Avantika Agarwal and Shalev Ben-David. Oracle separations for the quantum-classical polynomial hierarchy. https://arxiv.org/abs/2410.19062v2, 2026. ITCS 2026. arXiv:2410.19062, version 2, 3 December 2025.
  8. [9]Prabhanjan Ananth, Amit Behera, Zikuan Huang, Fuyuki Kitagawa, and Takashi Yamakawa. Copy-protection from unclonable puncturable obfuscation, revisited. In Advances in Cryptology – EUROCRYPT 2026, volume 16541 of Lecture Notes in Computer Science, pages 541–570. Springer, 2026.DOI
  9. [10]Scott Aaronson and Paul Christiano. Quantum money from hidden subspaces. Theory of Computing, 9(9):349–401, 2013.arxiv.org/abs/1203.4740
  10. [11]Scott Aaronson, DeVon Ingram, and William Kretschmer. The acrobatics of BQP. In 37th Computational Complexity Conference (CCC 2022), volume 234 of Leibniz International Proceedings in Informatics, pages 20:1–20:17, 2022. Full version: arXiv:2111.10409, version 4.DOI
  11. [12]Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry, and Ruizhe Zhang. New approaches for quantum copy-protection, 2020. arXiv:2004.09674, version 7, 16 October 2020.arxiv.org/abs/2004.09674
  12. [13]Dorit Aharonov and Tomer Naveh. Quantum NP—a survey, 2002.DOI
  13. [14]Prabhanjan Ananth, Luowen Qian, and Henry Yuen. Cryptography from pseudorandom quantum states. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology – CRYPTO 2022, Part I, volume 13507 of Lecture Notes in Computer Science, pages 208–236, Santa Barbara, CA, USA, August 15–18, 2022. Springer, Cham, Switzerland.arxiv.org/abs/2112.10020
  14. [15]Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5):1510–1523, 1997.DOI
  15. [17]Paul Baecher, Christina Brzuska, and Marc Fischlin. Notions of black-box reductions, revisited. In Kazue Sako and Palash Sarkar, editors, Advances in Cryptology – ASIACRYPT 2013, Part I, volume 8269 of Lecture Notes in Computer Science, pages 296–315, Bengalore, India, December 1–5, 2013. Springer Berlin Heidelberg, Germany.
  16. [18]Amit Behera, Alper Cakan, and Vipul Goyal. Decisional monogamy-of-entanglement for coset states and applications to unclonable cryptography with correlated challenges, 2026. arXiv:2608.18841, version 2, 1 October 2026.
  17. [19]John Bostanci, Boyang Chen, and Barak Nehoran. Oracle separation between quantum commitments and quantum one-wayness, 2025. arXiv:2410.03358, version 3, 11 April 2025.
  18. [20]Zvika Brakerski, Ran Canetti, and Luowen Qian. On the computational hardness needed for quantum cryptography. In Yael Tauman Kalai, editor, ITCS 2023: 14th Innovations in Theoretical Computer Science Conference, volume 251, pages 24:1–24:21, Cambridge, MA, USA, January 10–13, 2023. Leibniz International Proceedings in Informatics (LIPIcs).
  19. [21]Shalev Ben-David and Srijita Kundu. Oracle separation of QMA and QCMA with bounded adaptivity. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), volume 297 of Leibniz International Proceedings in Informatics, pages 21:1–21:18, 2024.
  20. [22]James Bartusek and Eli Goldin. Unclonable encryption in the Haar random oracle model, 2026. CRYPTO 2026. Full version: arXiv:2603.11437, version 2, 15 June 2026.arxiv.org/abs/2603.11437
  21. [23]John Bostanci, Jonas Haferkamp, Chinmay Nirkhe, and Mark Zhandry. Separating QMA from QCMA with a classical oracle. https://arxiv.org/abs/2511.09551v2, 2026. STOC 2026. arXiv:2511.09551, version 2.
  22. [24]John Bostanci, Andrew Huang, and Vinod Vaikuntanathan. Separating quantum and classical advice with good codes. https://arxiv.org/abs/2602.09385v2, 2026. arXiv:2602.09385, version 2.
  23. [25]Rishabh Batra and Rahul Jain. Commitments are equivalent to statistically-verifiable one-way state generators. In 65th Annual Symposium on Foundations of Computer Science, pages 1178–1192, Chicago, IL, USA, October 27–30, 2024. IEEE Computer Society Press.arxiv.org/abs/2404.03220
  24. [26]Amit Behera, Giulio Malavolta, Tomoyuki Morimae, Tamer Mour, and Takashi Yamakawa. A new world in the depths of microcrypt: Separating OWSGs and quantum money from QEFID, 2025. EUROCRYPT 2025. Full version: arXiv:2410.03453, version 3, 5 February 2025.DOI
  25. [27]Zvika Brakerski and Omri Shmueli. (pseudo) random quantum states with binary phase, 2019. Version 2, 26 June 2019.arxiv.org/abs/1906.10611
  26. [28]Zvika Brakerski and Omri Shmueli. Scalable pseudorandom quantum states. In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology – CRYPTO 2020, Part II, volume 12171 of Lecture Notes in Computer Science, pages 417–440, Santa Barbara, CA, USA, August 17–21, 2020. Springer, Cham, Switzerland.arxiv.org/abs/2004.01976
  27. [29]Alper Cakan. Separating QMA from QCIP with a classical oracle, or, the power of quantum proofs over classical interaction for quantum verifiers, 2026.arxiv.org/abs/2610.03648
  28. [30]Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li. Exponential separations between learning with and without quantum memory. In 62nd Annual Symposium on Foundations of Computer Science, pages 574–585, Denver, CO, USA, February 7–10, 2022. IEEE Computer Society Press.arxiv.org/abs/2111.05881
  29. [31]Alper Cakan, Kai-Min Chung, Wei-Hsiang Hung, and Tzu-Yi Yang. Separating ClonableQMA and QCMA relative to a classical oracle, 2026. arXiv:2610.06740, version 1, 5 October 2026.arxiv.org/abs/2610.06740
  30. [33]Andrea Coladangelo and Sam Gunn. How to use quantum indistinguishability obfuscation. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, 56th Annual ACM Symposium on Theory of Computing, pages 1003–1008, Vancouver, BC, Canada, June 24–28, 2024. ACM Press.arxiv.org/abs/2311.07794
  31. [34]Alper Cakan and Vipul Goyal. How to copy-protect all puncturable functionalities without conjectures: A unified solution to quantum protection. Cryptology ePrint Archive, Paper 2025/1197, 2025.
  32. [35]Kai-Min Chung, Eli Goldin, and Matthew Gray. On central primitives for quantum cryptography with classical communication. In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology – CRYPTO 2024, Part VII, volume 14926 of Lecture Notes in Computer Science, pages 215–248, Santa Barbara, CA, USA, August 18–22, 2024. Springer, Cham, Switzerland.arxiv.org/abs/2402.17715
  33. [36]Alper Cakan, Vipul Goyal, Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa. Multi-copy security in quantum cryptography and more. https://arxiv.org/abs/2510.12626v2, 2026.
  34. [37]Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang. Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, 52nd Annual ACM Symposium on Theory of Computing, pages 387–400, Chicago, IL, USA, June 22–26, 2020. ACM Press.
  35. [38]Alper Cakan, Vipul Goyal, and Omri Shmueli. Public-key quantum fire and key-fire from classical oracles. https://arxiv.org/abs/2504.16407v2, 2026. arXiv:2504.16407, version 2, 14 March 2026.
  36. [39]Andrea Coladangelo, Jiahui Liu, Qipeng Liu, and Mark Zhandry. Hidden cosets and applications to unclonable cryptography, 2022. arXiv:2107.05692, version 3, 14 July 2022.arxiv.org/abs/2107.05692
  37. [40]Bill Fefferman and Shelby Kimmel. Quantum vs. classical proofs and subset verification. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), volume 117 of Leibniz International Proceedings in Informatics, pages 22:1–22:23, 2018.
  38. [42]Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf. Exponential separations for one-way quantum communication complexity, with applications to cryptography. In David S. Johnson and Uriel Feige, editors, 39th Annual ACM Symposium on Theory of Computing, pages 516–525, San Diego, CA, USA, June 11–13, 2007. ACM Press.arxiv.org/abs/quant-ph/0611209
  39. [43]Aditya Gulati, Dakshita Khurana, and Kabir Tomer. How to build pseudorandom unitaries in microcrypt, 2026.arxiv.org/abs/2610.03711
  40. [44]David Gosset, Robin Kothari, and Kewen Wu. Quantum state preparation with optimal T-count. Quantum, 10:2168, 2026. Full version: arXiv:2411.04790, version 3.DOI
  41. [45]Eli Goldin, Tomoyuki Morimae, Saachi Mutreja, and Takashi Yamakawa. CountCrypt: Quantum cryptography between QCMA and PP, 2024. arXiv:2410.14792, version 3, 6 October 2025.arxiv.org/abs/2410.14792
  42. [46]Oded Goldreich. Foundations of Cryptography. Cambridge University Press, 2001.
  43. [47]Oded Goldreich. Foundations of Cryptography. Cambridge University Press, 2004.
  44. [48]Marios Georgiou and Mark Zhandry. Unclonable decryption keys. Cryptology ePrint Archive, Paper 2020/877, 2020. Revised 29 July 2020.
  45. [52]Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom quantum states. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology – CRYPTO 2018, Part III, volume 10993 of Lecture Notes in Computer Science, pages 126–152, Santa Barbara, CA, USA, August 19–23, 2018. Springer, Cham, Switzerland.DOI
  46. [53]Zander Kelley. An improved derandomization of the switching lemma. https://eccc.weizmann.ac.il/report/2020/182/revision/1/download, 2021. Electronic Colloquium on Computational Complexity, TR20-182, revision 1.DOI
  47. [54]Fuyuki Kitagawa, Ryo Nishimaki, Yuki Shirakawa, and Takashi Yamakawa. Trapdoor functions with secure key leasing and copy protection, 2026.arxiv.org/abs/2609.08423
  48. [55]Robin Kothari, Ryan O’Donnell, and Kewen Wu. No exponential quantum speedup for SIS∞ anymore. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, pages 101–105. ACM, 2026.DOI
  49. [56]William Kretschmer, Luowen Qian, Makrand Sinha, and Avishay Tal. Quantum cryptography in algorithmica, 2023. arXiv:2212.00879, version 2, 2 May 2023.DOI
  50. [57]William Kretschmer, Luowen Qian, and Avishay Tal. Quantum-computable one-way functions without one-way functions, 2024. arXiv:2411.02554, version 1, 4 November 2024.DOI
  51. [58]William Kretschmer. Quantum pseudorandomness and classical complexity. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021), volume 197 of Leibniz International Proceedings in Informatics, pages 2:1–2:20, 2021. Full version: arXiv:2103.09320, version 5, 18 September 2024.DOI
  52. [59]Dakshita Khurana and Kabir Tomer. Commitments from quantum one-wayness. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024. Full version: arXiv:2310.11526, version 4.arxiv.org/abs/2310.11526
  53. [60]Qipeng Liu. Non-uniformity and quantum advice in the quantum random oracle model. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology – EUROCRYPT 2023, Part I, volume 14004 of Lecture Notes in Computer Science, pages 117–143, Lyon, France, April 23–27, 2023. Springer, Cham, Switzerland.arxiv.org/abs/2210.06693
  54. [61]Xingjian Li, Qipeng Liu, Angelos Pelecanos, and Takashi Yamakawa. Classical vs quantum advice and proofs under classically-accessible oracle. In Venkatesan Guruswami, editor, ITCS 2024: 15th Innovations in Theoretical Computer Science Conference, volume 287, pages 72:1–72:19, Berkeley, CA, USA, January 30 – February 2, 2024. Leibniz International Proceedings in Informatics (LIPIcs).arxiv.org/abs/2303.04298
  55. [62]Jiahui Liu, Qipeng Liu, Luowen Qian, and Mark Zhandry. Collusion resistant copy-protection for watermarkable functionalities. In Eike Kiltz and Vinod Vaikuntanathan, editors, TCC 2022: 20th Theory of Cryptography Conference, Part I, volume 13747 of Lecture Notes in Computer Science, pages 294–323, Chicago, IL, USA, November 7–10, 2022. Springer, Cham, Switzerland.DOI
  56. [63]Jiahui Liu, Saachi Mutreja, and Henry Yuen. QMA vs QCMA and pseudorandomness. In Michal Koucký and Nikhil Bansal, editors, 57th Annual ACM Symposium on Theory of Computing, pages 1520–1531, Prague, Czechia, June 23–27, 2025. ACM Press.arxiv.org/abs/2411.14416
  57. [64]Urmila Mahadev. Classical verification of quantum computations. In Mikkel Thorup, editor, 59th Annual Symposium on Foundations of Computer Science, pages 259–267, Paris, France, October 7–9, 2018. IEEE Computer Society Press.
  58. [65]Fermi Ma and Hsin-Yuan Huang. How to construct random unitaries. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 806–809. ACM, 2025.arxiv.org/abs/2410.10116
  59. [66]Tomoyuki Morimae, Yuki Shirakawa, and Takashi Yamakawa. Cryptographic characterization of quantum advantage. In Michal Koucký and Nikhil Bansal, editors, 57th Annual ACM Symposium on Theory of Computing, pages 1863–1874, Prague, Czechia, June 23–27, 2025. ACM Press.
  60. [67]Tomoyuki Morimae and Takashi Yamakawa. Quantum commitments and signatures without one-way functions. In Advances in Cryptology – CRYPTO 2022, volume 13507 of Lecture Notes in Computer Science, pages 269–295. Springer, 2022.DOI
  61. [68]Tomoyuki Morimae and Takashi Yamakawa. One-wayness in quantum cryptography. In 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024), volume 310 of Leibniz International Proceedings in Informatics, pages 4:1–4:21, 2024. Full version: arXiv:2210.03394, version 3.arxiv.org/abs/2210.03394
  62. [69]Ashwin Nayak. Optimal lower bounds for quantum automata and random access codes. In 40th Annual Symposium on Foundations of Computer Science, pages 369–376, 1999. Full version: arXiv:quant-ph/9904093, version 3.
  63. [70]Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010.
  64. [71]Anand Natarajan and Chinmay Nirkhe. A distribution testing oracle separation between QMA and QCMA. Quantum, 8:1377, 2024.DOI
  65. [72]Oded Regev and Bo’az Klartag. Quantum one-way communication can be exponentially stronger than classical communication. In Lance Fortnow and Salil P. Vadhan, editors, 43rd Annual ACM Symposium on Theory of Computing, pages 31–40, San Jose, CA, USA, June 6–8, 2011. ACM Press.DOI
  66. [73]Benjamin Rossman, Rocco A. Servedio, and Li-Yang Tan. An average-case depth hierarchy theorem for Boolean circuits. In Venkatesan Guruswami, editor, 56th Annual Symposium on Foundations of Computer Science, pages 1030–1048, Berkeley, CA, USA, October 17–20, 2015. IEEE Computer Society Press.
  67. [74]Ran Raz and Avishay Tal. Oracle separation of BQP and PH. Journal of the ACM, 69(4), 2022.
  68. [75]Or Sattath. Microcrypt Zoo. https://sattath.github.io/microcrypt-zoo/. Accessed 23 October 2026.
  69. [76]Yuval R. Sanders, Guang Hao Low, Artur Scherer, and Dominic W. Berry. Black-box quantum state preparation without arithmetic. Physical Review Letters, 122(2):020502, 2019. Full version: arXiv:1807.03206, version 2.DOI
  70. [77]Larry J. Stockmeyer. The complexity of approximate counting (preliminary version). In 15th Annual ACM Symposium on Theory of Computing, pages 118–126, Boston, MA, USA, April 25–27, 1983. ACM Press.
  71. [78]Ewin Tang. A quantum-inspired classical algorithm for recommendation systems. In Moses Charikar and Edith Cohen, editors, 51st Annual ACM Symposium on Theory of Computing, pages 217–228, Phoenix, AZ, USA, June 23–26, 2019. ACM Press.
  72. [79]John Watrous. Succinct quantum proofs for properties of finite groups. In 41st Annual Symposium on Foundations of Computer Science, pages 537–546, Redondo Beach, CA, USA, November 12–14, 2000. IEEE Computer Society Press.
  73. [80]Takashi Yamakawa and Mark Zhandry. Verifiable quantum advantage without structure. Journal of the ACM, 71(3), 2024.
  74. [81]Mark Zhandry. How to construct quantum random functions, 2012. Electronic Colloquium on Computational Complexity, TR12-140, revision 2.
  75. [82]Mark Zhandry. How to construct quantum random functions. In 53rd Annual Symposium on Foundations of Computer Science, pages 679–687, New Brunswick, NJ, USA, October 20–23, 2012. IEEE Computer Society Press.
  76. [83]Mark Zhandry. Quantum lightning never strikes the same state twice. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2019, Part III, volume 11478 of Lecture Notes in Computer Science, pages 408–438, Darmstadt, Germany, May 19–23, 2019. Springer, Cham, Switzerland.
  77. [84]Mark Zhandry. Toward separating QMA from QCMA with a classical oracle. In Raghu Meka, editor, ITCS 2025: 16th Innovations in Theoretical Computer Science Conference, volume 325, pages 95:1–95:19, New York, NY, USA, January 7–10, 2025. Leibniz International Proceedings in Informatics (LIPIcs).

Paper details

vlnc:W_uvckdrvu
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 4

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents