loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02)
Limits on the Power of Quantum Statistical Zero-Knowledge
Vancouver, BC, Canada
November 16-November 19
ISBN: 0-7695-1822-2
ASCII Text
x 
 
John Watrous, "Limits on the Power of Quantum Statistical Zero-Knowledge," Foundations of Computer Science, IEEE Annual Symposium on, pp. 459, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002.
 
 
BibTex
x
 
@article{ 10.1109/SFCS.2002.1181970,
author = {John Watrous},
title = {Limits on the Power of Quantum Statistical Zero-Knowledge},
journal ={Foundations of Computer Science, IEEE Annual Symposium on},
volume = {0},
year = {2002},
issn = {0272-5428},
pages = {459},
doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2002.1181970},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, IEEE Annual Symposium on
TI - Limits on the Power of Quantum Statistical Zero-Knowledge
SN - 0272-5428
SP
EP
A1 - John Watrous,
PY - 2002
KW - null
VL - 0
JA - Foundations of Computer Science, IEEE Annual Symposium on
ER -
 
John Watrous, University of Calgary

In this paper we propose a definition for (honest verifier) quantum statistical zero-knowledge interactive proof systems and study the resulting complexity class, which we denote QSZKHV. We prove several facts regarding this class, including:

  • The following problem is a complete promise problem for QSZKHV: given instructions for preparing two mixed quantum states, are the states close together or far apart in the trace norm metric? This problem is a quantum generalization of the complete promise problem of Sahai and Vadhan [25] for (classical) statistical zero-knowledge.
  • QSZKHV is closed under complement.
  • QSZKHV \subseteq PSPACE. (At present it is not known if arbitrary quantum interactive proof systems can be simulated in PSPACE, even for one-round proof systems.)
  • Any polynomial-round honest verifier quantum statistical zero-knowledge proof system can be simulated by a two-message (i.e., one-round) honest verifier quantum statistical zero-knowledge proof system. Similarly, any polynomial-round honest verifier quantum statistical zero-knowledge proof system can be simulated by a three-message public-coin honest verifier quantum statistical zero-knowledge proof system.

    • These facts establish close connections between classical statistical zero-knowledge and our definition for quantum statistical zero-knowledge, and give some insight regarding the effect of this zero-knowledge restriction on quantum interactive proof systems. The relationship between our definition and possible definitions of general (i.e., not necessarily honest) quantum statistical zero-knowledge are also discussed.

    Citation:
    John Watrous, "Limits on the Power of Quantum Statistical Zero-Knowledge," focs, pp.459, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002
    Usage of this product signifies your acceptance of the Terms of Use.