On the efficiency of quantum algorithms for Hamiltonian simulation

We study algorithms simulating a system evolving with Hamiltonian H = Sigma(m)(j=1) H-j, where each of the H-j, j = 1, . . . , m, can be simulated efficiently. We are interested in the cost for approximating e(-iHt), t is an element of R, with error epsilon. We consider algorithms based on high order splitting formulas that play an important role in quantum Hamiltonian simulation. These formulas approximate e(-iHt) by a product of exponentials involving the H-j, j = 1, . . . , m. We obtain an upper bound for the number of required exponentials. Moreover, we derive the order of the optimal splitting method that minimizes our upper bound. We show significant speedups relative to previously known results.