Quantum State Search with Classical Interactive Advice
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)=Ω(2n), 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 𝒰 such that there exists a language L∈QMA𝒰 but L∉QCIP𝒰. 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.
Related
- EasyHybrid: An Interactive Graphical Environment for Quantum, Classical and Hybrid Simulations with pDynamo3
- Quantum-classical algorithm interpolation for spatial search
- Towards Efficient Function Optimisation with Quantum–Classical Hybrid Search
- A Spectrum-Based Converse for Quantum State Discrimination and Its Applications to Classical-Quantum Channel Coding
- Persistent State Method for Resonances on Classical and Quantum Computers
BibTeX
@misc{barhoush2026quantum,
title = {{Quantum State Search with Classical Interactive Advice}},
author = {Mohammed Barhoush},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.25657},
eprint = {2610.25657},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.25657},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum State Search with Classical Interactive Advice
AU - Mohammed Barhoush
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.25657
UR - https://arxiv.org/abs/2610.25657
AB - 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 𝒰 such that there exists a language L∈QMA^𝒰 but L∉QCIP^𝒰. 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.
ER -