Quantum simulation of the Sachdev-Ye-Kitaev model by asymmetric qubitization

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(N7/2t+N5/2t0.16em0expolylog(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¹⁰t²/ε). 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.