Probabilistically Checking Quantum Proofs, with Interaction

Baocheng Sun; Thomas Vidick

arxiv: 2606.09588 · v1 · pith:MJ27DVAOnew · submitted 2026-06-08 · 💻 cs.CC · quant-ph

Probabilistically Checking Quantum Proofs, with Interaction

Baocheng Sun , Thomas Vidick This is my paper

Pith reviewed 2026-06-27 14:04 UTC · model grok-4.3

classification 💻 cs.CC quant-ph

keywords QMAquantum interactive oracle proofsqIOPlocally testable codesPCPPquantum verificationinteractive proofs

0 comments

The pith

Any language in QMA has a quantum interactive oracle proof where the verifier reads only polylogarithmically many qubits.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs a quantum interactive oracle proof for every language in QMA. The verifier interacts with the prover using polynomially many qubits in total communication, but performs measurements on only a polylogarithmic number of qubits. The protocol achieves completeness exponentially close to 1 and soundness separated from 1 by a constant. This supplies the first information-theoretically sound local characterization of QMA in an interactive setting, using a quantum locally testable code together with classical proof techniques.

Core claim

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. Our protocol combines the use of a quantum locally testable code with classical techniques, notably probabilistically checkable proofs of proximity.

What carries the argument

Quantum locally testable code with local indistinguishability property, combined with classical probabilistically checkable proofs of proximity to enable verification by measuring few qubits.

If this is right

The protocol gives an interactive local and robust characterization of QMA.
Completeness reaches exponentially close to 1 while soundness stays a constant distance from 1.
Total communication stays polynomial while the number of qubits read stays polylogarithmic.
Complex multi-qubit tests are avoided by relying on local indistinguishability.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The interactive setting may allow compilation into succinct non-interactive protocols once a quantum PCP theorem is available.
The same combination of quantum LTC and classical PCPP could apply to verification tasks for other quantum complexity classes.
Interactive local verification might reduce the need for fully non-interactive quantum proof systems in some applications.

Load-bearing premise

A quantum locally testable code exists with the local indistinguishability property that can be combined with classical PCPP techniques.

What would settle it

A proof that some language in QMA admits no qIOP with polynomial total communication and only polylogarithmic qubit reads by the verifier.

read the original abstract

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 protocols. 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. 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a qIOP for QMA with polylog qubit reads by combining quantum LTCs and classical PCPPs, but the LTC parameters are the part that needs checking.

read the letter

The main thing to know is that the authors give a qIOP for QMA in which the verifier reads only a polylog number of qubits while total communication stays polynomial, with completeness near 1 and constant soundness gap.

They achieve this by combining a quantum locally testable code with classical PCPP techniques. The local indistinguishability of the code lets them replace heavier tests with simpler measurements. This is new in providing an interactive local robust characterization of QMA without a full quantum PCP.

The construction looks solid on the high level. The paper explains how the pieces fit and why the indistinguishability property simplifies the tests compared to earlier approaches.

The soft spot is the dependence on the quantum LTC. For the polylog read bound and constant soundness to survive the full composition, the code needs the right locality, distance, and indistinguishability parameters. The paper should include an explicit calculation showing how those parameters compose with the PCPP without blowing up the query count. The stress-test concern about whether indistinguishability directly gives the required gap is fair until the details are verified.

This paper is for people working on quantum complexity, interactive proofs, and quantum codes. A reader already comfortable with classical PCPPs and basic quantum error correction will follow the argument and see the technical move.

It deserves a serious referee because the claim is substantive and the method is grounded in existing tools. I would send it out for peer review.

Referee Report

1 major / 0 minor

Summary. The paper introduces quantum interactive oracle proofs (qIOPs) and claims a protocol for any language in QMA with polynomial total communication but only polylogarithmic qubit reads by the verifier. Completeness is exponentially close to 1 and soundness is bounded away from 1 by a constant. The construction combines a quantum locally testable code (LTC) with classical probabilistically checkable proofs of proximity (PCPP), using the LTC's local indistinguishability to avoid multi-qubit tests.

