CS Paper Radar

$\mathsf{EQP}\subseteq\mathsf{IP}$ Does Not Relativize

Sinan Oral, Supartha Podder

cs.CC quant-ph ·submitted 2026-11-09 17:28 UTC · v1

Abstract

We construct a recursive oracle $O$ and a unary language $L\in\mathsf{EQP}^O\setminus(\mathsf{IP}^O\cup\mathsf{PH}^O)$, strengthening the $\mathsf{BQP}$ versus $\mathsf{IP}$ oracle separation of Bouland et al. to exact quantum computation. The separation is based on a variant of the Forrelation problem in which the normalized correlation of one Boolean function with the Fourier transform of another is promised to be exactly $+1/2$ or $-1/2$. The main technical contribution is a repair method that constructs distributions supported on these exact levels while preserving the indistinguishability needed for the $\mathsf{IP}$ and $\mathsf{PH}$ lower bounds. A uniform polynomial-time quantum algorithm distinguishes the two cases with certainty using only three oracle queries.

Comment
50 pages, 1 figure, 2 tables

Closest papers

Nearest neighbours by meaning across the whole index.

$\mathsf{BQP} \subseteq \mathsf{IP}$ Does Not Relativize

cs.CC quant-ph ·2026-09-22 ·Adam Bouland, Andrew Huang, Anand Natarajan, Itay Shalit, Avishay Tal
similarity 0.79
Abstract

We construct an oracle relative to which $\mathsf{BQP} \not\subseteq \mathsf{IP}$, resolving a long-standing open question in quantum complexity theory. Together with recent work due to Aaronson et al., our work also gives the first oracle separation between $\mathsf{IP}$ and $\mathsf{MIP}$, answering a question dating back to Fortnow's thesis. Our separation is based on the Forrelation problem, where given Boolean functions $f$ and $g$, the goal is to determine if $f$ is correlated with the Fourier spectrum of $g$. While this task is solvable by a query-efficient quantum algorithm, we show that it admits no classical interactive protocol with polynomial communication and a polynomial-query verifier. Our proof is based on (i) a new structural result showing how to approximate Avg-Max circuits (which are well-known to capture the power of interactive proofs in the oracular setting) by convex functions with small first and second derivatives and (ii) a novel analysis establishing that the Forrelation distribution suggested by Aaronson and Ambainis fools such functions. Our results imply that any prover-efficient classical interactive protocol for $\mathsf{BQP}$ must rely on non-relativizing techniques. This might serve as a partial explanation for the lack of progress towards doubly-efficient, unconditionally sound classical verification of quantum computation.

0.43

Quantum Advantage with Sign-Free Proofs: An Oracle Separation between $\mathsf{StoqMA}$ and $\mathsf{MA}$

cs.CC quant-phcs.DS ·2026-11-05 ·Yassine Hamoudi, Yvan Le Borgne, Shrinidhi Teganahally Sridhara
theory similarity 0.71
Abstract · 21 pages, 3 figures

Several landmark oracle results (FOCS 2000, FOCS 2025, STOC 2026) establish strict separations along the chain $\mathsf{MA} \subseteq \mathsf{QCMA} \subseteq \mathsf{QMA}$, showing that quantum verification and quantum witnesses can each provide additional power over classical proof systems. These separations, however, use substantial coherent quantum computation, often through the quantum Fourier transform. We prove that a minimal quantum resource already suffices to outperform every classical verifier. Namely, we show the separation $$\mathsf{MA} \subsetneq \mathsf{StoqMA}$$ relative to a classical oracle. The class $\mathsf{StoqMA}$, introduced by Bravyi, Bessen, and Terhal (arXiv 2006), restricts the verifier to classical reversible computation, followed by a single Hadamard-basis measurement. Its power is closely tied to the complexity of stoquastic Hamiltonians, a sign-problem-free and seemingly more tractable class of quantum Hamiltonians. Our separating problem is to determine whether a sparse high-girth graph, given via an adjacency-list oracle, has a large or small Perron--Frobenius eigenvalue. This amounts to a ground-energy estimation task for a related stoquastic Hamiltonian. Our construction builds on a line of work on graph exploration problems with exponential quantum speedups, from welded trees (STOC 2003) to recent constructions (STOC 2021, arXiv 2026).

0.23

A Separation Between Types of Quantum Oracle Separations

cs.CC quant-ph ·2026-09-30 ·Scott Aaronson, Adam Bouland, Jordan Docter, Barak Nehoran
similarity 0.70
Abstract · 28 pages, 3 figures

