2026-07-23T16:50:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27046 2026-07-23T11:36:18Z ddc:004 open_access

Probabilistically Checking Quantum Proofs, with Interaction Sun, Baocheng Vidick, Thomas quantum complexity theory quantum probabilistically checkable proofs interactive oracle proofs quantum locally testable codes QMA 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Baocheng Sun and Thomas Vidick 2026 Is Part Of LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2026.4 urn:nbn:de:0030-drops-270463 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.4 eng https://creativecommons.org/licenses/by/4.0/legalcode