qip = pspace
文献类型：期刊论文
| 作者 | Jain Rahul ; Ji Zhengfeng ; Upadhyay Sarvagya ; Watrous John |
| 刊名 | JOURNAL OF THE ACM
 |
| 出版日期 | 2011 |
| 卷号 | 58期号:6页码:- |
| 关键词 | Theory Interactive proof systems quantum computation semidefinite programming matrix multiplicative weights update method |
| ISSN号 | 0004-5411 |
| 中文摘要 | This work considers the quantum interactive proof system model of computation, which is the (classical) interactive proof system model's natural quantum computational analogue. An exact characterization of the expressive power of quantum interactive proof systems is obtained: the collection of computational problems having quantum interactive proof systems consists precisely of those problems solvable by deterministic Turing machines that use at most a polynomial amount of space (or, more succinctly, QIP = PSPACE). This characterization is proved through the use of a parallelized form of the matrix multiplicative weights update method, applied to a class of semidefinite programs that captures the computational power of quantum interactive proof systems. One striking implication of this characterization is that quantum computing provides no increase in computational power whatsoever over classical computing in the context of interactive proof systems, for it is well known that the collection of computational problems having classical interactive proof systems coincides with those problems solvable by polynomial-space computations. |
| 英文摘要 | This work considers the quantum interactive proof system model of computation, which is the (classical) interactive proof system model's natural quantum computational analogue. An exact characterization of the expressive power of quantum interactive proof systems is obtained: the collection of computational problems having quantum interactive proof systems consists precisely of those problems solvable by deterministic Turing machines that use at most a polynomial amount of space (or, more succinctly, QIP = PSPACE). This characterization is proved through the use of a parallelized form of the matrix multiplicative weights update method, applied to a class of semidefinite programs that captures the computational power of quantum interactive proof systems. One striking implication of this characterization is that quantum computing provides no increase in computational power whatsoever over classical computing in the context of interactive proof systems, for it is well known that the collection of computational problems having classical interactive proof systems coincides with those problems solvable by polynomial-space computations. |
| 学科主题 | Computer Science |
| 收录类别 | SCI |
| 资助信息 | Centre for Quantum Technologies; Singapore Ministry of Education; Singapore National Research Foundation; NSF of China60736011, 60721061; Government of Canada through Industry Canada; Province of Ontario through the Ministry of Research and Innovation; NSERC; CIFAR; MITACS; QuantumWorks; Industry Canada; Industry Canada, Ontario's Ministry of Research and Innovation; U.S. ARO |
| 语种 | 英语 |
| 公开日期 | 2013-10-08 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/16139]  |
| 专题 | 软件研究所_软件所图书馆_期刊论文 |
| 推荐引用方式 GB/T 7714 | Jain Rahul,Ji Zhengfeng,Upadhyay Sarvagya,et al. qip = pspace[J]. JOURNAL OF THE ACM,2011,58(6):-. |
| APA | Jain Rahul,Ji Zhengfeng,Upadhyay Sarvagya,&Watrous John.(2011).qip = pspace.JOURNAL OF THE ACM,58(6),-. |
| MLA | Jain Rahul,et al."qip = pspace".JOURNAL OF THE ACM 58.6(2011):-. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。