D. Ristè

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

Quantum data is susceptible to decoherence induced by the environment and to errors in the hardware processing it. A future fault-tolerant quantum computer will use quantum error correction (QEC) to actively protect against both. In the smallest QEC codes, the information in one logical qubit is encoded in a two-dimensional subspace of a larger Hilbert space of multiple physical qubits. For each code, a set of non-demolition multi-qubit measurements, termed stabilizers, can discretize and signal physical qubit errors without collapsing the encoded information. Experimental demonstrations of QEC to date, using nuclear magnetic resonance, trapped ions, photons, superconducting qubits, and NV centers in diamond, have circumvented stabilizers at the cost of decoding at the end of a QEC cycle. This decoding leaves the quantum information vulnerable to physical qubit errors until re-encoding, violating a basic requirement for fault tolerance. Using a five-qubit superconducting processor, we realize the two parity measurements comprising the stabilizers of the three-qubit repetition code protecting one logical qubit from physical bit-flip errors. We construct these stabilizers as parallelized indirect measurements using ancillary qubits, and evidence their non-demolition character by generating three-qubit entanglement from superposition states. We demonstrate stabilizer-based quantum error detection (QED) by subjecting a logical qubit to coherent and incoherent bit-flip errors on its constituent physical qubits. While increased physical qubit coherence times and shorter QED blocks are required to actively safeguard quantum information, this demonstration is a critical step toward larger codes based on multiple parity measurements.