Toward the first quantum simulation with quantum speedup
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
Significance Near-term quantum computers will have limited numbers of qubits and will only be able to reliably perform limited numbers of gates. Therefore, it is crucial to identify applications of quantum processors that use the fewest possible resources. We argue that simulating the time evolution of spin systems is a classically hard problem of practical interest that is among the easiest to address with early quantum devices. We develop optimized implementations and perform detailed resource analyses for several leading quantum algorithms for this problem. By evaluating the best approaches to small-scale quantum simulation, we provide a detailed blueprint for what could be an early practical application of quantum computers. With quantum computers of significant size now on the horizon, we should understand how to best exploit their initially limited abilities. To this end, we aim to identify a practical problem that is beyond the reach of current classical computers, but that requires the fewest resources for a quantum computer. We consider quantum simulation of spin systems, which could be applied to understand condensed matter phenomena. We synthesize explicit circuits for three leading quantum simulation algorithms, using diverse techniques to tighten error bounds and optimize circuit implementations. Quantum signal processing appears to be preferred among algorithms with rigorous performance guarantees, whereas higher-order product formulas prevail if empirical error estimates suffice. Our circuits are orders of magnitude smaller than those for the simplest classically infeasible instances of factoring and quantum chemistry, bringing practical quantum computation closer to reality.