Quantum Echoes: Towards Verifiable Quantum Advantage

In the 5-stage model of quantum application development, discovering algorithms that exhibit quantum advantage is the mission of stage 1. The focus is especially on advantages verifiable by classical computers, quantum computers, or lab experiments. I'll introduce the Quantum Echoes algorithm, which measures the expectation value of a quantum observable called the out-of-time-order correlator (OTOC). We estimated that the quantum algorithm outperforms classical supercomputers by 13,000x using the Willow processor. This result can be independently verified by other quantum computers in the future. The Quantum Echoes algorithm can also be used for Hamiltonian learning of parameters in physical systems with similar dynamics. We demonstrated examples using Nuclear Magnetic Resonance spectroscopy on small molecules, showing great potential in real-world applications. It paves the way towards stage 2 of quantum application development: identifying concrete problems with verifiable quantum advantage.