Recent works have demonstrated that quantum oracles have subtle behavior, as access to inverse, conjugate or controlled queries can exponentially change the query complexity of certain tasks. Inspired by these works, we introduce the notion of meta-complexity of quantum relativization. We ask: for any two quantum complexity classes, under which "types" of quantum oracles are they equal or separated? Different pantheons of oracles (or quantum oracle types, e.g. unitary vs state, poly- vs superpoly-dimensional, closed under inverse or not) form a partially ordered set based on their power in separating complexity classes. Moreover, two oracle pantheons A and B are separated if there exists a pair of complexity classes that are separated under an oracle from pantheon A but yet the complexity classes are equivalent under all oracles from pantheon B. We show that this meta-complexity can be nontrivial by giving a complete classification, within the family of oracle pantheons defined in this paper, of which models can separate the complexity classes $\mathsf{PostBQP}$ and $\mathsf{PreciseBQP}$, the exponentially precise variant of $\mathsf{BQP}$. Both classes equal $\mathsf{PP}$ in the unrelativized setting. Within our taxonomy, they remain equal relative to real or polynomial-dimensional unitary oracles and whenever inverse or conjugate access is supplied. In contrast, we give a separation relative to forward-only complex diagonal unitaries of superpolynomial dimension, as well as a separation relative to single-qubit state-preparation oracles. We view this as a test case for the meta-complexity of oracles which underscores the subtlety inherent to the relativization of quantum complexity classes.

0.28

Quantum Advantage has Few Complexity Implications

cs.CC quant-phcs.CR ·2026-11-03 ·Eli Goldin, Alex Lombardi, Tomoyuki Morimae
similarity 0.70
Abstract

We consider the complexity implications of proofs of quantumness and (quantum verifier) oblivious state preparation. We show that both of these objects can coexist with the easiness of nondeterministic computation. That is, we give evidence that proofs of quantumness can exist when $\mathsf{P} = \mathsf{NP}$ and that (quantum verifier) oblivious state preparation can exist when $\mathsf{BQP} = \mathsf{QCMA}$. In particular, we give a classical oracle relative to which (1) $\mathsf{P}^\mathcal{O} = \mathsf{NP}^\mathcal{O}$ (2) $\mathsf{BQP}^\mathcal{O} = \mathsf{PSPACE}^\mathcal{O}$ (3) Proofs of quantumness exist. In particular, there exists a language in $\mathsf{IP}^\mathcal{O} \subseteq \mathsf{BQP}^\mathcal{O}$ which is hard on average against $\mathsf{P}^\mathcal{O}/poly$. We give a unitary oracle such that (1) $\mathsf{BQP}^\mathcal{O} = \mathsf{QCMA}^\mathcal{O}$ (2) Quantum verifier oblivious state preparation exists. These oracle separations directly imply a number of related consequences. For example, our first result implies that proofs of quantumness cannot be used to construct classical or quantum cryptography with a relativizing proof. Our second result implies that quantum computation/classical communication oblivious transfer cannot be used to construct post-quantum one-way functions with a relativizing proof.

0.24

Structured Quantum Hardness from Unstructured Assumptions

cs.CC quant-phcs.CR ·2026-11-05 ·Xiao Liang, Takashi Yamakawa, Chak Fai Yung
similarity 0.69
Abstract · 114 pages

Whether useful structured hardness can arise from unstructured assumptions is a fundamental question in complexity and cryptography. The longstanding Bennett-Gill question asks whether $\mathsf{NP}\cap\mathsf{coNP}$ remains hard relative to a random oracle; [GIKKLS, STOC 2023] recently gave a conditional affirmative answer in the classical setting. We establish the quantum analogue: if $\mathsf{UP}\not\subseteq\mathsf{BQP}$, then $\mathsf{NP}^{O}\cap\mathsf{coNP}^{O}\not\subseteq\mathsf{BQP}^{O}$ with probability $1$ over a random oracle $O$. Beyond extending the classical result, this separation has a distinctly quantum significance: Shor's algorithms defeat canonical number-theoretic hardness candidates, while lattice assumptions and other leading post-quantum cryptographic assumptions do not directly supply hard languages with two-sided classical certification on every input. Our conditional oracle separation provides evidence that such structured quantum hardness can nevertheless arise from unstructured sources. Complementing this result, we rule out fully black-box quantum reductions of worst-case quantum hardness in $\mathsf{NP}\cap\mathsf{coNP}$ to post-quantum injective one-way functions and indistinguishability obfuscation. This barrier excludes a broad class of black-box approaches to deriving structured quantum hardness from generic cryptographic primitives, providing partial evidence that the non-black-box techniques in our first result are essential.

0.24

Separating QMA from QCIP with a Classical Oracle, or, the Power of Quantum Proofs over Classical Interaction for Quantum Verifiers

