 |
|
||||||||||
QIP 2010 at
ETH Life
The daily web-journal of ETH Zurich:
"Nach dem grossen Schleier lüften"
18.01.2010
QIP 2010 at the
Swiss Radio DRS
Echo der Zeit
from Monday Jan 18, 2010
in German, Link >>
(Real Player recommended)
Sponsors
Pauli Center for Theoretical Studies
The Swiss National Science Foundation
ETH Zurich (Computer Science and Physics Department)
Quantum Science and Technology
CQT Singapore
QAP European Project
Sandia National Laboratories
Institute for Quantum Computing
id Quantique
QIP = PSPACE
Rahul Jain, National University of Singapore
joint work with Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous
We prove that the complexity class QIP, which consists of all problems having quantum interactive proof systems, is contained in PSPACE, the class of problems that can be solved in polynomial space. This containment is proved by applying a parallelized form of the matrix multiplicative weights update method to a class of semi-definite 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.
Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne
graphische Elemente dargestellt. Die Funktionalität der
Website ist aber trotzdem gewährleistet. Wenn Sie diese
Website regelmässig benutzen, empfehlen wir Ihnen, auf
Ihrem Computer einen aktuellen Browser zu installieren. Weitere
Informationen finden Sie auf
folgender
Seite.
Important Note:
The content in this site is accessible to any browser or
Internet device, however, some graphics will display correctly
only in the newer versions of Netscape. To get the most out of
our site we suggest you upgrade to a newer browser.
More
information
