Trotter error and gate complexity of the SYK and sparse SYK models

The Sachdev–Ye–Kitaev (SYK) model is a prominent model of strongly interacting fermions that serves as a toy model of quantum gravity and black hole physics. In this work, we study the Trotter error and gate complexity of the quantum simulation of the SYK model using Lie–Trotter–Suzuki formulas. Building on recent results by Chen and Brandão \cite{Anthony} — in particular their uniform smoothing technique for random matrix polynomials — we derive bounds on the first- and higher-order Trotter error of the SYK model, and subsequently find near-optimal gate complexities for simulating these models using Lie–Trotter–Suzuki formulas. For the k -local SYK model on n Majorana fermions, at time t , our gate complexity estimates for the first-order Lie–Trotter–Suzuki formula scales with O ~ ( n k + 5 2 t 2 ) for even k and O ~ ( n k + 3 t 2 ) for odd k , and the gate complexity of simulations using higher-order formulas scales with O ~ ( n k + 1 2 t ) for even k and O ~ ( n k + 1 t ) for odd k . Given that the SYK model has Θ ( n k ) terms, these estimates are close to optimal. These gate complexities can be further improved upon in the context of simulating the time evolution of an arbitrary fixed input state | ψ ⟩ , leading to a O ( n 2 ) -reduction in gate complexity for first-order formulas and O ( n ) -reduction for higher-order formulas.We also apply our techniques to the sparse SYK model, which is a simplified variant of the SYK model obtained by deleting all but a Θ ( n ) fraction of the terms in a uniformly i.i.d. manner. We find the average (over the random term removal) gate complexity for simulating this model using higher-order formulas scales with