Interactive quantum advantage with noisy, shallow Clifford circuits

Understand

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.