Two-message quantum interactive proofs are in PSPACE
classification
💻 cs.CC
quant-ph
keywords
classinteractivepspacequantumtwo-messagealgorithmapproximatelycertain
read the original abstract
We prove that QIP(2), the class of problems having two-message quantum interactive proof systems, is a subset of PSPACE. This relationship is obtained by means of an efficient parallel algorithm, based on the multiplicative weights update method, for approximately solving a certain class of semidefinite programs.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.