# Quantum Simulation of the Sachdev-Ye-Kitaev Model by Asymmetric Qubitization. (arXiv:1806.02793v2 [quant-ph] UPDATED)

We show that one can quantum simulate the dynamics of a Sachdev-Ye-Kitaev

model with $N$ Majorana modes for time $t$ to precision $\epsilon$ with gate

complexity $O(N^{7/2} t + N^{5/2} t \,{\rm polylog}(N/ \epsilon))$. In addition

to scaling sublinearly in the number of Hamiltonian terms, this gate complexity

represents an exponential improvement in $1/\epsilon$ and large polynomial

improvement in $N$ and $t$ over prior state-of-the-art algorithms which scale

as $O(N^{10} t^2 / \epsilon)$. 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\left\vert{0}\right\rangle \mapsto \left\vert{A}\right\rangle$

and $B \left\vert{0}\right\rangle \mapsto \left\vert{B}\right\rangle$, such

that $H = \left\langle{B}\right\vert U\left\vert{A}\right\rangle$. 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.