Probabilistically Checking Quantum Proofs, with Interaction
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 protoocls. 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. Previous works in the information-theoretic setting either considered two isolated but entangled quantum provers or quantum verifiers whose effort in a single round is small but remains polynomial when aggregated across all rounds of the protocol. 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.
Cite this item
Sun, B., & Vidick, T. (2026). Probabilistically Checking Quantum Proofs, with Interaction. In D. Moshkovitz (Editor), 41st Computational Complexity Conference (CCC 2026) (No. 4). 41 Computational Complexity Conference, Lisbon, Portugal, August 3, 2026. https://doi.org/10.4230/LIPIcs.CCC.2026.4
Click Copy to copy the citation, or select the text manually.
10.4230_lipics.ccc.2026.4.pdf
Main Document
Submitted version (Preprint)
openaccess
CC BY
1.11 MB
Adobe PDF
77479c3673059cb64e540643398960f5