Fast convergence of Majorana Propagation for weakly interacting fermions

Simulating the time dynamics of an observable under Hamiltonian evolution is one of the most promising candidates for quantum advantage as we do not expect efficient classical algorithms for this problem except in restricted settings. Here, we introduce such a setting by showing that Majorana Propagation, a simple algorithm combining Trotter steps and truncations, efficiently finds a low-degree approximation of the time-evolved observable as soon as such an approximation exists. This provides the first provable guarantee about Majorana Propagation for Hamiltonian evolution. As an application of this result, we prove that Majorana Propagation can efficiently simulate the time dynamics of any sparse quartic Hamiltonian up to time t_max(u) depending on the interaction strength u. For a time horizon t leq t_max(u), the runtime of the algorithm is N^{O\(log(t/varepsilon\))} where N is the number of Majorana modes and varepsilon is the error measured in the normalized Frobenius norm. Importantly, in the limit of small u, t_max(u) goes to +infty, formalizing the intuition that the algorithm is accurate at all times when the Hamiltonian is quadratic.