Quantum simulation via randomized product formulas: Low gate complexity with accuracy guarantees
Quantum simulation has wide applications in quantum chemistry and physics. Recently, scientists have begun exploring the use of randomized methods for accelerating quantum simulation. Among them, a simple and powerful technique, called qDRIFT, is known to generate random product formulas for which the average quantum channel approximates the ideal evolution. This work provides a comprehensive analysis of a single realization of the random product formula produced by qDRIFT. The main results prove that a typical realization of the randomized product formula approximates the ideal unitary evolution up to a small diamond-norm error. The gate complexity is independent of the number of terms in the Hamiltonian, but it depends on the system size and the sum of the interaction strengths in the Hamiltonian. Remarkably, the same random evolution starting from an arbitrary, but fixed, input state yields a much shorter circuit suitable for that input state. If the observable is also fixed, the same random evolution provides an even shorter product formula. The proofs depend on concentration inequalities for vector and matrix martingales. Numerical experiments verify the theoretical predictions.
The authors want to thank John Preskill and Yuan Su for valuable inputs and inspiring discussions. Earl Campbell and Nathan Wiebe provided insightful comments, as well as encouraging feedback. CC is thankful for Physics TA Relief Fellowship at Caltech. HH is supported by the Kortschak Scholars Program. RK acknowledges funding from ONR Award N00014-17-1-2146 and ARO Award W911NF121054). JAT gratefully acknowledges funding from the ONR Awards N00014-17-1-2146 and N00014-18-1-2363 and from NSF Award 1952777.
Submitted - 2008.11751.pdf