| qip = pspace | |
| Jain Rahul; Ji Zhengfeng; Upadhyay Sarvagya; Watrous John | |
| 2010 | |
| 会议名称 | 42nd ACM Symposium on Theory of Computing, STOC 2010 |
| 会议录名称 | Proceedings of the Annual ACM Symposium on Theory of Computing |
| 页码 | 573-581 |
| 会议日期 | 43987 |
| 会议地点 | Cambridge, MA, United states |
| 收录类别 | ei |
| 出版地 | United States |
| ISSN | 7378017 |
| ISBN | 9781610000000 |
| 部门归属 | (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 |
| 摘要 | 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. |
| 关键词 | Computational Linguistics Mathematical Programming Quantum Computers Quantum Theory |
| 主办者 | ACM Special Interest Group on Algorithms and Computation Theory; SIGACT |
| 语种 | 英语 |
| 内容类型 | 会议论文 |
| URI标识 | http://ir.iscas.ac.cn/handle/311060/8868 |
| 专题 | 2010软件所会议论文 |
| 推荐引用方式 GB/T 7714 | Jain Rahul,Ji Zhengfeng,Upadhyay Sarvagya,et al. qip = pspace[C]. United States,2010:573-581. |
| 条目包含的文件 | ||||||
| 文件名称/大小 | 文献类型 | 版本类型 | 开放类型 | 使用许可 | ||
| p573-jain.pdf（360KB） | 限制开放 | -- | 请求全文 | |||
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论