In computational complexity, interactive proof systems model a game between a powerful prover (Merlin) who claims a statement is true, and a polynomial-time verifier (Arthur) who tries to validate that claim. When we introduce quantum mechanics into this framework, the rules of verification change dramatically.
For a single prover, adding quantum capabilities does not expand the horizon of what can be verified as much as one might expect. In their landmark paper QIP = PSPACE, Rahul Jain et al. proved that the class of languages decidable by quantum interactive proofs ($\text{QIP}$) is exactly equal to $\text{PSPACE}$ (Polynomial Space), the same as its classical counterpart. The intuition behind this equivalence is that a single prover's optimal quantum strategy can be completely formulated as a semidefinite program. Because these mathematical programs can be solved using polynomial space, a classical verifier can simulate the entire quantum interaction.
To break past this space-bounded ceiling, we must introduce a second interrogation room. By moving from a single prover to multiple provers, the verifier gains the ability to cross-examine them. However, in the quantum world, the power of this cross-examination depends entirely on a single question: Are the provers allowed to be entangled?
The Power of Unentanglement and Hierarchy Collapse
If we strictly forbid the provers from sharing quantum entanglement, we enter the domain of $\text{QMA}(k)$—Quantum Merlin-Arthur protocols with $k$ unentangled provers. At first glance, depriving the provers of a resource like entanglement might seem to weaken the proof system. In reality, it does the opposite: it empowers the verifier.
When provers are guaranteed to be unentangled, their joint state must be a product state. This structural independence is a powerful constraint that the verifier can exploit. In The Power of Unentanglement, Salman Beigi et al. demonstrated that a verifier can leverage this lack of correlation to perform product-state tests (such as the SWAP test). This allows the verifier to ensure that the provers are not colluding or sending entangled states, making it possible to verify hard classical problems like 3SAT using significantly shorter quantum proofs than would otherwise be required.
Unentangled Provers (QMA(k))
[Prover 1] ---- (Product State) ----> [Verifier] <---- (Product State) ---- [Prover 2]
|
(Performs SWAP Test)
This raises a fundamental structural question: does adding more unentangled provers ($k > 2$) make the system progressively more powerful? The authors showed that under a "weak Additivity Conjecture" in quantum information theory, the entire hierarchy collapses to just two provers:
$$\text{QMA}(k) = \text{QMA}(2) \quad \text{for all } k \ge 2$$
The intuition behind this collapse lies in protocol amplification. If a verifier can efficiently amplify the gap between a true statement and a false statement using only two provers, any multi-prover protocol can be compressed. The verifier can simply ask two independent provers to each provide a subset of the $k$ required proofs and then run the product tests across those subsets.
This tension between independent challenges and prover coordination also manifests in public-coin systems. Scott Aaronson et al. explored this boundary in AM with Multiple Merlins, investigating whether the computational advantages of unentangled quantum provers hold when the verifier's randomness is completely transparent.
The Explosion of Entangled Provers
What happens if we flip the script and allow the provers to share quantum entanglement? This defines the class $\text{MIP}^*$.
Intuitively, entanglement should make it easier for provers to cheat. By sharing entangled pairs, they can use non-local correlations (violating Bell inequalities) to coordinate their answers to the verifier's questions without actively communicating. This coordination threatens to undermine the verifier's ability to cross-examine them effectively.
However, the verifier can turn this vulnerability into a tool through a mechanism known as rigidity. Because certain non-local games have unique optimal quantum strategies, the verifier can use the provers' responses to force them into sharing a highly specific entangled state and executing highly specific quantum operations.
Instead of checking the problem directly, the verifier tests the provers' quantum behavior. In Quantum soundness of testing tensor codes, Zhengfeng Ji et al. proved that error-correcting tensor codes remain robust even when tested by provers sharing entanglement. This quantum soundness allows the verifier to delegate massive, complex computations to the provers while maintaining complete control over the verification process.
Entangled Provers (MIP*)
[Prover 1] <====== (Entanglement / Non-local Correlations) ======> [Prover 2]
| |
(Question) (Question)
v v
[Verifier] <------------------------------------------------------- [Verifier]
|
(Rigidity & Tensor Code Tests)
By forcing the provers to manage massive entangled states, the verifier can scale up the complexity of the problems being checked. In Quantum proof systems for iterated exponential time, and beyond, Joseph F. Fitzsimons et al. introduced a compression technique for $\text{MIP}^*$ protocols. This technique allows a verifier to check languages with iterated exponential time complexity, demonstrating that the power of entangled provers vastly outstrips classical multi-prover systems.
Alternative Dynamics and Verifier Constraints
The boundaries of quantum verification are highly sensitive to the exact constraints placed on both the provers and the verifier. If we alter the communication rules or the provers' motivations, the complexity landscape shifts again:
- Classical Communication: In Quantum Multi Prover Interactive Proofs with Communicating Provers, Michael Ben-Or et al. analyzed a model where provers can communicate classically but share no entanglement, proving that this configuration can efficiently recognize languages in $\text{NEXP}$.
- Rational Agents: Moving away from the traditional honest-versus-malicious paradigm, Samuel McCauley et al. explored Rational Proofs with Multiple Provers, modeling the interaction using game theory where provers are motivated purely by maximizing a financial payout.
We can also look at these systems by restricting the verifier's own computational resources. Remarkably, a verifier does not even need quantum hardware to exploit the power of quantum provers. In Classical Verification of Quantum Proofs, Zhengfeng Ji demonstrated that a purely classical verifier can use a multi-player one-round game to verify $\text{QMA}$-hard problems, showing that the structural rigidity of entanglement can be harvested using classical checks alone.
Conversely, if the verifier is quantum but severely space-bounded, the internal mechanics of the verifier's circuit become critical. In Space-bounded quantum interactive proof systems, François Le Gall et al. discovered a sharp "measurement gap" when the verifier is restricted to logarithmic space. If the logspace verifier is forced to remain purely unitary, the system's power is bounded within polynomial time ($\text{P}$). However, if the verifier is allowed to make intermediate measurements during the interaction, the system's power expands to encompass $\text{NP}$. This reveals that when memory is scarce, the ability to collapse quantum states via measurement acts as an essential computational resource.
Key Foundational Work
The Power of Unentanglement (2009) — contributed 5 concept elements to this direction.
Quantum Multi Prover Interactive Proofs with Communicating Provers (2008) — contributed 2 concept elements to this direction.
QIP = PSPACE (2009) — contributed 2 concept elements to this direction.