Significance. If the result holds, it would give the first information-theoretically sound local and robust characterization of QMA in an interactive setting. This is a notable advance in the absence of a quantum PCP theorem and could support further work on succinct quantum verification protocols, analogous to the role of classical IOPs.

major comments (1)

[Abstract] Abstract: the central claim that the verifier reads only polylog qubits while preserving a constant soundness gap depends on the existence of a quantum LTC whose local indistinguishability and testability parameters enable replacement of multi-qubit tests by single/few-qubit measurements. No parameters (locality, distance, rate) or reduction establishing that indistinguishability yields the required soundness for QMA instances are supplied, rendering the soundness of the LTC-PCPP combination unassessable from the given text.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their review. We respond to the major comment below.

read point-by-point responses

Referee: [Abstract] Abstract: the central claim that the verifier reads only polylog qubits while preserving a constant soundness gap depends on the existence of a quantum LTC whose local indistinguishability and testability parameters enable replacement of multi-qubit tests by single/few-qubit measurements. No parameters (locality, distance, rate) or reduction establishing that indistinguishability yields the required soundness for QMA instances are supplied, rendering the soundness of the LTC-PCPP combination unassessable from the given text.

Authors: The abstract is a high-level summary of the result and therefore omits the concrete LTC parameters and the explicit reduction. These appear in the body of the manuscript, where the quantum LTC is instantiated with polylogarithmic locality, constant relative distance, and inverse-polylog rate; the local indistinguishability property is then used to replace multi-qubit tests by single-qubit measurements while preserving the constant soundness gap. We will revise the abstract to include a brief statement of these parameters together with a pointer to the relevant construction sections. revision: yes

Circularity Check

0 steps flagged

No circularity; qIOP construction for QMA combines assumed quantum LTC properties with classical PCPP without self-referential reduction

full rationale

The paper's main result is presented as a construction that assumes the existence of a quantum LTC with local indistinguishability and combines it with classical PCPP techniques to achieve polylog qubit reads. No equations or steps in the provided abstract reduce a claimed prediction or uniqueness result back to a fitted parameter or self-citation by construction. The local indistinguishability is invoked as a property of the LTC to avoid multi-qubit tests, but this is an external assumption rather than a self-definitional loop. The derivation chain remains self-contained against the stated assumptions, with no load-bearing self-citation or renaming of known results evident.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based on abstract only; the construction depends on prior quantum LTC existence and properties plus classical PCPP, treated as domain assumptions rather than new inventions.

axioms (1)

domain assumption Existence of quantum locally testable codes with local indistinguishability property suitable for combination with PCPP
Invoked in abstract to enable the protocol without complex multi-qubit tests.

pith-pipeline@v0.9.1-grok · 5803 in / 1311 out tokens · 29117 ms · 2026-06-27T14:04:54.712176+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

15 extracted references · 3 linked inside Pith

[1]

Interactive proofs for quantum computations.arXiv preprint arXiv:1704.04487,

[ABOEM17] Dorit Aharonov, Michael Ben-Or, Elad Eban, and Urmila Mahadev. Interactive proofs for quantum computations.arXiv preprint arXiv:1704.04487,

Pith/arXiv arXiv
[2]

Vad- han

[BGH+04] Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vad- han. Robust PCPs of proximity, shorter PCPs and applications to coding. In L´ aszl´ o Babai, editor,Proceedings of the 36th Annual ACM Symposium on Theory of Com- puting, Chicago, IL, USA, June 13-16, 2004, pages 1–10. ACM,

2004
[3]

Zero-knowledge proof systems for QMA

[BJSW16] Anne Broadbent, Zhengfeng Ji, Fang Song, and John Watrous. Zero-knowledge proof systems for QMA. In Irit Dinur, editor,IEEE 57th Annual Symposium on Foun- dations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 31–40. IEEE Computer Society,

