View article

We show that one can quantum simulate the dynamics of a Sachdev-Ye-Kitaev model with N Majorana modes for time t to precision ε with gate complexity O (N 7/2 t+ N 5/2 t polylog (N/ε)). In addition to scaling sublinearly in the number of Hamiltonian terms, this gate complexity represents an exponential improvement in 1/ε and large polynomial improvement in N and t over prior state-of-the-art algorithms which scale as O (N 10 t 2/ε). Our approach involves a variant of the qubitization technique in which we encode the Hamiltonian H as an asymmetric projection of a signal oracle U onto two different signal states prepared by state oracles, A| 0〉↦| A〉 and B| 0〉↦| B〉, such that H=〈 B| U| A〉. Our strategy for applying this method to the Sachdev-Ye-Kitaev model involves realizing B using only Hadamard gates and realizing A as a random quantum circuit.