Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.25657

Quantum State Search with Classical Interactive Advice

Mohammed Barhoush

quant-phSubmitted Oct 19, 2026• Announced Oct 20, 2026• 0 citations• Revised Oct 21, 2026 (v2)
v1 · Oct 19, 2026v2 · Oct 21, 2026
arXivHTMLPDF

Abstract

We study whether a quantum verifier can find a hidden quantum state by exchanging classical messages with an unbounded prover who knows the state. The verifier has access to a reflection oracle about the target. For a Haar-random $n$-qubit target, we prove that achieving constant average fidelity with the target requires $(q+1)^2(B+1)=Ω(2^n)$, where $q$ is the number of verifier queries and $B$ is the total prover-to-verifier communication. The bound allows arbitrary classical interaction and unrestricted computation between queries. Our proof extends the lower bound of Aaronson and Kuperberg (ToC'07) from a single classical proof to an arbitrary classical interaction. As a result, we obtain a quantum-oracle separation of QMA from QCIP. In particular, we give a unitary oracle $\mathcal{U}$ such that there exists a language $L\in\mathrm{QMA}^{\mathcal{U}}$ but $L\notin\mathrm{QCIP}^{\mathcal{U}}$. Our separation holds even for UniqueQMA, the restriction of QMA to verification with a unique quantum witness, which is known to be strictly weaker than QMA in the quantum black-box setting. We further give an oracle construction for a notion known as QMA--QCIP[2] gap problem. This gives average case hardness for a QMA language under classical access to a QCIP[2] decision oracle and is used in establishing negative results on witness encryption and quantum indistinguishability obfuscation.

AI Summary

Can classical interaction help a quantum verifier prepare a hidden state when it has access to a reflection about that state? The paper considers a Haar-random $n$-qubit target $|\psi\rangle$, an unbounded prover with complete knowledge of it, and a verifier with unrestricted computation between queries to $R_\psi=I-2|\psi\rangle\langle\psi|$. Achieving constant average fidelity requires $(q+1)^2(B+1)=\Omega(2^n)$, where $q$ counts verifier queries and $B$ counts prover-to-verifier classical bits. For $2n\leq B=o(2^n)$, this matches an existing one-message upper bound. The proof extends the Aaronson–Kuperberg classical-advice lower bound to arbitrary classical interaction. With verifier queries replaced by identities, conditioning on a transcript restricts the target’s Haar distribution to a compatible set. Its expected logarithmic inverse measure is at most $B\ln2$. A conditioned-Haar overlap bound and a query hybrid then bound the average change in optimal acceptance probability by $2q\sqrt{(1+B\ln2)/2^n}$. Consequences include a unitary-oracle separation $\mathrm{UniqueQMA}^{\mathcal U}\not\subseteq\mathrm{QCIP}^{\mathcal U}$, covering polynomially many classical rounds, and a sampler-augmented oracle yielding an average-case QMA–QCIP[2] gap problem. The latter uses sampler perturbations and randomly thresholded decision-oracle completions to control adaptive classical queries. The model excludes shared setup and entanglement. The separation is relativized, uses length-respecting oracle access, and does not imply an unrelativized separation. The average-case result concerns uniform efficient distinguishers and guarantees hardness for a suitable valid decision-oracle completion, not every completion. Concurrent work gives a classical-oracle QMA–QCIP separation, without the unique-witness guarantee.

No sign of AI-generated text

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
23 pages

Related papers

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

Alper Çakan

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.

arXiv:2610.03648•Oct 2, 2026•1 citation

Quantum Interactive Oracle Proofs

Baocheng Sun, Thomas Vidick

We initiate the study of quantum Interactive Oracle Proofs (qIOPs), a generalization of both quantum Probabilistically Checkable Proofs and quantum Interactive Proofs, as well as a quantum analogue of classical Interactive Oracle Proofs. In the model of quantum Interactive Oracle Proofs, we allow multiple rounds of quantum interaction between the quantum prover and the quantum verifier, but the verifier has limited access to quantum resources. This includes both queries to the prover's messages and the complexity of the quantum circuits applied by the verifier. The question of whether QMA admits a quantum interactive oracle proof system is a relaxation of the quantum PCP Conjecture. We show the following two main constructions of qIOPs, both of which are unconditional: - We construct a qIOP for QMA in which the verifier shares polynomially many EPR pairs with the prover at the start of the protocol and reads only a constant number of qubits from the prover's messages. - We provide a stronger construction of qIOP for QMA in which the verifier not only reads a constant number of qubits but also operates on a constant number of qubits overall, including those in their private registers. However, in this stronger setting, the communication complexity becomes exponential. This leaves open the question of whether strong qIOPs for QMA, with polynomial communication complexity, exist. As a key component of our construction, we introduce a novel single prover many-qubits test, which may be of independent interest.

cs.CCCross-listedarXiv:2601.12874•Jan 20, 2026•1 citation

Separating QMA from QCMA with a classical oracle

John Bostanci, Jonas Haferkamp, Chinmay Nirkhe +1 more

We construct a classical oracle proving that, in a relativized setting, the set of languages decidable by an efficient quantum verifier with a quantum witness (QMA) is strictly bigger than those decidable with access only to a classical witness (QCMA). The separating classical oracle we construct is for a decision problem we coin spectral Forrelation -- the oracle describes two subsets of the boolean hypercube, and the computational task is to decide if there exists a quantum state whose standard basis measurement distribution is well supported on one subset while its Fourier basis measurement distribution is well supported on the other subset. This is equivalent to estimating the spectral norm of a "Forrelation" matrix between two sets that are accessible through membership queries. Our lower bound derives from a simple observation that a query algorithm with a classical witness can be run multiple times to generate many samples from a distribution, while a quantum witness is a "use once" object. This observation allows us to reduce proving a QCMA lower bound to proving a sampling hardness result which does not simultaneously prove a QMA lower bound. To prove said sampling hardness result for QCMA, we observe that quantum access to the oracle can be compressed by expressing the problem in terms of bosons -- a novel "second quantization" perspective on compressed oracle techniques, which may be of independent interest. Using this compressed perspective on the sampling problem, we prove the sampling hardness result, completing the proof.

quant-pharXiv:2511.09551•ACM Symposium on Theory of Computing (STOC)•Nov 13, 2025•12 citations

Quantum Versus Classical Proofs and Advice

Scott Aaronson, Greg Kuperberg

This paper studies whether quantum proofs are more powerful than classical proofs, or in complexity terms, whether QMA=QCMA. We prove three results about this question. First, we give a "quantum oracle separation" between QMA and QCMA. More concretely, we show that any quantum algorithm needs $Ω(\sqrt{2^n/(m+1)})$ queries to find an $n$-qubit "marked state" $\lvertψ\rangle$, even if given an $m$-bit classical description of $\lvertψ\rangle$ together with a quantum black box that recognizes $\lvertψ\rangle$. Second, we give an explicit QCMA protocol that nearly achieves this lower bound. Third, we show that, in the one previously-known case where quantum proofs seemed to provide an exponential advantage, classical proofs are basically just as powerful. In particular, Watrous gave a QMA protocol for verifying non-membership in finite groups. Under plausible group-theoretic assumptions, we give a QCMA protocol for the same problem. Even with no assumptions, our protocol makes only polynomially many queries to the group oracle. We end with some conjectures about quantum versus classical oracles, and about the possibility of a classical oracle separation between QMA and QCMA.

arXiv:quant-ph/0604056•Electronic colloquium on computational complexity•Apr 10, 2006•29 citations

Probabilistically Checking Quantum Proofs, with Interaction

Baocheng Sun, Thomas Vidick

The model of interactive oracle proofs (IOP) generalizes the notion of probabilistically checkable proof (PCP), in which a static proof is verified probabilistically by querying a small number of bits, to the interactive setting: a polynomial-time verifier interacts with an unbounded prover, but is restricted to only reading a small number of bits, in total, from the messages sent by the prover. IOPs provide a relaxed setting in which to study local probabilistic verification. They have proved instrumental in devising efficient methods for verification through subsequent compilation into non-interactive or succinct protocols. We study a quantum analogue of interactive oracle proofs (qIOP) in which the verifier and communication are both allowed to be quantum; yet the verifier is restricted to perform measurements only on a small number of qubits received from the prover. Our main result is a qIOP for any language in QMA, in which the total communication is polynomial but the verifier only reads a polylogarithmic number of qubits in total. The protocol has completeness parameter exponentially close to $1$ and soundness bounded away from $1$ by a constant. In the absence of a quantum PCP theorem, this provides the first information-theoretically sound local and robust characterization of QMA, albeit interactive. Our protocol combines the use of a quantum locally testable code (LTC) with classical techniques, notably probabilistically checkable proofs of proximity (PCPP). We avoid the necessity for complex multi-qubit tests employed in other settings by leveraging the local indistinguishability property of the quantum LTC.

cs.CCCross-listedarXiv:2606.09588•Leibniz international proceedings in informatics•Jun 9, 2026•2 citations

Classical Verification of Quantum Computation Beyond the Polynomial Hierarchy

Atul Mantri

It is not known whether a classical polynomial-time verifier can verify arbitrary polynomial-time quantum computations with an efficient quantum honest prover without computational assumptions. We show that, relative to a classical oracle, such verification is possible for a language beyond the polynomial hierarchy that is decided exactly in quantum polynomial time. The protocol is public-coin, with perfect completeness and soundness error at most 1/4. To our knowledge, no language with such a proof system was previously proved to lie outside AM relative to an oracle. For every unbounded polynomial-time computable function, the oracle can be chosen so that the message count and the oracle query counts of the quantum algorithm, verifier, and honest prover are bounded by this function of the input length. The message count is optimal up to a constant factor, since for a suitable oracle every interactive proof system for the language uses at least a constant fraction of the messages of our protocol on infinitely many lengths, with a constant depending on its verifier. The language is a variant of recursive Fourier sampling in which code tables encode secrets that address data tables. The tables are evaluated recursively, and the oracle stores only the leaves. The quantum algorithm recovers every secret exactly, and the verifier checks the prover's secrets recursively against random code entries. The recursion restricts the input in a correlated way, as the same secret fixes the code bits and chooses the free coordinate, so Håstad's switching lemma does not apply. We prove a switching theorem for these restrictions, which may be of independent interest. For instances of sufficient height, no constant-depth circuit of size $2^{\mathrm{poly}(n)}$ changes its output with probability above $2^{-Ω(n)}$ when the answer of a random instance is flipped by changing a single leaf.

quant-pharXiv:2610.37635•Oct 28, 2026•2 citations
We study whether a quantum verifier can find a hidden quantum state by exchanging classical messages with an unbounded prover who knows the state. The verifier has access to a reflection oracle about the target. For a Haar-random nnn-qubit target, we prove that achieving constant average fidelity with the target requires (q+1)2(B+1)=Ω(2n)(q+1)^2(B+1)=Ω(2^n)(q+1)2(B+1)=Ω(2n), where qqq is the number of verifier queries and BBB is the total prover-to-verifier communication. The bound allows arbitrary classical interaction and unrestricted computation between queries. Our proof extends the lower bound of Aaronson and Kuperberg (ToC'07) from a single classical proof to an arbitrary classical interaction.
As a result, we obtain a quantum-oracle separation of QMA from QCIP. In particular, we give a unitary oracle U\mathcal{U}U such that there exists a language L∈QMAUL\in\mathrm{QMA}^{\mathcal{U}}L∈QMAU but L∉QCIPUL\notin\mathrm{QCIP}^{\mathcal{U}}L∈/QCIPU. Our separation holds even for UniqueQMA, the restriction of QMA to verification with a unique quantum witness, which is known to be strictly weaker than QMA in the quantum black-box setting.
We further give an oracle construction for a notion known as QMA--QCIP[2] gap problem. This gives average case hardness for a QMA language under classical access to a QCIP[2] decision oracle and is used in establishing negative results on witness encryption and quantum indistinguishability obfuscation.
Can classical interaction help a quantum verifier prepare a hidden state when it has access to a reflection about that state? The paper considers a Haar-random nnn-qubit target ∣ψ⟩|\psi\rangle∣ψ⟩, an unbounded prover with complete knowledge of it, and a verifier with unrestricted computation between queries to Rψ=I−2∣ψ⟩⟨ψ∣R_\psi=I-2|\psi\rangle\langle\psi|Rψ​=I−2∣ψ⟩⟨ψ∣. Achieving constant average fidelity requires (q+1)2(B+1)=Ω(2n)(q+1)^2(B+1)=\Omega(2^n)(q+1)2(B+1)=Ω(2n), where qqq counts verifier queries and BBB counts prover-to-verifier classical bits. For 2n≤B=o(2n)2n\leq B=o(2^n)2n≤B=o(2n), this matches an existing one-message upper bound.
The proof extends the Aaronson–Kuperberg classical-advice lower bound to arbitrary classical interaction. With verifier queries replaced by identities, conditioning on a transcript restricts the target’s Haar distribution to a compatible set. Its expected logarithmic inverse measure is at most Bln⁡2B\ln2Bln2. A conditioned-Haar overlap bound and a query hybrid then bound the average change in optimal acceptance probability by 2q(1+Bln⁡2)/2n2q\sqrt{(1+B\ln2)/2^n}2q(1+Bln2)/2n​.
Consequences include a unitary-oracle separation UniqueQMAU⊈QCIPU\mathrm{UniqueQMA}^{\mathcal U}\not\subseteq\mathrm{QCIP}^{\mathcal U}UniqueQMAU⊆QCIPU, covering polynomially many classical rounds, and a sampler-augmented oracle yielding an average-case QMA–QCIP[2] gap problem. The latter uses sampler perturbations and randomly thresholded decision-oracle completions to control adaptive classical queries.
The model excludes shared setup and entanglement. The separation is relativized, uses length-respecting oracle access, and does not imply an unrelativized separation. The average-case result concerns uniform efficient distinguishers and guarantees hardness for a suitable valid decision-oracle completion, not every completion. Concurrent work gives a classical-oracle QMA–QCIP separation, without the unique-witness guarantee.
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 QMA\mathsf{QMA}QMA and QCMA\mathsf{QCMA}QCMA. However, while they are not in QCMA\mathsf{QCMA}QCMA, the problems used in both separations still lie in AM\mathsf{AM}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 QCIP\mathsf{QCIP}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 O\mathcal{O}O such that QMAO⊈QCIPO\mathsf{QMA}^{\mathcal{O}}\not\subseteq\mathsf{QCIP}^{\mathcal{O}}QMAO⊆QCIPO, thus showing that some languages indeed require quantum proofs, with no classical replacements. Since QCMA=QCIP[1]\mathsf{QCMA}=\mathsf{QCIP}[1]QCMA=QCIP[1], this strengthens the earlier QMA\mathsf{QMA}QMA--QCMA\mathsf{QCMA}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.
We initiate the study of quantum Interactive Oracle Proofs (qIOPs), a generalization of both quantum Probabilistically Checkable Proofs and quantum Interactive Proofs, as well as a quantum analogue of classical Interactive Oracle Proofs. In the model of quantum Interactive Oracle Proofs, we allow multiple rounds of quantum interaction between the quantum prover and the quantum verifier, but the verifier has limited access to quantum resources. This includes both queries to the prover's messages and the complexity of the quantum circuits applied by the verifier. The question of whether QMA admits a quantum interactive oracle proof system is a relaxation of the quantum PCP Conjecture. We show the following two main constructions of qIOPs, both of which are unconditional: - We construct a qIOP for QMA in which the verifier shares polynomially many EPR pairs with the prover at the start of the protocol and reads only a constant number of qubits from the prover's messages. - We provide a stronger construction of qIOP for QMA in which the verifier not only reads a constant number of qubits but also operates on a constant number of qubits overall, including those in their private registers. However, in this stronger setting, the communication complexity becomes exponential. This leaves open the question of whether strong qIOPs for QMA, with polynomial communication complexity, exist. As a key component of our construction, we introduce a novel single prover many-qubits test, which may be of independent interest.
We construct a classical oracle proving that, in a relativized setting, the set of languages decidable by an efficient quantum verifier with a quantum witness (QMA) is strictly bigger than those decidable with access only to a classical witness (QCMA). The separating classical oracle we construct is for a decision problem we coin spectral Forrelation -- the oracle describes two subsets of the boolean hypercube, and the computational task is to decide if there exists a quantum state whose standard basis measurement distribution is well supported on one subset while its Fourier basis measurement distribution is well supported on the other subset. This is equivalent to estimating the spectral norm of a "Forrelation" matrix between two sets that are accessible through membership queries. Our lower bound derives from a simple observation that a query algorithm with a classical witness can be run multiple times to generate many samples from a distribution, while a quantum witness is a "use once" object. This observation allows us to reduce proving a QCMA lower bound to proving a sampling hardness result which does not simultaneously prove a QMA lower bound. To prove said sampling hardness result for QCMA, we observe that quantum access to the oracle can be compressed by expressing the problem in terms of bosons -- a novel "second quantization" perspective on compressed oracle techniques, which may be of independent interest. Using this compressed perspective on the sampling problem, we prove the sampling hardness result, completing the proof.
This paper studies whether quantum proofs are more powerful than classical proofs, or in complexity terms, whether QMA=QCMA. We prove three results about this question. First, we give a "quantum oracle separation" between QMA and QCMA. More concretely, we show that any quantum algorithm needs Ω(2n/(m+1))Ω(\sqrt{2^n/(m+1)})Ω(2n/(m+1)​) queries to find an nnn-qubit "marked state" ∣ψ⟩\lvertψ\rangle∣ψ⟩, even if given an mmm-bit classical description of ∣ψ⟩\lvertψ\rangle∣ψ⟩ together with a quantum black box that recognizes ∣ψ⟩\lvertψ\rangle∣ψ⟩. Second, we give an explicit QCMA protocol that nearly achieves this lower bound. Third, we show that, in the one previously-known case where quantum proofs seemed to provide an exponential advantage, classical proofs are basically just as powerful. In particular, Watrous gave a QMA protocol for verifying non-membership in finite groups. Under plausible group-theoretic assumptions, we give a QCMA protocol for the same problem. Even with no assumptions, our protocol makes only polynomially many queries to the group oracle. We end with some conjectures about quantum versus classical oracles, and about the possibility of a classical oracle separation between QMA and QCMA.
The model of interactive oracle proofs (IOP) generalizes the notion of probabilistically checkable proof (PCP), in which a static proof is verified probabilistically by querying a small number of bits, to the interactive setting: a polynomial-time verifier interacts with an unbounded prover, but is restricted to only reading a small number of bits, in total, from the messages sent by the prover. IOPs provide a relaxed setting in which to study local probabilistic verification. They have proved instrumental in devising efficient methods for verification through subsequent compilation into non-interactive or succinct protocols. We study a quantum analogue of interactive oracle proofs (qIOP) in which the verifier and communication are both allowed to be quantum; yet the verifier is restricted to perform measurements only on a small number of qubits received from the prover. Our main result is a qIOP for any language in QMA, in which the total communication is polynomial but the verifier only reads a polylogarithmic number of qubits in total. The protocol has completeness parameter exponentially close to 111 and soundness bounded away from 111 by a constant. In the absence of a quantum PCP theorem, this provides the first information-theoretically sound local and robust characterization of QMA, albeit interactive. Our protocol combines the use of a quantum locally testable code (LTC) with classical techniques, notably probabilistically checkable proofs of proximity (PCPP). We avoid the necessity for complex multi-qubit tests employed in other settings by leveraging the local indistinguishability property of the quantum LTC.
It is not known whether a classical polynomial-time verifier can verify arbitrary polynomial-time quantum computations with an efficient quantum honest prover without computational assumptions. We show that, relative to a classical oracle, such verification is possible for a language beyond the polynomial hierarchy that is decided exactly in quantum polynomial time. The protocol is public-coin, with perfect completeness and soundness error at most 1/4. To our knowledge, no language with such a proof system was previously proved to lie outside AM relative to an oracle. For every unbounded polynomial-time computable function, the oracle can be chosen so that the message count and the oracle query counts of the quantum algorithm, verifier, and honest prover are bounded by this function of the input length. The message count is optimal up to a constant factor, since for a suitable oracle every interactive proof system for the language uses at least a constant fraction of the messages of our protocol on infinitely many lengths, with a constant depending on its verifier. The language is a variant of recursive Fourier sampling in which code tables encode secrets that address data tables. The tables are evaluated recursively, and the oracle stores only the leaves. The quantum algorithm recovers every secret exactly, and the verifier checks the prover's secrets recursively against random code entries. The recursion restricts the input in a correlated way, as the same secret fixes the code bits and chooses the free coordinate, so Håstad's switching lemma does not apply. We prove a switching theorem for these restrictions, which may be of independent interest. For instances of sufficient height, no constant-depth circuit of size 2poly(n)2^{\mathrm{poly}(n)}2poly(n) changes its output with probability above 2−Ω(n)2^{-Ω(n)}2−Ω(n) when the answer of a random instance is flipped by changing a single leaf.