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.
|
|
|