Quantum Interactive Proofs

The quantum analogue of IP: the class of decision problems verifiable by an interactive proof where both the verifier (a polynomial-time quantum algorithm) and the prover (unbounded) exchange quantum messages over polynomially many rounds. We require:

1. If the answer is “yes,” there exists a prover strategy causing the verifier to accept with probability at least 2/3.
2. If the answer is “no,” for every prover strategy the verifier rejects with probability at least 2/3.

See the complexity zoo entry here.

Known relationships

• $\mathbf{IP}\subseteq \mathbf{QIP}$: classical interactive proofs are a special case (restrict messages to classical strings).
• $\mathbf{QIP}=\mathbf{PSPACE}$ — TODO citation (Jain, Ji, Upadhyay, Watrous 2010). Since $\mathbf{IP}=\mathbf{PSPACE}$ as well, quantum interactive proofs are no more powerful than classical interactive proofs. This is a striking collapse: quantum communication between prover and verifier adds no power to multi-round interactive proofs.
• $\mathbf{QIP}(2)$ (two-message quantum IP: verifier sends a quantum challenge, prover responds) strictly contains $\mathbf{SZK}$ and is believed to contain problems outside $\mathbf{AM}$ — TODO citation.
• $\mathbf{QIP}(1)=\mathbf{QMA}$: a single-message quantum interactive proof is exactly Quantum Merlin-Arthur.

Multi-prover extensions

• $\mathbf{MI}{\mathbf{P}}^{\ast }$ (multiple quantum-entangled provers): provers share arbitrary prior entanglement but cannot communicate during the protocol. Remarkably, $\mathbf{MI}{\mathbf{P}}^{\ast }=\mathbf{RE}$ (the class of recursively enumerable languages) — TODO citation (Ji, Natarajan, Vidick, Wright, Yuen 2020). This means entangled provers can convince a classical verifier of undecidable statements! This result resolved the Connes embedding conjecture in the negative.
• $\mathbf{MI}{\mathbf{P}}^{\ast }$ vs $\mathbf{MIP}$: the classical multi-prover class $\mathbf{MIP}=\mathbf{NEXP}$, so entanglement exponentially (in fact, incomparably) increases prover power.

Relevance to cryptography

• $\mathbf{QIP}=\mathbf{PSPACE}$ implies that quantum zero-knowledge protocols with multiple rounds are no more expressive than classical ones from a language-recognition standpoint.
• The $\mathbf{MI}{\mathbf{P}}^{\ast }=\mathbf{RE}$ result has profound implications: it shows that quantum entanglement can be used to certify computations in ways that are fundamentally unverifiable by classical means — raising both opportunities and challenges for quantum cryptographic protocols.