Oracle Separations for Quantum Statistical Zero-Knowledge

01/26/2018
by   Sanketh Menda, et al.
0

This paper investigates the power of quantum statistical zero knowledge interactive proof systems in the relativized setting. We prove the existence of an oracle relative to which quantum statistical zero-knowledge does not contain UP intersect coUP, and we prove that quantum statistical zero knowledge does not contain UP relative to a random oracle with probability 1. Our proofs of these statements rely on a bound on output state discrimination for relativized quantum circuits based on the quantum adversary method of Ambainis, following a technique similar to one used by Ben-David and Kothari to prove limitations on a query complexity variant of quantum statistical zero-knowledge.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset