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

Yiyuan Chen; Jonas Helsen; Maris Ozols

doi:10.22331/q-2026-02-09-1999

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

Yiyuan Chen¹, Jonas Helsen^2,3, and Maris Ozols^4,1,2

¹Korteweg-de Vries Institute for Mathematics, University of Amsterdam, The Netherlands
²QuSoft, Amsterdam, The Netherlands
³CWI, Amsterdam, The Netherlands
⁴Institute for Logic, Language, and Computation, University of Amsterdam, The Netherlands

Published:	2026-02-09, volume 10, page 1999
Editor:	Álvaro Alhambra
Eprint:	arXiv:2502.18420v2
Doi:	https://doi.org/10.22331/q-2026-02-09-1999
Citation:	Quantum 10, 1999 (2026).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

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 [6] — in particular their uniform smoothing technique for random matrix polynomials — 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 using Lie–Trotter–Suzuki formulas. 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\rangle$, leading to a $\mathcal{O}(n^2)$-reduction in gate complexity for first-order formulas and $\mathcal{O}(\sqrt{n})$-reduction for higher-order formulas.

We also apply our techniques to 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. We find the average (over the random term removal) gate complexity for simulating this model using higher-order formulas scales with $\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\rangle$.

Our results highlight the potential of Lie–Trotter–Suzuki formulas for efficiently simulating the SYK and sparse SYK models, and our analytical methods can be naturally extended to other Gaussian random Hamiltonians.

► BibTeX data

@article{Chen2026trottererrorgate,
  doi = {10.22331/q-2026-02-09-1999},
  url = {https://doi.org/10.22331/q-2026-02-09-1999},
  title = {Trotter error and gate complexity of the {SYK} and sparse {SYK} models},
  author = {Chen, Yiyuan and Helsen, Jonas and Ozols, Maris},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {10},
  pages = {1999},
  month = feb,
  year = {2026}
}

► References

[1] Alexei Kitaev, A simple model of quantum holography (part 1), online.kitp.ucsb.edu/online/entangled15/kitaev/.
https://online.kitp.ucsb.edu/online/entangled15/kitaev/

[2] Alexei Kitaev, A simple model of quantum holography (part 2), online.kitp.ucsb.edu/online/entangled15/kitaev2/.
https://online.kitp.ucsb.edu/online/entangled15/kitaev2/

[3] Daniel Jafferis, Alexander Zlokapa, Joseph D. Lykken, David K. Kolchmeyer, Samantha I. Davis, Nikolai Lauk, Hartmut Neven, and Maria Spiropulu, Traversable wormhole dynamics on a quantum processor, Nature, 612(7938) 51-55 (2022), 10.1038/s41586-022-05424-3.
https://doi.org/10.1038/s41586-022-05424-3

[4] Swapnamay Mondal, A simple model for Hawking radiation, Journal of High Energy Physics, 2020(3) (2020), 10.1007/jhep03(2020)119.
https://doi.org/10.1007/jhep03(2020)119

[5] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu, Theory of Trotter Error with Commutator Scaling, Phys. Rev. X, 11(1) 011020 (2021), 10.1103/PhysRevX.11.011020.
https://doi.org/10.1103/PhysRevX.11.011020

[6] Chi-Fang Chen and Fernando Brandão, Average-Case Speedup for Product Formulas, Communications in Mathematical Physics, 405 (2024), 10.1007/s00220-023-04912-5.
https://doi.org/10.1007/s00220-023-04912-5

[7] De Huang, Jonathan Niles-Weed, Joel A. Tropp, and Rachel Ward, Matrix Concentration for Products, Found. Comput. Math., 22(6) 1767–1799 (2022), 10.1007/s10208-021-09533-9.
https://doi.org/10.1007/s10208-021-09533-9

[8] Zhang Jiang, Amir Kalev, Wojciech Mruczkiewicz, and Hartmut Neven, Optimal fermion-to-qubit mapping via ternary trees with applications to reduced quantum states learning, Quantum, 4 276 (2020), 10.22331/q-2020-06-04-276.
https://doi.org/10.22331/q-2020-06-04-276

[9] L. García-Álvarez, I. L. Egusquiza, L. Lamata, A. del Campo, J. Sonner, and E. Solano, Digital Quantum Simulation of Minimal $\text{AdS/CFT}$, Physical Review Letters, 119(4) (2017), 10.1103/PhysRevLett.119.040501.
https://doi.org/10.1103/PhysRevLett.119.040501

[10] Ignacio García-Mata, Rodolfo Jalabert, and Diego Wisniacki, Out-of-time-order correlations and quantum chaos, Scholarpedia, 18(4) 55237 (2023), 10.4249/scholarpedia.55237.
https://doi.org/10.4249/scholarpedia.55237

[11] Koji Hashimoto, Keiju Murata, and Ryosuke Yoshii, Out-of-time-order correlators in quantum mechanics, Journal of High Energy Physics, 2017(10) (2017), 10.1007/jhep10(2017)138.
https://doi.org/10.1007/jhep10(2017)138

[12] Masuo Suzuki, General theory of fractal path integrals with applications to many-body theories and statistical physics, Journal of Mathematical Physics, 32(2) 400-407 (1991), 10.1063/1.529425.
https://doi.org/10.1063/1.529425

[13] Vladimir Rosenhaus, An introduction to the $\text{SYK}$ model, Journal of Physics A: Mathematical and Theoretical, 52(32) 323001 (2019), 10.1088/1751-8121/ab2ce1.
https://doi.org/10.1088/1751-8121/ab2ce1

[14] Nicole Tomczak-Jaegermann, The moduli of smoothness and convexity and the Rademacher averages of the trace classes $\text{S}_{p}$ $(1\leq p<\infty)$, Studia Mathematica, 50(2) 163-182 (1974), eudml.org/doc/217886.
http://eudml.org/doc/217886

[15] Keith Ball, Eric A. Carlen, and Elliott H. Lieb, Sharp uniform convexity and smoothness inequalities for trace norms, Inventiones mathematicae, 115 463-482 (1994), 10.1007/BF01231769.
https://doi.org/10.1007/BF01231769

[16] Muhammad Asaduzzaman, Raghav G. Jha, and Bharath Sambasivam, Sachdev-Ye-Kitaev model on a noisy quantum computer, Phys. Rev. D, 109(10) 105002 (2024), 10.1103/PhysRevD.109.105002.
https://doi.org/10.1103/PhysRevD.109.105002

[17] Michael A. Nielsen and Isaac L. Chuang, Quantum Computation and Quantum Information: 10th Anniversary Edition, Cambridge University Press, (2010), 10.1017/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667

[18] Patrick Orman, Hrant Gharibyan, and John Preskill, Quantum chaos in the sparse SYK model, (2024), arXiv:2403.13884.
arXiv:2403.13884

[19] Shenglong Xu, Leonard Susskind, Yuan Su, and Brian Swingle, A Sparse Model of Quantum Holography, (2020), arXiv:2008.02303.
arXiv:2008.02303

[20] Juan Maldacena and Douglas Stanford, Remarks on the Sachdev-Ye-Kitaev model, Physical Review D, 94(10) (2016), 10.1103/PhysRevD.94.106002.
https://doi.org/10.1103/PhysRevD.94.106002

[21] Shao-Kai Jian and Hong Yao, Solvable Sachdev-Ye-Kitaev Models in Higher Dimensions: From Diffusion to Many-Body Localization, Physical Review Letters, 119(20) (2017), 10.1103/PhysRevLett.119.206602.
https://doi.org/10.1103/PhysRevLett.119.206602

[22] Seth Lloyd, Universal Quantum Simulators, Science, 273(5278) 1073-1078 (1996), 10.1126/science.273.5278.1073.
https://doi.org/10.1126/science.273.5278.1073

[23] Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders, Efficient quantum algorithms for simulating sparse Hamiltonians, Communications in Mathematical Physics, 270(2) 359–371 (2006), 10.1007/s00220-006-0150-x.
https://doi.org/10.1007/s00220-006-0150-x

[24] Rolando D. Somma, A Trotter-Suzuki approximation for Lie groups with applications to Hamiltonian simulation, Journal of Mathematical Physics, 57(6) (2016), 10.1063/1.4952761.
https://doi.org/10.1063/1.4952761

[25] Andrew M. Childs and Yuan Su, Nearly Optimal Lattice Simulation by Product Formulas, Phys. Rev. Lett., 123(5) 050503 (2019), 10.1103/PhysRevLett.123.050503.
https://doi.org/10.1103/PhysRevLett.123.050503

[26] Ryan Babbush, Dominic W. Berry, and Hartmut Neven, Quantum simulation of the Sachdev-Ye-Kitaev model by asymmetric qubitization, Phys. Rev. A, 99(4) 040301 (2019), 10.1103/PhysRevA.99.040301.
https://doi.org/10.1103/PhysRevA.99.040301

[27] Edison M. Murairi, Michael J. Cervia, Hersh Kumar, Paulo F. Bedaque, and Andrei Alexandru, How many quantum gates do gauge theories require?, Phys. Rev. D, 106(9) 094504 (2022), 10.1103/PhysRevD.106.094504.
https://doi.org/10.1103/PhysRevD.106.094504

[28] Ewout van den Berg and Kristan Temme, Circuit optimization of Hamiltonian simulation by simultaneous diagonalization of Pauli clusters, Quantum, 4 322 (2020), 10.22331/q-2020-09-12-322.
https://doi.org/10.22331/q-2020-09-12-322

[29] Daniel Miller, Laurin E. Fischer, Kyano Levi, Eric J. Kuehnke, Igor O. Sokolov, Panagiotis Kl. Barkoutsos, Jens Eisert, and Ivano Tavernelli, Hardware-tailored diagonalization circuits, npj Quantum Information, 10(1) (2024), 10.1038/s41534-024-00901-1.
https://doi.org/10.1038/s41534-024-00901-1

[30] Michael A. Nielsen, The Fermionic canonical commutation relations and the Jordan–Wigner transform, (2005), futureofmatter.com/assets/fermions_and_jordan_wigner.pdf.
https://futureofmatter.com/assets/fermions_and_jordan_wigner.pdf

[31] Eric R. Anschuetz, David Gamarnik, and Bobak T. Kiani, Bounds on the Ground State Energy of Quantum $p$-Spin Hamiltonians, Communications in Mathematical Physics, 406(10) (2025), 10.1007/s00220-025-05412-4.
https://doi.org/10.1007/s00220-025-05412-4

[32] Antonio M. García-Garcá, Yiyang Jia, and Jacobus J. M. Verbaarschot, Exact moments of the Sachdev-Ye-Kitaev model up to order $1/{N}^2$, Journal of High Energy Physics, 2018(4) (2018), 10.1007/jhep04(2018)146.
https://doi.org/10.1007/jhep04(2018)146

[33] Nicholas Crawford, Thermodynamics and Universality for Mean Field Quantum Spin Glasses, Communications in Mathematical Physics, 274(3) 821–839 (2007), 10.1007/s00220-007-0263-x.
https://doi.org/10.1007/s00220-007-0263-x

[34] Yiyuan Chen, GitHub repository for the source codes of the numerics, github.com/cyy020726/Trotter-error-and-gate-complexity-of-the-SYK-and-sparse-SYK-models.
https://github.com/cyy020726/Trotter-error-and-gate-complexity-of-the-SYK-and-sparse-SYK-models

Cited by

[1] Etienne Granet, Yuta Kikuchi, Henrik Dreyer, and Enrico Rinaldi, "Simulating sparse SYK model with a randomized algorithm on a trapped-ion quantum computer", npj Quantum Information 12 1, 43 (2026).

[2] Talal Ahmed Chowdhury, Kwangmin Yu, and Raza Sabbir Sufian, "Probing entanglement dynamics in the SYK model using quantum computers", Results in Physics 79, 108526 (2025).

[3] Sabhyata Gupta, Bharath Sambasivam, Sophia E. Economou, Edwin Barnes, Alexander F. Kemper, and Raghav G. Jha, "Ground state preparation of random all-to-all Hamiltonians using ADAPT-VQE", arXiv:2606.18339, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-12 00:18:52) and SAO/NASA ADS (last updated successfully 2026-08-12 00:18:53). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.