Toward the first quantum simulation with quantum speedup

Abstract

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.

Keywords: quantum circuits; quantum computing; quantum simulation.

Fig. 1.

Gate counts for optimized implementations of the PF algorithm (using the fourth-order formula with commutator bound and the better of the fourth- or sixth-order formulas with empirical error bound), the TS algorithm, and the QSP algorithm (using the segmented version with analytic error bound and the nonsegmented version with empirical Jacobi–Anger error bound) for system sizes between 10 and 100. (Left) cnot gates for Clifford+$R_z$ circuits. (Right) $T$ gates for Clifford+$T$ circuits.

Fig. 2.

Numbers of qubits used by the PF, TS, and QSP algorithms. See SI Appendix, Eqs. 184 and 195 for the precise qubit counts of the TS and QSP algorithms, respectively. Jumps in the qubit count of the TS algorithm correspond to increases in the size of each of $K$ registers used to index one of $L$ terms in the Hamiltonian, as detailed in SI Appendix, section G.

Fig. 3.

Total gate counts in the Clifford+$R_z$ basis for product formula algorithms using the (Left) minimized, (Center) commutator, and (Right) empirical bounds, for system sizes between 13 and 500.

Fig. 4.

Comparison of resource requirements for factoring a 1,024-bit number (35) (purple), simulation of FeMoco (30) (orange), and 50-spin simulations described in this paper (segmented QSP in green; sixth-order PF with empirical error bound in red).