cs.CC ·2026-10-02 ·Alper Cakan
hot direction similarity 0.68
Abstract

Whether some problems require quantum proofs has been a central question in quantum complexity (Aharonov and Naveh, 2002; Aaronson and Kuperberg, CCC 2007). Recently, breakthrough work of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC 2026), followed by a simpler separation due to Bostanci, Huang, and Vaikuntanathan (FOCS 2026), established a classical oracle separation between $\mathsf{QMA}$ and $\mathsf{QCMA}$. However, while they are not in $\mathsf{QCMA}$, the problems used in both separations still lie in $\mathsf{AM}$: they admit a two-message public-coin proof system with a classical verifier. In this work, we ask whether some problems truly require quantum proofs. More formally, we consider the complexity class $\mathsf{QCIP}$, introduced by Buhrman, Le Gall, and Weggemans (2024), where an efficient quantum verifier interacts with an unbounded prover over a classical channel for an arbitrary polynomial number of rounds. We construct a classical oracle $\mathcal{O}$ such that $\mathsf{QMA}^{\mathcal{O}}\not\subseteq\mathsf{QCIP}^{\mathcal{O}}$, thus showing that some languages indeed require quantum proofs, with no classical replacements. Since $\mathsf{QCMA}=\mathsf{QCIP}[1]$, this strengthens the earlier $\mathsf{QMA}$--$\mathsf{QCMA}$ separations, which now follow as a special case of our result. As a technical contribution, we extend to the complexity theory setting the techniques developed by Cakan, Goyal, and Shmueli (CRYPTO 2026) in the context of cryptography for analyzing classically interacting quantum machines. We believe this may be of independent interest.

0.48

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

cs.CR quant-ph ·2026-11-19 ·Alper Cakan
similarity 0.68
Abstract · In submission at STOC'27

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 $\mathsf{QMA}$ from $\mathsf{QCIP}$, we introduce a new problem called Codeword-Hash pairs in Noise ($\mathsf{CHN}$) and prove that, in the query complexity model, it is in $\mathsf{QMA}$ but hard for the $\mathsf{QCMA}$ hierarchy $\mathsf{QCMAH} = \bigcup_{d\geq1}\mathsf{QCMA}^{\mathsf{QCMA}^{\cdots^{\mathsf{QCMA}}}}$, the classical-witness quantum-verifier analogue of $\mathsf{PH}=\bigcup_{d\ge1}\mathsf{NP}^{\mathsf{NP}^{\cdots^{\mathsf{NP}}}}$. Using this problem, we show that there exists a classical oracle ${O}$ such that $\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 $\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}$ with $\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).

0.24

Quantum Submodular Maximization

cs.CC quant-phcs.DS ·2026-10-03 ·Yonggang Jiang, Xiaoming Sun, Penghui Yao, Zekun Ye, Jialin Zhang +1 more
theory similarity 0.67
Abstract · 62 pages; abstract shortened for arXiv

We study the quantum query complexity of maximizing a non-negative submodular function, considering both the unconstrained setting and, for monotone functions, a cardinality constraint $k$ on an $n$-element ground set. In the exact reversible digital value-oracle model, our unconstrained algorithm achieves an expected $(1/2-\varepsilon)$-approximation using only $O_\varepsilon(\log n)$ queries. In contrast, any classical randomized algorithm that attains a fixed expected ratio above $1/4$ requires $Ω(n/\log n)$ queries (Li, Feldman, Kazemi, and Karbasi, 2022), establishing an exponential separation in query complexity. For cardinality-constrained maximization, we give a bounded-error quantum algorithm that achieves a $(1-1/e-\varepsilon)$-approximation using $\widetilde O_\varepsilon(\min\{\sqrt n,n/k\})$ queries. When $k=o(n)$, our algorithm achieves at least a quadratic speedup up to logarithmic factors over classical randomized algorithms (Mirzasoleiman, Badanidiyuru, Karbasi, Vondrák, and Krause, 2015; Peng and Rubinstein, 2025). Moreover, when $k=cn$ for any fixed rational $c<1-1/e-\varepsilon$, the query complexity reduces to $O_{\varepsilon,c}(\log n)$, yielding an exponential separation from the classical $Ω(n/\log n)$ lower bound (Li, Feldman, Kazemi, and Karbasi, 2022). We further prove quantum lower bounds of $\exp(Ω(\varepsilon^2n))$ queries for achieving a ratio beyond $1/2+\varepsilon$ without constraints, and $\exp(Ω(\varepsilon^2k))$ queries for exceeding $1-1/e+\varepsilon$ when $k/n\le\varepsilon$. These barriers demonstrate that quantum computation offers no exponential speedup at these approximation thresholds.

0.24