2016
[4]

Succinct classical verifica- tion of quantum computation

[BKL+22] James Bartusek, Yael Tauman Kalai, Alex Lombardi, Fermi Ma, Giulio Malavolta, Vinod Vaikuntanathan, Thomas Vidick, and Lisa Yang. Succinct classical verifica- tion of quantum computation. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barb...

2022
[5]

Deran- domised tensor product gap amplification for quantum Hamiltonians.arXiv preprint arXiv:2510.01333,

[BMVZ25] Thiago Bergamaschi, Tony Metger, Thomas Vidick, and Tina Zhang. Deran- domised tensor product gap amplification for quantum Hamiltonians.arXiv preprint arXiv:2510.01333,

arXiv
[6]

Efficiently stable presentations from error-correcting codes.arXiv preprint arXiv:2311.04681,

[CVY23] Michael Chapman, Thomas Vidick, and Henry Yuen. Efficiently stable presentations from error-correcting codes.arXiv preprint arXiv:2311.04681,

arXiv
[7]

Expansion of high-dimensional cubical complexes: with application to quantum locally testable codes

[DLV24] Irit Dinur, Ting-Chun Lin, and Thomas Vidick. Expansion of high-dimensional cubical complexes: with application to quantum locally testable codes. In65th IEEE Annual 47 Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024, pages 379–385. IEEE,

2024
[8]

[EH17] Lior Eldar and Aram W. Harrow. Local hamiltonians whose ground states are hard to approximate. In Chris Umans, editor,58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 427–438. IEEE Computer Society,

2017
[9]

[Got97] Daniel Gottesman.Stabilizer codes and quantum error correction.PhD thesis, Thesis, eprint: quant-ph/9705052,

Pith/arXiv arXiv
[10]

A simple protocol for verifiable delegation of quantum compu- tation in one round

[Gri19] Alex Bredariol Grilo. A simple protocol for verifiable delegation of quantum compu- tation in one round. In46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, volume 132, pages 28–1,

2019
[11]

Two bases suffice for QMA 1-completeness.arXiv preprint arXiv:2509.24390,

[MN25] Henry Ma and Anand Natarajan. Two bases suffice for QMA 1-completeness.arXiv preprint arXiv:2509.24390,

arXiv
[12]

Succinct arguments for QMA from standard assumptions via compiled nonlocal games.CoRR, abs/2404.19754,

[MNZ24] Tony Metger, Anand Natarajan, and Tina Zhang. Succinct arguments for QMA from standard assumptions via compiled nonlocal games.CoRR, abs/2404.19754,

arXiv
[13]

The status of the quantum PCP conjecture (games version).CoRR, abs/2403.13084,

[NN24] Anand Natarajan and Chinmay Nirkhe. The status of the quantum PCP conjecture (games version).CoRR, abs/2403.13084,

arXiv
[14]

Robust self-testing of many-qubit states

[NV16] Anand Natarajan and Thomas Vidick. Robust self-testing of many-qubit states. CoRR, abs/1610.03574,

Pith/arXiv arXiv
[15]

Bounding the quantum value of compiled non- local games: From CHSH to BQP verification

[NZ23] Anand Natarajan and Tina Zhang. Bounding the quantum value of compiled non- local games: From CHSH to BQP verification. In64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 1342–1348. IEEE,

2023

[1] [1]

Interactive proofs for quantum computations.arXiv preprint arXiv:1704.04487,

[ABOEM17] Dorit Aharonov, Michael Ben-Or, Elad Eban, and Urmila Mahadev. Interactive proofs for quantum computations.arXiv preprint arXiv:1704.04487,

Pith/arXiv arXiv

[2] [2]

Vad- han

