qip = pspace

ISCAS OpenIR

	qip = pspace
	Jain Rahul; Ji Zhengfeng; Upadhyay Sarvagya; Watrous John
	2011
发表期刊	JOURNAL OF THE ACM
ISSN	0004-5411
卷号	58 期号:6 页码:-
摘要	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.
收录类别	SCI
关键词	Theory Interactive Proof Systems Quantum Computation Semidefinite Programming Matrix Multiplicative Weights Update Method
部门归属	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.
学科领域	Computer Science
资助者	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
语种	英语
内容类型	期刊论文
URI标识	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):-.