{"id":"arxiv/2610.25657","url":"https://arxiv.org/abs/2610.25657","tags":["quant-ph"],"score":0,"title":"Quantum State Search with Classical Interactive Advice","domain":"quant-ph","source":"arxiv","authors":["Mohammed Barhoush"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-19","reactions":{}}