arXiv preprint ·
Quantum State Search with Classical Interactive Advice
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Quantum algorithm for high-dimensional nonlinear stochastic differential equations based on Carleman linearization
Subsystem quantum Rényi-Bhattacharyya distance in 2D CFTs and its holographic applications
Field demonstration of a self-contained 10 km mobile-to-ground quantum network node via common-aperture co-propagation
Distributed Phase Tags: A Locality-Preserving Realification Compiler for Misty-State Quantum Programs
Steering of topological criticality in the Su-Schrieffer-Heeger chain via non-Hermitian substitutional impurities
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.