Institutional Repository
| qip = pspace | |
| Jain Rahul; Ji Zhengfeng; Upadhyay Sarvagya; Watrous John | |
| 2010 | |
| Conference Name | 42nd ACM Symposium on Theory of Computing, STOC 2010 |
| Source | Proceedings of the Annual ACM Symposium on Theory of Computing |
| Pages | 573-581 |
| Conference Date | 43987 |
| Conference Place | Cambridge, MA, United states |
| Indexed Type | ei |
| Publish Place | United States |
| ISSN | 7378017 |
| ISBN | 9781610000000 |
| Department | (1) Department of Computer Science, Centre for Quantum Technologies, National University of Singapore, Singapore; (2) Perimeter Institute for Theoretical Physics, Waterloo, ON, Canada; (3) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China; (4) Institute for Quantum Computing, School of Computer Science, University of Waterloo, Waterloo, ON, Canada |
| English Abstract | 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. © 2010 ACM. |
| Keyword | Computational Linguistics Mathematical Programming Quantum Computers Quantum Theory |
| Sponsorship | ACM Special Interest Group on Algorithms and Computation Theory; SIGACT |
| Language | 英语 |
| Content Type | 会议论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/8868 |
| Collection | 2010软件所会议论文 |
| Recommended Citation GB/T 7714 | Jain Rahul,Ji Zhengfeng,Upadhyay Sarvagya,et al. qip = pspace[C]. United States,2010:573-581. |
| Files in This Item: | ||||||
| File Name/Size | DocType | Version | Access | License | ||
| p573-jain.pdf（360KB） | 限制开放 | -- | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment