complete problem for perfect zero-knowledge quantum proof

ISCAS OpenIR

	complete problem for perfect zero-knowledge quantum proof
	Yan Jun
	2012
会议名称	38th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2012
会议录名称	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
页码	419-430
会议日期	January 21
会议地点	Spindleruv Mlyn, Czech republic
收录类别	EI
ISSN	0302-9743
ISBN	9783642276590
部门归属	(1) School of Computer Science and Technology University of Science and Technology of China Hefei Anhui 230027 China; (2) State Key Laboratory of Computer Science Institute of Software Chinese Academy of Sciences Beijing 100190 China
摘要	The main purpose of this paper is to prove that (promise) problem Quantum State Identicalness (abbreviated QSI) is essentially complete for perfect zero-knowledge quantum interactive proof (QPZK). Loosely speaking, problem QSI is to decide whether two efficiently preparable quantum states (captured by quantum circuit of polynomial size) are identical or far apart (in trace distance). It is worthy noting that our result does not have classical counterpart yet; natural complete problem for perfect zero-knowledge interactive proof (PZK) is still unknown. Our proof generalizes Watrous' completeness proof for statistical zero-knowledge quantum interactive proof (QSZK), with an extra idea inspired by Malka to deal with completeness error. With complete problem at our disposal, we can immediately prove (and reprove) several interesting facts about QPZK. © 2012 Springer-Verlag.; The main purpose of this paper is to prove that (promise) problem Quantum State Identicalness (abbreviated QSI) is essentially complete for perfect zero-knowledge quantum interactive proof (QPZK). Loosely speaking, problem QSI is to decide whether two efficiently preparable quantum states (captured by quantum circuit of polynomial size) are identical or far apart (in trace distance). It is worthy noting that our result does not have classical counterpart yet; natural complete problem for perfect zero-knowledge interactive proof (PZK) is still unknown. Our proof generalizes Watrous' completeness proof for statistical zero-knowledge quantum interactive proof (QSZK), with an extra idea inspired by Malka to deal with completeness error. With complete problem at our disposal, we can immediately prove (and reprove) several interesting facts about QPZK. © 2012 Springer-Verlag.
关键词	Computer Science Quantum Cryptography Quantum Optics
语种	英语
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/15682
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	Yan Jun. complete problem for perfect zero-knowledge quantum proof[C],2012:419-430.