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.
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb