QIP = PSPACE

Equivalence · quantum setting · JJUW10, Sha90

Statement

QIP $=$ PSPACE — JJUW10, who prove $\mathbf{QIP}\subseteq \mathbf{PSPACE}$; the reverse inclusion follows from PSPACE ⊆ IP — Sha90 — and IP ⊆ QIP.

Sketch

Every quantum interactive proof can be parallelized to three messages — KW00. Its maximum acceptance probability is then the optimum of a semidefinite program of exponential dimension, which JJUW10 approximate with a matrix multiplicative-weights method parallelized by circuits of depth polylogarithmic in that dimension, which is polynomial depth, and polynomial space evaluates such circuits — JJUW10.