Quantum Simulation of the Sachdev-Ye-Kitaev Model by Asymmetric Qubitization

Abstract

We show that one can quantum simulate the dynamics of a Sachdev-Ye-Kitaev model with $N$ Majorana modes for time $t$ to precision $\hat{I}\mu$ with gate complexity $O(N^{7/2}t+N^{5/2}t\mathrm{polylog}(N/\hat{I}\mu ))$. In addition to scaling sublinearly in the number of Hamiltonian terms, this gate complexity represents an exponential improvement in $1/\hat{I}\mu$ and large polynomial improvement in $N$ and $t$ over prior state-of-the-art algorithms which scale as $O(N^{10}{t}^2/\hat{I}\mu )$. 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⟩\mapsto |A⟩$ and $B|0⟩\mapsto |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.

8 pages, 1 figure. This version adds a more complete analysis in appendix