Oracle Separations Between Quantum and Non-interactive Zero-Knowledge\n Classes

Abstract

We study the relationship between problems solvable by quantum algorithms in\npolynomial time and those for which zero-knowledge proofs exist. In prior work,\nAaronson [arxiv:quant-ph/0111102] showed an oracle separation between BQP and\nSZK, i.e. an oracle $A$ such that $\\mathrm{SZK}^A \\not\\subseteq\n\\mathrm{BQP}^A$. In this paper we give a simple extension of Aaronson's result\nto non-interactive zero-knowledge proofs with perfect security. This class,\nNIPZK, is the most restrictive zero-knowledge class. We show that even for this\nclass we can construct an $A$ with $\\mathrm{NIPZK}^A \\not\\subseteq\n\\mathrm{BQP}^A$.\n