  Noise is often regarded as anathema to quantum computation, but in some
settings it can be an unlikely ally. We consider the problem of learning the
class of $n$-bit parity functions by making queries to a quantum example
oracle. In the absence of noise, quantum and classical parity learning are easy
and almost equally powerful, both information-theoretically and
computationally. We show that in the presence of noise this story changes
dramatically. Indeed, the classical learning problem is believed to be
intractable, while the quantum version remains efficient. Depolarizing the
qubits at the oracle's output at any constant nonzero rate does not increase
the computational (or query) complexity of quantum learning more than
logarithmically. However, the problem of learning from corresponding classical
examples is the Learning Parity with Noise (LPN) problem, for which the best
known algorithms have superpolynomial complexity. This creates the possibility
of observing a quantum advantage with a few hundred noisy qubits. The presence
of noise is essential for creating this quantum-classical separation.
