中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 软件所图书馆  > 期刊论文
Subject: Computer Science
Title:
qip = pspace
Author: Jain Rahul ; Ji Zhengfeng ; Upadhyay Sarvagya ; Watrous John
Keyword: Theory ; Interactive proof systems ; quantum computation ; semidefinite programming ; matrix multiplicative weights update method
Source: JOURNAL OF THE ACM
Issued Date: 2011
Volume: 58, Issue:6, Pages:-
Indexed Type: SCI
Department: Jain Rahul Natl Univ Singapore Dept Comp Sci Singapore 117543 Singapore. Ji Zhengfeng Perimeter Inst Theorit Phys Waterloo ON N2L 2Y5 Canada. Upadhyay Sarvagya; Watrous John Univ Waterloo David R Cheriton Sch Comp Sci Waterloo ON N2L 3G1 Canada. Upadhyay Sarvagya; Watrous John Univ Waterloo Inst Quantum Comp Waterloo ON N2L 3G1 Canada. Ji Zhengfeng Chinese Acad Sci Inst Software Beijing 100864 Peoples R China.
Sponsorship: 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
Abstract: 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.
English Abstract: 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.
Language: 英语
Content Type: 期刊论文
URI: http://ir.iscas.ac.cn/handle/311060/16139
Appears in Collections:软件所图书馆_期刊论文

Files in This Item:

There are no files associated with this item.


Recommended Citation:
Jain Rahul,Ji Zhengfeng,Upadhyay Sarvagya,et al. qip = pspace[J]. JOURNAL OF THE ACM,2011-01-01,58(6):-.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[Jain Rahul]'s Articles
[Ji Zhengfeng]'s Articles
[Upadhyay Sarvagya]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[Jain Rahul]‘s Articles
[Ji Zhengfeng]‘s Articles
[Upadhyay Sarvagya]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2021  中国科学院软件研究所 - Feedback
Powered by CSpace