In the classical theory of computation, an interactive proof is a dialogue between a computationally limited Verifier and an all-powerful Prover. The goal is for the Prover to convince the Verifier that a statement is true (like "this graph is 3-colorable"). If the Verifier can talk to multiple provers who are kept in separate rooms and cannot communicate, the Verifier gains even more power—they can cross-examine the provers to ensure they aren't lying, much like a detective questioning suspects.
However, when these provers share quantum entanglement, the rules of the game change. Entanglement allows provers to coordinate their answers through non-local correlations, even when they are physically separated. For years, researchers wondered: does this coordination help the provers cheat, or does it give the Verifier a more powerful tool for verification?
The Double-Edged Sword of Entanglement
Initially, entanglement seemed like a nuisance for researchers. In The complexity-theoretic Bell inequality, Zhengfeng Ji explains that shared entanglement allows provers to bypass the logical constraints of classical systems. Because they can produce correlated responses that are impossible in a classical world, they might trick a Verifier into accepting a false proof.
This challenge is highlighted in Experimental relativistic zero-knowledge proofs by Pouriya Alikhani and colleagues. While special relativity prevents provers from communicating faster than light, it does not prevent them from using pre-shared entanglement to coordinate. This creates a potential security gap in protocols that assume provers are strictly independent.
From PSPACE to the Infinite
To understand the power of entanglement, we first look at the single-prover case. In the landmark paper QIP = PSPACE, Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous proved that quantum communication with a single prover doesn't actually add power beyond classical polynomial space (PSPACE).
But the story changes dramatically with multiple provers. In Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-Prover Interactive Proof Systems, Tsuyoshi Ito and his co-authors showed that even with just three entangled provers providing a single bit of information, a Verifier can check problems in NEXP (Nondeterministic Exponential Time).
The intuition here is that entanglement isn't just a way to cheat; it's a way to create rigidity.
Rigidity: The Verifier’s Secret Weapon
The breakthrough in this field came from the realization that if entangled provers want to win a specific game with the maximum possible probability, they are often forced to use a unique quantum state and unique measurements. This phenomenon is called rigidity or self-testing.
In Classical Verification of Quantum Proofs, Zhengfeng Ji demonstrated that a classical Verifier can use this rigidity to "force" provers to behave like a specific quantum circuit. By asking the right classical questions, the Verifier can effectively "see" into the quantum state shared by the provers.
This mechanism allows for incredible scaling:
- Compression: In Compression of Quantum Multi-Prover Interactive Proofs, Zhengfeng Ji showed that complex, multi-round interactions can be compressed into simple, one-round games.
- Exponential Scaling: Joseph F. Fitzsimons, Zhengfeng Ji, Thomas Vidick, and Henry Yuen proved in Quantum proof systems for iterated exponential time, and beyond that these systems could verify problems far beyond NEXP, reaching into iterated exponential time.
The Ultimate Result: MIP* = RE
The culmination of this research direction is the proof that MIP* = RE, presented in the 2020 paper MIP*=RE by Zhengfeng Ji, Anand Natarajan, Thomas Vidick, and John C. Wright.
This result states that multi-prover interactive proofs with entanglement ($MIP^*$) can verify any problem that is "Recursively Enumerable" ($RE$). This includes the Halting Problem—the question of whether a computer program will eventually stop running.
How can a classical Verifier check something undecidable? The intuition lies in the fact that the amount of entanglement provers can share is unbounded. The Verifier uses a recursive "gap-amplification" technique. They force the provers to use larger and larger entangled states to prove properties of larger and larger computations. Because the Verifier can use the "rigidity" of these massive quantum states to ensure the provers are following the rules, they can effectively delegate a computation of infinite size to the provers.
To ensure this logic held up, the researchers had to prove the Quantum soundness of the classical low individual degree test. This mathematical "rescue mission" by Anand Natarajan, John Wright, and others confirmed that even when provers use complex quantum strategies, the classical tests used to verify their honesty remain robust.
Ultimately, this line of research shows that entanglement doesn't just change the numerical outcomes of physics experiments; it fundamentally shifts the boundary of what is mathematically verifiable.