Doubling the order of approximation via the randomized product formula

Hamiltonian simulation is a major application of quantum computing, for example, enabling prediction of the properties of molecules. Prior work has used product formulas with randomization to improve performance, but has only yielded modest improvements over the excellent performance provided by deterministic high-order product formulas. In this work, we provide a randomized scheme that greatly increases the order of product formulas, thereby providing a large advantage over the best-performing deterministic schemes. Our scheme is based on applying randomly chosen corrections to a high-order symmetric product formula. If the original product formula is of order 2k (so the error is of order 2k+1), then the corrected formula is of order 4k+1, corresponding to a doubling of the order of the error. In practice, applying the corrections in a quantum algorithm requires some structure to the Hamiltonian, for example, the Pauli strings as are commonly used in the simulation of quantum chemistry.