Source-linked AI summary
QIP = PSPACE
Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous
TL;DR
The paper asks how precisely to bound the power of quantum interactive proofs, whose containment in PSPACE was previously unresolved. It applies a parallelized matrix multiplicative weights method to semidefinite programs representing quantum interactive proofs, establishing QIP = PSPACE.
Problem
The paper addresses the open problem of establishing more precise complexity bounds for QIP, the class of problems with quantum interactive proof systems.
Method
The proof applies a parallelized matrix multiplicative weights update method to semidefinite programs capturing quantum interactive-proof acceptance probabilities.
Results
QIP interactive proofs can be parallelized to three messages, which already have the full power of polynomial-message quantum interactive proofs.
Takeaways & Limitations
Together with IP = PSPACE and the immediate inclusion PSPACE ⊆ QIP, the paper establishes QIP = PSPACE.
Takeaways & Limitations
The parallel circuit implementation is only approximated in NC because the required matrix operations are not known to be exactly implementable there.
Abstract
from arXiv · showhide
We prove that the complexity class QIP, which consists of all problems having quantum interactive proof systems, is contained in PSPACE. This containment is proved by applying a parallelized form of the matrix multiplicative weights update method to a class of semidefinite programs that captures the computational power of quantum interactive proofs. As the containment of PSPACE in QIP follows immediately from the well-known equality IP = PSPACE, the equality QIP = PSPACE follows.
1 Introduction
Quantum interactive proofs extend classical interactive verification by allowing quantum information, yet their power can be characterized within PSPACE. The paper builds on QIP(2) methods, the QIP = QMAM characterization, and three-message parallelization to establish the broader result.
- Interactive proof systems use polynomial-time verifiers interacting with computationally unbounded provers, followed by probabilistic acceptance or rejection.
- IP equals PSPACE, the class of problems solvable deterministically in polynomial space, providing the lower-bound basis for the paper’s QIP characterization.
- QIP allows quantum provers and verifiers to process and exchange quantum information, extending the classical interactive-proof model.
- Quantum interactive proofs can be parallelized to three messages without losing the power of protocols with polynomially many messages.
- The paper extends the known containment QIP(2) ⊆ PSPACE to all QIP using parallelized matrix multiplicative weights for semidefinite programs.
- The characterization QIP = QMAM enables the approach by reducing general quantum interactive proofs to quantum Arthur–Merlin games.
2 Preliminaries
The preliminaries introduce the linear-algebraic, quantum-information, and semidefinite-programming concepts used later, then describe quantum Arthur–Merlin games and their reduction from QIP.
- 2.1 Linear algebra and quantum information: Quantum registers are finite-dimensional spaces with standard basis states, while quantum states are density operators and measurements produce outcomes with probabilities determined by inner products.The preliminaries also define operators, adjoints, tensor products, partial traces, and common operator classes.
- 2.2 Semidefinite programming: Semidefinite programs optimize linear objectives over positive semidefinite operators subject to linear-mapping constraints, with primal and dual feasible sets defined by opposite inequalities.The formulation uses Hermitian operators C and D and a linear map Ψ that preserves Hermiticity.
- 2.2 Semidefinite programming: Weak duality guarantees that every dual feasible solution upper-bounds the primal objective, while strict feasibility can establish strong duality and equality of optimal values.Strong duality is stated under strict dual or symmetric strict primal feasibility conditions.
- 2.3 Single-coin quantum Arthur–Merlin games: Quantum Arthur–Merlin games restrict Arthur’s messages to uniformly generated random bits while allowing Merlin’s messages and Arthur’s final computation to be quantum.The paper uses the characterization that every QIP problem has a single-coin game with perfect completeness and soundness at most 1/2 + ε.
3 A semidefinite programming formulation of the problem
The section formulates the optimal acceptance probability of a single-coin quantum Arthur–Merlin game as a semidefinite program. The formulation preserves the shared-register constraint and supports a promise-gap decision problem with strong duality.
- 3 A semidefinite programming formulation of the problem: Merlin’s conditional states must agree on register W because Merlin cannot modify W after Arthur chooses the random bit.Holding a purification of the shared state makes this agreement the only constraint on Merlin’s choices.
- 3 A semidefinite programming formulation of the problem: The optimal probability that Merlin convinces Arthur to accept is represented by a semidefinite program over a positive semidefinite operator X.The construction maps feasible X to conditional states ρ0 and ρ1 satisfying the protocol’s state constraints.
- 3 A semidefinite programming formulation of the problem: Replacing the primal inequality by equality preserves the optimum, and boundedness plus strict dual feasibility yields strong duality.Thus the primal and dual semidefinite programs have the same optimal values.
- 3 A semidefinite programming formulation of the problem: The program can be rewritten through a linear map and its adjoint without changing its optimal value.The change of variables assumes Q is invertible and produces a form closer to the earlier QIP(2) formulation.
- 3 A semidefinite programming formulation of the problem: The relevant promise-gap problem distinguishes optimal values above 7/8 from values below 5/8 while bounding ∥Q^-1∥ by a fixed constant.The optimal value is promised not to lie in the interval (5/8, 7/8).
4 The main algorithm and its analysis
The paper presents a matrix multiplicative-weights algorithm for a semidefinite program and proves correctness by constructing primal solutions on acceptance and dual solutions on rejection.
- On acceptance, the algorithm constructs a primal feasible solution whose objective value exceeds 5/8, implying an optimal value at least 7/8.The proof uses the operators ρ, Π, and ξ from the accepting iteration to build the feasible solution.
- The algorithm accepts when the semidefinite-program value exceeds 7/8 and rejects when it is below 5/8.Figure 1 specifies these thresholds for the algorithm's decision rule.
- On rejection, the constructed operator Y is dual feasible with objective value below 7/8, implying the semidefinite-program optimum is at most 5/8.The argument establishes dual feasibility and then applies the resulting objective bound.
- The analysis relies on operator inequalities for qubit systems and exponential-update bounds to control the primal and dual objectives across iterations.Lemma 1 bounds positive operators using a partial trace, while Lemma 2 supplies inequalities for matrix exponentials.
5 Proof that QIP is contained in PSPACE
The proof reduces QIP verification to a semidefinite program and shows that its algorithm can be approximated by NC computations, yielding QIP ⊆ PSPACE.
- The proof follows the QIP(2) containment strategy while extending it to all QIP through the semidefinite-program algorithm developed earlier.The algorithm is applied to the semidefinite-program characterization of QIP.
- The computed operator satisfies Q−1/2 ≤ 1/ε = 64, while the semidefinite-program value is separated by thresholds 7/8 and 5/8 for yes and no instances.Approximating Q by R^2 changes optimal values by at most 2ε, preserving the required separation.
- The operator Q is computed from the input and verifier circuit in NC(poly), after which the semidefinite-program algorithm is run on Q.The two computational steps are explicit Q construction followed by the algorithm's NC implementation.
- Although Q−1/2, matrix exponentials, and spectral decompositions require approximation, the algorithm can be approximated in NC with sufficient accuracy to distinguish the two cases.The paper identifies these approximations as the main difficulty in the second computational step.
- Each iteration is computable in NC, and the total of T = O(log N) iterations uses polynomially many stored bits, so the composition is in NC(poly).This establishes the required bounded-space simulation after composing the two steps.