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}$ — JJUW10. Since $\mathbf{IP}=\mathbf{PSPACE}$ as well — Sha90 — quantum interactive proofs are no more powerful than classical interactive proofs.
• $\mathbf{QIP}(2)$ (two-message quantum IP: verifier sends a quantum challenge, prover responds) contains $\mathbf{SZK}$, since $\mathbf{SZK}\subseteq \mathbf{AM}\subseteq \mathbf{QIP}(2)$ — AH91.
• $\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. $\mathbf{MI}{\mathbf{P}}^{\ast }=\mathbf{RE}$ (the class of recursively enumerable languages) — JNVWY20. This result resolved the Connes embedding conjecture in the negative.
• $\mathbf{MI}{\mathbf{P}}^{\ast }⊈\mathbf{MIP}$: $\mathbf{MIP}=\mathbf{NEXP}$ — BFL90, $\mathbf{NEEXP}\subseteq \mathbf{MI}{\mathbf{P}}^{\ast }$ — NW19, and $\mathbf{NEXP}⊊\mathbf{NEEXP}$ by the nondeterministic time hierarchy theorem — standard; see no-mip-to-multi-prover-extensions.

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.

Participates in

Builds on Quantum Interactive Proofs

• QIP = PSPACE

Produces Quantum Interactive Proofs

• IP ⊆ QIP
• QSZK ⊆ QIP

Barriers

• No free reduction from MIP* to MIP (via Multi-prover extensions)