Nathan Ju

Abstract Recent work by Bravyi et al. constructs a relation problem that a noisy constant-depth quantum circuit (QNC^0) can solve with near certainty (probability 1 - o(1)), but that any bounded fan-in constant-depth classical circuit (NC^0) fails with some constant probability. We show that this robustness to noise can be achieved in the other low-depth quantum/classical circuit separations in this area. In particular, we show a general strategy for adding noise tolerance to the interactive protocols of Grier and Schaeffer. As a consequence, we obtain an unconditional separation between noisy QNC^0 circuits and AC^0[p] circuits for all primes p \geq 2, and a conditional separation between noisy QNC^0 circuits and log-space classical machines under a plausible complexity-theoretic conjecture. A key component of this reduction is showing average-case hardness for the classical simulation tasks---that is, showing that a classical simulation of the quantum interactive task is still powerful even if it is allowed to err on some constant fraction of inputs. We show that is possible even for quantum tasks which are parity-L-hard to simulate. To do this, we borrow techniques from randomized encodings used in cryptography.