Benchmarking time evolution algorithms for quantum advantage*

Recent hardware advances have brought quantum simulations of quantum dynamics close to the limits of classical simulability. A recent subject of debate has been where exactly the quantum advantage regime begins for this class of quantum simulation tasks. In response to a recent quantum dynamics experiment from IBM, a series of classical approaches have been proposed that efficiently capture the simulated dynamics with accuracy comparable to or exceeding that of the quantum computer. However, the complexity of many classical algorithms increases exponentially with simulation time, which calls into question the utility of these methods beyond the times reached in the quantum simulation experiments. With the understanding that hardware coherence times are steadily improving, we report benchmarking results for a recently proposed tensor network algorithm that uses belief propagation as an approximate contraction heuristic. The focus of our tests is on determining, for a given system size, how much accuracy is maintained with increasing simulation time for this approximate tensor network algorithm. We comment on the implications of these benchmarks for future quantum computing experiments, in particular on the circuit depths that may be necessary in order to challenge the algorithm's regime of validity.