Randomizing multi-product formulas for improved Hamiltonian simulation

Digital quantum simulation suggests a path forward for the efficient simulation of problems in condensed-matter physics, quantum chemistry and materials science. While the majority of quantum simulation algorithms are deterministic, a recent surge of ideas has shown that randomization can greatly benefit algorithmic performance. In this work, we introduce a scheme for quantum simulation that unites the advantages of randomized compiling and higher-order linear-combination-of-unitaries (LCU) algorithms. In doing so, we propose a framework of randomized sampling that could prove useful for quantum simulation on near-term devices and present two new LCU algorithms tailored to this framework. Our framework greatly reduces the circuit depth by circumventing the need for oblivious amplitude amplification required by standard LCU methods, rendering it especially useful for medium-term quantum computing. Our algorithms achieve a simulation error that shrinks exponentially with the circuit depth. To corroborate their functioning, we prove rigorous performance bounds and discuss examples at hand of non-interacting models.