אִם יִרְצֶה הַשֵּׁם
1. TL;DRs by audience
For the complexity theorist.
The paper defines quantum Interactive Oracle Proofs (qIOP), the common generalization of qPCP and QIP and the quantum analogue of classical IOPs, and proves two unconditional containments. First, QMA ⊆ GQIOP(3, poly, O(1)): a 3-message protocol with poly(n) pre-shared EPR pairs, polynomial communication, and a verifier that reads only O(1) qubits of the prover's messages, with completeness ≥ 1 − Θ(2^−s(n)) and soundness ≤ ½ + 0.001 + 2^−s(n)/2. Second, QMA ⊆ SQIOP(O(1), exp∘poly, O(1)): a strong qIOP where the verifier both reads and operates on only O(1) qubits total — including its private register — at the cost of exponential communication, with soundness ≤ 1 − 0.4p against completeness ≥ 1 − p·Θ(2^−s(n)). The engine of the second result is a new single-prover many-qubits test built from purified Pauli measurements plus Gowers–Hatami stability for the Weyl–Heisenberg group.
For the practitioner (quantum verification / delegation). Two protocols by which a verifier with almost no quantum budget can be convinced that a quantum witness for a QMA instance exists. Protocol 1 is teleportation-based: prover teleports N copies of the witness into the verifier's EPR halves, then the verifier measures its own halves and uses a classical PCP-of-proximity to correct for the teleportation one-time pad while reading only a constant number of committed bits. After the EPR distribution, communication is entirely classical. Protocol 2 removes the verifier's polynomial-size quantum computation entirely but blows communication up to exp(poly(n)) — not implementable, but the honest prover is a log-depth circuit with unbounded fan-out CNOTs.
For the general reader. The quantum PCP conjecture asks whether a quantum proof can be checked by looking at only a handful of its qubits. Nobody knows. This paper takes a step sideways: allow the checker and the prover to talk back and forth a few times, and then it turns out you really can get away with reading only a constant number of qubits. That doesn't prove the conjecture, but it shows the goal isn't obviously impossible.
For the skeptic. The headline "relaxation of the quantum PCP conjecture" is doing rhetorical work. The authors state plainly (Question 1.8) that no transformation from qIOP to qPCP is known — not even from a strong qIOP to an exponential-size qPCP. So the constructions yield "no new insights into the form of local Hamiltonians that could arise from quantum PCP reductions, nor into the reductions themselves." Furthermore, gap amplification proceeds via H′ = (1 − 2H)^⊗N, which destroys locality — the very property qPCP is about. Protocol 1's verifier still performs polynomial-size quantum computation on its private register, so "constant query complexity" does not mean "constant quantum effort." Protocol 2 fixes that but costs exponential communication, making it an existence statement rather than a protocol. Evidence for qPCP here is suggestive, not structural.
For the decision-maker. Zero near-term deployment value. This is foundational complexity theory with a plausible 5–15 year path to relevance in verifiable delegated quantum computation and succinct arguments for QMA. Its value now is as a technical toolkit — specifically the single-prover many-qubits test, which is the first information-theoretic (assumption-free) compilation of multi-prover qubit-testing into a single-prover setting. Prior compilations of this kind (KLVY23, MNZ24, NZ23) required cryptographic assumptions. Watch for follow-ups that reduce Protocol 2's communication to polynomial; that would be the milestone worth reacting to.
2. The real-world problem
Verifying quantum computation is hard in a specific way: a quantum proof cannot be copied, cannot be read without disturbing it, and cannot be spot-checked the way a classical proof can. Classically, the PCP theorem says any NP proof can be rewritten so a verifier reading O(1) random bits catches a false claim with constant probability — the foundation of hardness-of-approximation and of every succinct cryptographic argument (SNARKs) in production today.
The quantum analogue (qPCP) has been open for over two decades. Its resolution would carry implications for the foundations of quantum mechanics via the NLTS theorem (proved in ABN23, which raised confidence in qPCP's plausibility). It would also enable succinct arguments for QMA — practically, a way for a classical or near-classical client to verify that a quantum cloud service actually solved a hard quantum problem, without re-running it.
This paper asks the weaker question: if the verifier is allowed a constant number of rounds of interaction rather than a single static proof, can it get down to constant qubit-reads? The answer is yes, unconditionally.
3. Surprising and counterintuitive findings
Adding interaction breaks the barrier that a static proof couldn't. Constant-query verification of QMA, which is exactly the open qPCP conjecture in the one-shot setting, becomes provable once you allow three messages. The relaxation is not marginal — it's the difference between open and closed.
The "flipping" tests are load-bearing in a way soundness analysis doesn't reveal. In the single-qubit test, the verifier sometimes applies a phase-flip (Z) before measuring. Removing the flipped variants preserves soundness but destroys robustness: the authors explicitly constructed counterexamples that pass the single-prover Magic Square test using commuting operators only. This is a genuinely surprising failure mode — a test can be sound and still fail to certify the algebraic structure it was designed to certify. The intuition offered: without flipping, the prover need only play the game on one initial state of its choosing; flipping forces play across multiple initial states.
Cross-prover commutation is not needed. The natural guess when compressing a two-prover protocol into one prover is that the two provers' operators should still commute, and that the single prover should be tested for holding EPR pairs. Neither appears in the final protocol. The stated reason: EPR pairs exist in nonlocal games to bridge two Hilbert spaces (an operator on prover 1 equals its transpose on prover 2); with one prover there is nothing to bridge, and the operators simply do not commute.
Classical equivalences silently fail. Remark 1.4 notes that classically, adaptive and non-adaptive IOPs coincide, and reading-per-round coincides with reading-everything-at-the-end. Neither equivalence is known to survive quantization — so the definitional variants (general / restricted / strong) are genuinely distinct objects, not bookkeeping.
Protocol 1's communication is classical. Aside from the initial EPR distribution, every message is classical. If the entanglement is assumed pre-shared, the protocol is fully classical in its messaging — which motivates the paper's Question 1.12 about fully classical communication between quantum parties.
4. Jargon, translated
| Term | Plain meaning |
|---|---|
| QMA | The quantum version of NP: problems whose "yes" answers have a quantum state as a certificate that a quantum computer can check efficiently. |
| PCP | A proof rewritten so that reading a constant number of random positions suffices to catch cheating. Like a document formatted so any forgery corrupts a constant fraction of every page. |
| qPCP conjecture | The claim that QMA proofs can be rewritten so only a constant number of qubits need be measured. Open. |
| IOP | PCP plus conversation: several rounds, verifier still reads only a few bits of each message. Underlies modern SNARK constructions. |
| Query complexity q(n) | Total qubits of the prover's messages the verifier actually touches, summed over all rounds. The quantity being driven to O(1). |
| Strong qIOP | Stricter variant: the verifier must hand back the prover's entire message register each round and store nothing, so its total quantum footprint — private register included — is O(1). |
| Local Hamiltonian problem | The QMA-complete problem of estimating the lowest energy of a sum of terms each acting on a few qubits. The standard proxy for "hard quantum problem." |
| Clifford-Hamiltonian problem | A structured special case (BJSW16) where each term is C†(|0⟩⟨0|)^⊗5 C for a 5-qubit Clifford C. QMA-complete; the paper's starting point because Clifford conjugation maps Pauli measurements to Pauli measurements. |
| Gap amplification | Turning a tiny yes/no separation into a large one. Here: H′ = (1 − 2H)^⊗N with N = q²(n), pushing the gap from inverse-polynomial to 1 − 2^−s(n) vs 2^−s(n). Cost: the result is no longer local. |
| Purified measurement | Measuring coherently — recording the outcome into an ancilla register rather than collapsing — so the operation can be undone later. Central to the protocol: the prover measures in Z, hands the record to the verifier, gets it back, undoes it, and re-measures in X. |
| One-time pad (teleportation pad) | Teleportation delivers the state scrambled by random Pauli X(p)Z(q). The recipient needs (p, q) to interpret results. Here, (p, q) is classical, which is what makes the whole construction work. |
| PCP of Proximity (PCPP) | A PCP where the verifier also gets oracle access to the input and only has to reject inputs far from valid. Instantiated here from BGH+04 for Circuit Value: O(log n) randomness, O(1) queries, perfect completeness, soundness 1 − Ω(δ). |
| Gowers–Hatami stability | A theorem saying an approximate representation of a group is close to an exact one. Applied to the Weyl–Heisenberg (Pauli) group, it converts "the prover's operators nearly anti-commute" into "the prover is, up to isometry, really measuring Paulis." |
| Hadamard code | Encode a k-bit string by all 2^k of its inner products with other strings. Locally testable and self-correctable — hence usable with constant queries — but exponentially long. This is the direct source of Protocol 2's exp(poly) communication. |
| λ-biased set | A small pseudorandom substitute for "all 2^k strings," used by de la Salle (dlS22) to shorten exactly this kind of encoding. The paper tried it and it failed (see §7). |
5. Methodology
5.1 Shared framework
Both protocols reduce QMA to the 5-local Clifford-Hamiltonian problem LCH(5, 2^−p(n), 1/q(n)) (QMA-complete by BJSW16), then amplify the gap by tensoring: H′ = (1 − 2H)^⊗N, N = q²(n). Yes-instances get λmax ≥ 1 − 2^−s(n); no-instances λmax ≤ 2^−s(n). Terms of H′ can be sampled efficiently even though there are exponentially many, and each sampled term is non-local. A 5-qubit Clifford projection is then decomposed into five sequential Pauli-basis projections C†(I^⊗j−1 ⊗ (I+Z)/2 ⊗ I^⊗5−j)C, so energy estimation reduces to Pauli measurements — which is the form the qubit tests can certify.
5.2 Protocol 1 — teleportation + PCPP commitment
- Verifier and prover share nN EPR pairs (equivalently, the verifier sends half-EPR pairs in round 1).
- Prover prepares N copies of the max-eigenvalue eigenstate |φ⟩ of (1 − 2H) and teleports them, obtaining classical one-time-pad bits s = (s₀, s₁).
- Verifier samples terms l₁…l_N, measures its EPR halves with the corresponding Pauli observables, obtaining outcomes r_{i,j}.
- Verifier builds a Boolean circuit C(x) that XORs its outcomes against the pad corrections a·x₀ ⊕ b·x₁ ⊕ c·(x₀+x₁) and ANDs across the N samples.
- The key move: the prover cannot be told (a, b, c) up front — it would cheat. So the prover first commits to the pad by sending an error-correcting encoding of s; only then does the verifier send the circuit; the prover then supplies a PCPP proof that the committed codeword evaluates C to 0. The verifier checks with O(1) queries at proximity ε = 0.001.
The soundness of the PCPP is what buys constant query complexity: a committed string far from any codeword consistent with a valid pad is rejected with constant probability.
5.3 Protocol 2 — single-prover many-qubits test
The novel component. Three-round structure for a single qubit:
- Round 1: prover sends a purified Z-basis measurement record in register R.
- Verifier: applies Z, or measures in Z, or does nothing; returns R.
- Round 2: prover undoes the Z measurement, sends a purified X-basis measurement in R.
- Verifier: again applies Z / measures / does nothing.
- Round 3: verifier returns R with a one-bit question ("X" or "Z"); prover undoes the X measurement and answers.
Four tests, each with probability ¼: Z-consistency, X-consistency (standard), X-consistency (flipped), and anti-commutation. The design exploits the identity that phase-flipping a purified measurement record equals applying the observable itself, and measuring the record equals measuring the observable — so the verifier can distribute the factors of the relation XZ = −ZX across different rounds, and the consistency tests stitch them back into a statement about the final-round observables.
Scaling to n qubits (following NV16) requires the prover to send Hadamard encodings of purified measurement results for all a, b ∈ F₂ⁿ, since it must not learn which position the verifier will read. That is the exp(poly) communication. Robustness comes from Theorem 4.23: approximate anti-commutation under two distributions (µ₁, and µ₂ obtained by re-randomizing b ↦ b + r) implies, via Gowers–Hatami, that the prover's operators are O(δ)-close to a genuine Pauli representation up to isometry.
Energy estimation rides on top: to measure X(a)Z(b)Y(c), the verifier uses a control qubit in |+⟩, applies CNOTs at positions b+c in round 1 and a+c in round 2, and applies the phase gate |c| times.
6. Results, quantified
| Protocol 1 (general qIOP) | Protocol 2 (strong qIOP) | |
|---|---|---|
| Containment | QMA ⊆ GQIOP(3, poly, O(1)) | QMA ⊆ SQIOP(O(1), exp∘poly, O(1)) |
| Messages | 3 | O(1) |
| Query complexity | O(1) qubits | O(1) qubits |
| Verifier's total quantum footprint | poly(n) (private EPR halves) | O(1) qubits overall |
| Communication | poly(n) | exp(poly(n)) |
| Completeness | ≥ 1 − Θ(2^−s(n)) | ≥ 1 − p·Θ(2^−s(n)) |
| Soundness | ≤ ½ + ε + 2^−s(n)/2, ε = 0.001 | ≤ 1 − 0.4p |
| Gap | ≈ 0.499 | ≈ 0.4p (p = Pr[energy test]) |
| Honest prover cost | efficient, given copies of the witness | exp time, but log-depth with unbounded fan-out CNOT |
| Assumptions | none (information-theoretic) | none (information-theoretic) |
No confidence intervals apply — these are proved bounds, not measurements. The relevant uncertainty is instead hidden in the Θ(·) notation throughout the robustness analysis: the constants in E‖f_X(a)f_Z(b) − V†g(X(a)Z(b))V‖²_σ ≤ Θ(δ) are never made explicit, so the quantitative robustness (how small δ must be for the conclusion to bite) is unquantified.
7. Deployment and integration
Protocol 1 is the only one with any implementability story, and it is still far off. It needs poly(n) EPR pairs distributed and held coherently, N copies of the QMA witness, and a verifier performing polynomial-size quantum computation on its own register. The classical layer — the ECC commitment and the BGH+04 PCPP — is standard machinery and would be the easy part. The regime it fits is not "thin client, powerful server" (the verifier is quantum-heavy) but rather "two quantum parties, one of which shouldn't have to touch the other's data."
Protocol 2 is not implementable, by construction. Exponential communication means the message cannot be transmitted, let alone stored, even though the verifier only reads O(1) qubits of it. The authors are candid: it is offered because "the test should be of independent interest and may be a target for subsequent improvements."
Integration pathways worth tracking: - Succinct arguments for QMA. GJMZ23 builds quantum-communication succinct arguments for QMA under assumptions weaker than one-way functions, conditional on qPCP. The paper asks (Question 1.10) whether qIOPs can discharge that assumption. - Fiat–Shamir. Question 1.11 asks whether the transform applies to qIOPs to yield a non-interactive succinct quantum argument. Standard classical practice; unknown here. - Blocked path: qIOP → qPCP. Classically, public-coin IOPs with short verifier messages compile to PCPs (ABCY22). No analogue is known quantumly, and this is the load-bearing gap between the paper's results and the conjecture it relaxes.
Interoperability note. The models here are incomparable to the existing limited-verifier verification literature (FK17, ABOEM17, FHM18, surveyed in GKK19). Those protocols keep per-round verifier work constant but use polynomially many rounds, so total verifier effort is polynomial. This paper bounds total effort at a constant but places no limit on the verifier's quantum memory. Neither model dominates.
8. Limitations, assumptions, boundary conditions
- No bridge to qPCP. Stated in the paper: it is not even known whether a strong qIOP implies an exponential-size quantum PCP. The "evidence for qPCP" framing rests on plausibility, not implication.
- Locality is destroyed. Gap amplification via tensoring yields a non-local Hamiltonian. Since qPCP is fundamentally a statement about local Hamiltonians, the constructions cannot say anything about the shape of Hamiltonians a qPCP reduction would produce — the authors concede this directly.
- "Constant query" ≠ "constant work" in Protocol 1. The verifier's polynomial-size private quantum computation is exactly what motivated the strong variant. Any reading that treats Protocol 1 as a lightweight-verifier result is wrong.
- Exponential communication in Protocol 2 is not a soft cost. It is the difference between a protocol and an existence proof, and closing it is Question 1.9, the paper's own most prominent open problem.
- The known route to shortening it is blocked. The de la Salle (dlS22) λ-biased-set technique requires the prover's state to be maximally mixed for π(a)X = U(a)XU(a)† to be a unitary representation and for the Poincaré inequality to apply. In multi-prover synchronous games this is WLOG (provers start with EPR pairs); with a single prover choosing an arbitrary initial state, it fails. The authors substituted a locally testable code and still did not close the gap. This is a real technical obstruction, not an engineering gap.
- Constant-factor opacity. Robustness is stated with Θ(·) throughout; concrete parameter regimes are unavailable.
- The prover model is unbounded. Both classes assume computationally unbounded quantum provers. Protocol 1's honest prover is efficient given a supply of witness copies; Protocol 2's is exponential-time (though shallow). Neither is a claim about efficiently-preparable proofs.
- Restricted variant unaddressed. The definitions introduce restricted qIOPs (verifier's returned private register must be classical), but the results cover general and strong only. The middle of the hierarchy is unmapped.
- Minor errors that don't affect the results. Lemma 4.11's displayed chain for the no-instance case has an inverted inequality (
≤ (1−2b)^N = … ≥ 1 − 2^−s(n), where the claim being proved isλmax ≤ 2^−s(n)); Theorem 7.34's soundness is stated with= Θ(δ)where an upper boundO(δ)is meant. There is also a typo, "aglorithm," in §1.4. These read as drafting slips in a v1 preprint.
9. Future directions
The paper's own five open questions, roughly in order of consequence:
- Q1.9 — strong qIOPs with polynomial communication. The headline follow-up. Would give a genuinely lightweight quantum verifier for QMA, unconditionally.
- Q1.8 — black-box qIOP → qPCP. The result that would convert this from "adjacent progress" into "progress on qPCP."
- Q1.12 — fully classical communication with quantum prover and verifier. Motivated by the observation that Protocol 2's verifier only ever applies Z or measures in Z — its actions "have a classical flavor." Protocol 1 already achieves this modulo pre-shared entanglement.
- Q1.10 — delegation below one-way functions without qPCP.
- Q1.11 — Fiat–Shamir on qIOPs.
Beyond the paper: the single-prover many-qubits test is the reusable artifact. It is the first information-theoretic single-prover analogue of the NV16 multi-prover qubit test, and self-testing-style results tend to propagate quickly into device-independent cryptography and verification once available. The counterexample finding about flipping tests is also worth internalizing by anyone designing sequential self-tests — it is a concrete demonstration that soundness does not imply rigidity.
10. Conflicts of interest and interpretive bias
Funding. T. Vidick: AFOSR Grant FA9550-22-1-0391 and the Swiss State Secretariat for Education, Research and Innovation; part of the work done at Weizmann under a Center for New Scientists grant. B. Sun: Weizmann School of Science scholarship. Acknowledgment to Zvika Brakerski. US Air Force funding of foundational quantum verification research is routine and creates no obvious steering pressure on a pure existence result, but it is disclosed.
Interpretive bias to watch. The framing "the existence of qIOPs provides evidence supporting the validity of the qPCP conjecture" is the paper's weakest claim, and the paper itself supplies the counterargument two pages later in Question 1.8. A reader should treat the qPCP-evidence framing as motivation rather than result. Vidick is among the most prominent researchers in quantum interactive proofs (MIP* = RE), which cuts both ways: deep familiarity with the nonlocal-games toolkit is precisely why the NV16-style test could be adapted, and it also means the chosen framing — approach qPCP through nonlocal games and interaction rather than through quantizing classical PCP machinery — reflects a methodological commitment that the field does not universally share. BH13 and NN24 represent the more pessimistic line about whether such transformations survive quantization, and both are cited fairly.
Self-assessment quality. High. The limitations are stated by the authors rather than extracted against resistance: the failed dlS22 attempt is documented in detail including why it failed, the absence of a qIOP→qPCP transformation is foregrounded in the open-questions section rather than buried, and the exponential communication of the second result appears in the abstract. This is candid work.