Entanglement accelerates quantum simulation

Abstract

Quantum entanglement is an essential feature of many-body systems that impacts both quantum information processing and fundamental physics. Classical simulation methods can efficiently simulate many-body states with low entanglement, but struggle as the degree of entanglement grows. Here we investigate the relationship between quantum entanglement and quantum simulation, and show that product formula approximations for simulating many-body systems can perform better for entangled systems. We establish an upper bound for algorithmic error in terms of entanglement entropy that is tighter than previous results, and develop an adaptive simulation algorithm that incorporates measurement gadgets to estimate the algorithmic error. This shows that entanglement is not only an obstacle to classical simulation, but also a feature that can accelerate quantum algorithms.