Trotter error and gate complexity of the SYK and sparse SYK models

Abstract

The Sachdev--Ye--Kitaev (SYK) model is a prominent model of strongly interacting fermions that serves as a toy model of quantum gravity and black hole physics. In this work, we study the Trotter error and gate complexity of the quantum simulation of the SYK model using Lie--Trotter--Suzuki formulas. Building on recent results by Chen and Brandão (arXiv:2111.05324), we derive bounds on the first- and higher-order Trotter error of the SYK model, and subsequently find near-optimal gate complexities for simulating these models. For the $k$-local SYK model on $n$ Majorana fermions, at time $t$, our gate complexity estimates for the first-order Lie--Trotter--Suzuki formula scales with $\tilde{\mathcal{O}}(n^{k+\frac{5}{2}}{t}^2)$ for even $k$ and $\tilde{\mathcal{O}}(n^{k+3}{t}^2)$ for odd $k$, and the gate complexity of simulations using higher-order formulas scales with $\tilde{\mathcal{O}}(n^{k+\frac{1}{2}}t)$ for even $k$ and $\tilde{\mathcal{O}}(n^{k+1}t)$ for odd $k$. Given that the SYK model has $\Theta (n^k)$ terms, these estimates are close to optimal. These gate complexities can be further improved upon in the context of simulating the time evolution of an arbitrary fixed input state $|\psi ⟩$, leading to a $\mathcal{O}(n^2)$-reduction in gate complexity for first-order and $\mathcal{O}(\sqrt{n})$-reduction for higher-order formulas. Regarding the sparse SYK model, which is a simplified variant of the SYK model obtained by deleting all but a $\Theta (n)$ fraction of the terms in a uniformly i.i.d. manner, our average gate complexity estimates for higher-order formulas scale as $\tilde{\mathcal{O}}(n^{1+\frac{1}{2}}t)$ for even $k$ and $\tilde{\mathcal{O}}(n^{2}t)$ for odd $k$. Similar to the full SYK model, we obtain a $\mathcal{O}(\sqrt{n})$-reduction simulating the time evolution of an arbitrary fixed input state $|\psi ⟩$.

67 pages

References in corpus (20)

• Comments on the Sachdev-Ye-Kitaev model
• Efficient quantum algorithms for simulating sparse Hamiltonians
• A Theory of Trotter Error
• Out-of-time-order correlators in quantum mechanics
• Nearly optimal lattice simulation by product formulas
• An introduction to the SYK model
• Digital Quantum Simulation of Minimal AdS/CFT
• Solvable Sachdev-Ye-Kitaev models in higher dimensions: from diffusion to many-body localization
• Quantum Simulation of the Sachdev-Ye-Kitaev Model by Asymmetric Qubitization
• Optimal fermion-to-qubit mapping via ternary trees with applications to reduced quantum states learning
• Circuit optimization of Hamiltonian simulation by simultaneous diagonalization of Pauli clusters
• Exact moments of the Sachdev-Ye-Kitaev model up to order $1/N^2$
• How many quantum gates do gauge theories require?
• A Trotter-Suzuki approximation for Lie groups with applications to Hamiltonian simulation
• Thermodynamics and Universality for Mean Field Quantum Spin Glasses
• Sachdev-Ye-Kitaev model on a noisy quantum computer
• Average-case Speedup for Product Formulas
• Hardware-Tailored Diagonalization Circuits
• Bounds on the ground state energy of quantum $p$-spin Hamiltonians
• A simple model for Hawking radiation

Cited by in corpus (1)

• Simulating sparse SYK model with a randomized algorithm on a trapped-ion quantum computer