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

Benjamin Morrison, Adam Groce

We study the relationship between problems solvable by quantum algorithms in polynomial time and those for which zero-knowledge proofs exist. In prior work, Aaronson [arxiv:quant-p…