| Title: | qip = pspace |
| Author: | Jain Rahul
; Ji Zhengfeng
; Upadhyay Sarvagya
; Watrous John
|
| Source: | Proceedings of the Annual ACM Symposium on Theory of Computing
|
| Conference Name: | 42nd ACM Symposium on Theory of Computing, STOC 2010
|
| Conference Date: | 43987
|
| Issued Date: | 2010
|
| Conference Place: | Cambridge, MA, United states
|
| Keyword: | Computational linguistics
; Mathematical programming
; Quantum computers
; Quantum theory
|
| Publish Place: | United States
|
| Indexed Type: | ei
|
| 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
|
| Sponsorship: | ACM Special Interest Group on Algorithms and Computation Theory; SIGACT
|
| 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. |
| Language: | 英语
|
| Content Type: | 会议论文
|
| URI: | http://ir.iscas.ac.cn/handle/311060/8868
|
| Appears in Collections: | 中科院软件所图书馆_2010软件所会议论文
|
| File Name/ File Size |
Content Type |
Version |
Access |
License |
|
|---|
| p573-jain.pdf（360KB） | -- | -- | 限制开放 | -- | 联系获取全文 |
|
| Recommended Citation: | |
Jain Rahul,Ji Zhengfeng,Upadhyay Sarvagya,et al. qip = pspace[C]. 见:42nd ACM Symposium on Theory of Computing, STOC 2010. Cambridge, MA, United states. 43987.
|
|
|
