Two-message quantum interactive proofs are in PSPACE

Simple item page
dc.creatorJain, Rahul
dc.creatorUpadhyay, Sarvagya
dc.creatorWatrous, John
dc.date2009-05-08
dc.date.accessioned2026-07-07T13:13:07Z
dc.date.available2026-07-07T13:13:07Z
dc.descriptionWe 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.
dc.description24 pages
dc.identifierhttps://arxiv.org/abs/0905.1300
dc.identifierhttp://arxiv.org/abs/0905.1300
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/229784
dc.subjectComputational Complexity
dc.subjectQuantum Physics
dc.subjectF.1.3; F.2.1
dc.titleTwo-message quantum interactive proofs are in PSPACE
dc.typetext

Files

Collections

arXiv