Quantum Complexity Theory
Stub. A bird's-eye survey of quantum complexity classes — BQP (quantum polynomial time), QMA and the local Hamiltonian problem (quantum NP), QIP = PSPACE (quantum interactive proofs), MIP* = RE (multi-prover quantum interactive proofs, surprisingly as powerful as all recursively enumerable languages), QMA(k), and the QPCP conjecture — and the complexity of quantum entanglement: deciding whether a state is entangled, product/separable states, and QMA/QMA(2) as convex optimization problems over quantum states.
Corresponds to advanced course, Lectures 23–24. Surveys how the classical complexity landscape generalizes once the model of computation is quantum. BQP is the quantum analogue of P/BPP (efficient quantum algorithms); QMA is the quantum analogue of NP/MA, with the local Hamiltonian problem (estimate a quantum system’s ground-state energy) as its canonical complete problem; QIP = PSPACE is the striking quantum counterpart of the classical IP = PSPACE theorem (interactive-proofs-and-the-pcp-theorem); and MIP* = RE (multiple provers sharing quantum entanglement) is an even more dramatic strengthening — entangled provers make multi-prover interactive proofs as powerful as the recursively enumerable languages, resolving (negatively) the decades-old Connes embedding problem along the way. The quantum analogue of the PCP theorem (the QPCP conjecture) remains open. The entanglement half asks genuinely new (classically meaningless) questions: deciding whether a quantum state is entangled or far from it, product vs. separable states, and how the complexity of these questions differs for pure versus mixed states — framed via QMA and QMA(2) as convex optimization problems over the space of quantum states.
Outline (TODO — flesh out each)
- BQP
- QMA and the local Hamiltonian problem
- QIP = PSPACE
- MIP* = RE
- QMA(k); the QPCP conjecture
- The complexity of quantum entanglement — product and separable states
- Pure versus mixed states
- QMA and QMA(2) as convex optimization programs