A verifiable quantum advantage

Nature is brimming with chaos, a phenomenon characterized by the high sensitivity of a system toward small perturbations. In the macroscopic world, notable examples of chaotic systems include weather patterns, wherein a small change in initial conditions leads to vastly different outcomes over time (often dubbed “the butterfly effect”), and population dynamics, where small shifts in local populations may eventually affect the entire ecosystem. Chaos is similarly abundant in quantum systems, with examples including the dynamics of magnetization of atomic nuclei when subjected to a time-varying magnetic field, and the flow of electrons in high-temperature superconductors.

Simulating quantum-chaotic systems is challenging for classical computation due to exponentially scaling computational cost, making quantum computers ideal for achieving quantum advantage. In 2019, we demonstrated the first beyond-classical quantum computation by sampling bitstrings from a highly chaotic quantum state of qubits. However, this random circuit sampling approach has limited practical utility since the same bitstring never appears twice in a large quantum system, restricting its ability to reveal useful information.

Out-of-time-order correlator

The interference nature of the OTOC leads to two consequences crucial for attaining quantum advantage. First, the forward and backward evolutions partially reverse the effects of chaos and amplify the quantum signal measured at the end. We observed the signature of this amplification in OTOC signals. More specifically, OTOC signal magnitude, characterized by the width of the distribution of OTOC values over the ensemble of random circuits, scales as a negative power of time, whereas quantum signals measured without back evolutions decay exponentially. The slow power law decay of OTOCs suggests that measuring these quantities on a quantum computer is significantly more efficient than classical simulations, where costs increase exponentially over time.