[BGH+04] Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vad- han. Robust PCPs of proximity, shorter PCPs and applications to coding. In L´ aszl´ o Babai, editor,Proceedings of the 36th Annual ACM Symposium on Theory of Com- puting, Chicago, IL, USA, June 13-16, 2004, pages 1–10. ACM,

2004

[3] [3]

Zero-knowledge proof systems for QMA

[BJSW16] Anne Broadbent, Zhengfeng Ji, Fang Song, and John Watrous. Zero-knowledge proof systems for QMA. In Irit Dinur, editor,IEEE 57th Annual Symposium on Foun- dations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 31–40. IEEE Computer Society,

2016

[4] [4]

Succinct classical verifica- tion of quantum computation

[BKL+22] James Bartusek, Yael Tauman Kalai, Alex Lombardi, Fermi Ma, Giulio Malavolta, Vinod Vaikuntanathan, Thomas Vidick, and Lisa Yang. Succinct classical verifica- tion of quantum computation. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barb...

2022

[5] [5]

Deran- domised tensor product gap amplification for quantum Hamiltonians.arXiv preprint arXiv:2510.01333,

[BMVZ25] Thiago Bergamaschi, Tony Metger, Thomas Vidick, and Tina Zhang. Deran- domised tensor product gap amplification for quantum Hamiltonians.arXiv preprint arXiv:2510.01333,

arXiv

[6] [6]

Efficiently stable presentations from error-correcting codes.arXiv preprint arXiv:2311.04681,

[CVY23] Michael Chapman, Thomas Vidick, and Henry Yuen. Efficiently stable presentations from error-correcting codes.arXiv preprint arXiv:2311.04681,

arXiv

[7] [7]

Expansion of high-dimensional cubical complexes: with application to quantum locally testable codes

[DLV24] Irit Dinur, Ting-Chun Lin, and Thomas Vidick. Expansion of high-dimensional cubical complexes: with application to quantum locally testable codes. In65th IEEE Annual 47 Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024, pages 379–385. IEEE,

2024

[8] [8]

[EH17] Lior Eldar and Aram W. Harrow. Local hamiltonians whose ground states are hard to approximate. In Chris Umans, editor,58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 427–438. IEEE Computer Society,

2017

[9] [9]

[Got97] Daniel Gottesman.Stabilizer codes and quantum error correction.PhD thesis, Thesis, eprint: quant-ph/9705052,

Pith/arXiv arXiv

[10] [10]

A simple protocol for verifiable delegation of quantum compu- tation in one round

[Gri19] Alex Bredariol Grilo. A simple protocol for verifiable delegation of quantum compu- tation in one round. In46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, volume 132, pages 28–1,

2019

[11] [11]

Two bases suffice for QMA 1-completeness.arXiv preprint arXiv:2509.24390,

[MN25] Henry Ma and Anand Natarajan. Two bases suffice for QMA 1-completeness.arXiv preprint arXiv:2509.24390,

arXiv

[12] [12]

Succinct arguments for QMA from standard assumptions via compiled nonlocal games.CoRR, abs/2404.19754,

[MNZ24] Tony Metger, Anand Natarajan, and Tina Zhang. Succinct arguments for QMA from standard assumptions via compiled nonlocal games.CoRR, abs/2404.19754,

arXiv

[13] [13]

The status of the quantum PCP conjecture (games version).CoRR, abs/2403.13084,

[NN24] Anand Natarajan and Chinmay Nirkhe. The status of the quantum PCP conjecture (games version).CoRR, abs/2403.13084,

arXiv

[14] [14]

Robust self-testing of many-qubit states

[NV16] Anand Natarajan and Thomas Vidick. Robust self-testing of many-qubit states. CoRR, abs/1610.03574,

Pith/arXiv arXiv

[15] [15]

Bounding the quantum value of compiled non- local games: From CHSH to BQP verification

[NZ23] Anand Natarajan and Tina Zhang. Bounding the quantum value of compiled non- local games: From CHSH to BQP verification. In64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 1342–1348. IEEE,

2023