In quantum complexity theory, verifying the correctness of a quantum computation is a fundamental challenge. For problems in QMA (Quantum Merlin-Arthur)—the quantum analogue of NP—an untrusted prover possesses a quantum state (a "proof") that certifies the solution to a hard problem, such as the local Hamiltonian problem established by Oded Regev 0001 in 3-local Hamiltonian is QMA-complete.
Traditionally, verifying these proofs requires extensive quantum communication, multiple rounds of interaction, or large message sizes. This creates a steep bottleneck for resource-constrained verifiers, especially classical ones. To overcome this, a major research direction focuses on protocol compression: collapsing multi-round quantum interactions into minimal rounds and shrinking large quantum messages into succinct classical or quantum arguments.
Collapsing Rounds via State Snapshots
The most intuitive way to make an interactive proof more efficient is to reduce the number of communication rounds. If a protocol requires a verifier and a prover to go back and forth multiple times, can we compress that entire exchange into a single round?
The core mechanism for achieving this involves intermediate state snapshots. In Using Entanglement in Quantum Multi-Prover Interactive Proofs, Hirotada Kobayashi et al. demonstrated that a multi-round protocol can be collapsed into a single round by introducing an auxiliary prover. Instead of executing the protocol step-by-step, the provers are forced to provide a snapshot of the intermediate quantum state from the exact midpoint of the original protocol.
To ensure the provers are not cheating, the verifier uses a simple but powerful trick: they randomly choose to either execute the simulation forward to the end or backward to the beginning. If the provers provide an inconsistent snapshot, one of these two verification paths will catch the deception with predictable probability.
This capability to bound and minimize interaction depth is a structural feature of quantum proofs. For single-prover systems, Rahul Jain et al. proved in QIP = PSPACE that any multi-round quantum interactive proof can be compressed into a three-message format without any loss in verification power. Even when shifting paradigms to game-theoretic models, such as the rational provers studied by Samuel McCauley et al. in Rational Proofs with Multiple Provers, multi-prover interactions can consistently be reduced to a minimal three-round, two-prover structure.
From Quantum Messages to Classical Nonlocal Games
While reducing rounds simplifies the interaction, the verifier might still need to receive or process complex quantum states. To achieve true communication efficiency, researchers aim to replace quantum messages entirely with short, classical strings.
The breakthrough idea here is to encode the verification logic directly into a nonlocal game. In Compression of Quantum Multi-Prover Interactive Proofs, Zhengfeng Ji showed that any multi-round quantum multiprover proof system can be compiled into a single-round nonlocal game where the verifier only sends logarithmic-length classical queries and receives constant-length classical responses.
[Multi-Round Quantum Proof] ──(Compression)──> [Single-Round Nonlocal Game]
- Heavy quantum exchanges - Log-length classical queries
- High round complexity - Constant-length classical responses
Instead of inspecting a physical quantum state, a classical verifier leverages the quantum correlations (entanglement) shared between non-communicating provers. By asking strategically chosen classical questions, the verifier forces the provers to perform local quantum measurements on their shared state and report the classical outcomes.
This compression framework is highly scalable. Joseph F. Fitzsimons et al. extended this technique in Quantum proof systems for iterated exponential time, and beyond, showing that by recursively reducing the verifier's description size, such systems can verify languages of iterated exponential time complexity using a fixed number of provers.
To guarantee that these classical queries remain secure against malicious provers exploiting quantum entanglement, the underlying classical codes must be robust. This was validated by Zhengfeng Ji et al. in Quantum soundness of testing tensor codes, where the authors used operator algebra to prove that classical tensor codes maintain their soundness even when evaluated against general quantum strategies.
Achieving Succinctness via Cryptographic Commitments
When multiple non-communicating provers are not available, a single prover can still be compressed into a succinct argument using cryptographic commitments. The goal is to let a prover "lock" themselves to a large quantum state using a tiny commitment string, and later prove local properties of that state without revealing or transmitting the whole thing.
In Commitments to Quantum States, Sam Gunn et al. formalized this using a security property called swap binding. This framework allows a prover to commit to a massive quantum state via a tiny quantum message, yielding three-message succinct arguments for QMA. To make this process entirely classical for the verifier, Sam Gunn et al. later leveraged the lattice-based Learning With Errors (LWE) assumption in Classical Commitments to Quantum States. This protocol allows a purely classical machine to force a quantum prover to commit to a quantum state, creating a generic pipeline to verify quantum Probabilistically Checkable Proofs (PCPs).
[Quantum Prover] ───(LWE-based Classical Commitment)───> [Classical Verifier]
<───(Short Classical Challenge)────────
───(Succinct Classical Opening)───────>
An alternative algorithmic approach to this problem is the Quantum Merkle Tree, introduced by Ramis Movassagh et al. in Quantum Merkle Trees. Operating in the Quantum Haar Random Oracle Model, this structure allows a prover to cryptographically hash a large quantum state down to a small root. The verifier can then succinctly check local properties of the state with minimal communication overhead.
By combining round-reduction techniques, nonlocal classical games, and succinct commitments, this research direction bridges the gap between quantum complexity and classical verification, showing that verifying quantum states does not inherently require complex quantum infrastructure.
Key Foundational Work
Using Entanglement in Quantum Multi-Prover Interactive Proofs (2009) — contributed 5 concept elements to this direction.
QIP = PSPACE (2009) — contributed 2 concept elements to this direction.
3-local Hamiltonian is QMA-complete (2003) — contributed 1 concept elements to this direction.