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.

Article web page: