{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T09:07:31Z","timestamp":1773652051725,"version":"3.50.1"},"reference-count":50,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T00:00:00Z","timestamp":1773619200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"U.S. National Science Foundation","doi-asserted-by":"publisher","award":["PHY-2317110"],"award-info":[{"award-number":["PHY-2317110"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-SCL0000121"],"award-info":[{"award-number":["DE-SCL0000121"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"\n Finding the ground state of strongly-interacting fermionic systems is often the prerequisite for fully understanding both quantum chemistry and condensed matter systems. The Sachdev\u2013Ye\u2013Kitaev (SYK) model is a representative example of such a system; it is particularly interesting not only due to the existence of efficient quantum algorithms preparing approximations to the ground state such as Hastings\u2013O'Donnell (STOC 2022), but also known no-go results for many classical ansatzes in preparing low-energy states. However, this quantum-classical separation is known to not persist when the SYK model is sufficiently sparsified, i.e., when terms in the model are discarded with probability\n \n 1<\/mml:mn>\n &#x2212;<\/mml:mo>\n p<\/mml:mi>\n <\/mml:math>\n , where\n \n p<\/mml:mi>\n =<\/mml:mo>\n &#x0398;<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n \n n<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:math>\n and\n \n n<\/mml:mi>\n <\/mml:math>\n is the system size. This raises the question of how robust the quantum and classical complexities of the SYK model are to sparsification.In this work we initiate the study of the sparse SYK model where\n \n p<\/mml:mi>\n &#x2208;<\/mml:mo>\n [<\/mml:mo>\n &#x0398;<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n \n n<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n ,<\/mml:mo>\n 1<\/mml:mn>\n ]<\/mml:mo>\n <\/mml:math>\n and show there indeed exists a certain robustness of sparsification. We prove that with high probability, Gaussian states achieve only a\n \n &#x0398;<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n \n n<\/mml:mi>\n <\/mml:msqrt>\n )<\/mml:mo>\n <\/mml:math>\n -factor approximation to the true ground state energy of sparse SYK for all\n \n p<\/mml:mi>\n &#x2265;<\/mml:mo>\n &#x03A9;<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mi>\n &#x2061;<\/mml:mo>\n n<\/mml:mi>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:math>\n , and that Gaussian states cannot achieve constant-factor approximations unless\n \n p<\/mml:mi>\n &#x2264;<\/mml:mo>\n O<\/mml:mi>\n (<\/mml:mo>\n \n log<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n &#x2061;<\/mml:mo>\n n<\/mml:mi>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n \n n<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:math>\n . Additionally, we prove that the quantum algorithm of Hastings\u2013O'Donnell still achieves a constant-factor approximation to the ground state energy when\n \n p<\/mml:mi>\n &#x2265;<\/mml:mo>\n &#x03A9;<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mi>\n &#x2061;<\/mml:mo>\n n<\/mml:mi>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:math>\n . Combined, these show a provable separation between classical algorithms outputting Gaussian states and efficient quantum algorithms for the goal of finding approximate sparse SYK ground states whenever\n \n p<\/mml:mi>\n &#x2265;<\/mml:mo>\n &#x03A9;<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mi>\n &#x2061;<\/mml:mo>\n n<\/mml:mi>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:math>\n , extending the analogous\n \n p<\/mml:mi>\n =<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:math>\n result of Hastings\u2013O'Donnell.\n <\/jats:p>","DOI":"10.22331\/q-2026-03-16-2029","type":"journal-article","created":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T08:32:03Z","timestamp":1773649923000},"page":"2029","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":0,"title":["Optimizing Sparse SYK"],"prefix":"10.22331","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7674-0548","authenticated-orcid":false,"given":"Matthew","family":"Ding","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, CA 94305, USA"},{"name":"California Institute of Technology, Pasadena, CA 91125, USA"},{"name":"University of California, Berkeley, CA 94720, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8152-6340","authenticated-orcid":false,"given":"Robbie","family":"King","sequence":"additional","affiliation":[{"name":"Google Quantum AI, Venice, CA 90291, USA"},{"name":"University of California, Berkeley, CA 94720, USA"},{"name":"California Institute of Technology, Pasadena, CA 91125, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1477-0308","authenticated-orcid":false,"given":"Bobak T.","family":"Kiani","sequence":"additional","affiliation":[{"name":"Bowdoin College, Brunswick, ME 04011, USA"},{"name":"Harvard University, Cambridge, MA 02138, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9825-3692","authenticated-orcid":false,"given":"Eric R.","family":"Anschuetz","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena, CA 91125, USA"}]}],"member":"9598","published-online":{"date-parts":[[2026,3,16]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Richard P. Feynman ``Simulating physics with computers'' International Journal of Theoretical Physics 21, 467-488 (1982).","DOI":"10.1007\/BF02650179"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Yudong Cao, Jonathan Romero, Jonathan P Olson, Matthias Degroote, Peter D Johnson, M\u00e1ria Kieferov\u00e1, Ian D Kivlichan, Tim Menke, Borja Peropadre, and Nicolas PD Sawaya, ``Quantum Chemistry in the Age of Quantum Computing'' Chemical Reviews 119, 10856\u201310915 (2019).","DOI":"10.1021\/acs.chemrev.8b00803"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Sergey B. Bravyiand Alexei Yu. Kitaev ``Fermionic Quantum Computation'' Annals of Physics 298, 210\u2013226 (2002).","DOI":"10.1006\/aphy.2002.6254"},{"key":"3","unstructured":"Dorit Aharonovand Tomer Naveh ``Quantum NP - A Survey'' (2002)."},{"key":"4","doi-asserted-by":"publisher","unstructured":"Julia Kempe, Alexei Kitaev, and Oded Regev, ``The complexity of the local Hamiltonian problem'' SIAM Journal on Computing 35, 1070\u20131097 (2006).","DOI":"10.1137\/S0097539704445226"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Sevag Gharibian, Yichen Huang, Zeph Landau, and Seung Woo Shin, ``Quantum Hamiltonian Complexity'' Foundations and Trends in Theoretical Computer Science 10, 159\u2013282 (2015).","DOI":"10.1561\/0400000066"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Matthew B. Hastingsand Ryan O'Donnell ``Optimizing strongly interacting fermionic Hamiltonians'' Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing 776\u2013789 (2022).","DOI":"10.1145\/3519935.3519960"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Eric R. Anschuetz, Chi-Fang Chen, Bobak T. Kiani, and Robbie King, ``Strongly Interacting Fermions Are Nontrivial yet Nonglassy'' Phys. Rev. Lett. 135, 030602 (2025).","DOI":"10.1103\/cbqf-d24r"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Subir Sachdevand Jinwu Ye ``Gapless spin-fluid ground state in a random quantum Heisenberg magnet'' Phys. Rev. Lett. 70, 3339\u20133342 (1993).","DOI":"10.1103\/PhysRevLett.70.3339"},{"key":"9","unstructured":"Alexei Kitaev ``A simple model of quantum holography'' (2015)."},{"key":"10","doi-asserted-by":"publisher","unstructured":"Zhang Jiang, Kevin J. Sung, Kostyantyn Kechedzhi, Vadim N. Smelyanskiy, and Sergio Boixo, ``Quantum Algorithms to Simulate Many-Body Physics of Correlated Fermions'' Physical Review Applied 9, 044036 (2018).","DOI":"10.1103\/physrevapplied.9.044036"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Vladimir Rosenhaus ``An introduction to the SYK model'' Journal of Physics A: Mathematical and Theoretical 52, 323001 (2019).","DOI":"10.1088\/1751-8121\/ab2ce1"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Antonio M. Garc\u00eda-Garc\u00eda, Yiyang Jia, and Jacobus J. M. Verbaarschot, ``Exact moments of the Sachdev-Ye-Kitaev model up to order $1\/N^2$'' JHEP 04, 146 (2018).","DOI":"10.1007\/JHEP04(2018)146"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Renjie Feng, Gang Tian, and Dongyi Wei, ``Spectrum of SYK model'' Peking Mathematical Journal 2, 41\u201370 (2019).","DOI":"10.1007\/s42543-018-0007-1"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Arijit Haldar, Omid Tavakol, and Thomas Scaffidi, ``Variational wave functions for Sachdev-Ye-Kitaev models'' Phys. Rev. Res. 3, 023020 (2021).","DOI":"10.1103\/PhysRevResearch.3.023020"},{"key":"15","unstructured":"Shenglong Xu, Leonard Susskind, Yuan Su, and Brian Swingle, ``A Sparse Model of Quantum Holography'' (2020)."},{"key":"16","doi-asserted-by":"publisher","unstructured":"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, 51\u201355 (2022).","DOI":"10.1038\/s41586-022-05424-3"},{"key":"17","unstructured":"Bryce Kobrin, Thomas Schuster, and Norman Y. Yao, ``Comment on ``Traversable wormhole dynamics on a quantum processor'''' (2023)."},{"key":"18","doi-asserted-by":"publisher","unstructured":"Patrick Orman, Hrant Gharibyan, and John Preskill, ``Quantum chaos in the sparse SYK model'' Journal of High Energy Physics 2025, 1\u201324 (2025).","DOI":"10.1007\/JHEP02(2025)173"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Yaroslav Herasymenko, Maarten Stroeks, Jonas Helsen, and Barbara Terhal, ``Optimizing sparse fermionic Hamiltonians'' Quantum 7, 1081 (2023).","DOI":"10.22331\/q-2023-08-10-1081"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Daniel Hothem, Ojas Parekh, and Kevin Thompson, ``Improved Approximations for Extremal Eigenvalues of Sparse Hamiltonians'' 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (2023).","DOI":"10.4230\/LIPICS.TQC.2023.6"},{"key":"21","unstructured":"Joshua Cudbyand Sergii Strelchuk ``Gaussian decomposition of magic states for matchgate computations'' (2025)."},{"key":"22","doi-asserted-by":"publisher","unstructured":"M. Hebenstreit, R. Jozsa, B. Kraus, S. Strelchuk, and M. Yoganathan, ``All Pure Fermionic Non-Gaussian States Are Magic States for Matchgate Computations'' Phys. Rev. Lett. 123, 080503 (2019).","DOI":"10.1103\/PhysRevLett.123.080503"},{"key":"23","unstructured":"M. B. Hastings ``Field Theory and The Sum-of-Squares for Quantum Systems'' (2023)."},{"key":"24","unstructured":"Joao Basso, Chi-Fang Chen, and Alexander M. Dalzell, ``Optimizing random local Hamiltonians by dissipation'' (2024)."},{"key":"25","doi-asserted-by":"publisher","unstructured":"Chi-Fang Chen, Alexander M. Dalzell, Mario Berta, Fernando G. S. L. Brand\u00e3o, and Joel A. Tropp, ``Sparse Random Hamiltonians Are Quantumly Easy'' Phys. Rev. X 14, 011014 (2024).","DOI":"10.1103\/PhysRevX.14.011014"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Andrea Montanari ``Optimization of the Sherrington-Kirkpatrick Hamiltonian'' 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) 1417\u20131433 (2019).","DOI":"10.1109\/FOCS.2019.00087"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Ahmed El Alaoui, Andrea Montanari, and Mark Sellke, ``Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization'' 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) 323\u2013334 (2022).","DOI":"10.1109\/FOCS54457.2022.00038"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Mor Harchol-Balter ``Introduction to Probability for Computing'' Cambridge University Press (2023).","DOI":"10.1017\/9781009309097"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Richard Brauerand Hermann Weyl ``Spinors in n Dimensions'' American Journal of Mathematics 57, 425\u2013449 (1935).","DOI":"10.2307\/2371218"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Jacopo Suraceand Luca Tagliacozzo ``Fermionic Gaussian states: an introduction to numerical approaches'' SciPost Physics Lecture Notes 54 (2022).","DOI":"10.21468\/scipostphyslectnotes.54"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Sergey Bravyi, David Gosset, Robert K\u00f6nig, and Kristan Temme, ``Approximation algorithms for quantum many-body problems'' Journal of Mathematical Physics 60, 032203 (2019).","DOI":"10.1063\/1.5085428"},{"key":"32","doi-asserted-by":"publisher","unstructured":"G. C. Wick ``The Evaluation of the Collision Matrix'' Phys. Rev. 80, 268\u2013272 (1950).","DOI":"10.1103\/PhysRev.80.268"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Carlos de Gois, Kiara Hansenne, and Otfried G\u00fchne, ``Uncertainty relations from graph theory'' Physical Review A 107, 062211 (2023).","DOI":"10.1103\/PhysRevA.107.062211"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Zhen-Peng Xu, Ren\u00e9 Schwonnek, and Andreas Winter, ``Bounding the Joint Numerical Range of Pauli Strings by Graph Parameters'' PRX Quantum 5, 020318 (2024).","DOI":"10.1103\/PRXQuantum.5.020318"},{"key":"35","doi-asserted-by":"publisher","unstructured":"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, 232 (2025).","DOI":"10.1007\/s00220-025-05412-4"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Robbie King, David Gosset, Robin Kothari, and Ryan Babbush, ``Triply Efficient Shadow Tomography'' PRX Quantum 6, 010336 (2025).","DOI":"10.1103\/PRXQuantum.6.010336"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Martin J Wainwright ``High-dimensional statistics: A non-asymptotic viewpoint'' Cambridge University Press (2019).","DOI":"10.1017\/9781108627771"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Roman Vershynin ``High-dimensional probability: An introduction with applications in data science'' Cambridge University Press (2018).","DOI":"10.1017\/9781108231596"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Afonso S. Bandeiraand Ramon van Handel ``Sharp nonasymptotic bounds on the norm of random matrices with independent entries'' The Annals of Probability 44, 2479\u20132506 (2016).","DOI":"10.1214\/15-aop1025"},{"key":"40","doi-asserted-by":"publisher","unstructured":"Zhi-Dong Baiand Yong-Qua Yin ``Necessary and sufficient conditions for almost sure convergence of the largest eigenvalue of a Wigner matrix'' The Annals of Probability 16, 1729\u20131741 (1988).","DOI":"10.1214\/aop\/1176991594"},{"key":"41","doi-asserted-by":"publisher","unstructured":"Greg W. Anderson, Alice Guionnet, and Ofer Zeitouni, ``Real and complex Wigner matrices'' Cambridge University Press (2009).","DOI":"10.1017\/CBO9780511801334"},{"key":"42","doi-asserted-by":"publisher","unstructured":"B. Laurentand P. Massart ``Adaptive estimation of a quadratic functional by model selection'' The Annals of Statistics 28, 1302\u20131338 (2000).","DOI":"10.1214\/aos\/1015957395"},{"key":"43","doi-asserted-by":"publisher","unstructured":"Joel A. Tropp ``User-Friendly Tail Bounds for Sums of Random Matrices'' Foundations of Computational Mathematics 12, 389\u2013434 (2011).","DOI":"10.1007\/s10208-011-9099-z"},{"key":"44","doi-asserted-by":"publisher","unstructured":"Cornelius Lanczos ``An iteration method for the solution of the eigenvalue problem of linear differential and integral operators'' Journal of Research of the National Bureau of Standards 45, 255\u2013282 (1950).","DOI":"10.6028\/jres.045.026"},{"key":"45","doi-asserted-by":"publisher","unstructured":"Christopher C Paige ``Computational variants of the Lanczos method for the eigenproblem'' IMA Journal of Applied Mathematics 10, 373\u2013381 (1972).","DOI":"10.1093\/imamat\/10.3.373"},{"key":"46","doi-asserted-by":"publisher","unstructured":"H-G Weikert, H-D Meyer, LS Cederbaum, and Francesco Tarantelli, ``Block Lanczos and many-body theory: Application to the one-particle Green\u2019s function'' The Journal of Chemical Physics 104, 7122\u20137138 (1996).","DOI":"10.1063\/1.471429"},{"key":"47","doi-asserted-by":"publisher","unstructured":"Hong-Yi Chen, R. Wortis, and W. A. Atkinson, ``Disorder-induced zero-bias anomaly in the Anderson-Hubbard model: Numerical and analytical calculations'' Phys. Rev. B 84, 045113 (2011).","DOI":"10.1103\/PhysRevB.84.045113"},{"key":"48","doi-asserted-by":"publisher","unstructured":"Victor H. de la Pe\u00f1aand Stephen J. Montgomery-Smith ``Bounds on the tail probability of U-statistics and quadratic forms'' Bull. Amer. Math. Soc 31, 223\u2013227 (1994).","DOI":"10.48550\/arXiv.math\/9309210"},{"key":"49","doi-asserted-by":"publisher","unstructured":"Aline Bonami ``\u00c9tude des coefficients de Fourier des fonctions de $L^p(G)$'' Annales de l'institut Fourier 20, 335\u2013402 (1970).","DOI":"10.5802\/aif.357"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2026-03-16-2029\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T08:32:10Z","timestamp":1773649930000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2026-03-16-2029\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,16]]},"references-count":50,"URL":"https:\/\/doi.org\/10.22331\/q-2026-03-16-2029","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,16]]},"article-number":"2029"}}