Optimizing Sparse SYK
Summarize this article with:
AbstractFinding the ground state of strongly-interacting fermionic systems is often the prerequisite for fully understanding both quantum chemistry and condensed matter systems. The Sachdev–Ye–Kitaev (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–O'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 $1-p$, where $p=\Theta(1/n^3)$ and $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 $p \in [\Theta(1/n^3),1]$ and show there indeed exists a certain robustness of sparsification. We prove that with high probability, Gaussian states achieve only a $\Theta(1/\sqrt{n})$-factor approximation to the true ground state energy of sparse SYK for all $p\geq\Omega(\log n/n^2)$, and that Gaussian states cannot achieve constant-factor approximations unless $p \leq O(\log^2 n/n^3)$. Additionally, we prove that the quantum algorithm of Hastings–O'Donnell still achieves a constant-factor approximation to the ground state energy when $p\geq\Omega(\log n/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 $p \geq \Omega(\log n/n)$, extending the analogous $p=1$ result of Hastings–O'Donnell.Featured image: A visualization of the Hastings–O’Donnell quantum algorithm applied to sparse SYK. This algorithm achieves a constant approximation to the ground state energy whenever $p\gtrsim 1/n$.Popular summaryOne central task in quantum chemistry is finding the ground state of physical systems. Though this is difficult in general—even for quantum computers—there exist effective classical methods such as Hartree–Fock which output Gaussian state approximations to ground states. Understanding when Gaussian states do not well-approximate the true ground state energy and when quantum algorithms do is thus important for understanding where one might find a quantum advantage in a practically relevant task. It was shown that Gaussian states provably fail and quantum algorithms succeed on typical instances of Sachdev–Ye–Kitaev (SYK), a popular model with applications to electron correlations and quantum gravity. However, it remains a major engineering challenge to simulate SYK on current quantum hardware due to its size and complexity. The sparse SYK model was proposed as a smaller and less-dense version of SYK; but whether it retains “SYK-like” properties is still unclear. Notably, previous works on sparse SYK have only considered the sparsest ($p=1/n^3$) case where each particle has a constant number of interactions. This leaves open the question of what happens between the sparsest ($p=1/n^3$) and densest ($p=1$) extremes. We make progress in two ways: first, we show that sparsifying SYK does not improve Gaussian state approximations up to $p\gtrsim1/n^2$ and can only achieve a near-optimal approximation in essentially the sparsest regime. Second, we prove a specific quantum algorithm does achieve a near-optimal approximation ratio for the sparse SYK model whenever $p\gtrsim1/n$. Our results suggest similar physical properties between SYK and sparse SYK in the “moderately sparse” regime, a new potential candidate for showcasing quantum advantage.► BibTeX data@article{Ding2026optimizingsparsesyk, doi = {10.22331/q-2026-03-16-2029}, url = {https://doi.org/10.22331/q-2026-03-16-2029}, title = {Optimizing {S}parse {SYK}}, author = {Ding, Matthew and King, Robbie and Kiani, Bobak T. and Anschuetz, Eric R.}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2029}, month = mar, year = {2026} }► References [1] Richard P. Feynman ``Simulating physics with computers'' International Journal of Theoretical Physics 21, 467-488 (1982). https://doi.org/10.1007/BF02650179 [2] Yudong Cao, Jonathan Romero, Jonathan P Olson, Matthias Degroote, Peter D Johnson, Mária Kieferová, Ian D Kivlichan, Tim Menke, Borja Peropadre, and Nicolas PD Sawaya, ``Quantum Chemistry in the Age of Quantum Computing'' Chemical Reviews 119, 10856–10915 (2019). https://doi.org/10.1021/acs.chemrev.8b00803 [3] Sergey B.
Bravyiand Alexei Yu. Kitaev ``Fermionic Quantum Computation'' Annals of Physics 298, 210–226 (2002). https://doi.org/10.1006/aphy.2002.6254 [4] Dorit Aharonovand Tomer Naveh ``Quantum NP - A Survey'' (2002). [5] Julia Kempe, Alexei Kitaev, and Oded Regev, ``The complexity of the local Hamiltonian problem'' SIAM Journal on Computing 35, 1070–1097 (2006). https://doi.org/10.1137/S0097539704445226 [6] Sevag Gharibian, Yichen Huang, Zeph Landau, and Seung Woo Shin, ``Quantum Hamiltonian Complexity'' Foundations and Trends in Theoretical Computer Science 10, 159–282 (2015). https://doi.org/10.1561/0400000066 [7] Matthew B. Hastingsand Ryan O'Donnell ``Optimizing strongly interacting fermionic Hamiltonians'' Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing 776–789 (2022). https://doi.org/10.1145/3519935.3519960 arXiv:2110.10701 [8] 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). https://doi.org/10.1103/cbqf-d24r [9] Subir Sachdevand Jinwu Ye ``Gapless spin-fluid ground state in a random quantum Heisenberg magnet'' Phys. Rev. Lett. 70, 3339–3342 (1993). https://doi.org/10.1103/PhysRevLett.70.3339 [10] Alexei Kitaev ``A simple model of quantum holography'' (2015). https://online.kitp.ucsb.edu/online/entangled15/kitaev/ [11] 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). https://doi.org/10.1103/physrevapplied.9.044036 [12] Vladimir Rosenhaus ``An introduction to the SYK model'' Journal of Physics A: Mathematical and Theoretical 52, 323001 (2019). https://doi.org/10.1088/1751-8121/ab2ce1 [13] Antonio M. García-García, 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). https://doi.org/10.1007/JHEP04(2018)146 [14] Renjie Feng, Gang Tian, and Dongyi Wei, ``Spectrum of SYK model'' Peking Mathematical Journal 2, 41–70 (2019). https://doi.org/10.1007/s42543-018-0007-1 [15] Arijit Haldar, Omid Tavakol, and Thomas Scaffidi, ``Variational wave functions for Sachdev-Ye-Kitaev models'' Phys. Rev. Res. 3, 023020 (2021). https://doi.org/10.1103/PhysRevResearch.3.023020 [16] Shenglong Xu, Leonard Susskind, Yuan Su, and Brian Swingle, ``A Sparse Model of Quantum Holography'' (2020). arXiv:2008.02303 [17] 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–55 (2022). https://doi.org/10.1038/s41586-022-05424-3 [18] Bryce Kobrin, Thomas Schuster, and Norman Y. Yao, ``Comment on ``Traversable wormhole dynamics on a quantum processor'''' (2023). arXiv:2302.07897 [19] Patrick Orman, Hrant Gharibyan, and John Preskill, ``Quantum chaos in the sparse SYK model'' Journal of High Energy Physics 2025, 1–24 (2025). https://doi.org/10.1007/JHEP02(2025)173 [20] Yaroslav Herasymenko, Maarten Stroeks, Jonas Helsen, and Barbara Terhal, ``Optimizing sparse fermionic Hamiltonians'' Quantum 7, 1081 (2023). https://doi.org/10.22331/q-2023-08-10-1081 [21] 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). https://doi.org/10.4230/LIPICS.TQC.2023.6 [22] Joshua Cudbyand Sergii Strelchuk ``Gaussian decomposition of magic states for matchgate computations'' (2025). arXiv:2307.12654 [23] 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). https://doi.org/10.1103/PhysRevLett.123.080503 [24] M. B. Hastings ``Field Theory and The Sum-of-Squares for Quantum Systems'' (2023). arXiv:2302.14006 [25] Joao Basso, Chi-Fang Chen, and Alexander M. Dalzell, ``Optimizing random local Hamiltonians by dissipation'' (2024). arXiv:2411.02578 [26] Chi-Fang Chen, Alexander M. Dalzell, Mario Berta, Fernando G. S. L. Brandão, and Joel A. Tropp, ``Sparse Random Hamiltonians Are Quantumly Easy'' Phys. Rev. X 14, 011014 (2024). https://doi.org/10.1103/PhysRevX.14.011014 [27] Andrea Montanari ``Optimization of the Sherrington-Kirkpatrick Hamiltonian'' 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) 1417–1433 (2019). https://doi.org/10.1109/FOCS.2019.00087 [28] 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–334 (2022). https://doi.org/10.1109/FOCS54457.2022.00038 [29] Mor Harchol-Balter ``Introduction to Probability for Computing'' Cambridge University Press (2023). https://doi.org/10.1017/9781009309097 [30] Richard Brauerand Hermann Weyl ``Spinors in n Dimensions'' American Journal of Mathematics 57, 425–449 (1935). https://doi.org/10.2307/2371218 [31] Jacopo Suraceand Luca Tagliacozzo ``Fermionic Gaussian states: an introduction to numerical approaches'' SciPost Physics Lecture Notes 54 (2022). https://doi.org/10.21468/scipostphyslectnotes.54 [32] Sergey Bravyi, David Gosset, Robert König, and Kristan Temme, ``Approximation algorithms for quantum many-body problems'' Journal of Mathematical Physics 60, 032203 (2019). https://doi.org/10.1063/1.5085428 [33] G. C. Wick ``The Evaluation of the Collision Matrix'' Phys. Rev. 80, 268–272 (1950). https://doi.org/10.1103/PhysRev.80.268 [34] Carlos de Gois, Kiara Hansenne, and Otfried Gühne, ``Uncertainty relations from graph theory'' Physical Review A 107, 062211 (2023). https://doi.org/10.1103/PhysRevA.107.062211 [35] Zhen-Peng Xu, René Schwonnek, and Andreas Winter, ``Bounding the Joint Numerical Range of Pauli Strings by Graph Parameters'' PRX Quantum 5, 020318 (2024). https://doi.org/10.1103/PRXQuantum.5.020318 [36] 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). https://doi.org/10.1007/s00220-025-05412-4 [37] Robbie King, David Gosset, Robin Kothari, and Ryan Babbush, ``Triply Efficient Shadow Tomography'' PRX Quantum 6, 010336 (2025). https://doi.org/10.1103/PRXQuantum.6.010336 [38] Martin J Wainwright ``High-dimensional statistics: A non-asymptotic viewpoint'' Cambridge University Press (2019). https://doi.org/10.1017/9781108627771 [39] Roman Vershynin ``High-dimensional probability: An introduction with applications in data science'' Cambridge University Press (2018). https://doi.org/10.1017/9781108231596 [40] Afonso S. Bandeiraand Ramon van Handel ``Sharp nonasymptotic bounds on the norm of random matrices with independent entries'' The Annals of Probability 44, 2479–2506 (2016). https://doi.org/10.1214/15-aop1025 [41] 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–1741 (1988). https://doi.org/10.1214/aop/1176991594 [42] Greg W. Anderson, Alice Guionnet, and Ofer Zeitouni, ``Real and complex Wigner matrices'' Cambridge University Press (2009). https://doi.org/10.1017/CBO9780511801334 [43] B. Laurentand P. Massart ``Adaptive estimation of a quadratic functional by model selection'' The Annals of Statistics 28, 1302–1338 (2000). https://doi.org/10.1214/aos/1015957395 [44] Joel A. Tropp ``User-Friendly Tail Bounds for Sums of Random Matrices'' Foundations of Computational Mathematics 12, 389–434 (2011). https://doi.org/10.1007/s10208-011-9099-z [45] 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–282 (1950). https://doi.org/10.6028/jres.045.026 [46] Christopher C Paige ``Computational variants of the Lanczos method for the eigenproblem'' IMA Journal of Applied Mathematics 10, 373–381 (1972). https://doi.org/10.1093/imamat/10.3.373 [47] H-G Weikert, H-D Meyer, LS Cederbaum, and Francesco Tarantelli, ``Block Lanczos and many-body theory: Application to the one-particle Green’s function'' The Journal of Chemical Physics 104, 7122–7138 (1996). https://doi.org/10.1063/1.471429 [48] 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). https://doi.org/10.1103/PhysRevB.84.045113 [49] Victor H. de la Peñaand Stephen J. Montgomery-Smith ``Bounds on the tail probability of U-statistics and quadratic forms'' Bull. Amer. Math. Soc 31, 223–227 (1994). https://doi.org/10.48550/arXiv.math/9309210 [50] Aline Bonami ``Étude des coefficients de Fourier des fonctions de $L^p(G)$'' Annales de l'institut Fourier 20, 335–402 (1970). https://doi.org/10.5802/aif.357Cited byCould not fetch Crossref cited-by data during last attempt 2026-03-16 08:27:46: Could not fetch cited-by data for 10.22331/q-2026-03-16-2029 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-03-16 08:27:47: No response from ADS or unable to decode the received json data when getting the list of citing works.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. AbstractFinding the ground state of strongly-interacting fermionic systems is often the prerequisite for fully understanding both quantum chemistry and condensed matter systems. The Sachdev–Ye–Kitaev (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–O'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 $1-p$, where $p=\Theta(1/n^3)$ and $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 $p \in [\Theta(1/n^3),1]$ and show there indeed exists a certain robustness of sparsification. We prove that with high probability, Gaussian states achieve only a $\Theta(1/\sqrt{n})$-factor approximation to the true ground state energy of sparse SYK for all $p\geq\Omega(\log n/n^2)$, and that Gaussian states cannot achieve constant-factor approximations unless $p \leq O(\log^2 n/n^3)$. Additionally, we prove that the quantum algorithm of Hastings–O'Donnell still achieves a constant-factor approximation to the ground state energy when $p\geq\Omega(\log n/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 $p \geq \Omega(\log n/n)$, extending the analogous $p=1$ result of Hastings–O'Donnell.Featured image: A visualization of the Hastings–O’Donnell quantum algorithm applied to sparse SYK. This algorithm achieves a constant approximation to the ground state energy whenever $p\gtrsim 1/n$.Popular summaryOne central task in quantum chemistry is finding the ground state of physical systems. Though this is difficult in general—even for quantum computers—there exist effective classical methods such as Hartree–Fock which output Gaussian state approximations to ground states. Understanding when Gaussian states do not well-approximate the true ground state energy and when quantum algorithms do is thus important for understanding where one might find a quantum advantage in a practically relevant task. It was shown that Gaussian states provably fail and quantum algorithms succeed on typical instances of Sachdev–Ye–Kitaev (SYK), a popular model with applications to electron correlations and quantum gravity. However, it remains a major engineering challenge to simulate SYK on current quantum hardware due to its size and complexity. The sparse SYK model was proposed as a smaller and less-dense version of SYK; but whether it retains “SYK-like” properties is still unclear. Notably, previous works on sparse SYK have only considered the sparsest ($p=1/n^3$) case where each particle has a constant number of interactions. This leaves open the question of what happens between the sparsest ($p=1/n^3$) and densest ($p=1$) extremes. We make progress in two ways: first, we show that sparsifying SYK does not improve Gaussian state approximations up to $p\gtrsim1/n^2$ and can only achieve a near-optimal approximation in essentially the sparsest regime. Second, we prove a specific quantum algorithm does achieve a near-optimal approximation ratio for the sparse SYK model whenever $p\gtrsim1/n$. Our results suggest similar physical properties between SYK and sparse SYK in the “moderately sparse” regime, a new potential candidate for showcasing quantum advantage.► BibTeX data@article{Ding2026optimizingsparsesyk, doi = {10.22331/q-2026-03-16-2029}, url = {https://doi.org/10.22331/q-2026-03-16-2029}, title = {Optimizing {S}parse {SYK}}, author = {Ding, Matthew and King, Robbie and Kiani, Bobak T. and Anschuetz, Eric R.}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2029}, month = mar, year = {2026} }► References [1] Richard P. Feynman ``Simulating physics with computers'' International Journal of Theoretical Physics 21, 467-488 (1982). https://doi.org/10.1007/BF02650179 [2] Yudong Cao, Jonathan Romero, Jonathan P Olson, Matthias Degroote, Peter D Johnson, Mária Kieferová, Ian D Kivlichan, Tim Menke, Borja Peropadre, and Nicolas PD Sawaya, ``Quantum Chemistry in the Age of Quantum Computing'' Chemical Reviews 119, 10856–10915 (2019). https://doi.org/10.1021/acs.chemrev.8b00803 [3] Sergey B.
Bravyiand Alexei Yu. Kitaev ``Fermionic Quantum Computation'' Annals of Physics 298, 210–226 (2002). https://doi.org/10.1006/aphy.2002.6254 [4] Dorit Aharonovand Tomer Naveh ``Quantum NP - A Survey'' (2002). [5] Julia Kempe, Alexei Kitaev, and Oded Regev, ``The complexity of the local Hamiltonian problem'' SIAM Journal on Computing 35, 1070–1097 (2006). https://doi.org/10.1137/S0097539704445226 [6] Sevag Gharibian, Yichen Huang, Zeph Landau, and Seung Woo Shin, ``Quantum Hamiltonian Complexity'' Foundations and Trends in Theoretical Computer Science 10, 159–282 (2015). https://doi.org/10.1561/0400000066 [7] Matthew B. Hastingsand Ryan O'Donnell ``Optimizing strongly interacting fermionic Hamiltonians'' Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing 776–789 (2022). https://doi.org/10.1145/3519935.3519960 arXiv:2110.10701 [8] 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). https://doi.org/10.1103/cbqf-d24r [9] Subir Sachdevand Jinwu Ye ``Gapless spin-fluid ground state in a random quantum Heisenberg magnet'' Phys. Rev. Lett. 70, 3339–3342 (1993). https://doi.org/10.1103/PhysRevLett.70.3339 [10] Alexei Kitaev ``A simple model of quantum holography'' (2015). https://online.kitp.ucsb.edu/online/entangled15/kitaev/ [11] 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). https://doi.org/10.1103/physrevapplied.9.044036 [12] Vladimir Rosenhaus ``An introduction to the SYK model'' Journal of Physics A: Mathematical and Theoretical 52, 323001 (2019). https://doi.org/10.1088/1751-8121/ab2ce1 [13] Antonio M. García-García, 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). https://doi.org/10.1007/JHEP04(2018)146 [14] Renjie Feng, Gang Tian, and Dongyi Wei, ``Spectrum of SYK model'' Peking Mathematical Journal 2, 41–70 (2019). https://doi.org/10.1007/s42543-018-0007-1 [15] Arijit Haldar, Omid Tavakol, and Thomas Scaffidi, ``Variational wave functions for Sachdev-Ye-Kitaev models'' Phys. Rev. Res. 3, 023020 (2021). https://doi.org/10.1103/PhysRevResearch.3.023020 [16] Shenglong Xu, Leonard Susskind, Yuan Su, and Brian Swingle, ``A Sparse Model of Quantum Holography'' (2020). arXiv:2008.02303 [17] 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–55 (2022). https://doi.org/10.1038/s41586-022-05424-3 [18] Bryce Kobrin, Thomas Schuster, and Norman Y. Yao, ``Comment on ``Traversable wormhole dynamics on a quantum processor'''' (2023). arXiv:2302.07897 [19] Patrick Orman, Hrant Gharibyan, and John Preskill, ``Quantum chaos in the sparse SYK model'' Journal of High Energy Physics 2025, 1–24 (2025). https://doi.org/10.1007/JHEP02(2025)173 [20] Yaroslav Herasymenko, Maarten Stroeks, Jonas Helsen, and Barbara Terhal, ``Optimizing sparse fermionic Hamiltonians'' Quantum 7, 1081 (2023). https://doi.org/10.22331/q-2023-08-10-1081 [21] 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). https://doi.org/10.4230/LIPICS.TQC.2023.6 [22] Joshua Cudbyand Sergii Strelchuk ``Gaussian decomposition of magic states for matchgate computations'' (2025). arXiv:2307.12654 [23] 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). https://doi.org/10.1103/PhysRevLett.123.080503 [24] M. B. Hastings ``Field Theory and The Sum-of-Squares for Quantum Systems'' (2023). arXiv:2302.14006 [25] Joao Basso, Chi-Fang Chen, and Alexander M. Dalzell, ``Optimizing random local Hamiltonians by dissipation'' (2024). arXiv:2411.02578 [26] Chi-Fang Chen, Alexander M. Dalzell, Mario Berta, Fernando G. S. L. Brandão, and Joel A. Tropp, ``Sparse Random Hamiltonians Are Quantumly Easy'' Phys. Rev. X 14, 011014 (2024). https://doi.org/10.1103/PhysRevX.14.011014 [27] Andrea Montanari ``Optimization of the Sherrington-Kirkpatrick Hamiltonian'' 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) 1417–1433 (2019). https://doi.org/10.1109/FOCS.2019.00087 [28] 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–334 (2022). https://doi.org/10.1109/FOCS54457.2022.00038 [29] Mor Harchol-Balter ``Introduction to Probability for Computing'' Cambridge University Press (2023). https://doi.org/10.1017/9781009309097 [30] Richard Brauerand Hermann Weyl ``Spinors in n Dimensions'' American Journal of Mathematics 57, 425–449 (1935). https://doi.org/10.2307/2371218 [31] Jacopo Suraceand Luca Tagliacozzo ``Fermionic Gaussian states: an introduction to numerical approaches'' SciPost Physics Lecture Notes 54 (2022). https://doi.org/10.21468/scipostphyslectnotes.54 [32] Sergey Bravyi, David Gosset, Robert König, and Kristan Temme, ``Approximation algorithms for quantum many-body problems'' Journal of Mathematical Physics 60, 032203 (2019). https://doi.org/10.1063/1.5085428 [33] G. C. Wick ``The Evaluation of the Collision Matrix'' Phys. Rev. 80, 268–272 (1950). https://doi.org/10.1103/PhysRev.80.268 [34] Carlos de Gois, Kiara Hansenne, and Otfried Gühne, ``Uncertainty relations from graph theory'' Physical Review A 107, 062211 (2023). https://doi.org/10.1103/PhysRevA.107.062211 [35] Zhen-Peng Xu, René Schwonnek, and Andreas Winter, ``Bounding the Joint Numerical Range of Pauli Strings by Graph Parameters'' PRX Quantum 5, 020318 (2024). https://doi.org/10.1103/PRXQuantum.5.020318 [36] 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). https://doi.org/10.1007/s00220-025-05412-4 [37] Robbie King, David Gosset, Robin Kothari, and Ryan Babbush, ``Triply Efficient Shadow Tomography'' PRX Quantum 6, 010336 (2025). https://doi.org/10.1103/PRXQuantum.6.010336 [38] Martin J Wainwright ``High-dimensional statistics: A non-asymptotic viewpoint'' Cambridge University Press (2019). https://doi.org/10.1017/9781108627771 [39] Roman Vershynin ``High-dimensional probability: An introduction with applications in data science'' Cambridge University Press (2018). https://doi.org/10.1017/9781108231596 [40] Afonso S. Bandeiraand Ramon van Handel ``Sharp nonasymptotic bounds on the norm of random matrices with independent entries'' The Annals of Probability 44, 2479–2506 (2016). https://doi.org/10.1214/15-aop1025 [41] 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–1741 (1988). https://doi.org/10.1214/aop/1176991594 [42] Greg W. Anderson, Alice Guionnet, and Ofer Zeitouni, ``Real and complex Wigner matrices'' Cambridge University Press (2009). https://doi.org/10.1017/CBO9780511801334 [43] B. Laurentand P. Massart ``Adaptive estimation of a quadratic functional by model selection'' The Annals of Statistics 28, 1302–1338 (2000). https://doi.org/10.1214/aos/1015957395 [44] Joel A. Tropp ``User-Friendly Tail Bounds for Sums of Random Matrices'' Foundations of Computational Mathematics 12, 389–434 (2011). https://doi.org/10.1007/s10208-011-9099-z [45] 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–282 (1950). https://doi.org/10.6028/jres.045.026 [46] Christopher C Paige ``Computational variants of the Lanczos method for the eigenproblem'' IMA Journal of Applied Mathematics 10, 373–381 (1972). https://doi.org/10.1093/imamat/10.3.373 [47] H-G Weikert, H-D Meyer, LS Cederbaum, and Francesco Tarantelli, ``Block Lanczos and many-body theory: Application to the one-particle Green’s function'' The Journal of Chemical Physics 104, 7122–7138 (1996). https://doi.org/10.1063/1.471429 [48] 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). https://doi.org/10.1103/PhysRevB.84.045113 [49] Victor H. de la Peñaand Stephen J. Montgomery-Smith ``Bounds on the tail probability of U-statistics and quadratic forms'' Bull. Amer. Math. Soc 31, 223–227 (1994). https://doi.org/10.48550/arXiv.math/9309210 [50] Aline Bonami ``Étude des coefficients de Fourier des fonctions de $L^p(G)$'' Annales de l'institut Fourier 20, 335–402 (1970). https://doi.org/10.5802/aif.357Cited byCould not fetch Crossref cited-by data during last attempt 2026-03-16 08:27:46: Could not fetch cited-by data for 10.22331/q-2026-03-16-2029 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-03-16 08:27:47: No response from ADS or unable to decode the received json data when getting the list of citing works.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.