  This paper introduces quantum analogues of non-interactive perfect and
statistical zero-knowledge proof systems. Similar to the classical cases, it is
shown that sharing randomness or entanglement is necessary for non-trivial
protocols of non-interactive quantum perfect and statistical zero-knowledge. It
is also shown that, with sharing EPR pairs a priori, the class of languages
having one-sided bounded error non-interactive quantum perfect zero-knowledge
proof systems has a natural complete problem. Non-triviality of such a proof
system is based on the fact proved in this paper that the Graph
Non-Automorphism problem, which is not known in BQP, can be reduced to our
complete problem. Our results may be the first non-trivial quantum
zero-knowledge proofs secure even against dishonest quantum verifiers, since
our protocols are non-interactive, and thus the zero-knowledge property does
not depend on whether the verifier in the protocol is honest or not. A
restricted version of our complete problem derives a natural complete problem
for BQP.
