Recent work has constructed a relation problem that a noisy constant-depth quantum circuit (QNC0) can solve with near certainty (probability 1−o(1)), but that any bounded fan-in constant-depth classical circuit (NC0) fails with some constant probability. It has been showed that it was possible to encode the qubits of the quantum circuit in such a way that it preserved the separation while affected by noise. Interestingly, this was accomplished not by explicitly carrying out the quantum error correction procedure, but by simply measuring the syndrome qubits of the code and requiring the classical circuit to do the same. In fact, their procedure provided a more-or-less general recipe for taking a constant-depth quantum/classical circuit separation and turning it into a separation in which the quantum circuit was also allowed noise.
This raises an obvious question: how many circuit separations can we upgrade in this way? NC0 circuits are fairly weak—they cannot even compute the logical AND of all input bits—and so it would be interesting to show that even larger classes of classical devices cannot solve a problem that a noisy shallow quantum circuit can.
A team of researchers at Institute for Quantum Computing, University of Waterloo, Canada has showed that this robustness to noise can be achieved in the other low-depth quantum/classical circuit separations in this area.
In particular, they proposed a general strategy for adding noise tolerance to the interactive protocols of Grier and Schaeffer. As a consequence, they obtained an unconditional separation between noisy QNC0 circuits and AC0[p] circuits for all primes p ≥ 2, and a conditional separation between noisy QNC0 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 with constant probability over a uniformly random input. The team shows that is true even for quantum tasks which are ⊕L-hard to simulate.
To do this, they borrowed techniques from randomized encodings used in cryptography.
The paper can be read there.