  The main promise of quantum computing is to efficiently solve certain
problems that are prohibitively expensive for a classical computer. Most
problems with a proven quantum advantage involve the repeated use of a black
box, or oracle, whose structure encodes the solution. One measure of the
algorithmic performance is the query complexity, i.e., the scaling of the
number of oracle calls needed to find the solution with a given probability.
Few-qubit demonstrations of quantum algorithms, such as Deutsch-Jozsa and
Grover, have been implemented across diverse physical systems such as nuclear
magnetic resonance, trapped ions, optical systems, and superconducting
circuits. However, at the small scale, these problems can already be solved
classically with a few oracle queries, and the attainable quantum advantage is
modest. Here we solve an oracle-based problem, known as learning parity with
noise, using a five-qubit superconducting processor. Running classical and
quantum algorithms on the same oracle, we observe a large gap in query count in
favor of quantum processing. We find that this gap grows by orders of magnitude
as a function of the error rates and the problem size. This result demonstrates
that, while complex fault-tolerant architectures will be required for universal
quantum computing, a quantum advantage already emerges in existing noisy
systems
