{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T00:11:26Z","timestamp":1783469486326,"version":"3.55.0"},"reference-count":34,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2023,8,10]],"date-time":"2023-08-10T00:00:00Z","timestamp":1691625600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Dutch Research Council","doi-asserted-by":"crossref","award":["601.QT.001-1"],"award-info":[{"award-number":["601.QT.001-1"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003246","name":"Dutch Research Council","doi-asserted-by":"crossref","award":["024.003.037"],"award-info":[{"award-number":["024.003.037"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"We consider the problem of approximating the ground state energy of a fermionic Hamiltonian using a Gaussian state. In sharp contrast to the dense case [1, 2], we prove that strictly q<\/mml:mi><\/mml:math>-local sparse<\/mml:mtext><\/mml:mrow><\/mml:mrow><\/mml:math> fermionic Hamiltonians have a constant Gaussian approximation ratio; the result holds for any connectivity and interaction strengths. Sparsity means that each fermion participates in a bounded number of interactions, and strictly q<\/mml:mi><\/mml:math>-local means that each term involves exactly q<\/mml:mi><\/mml:math> fermionic (Majorana) operators. We extend our proof to give a constant Gaussian approximation ratio for sparse fermionic Hamiltonians with both quartic and quadratic terms. With additional work, we also prove a constant Gaussian approximation ratio for the so-called sparse SYK model with strictly 4<\/mml:mn><\/mml:math>-local interactions (sparse SYK-4<\/mml:mn><\/mml:math> model). In each setting we show that the Gaussian state can be efficiently determined. Finally, we prove that the O<\/mml:mi>(<\/mml:mo>n<\/mml:mi>&#x2212;<\/mml:mo>1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>2<\/mml:mn><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:math> Gaussian approximation ratio for the normal (dense) SYK-4<\/mml:mn><\/mml:math> model extends to SYK-q<\/mml:mi><\/mml:math> for even q<\/mml:mi>&#x003E;<\/mml:mo>4<\/mml:mn><\/mml:math>, with an approximation ratio of O<\/mml:mi>(<\/mml:mo>n<\/mml:mi>1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>2<\/mml:mn>&#x2013;<\/mml:mo>q<\/mml:mi>\/<\/mml:mo><\/mml:mrow>4<\/mml:mn><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:math>. Our results identify non-sparseness as the prime reason that the SYK-4<\/mml:mn><\/mml:math> model can fail to have a constant approximation ratio [1, 2].<\/jats:p>","DOI":"10.22331\/q-2023-08-10-1081","type":"journal-article","created":{"date-parts":[[2023,8,10]],"date-time":"2023-08-10T12:48:04Z","timestamp":1691671684000},"page":"1081","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":13,"title":["Optimizing sparse fermionic Hamiltonians"],"prefix":"10.22331","volume":"7","author":[{"given":"Yaroslav","family":"Herasymenko","sequence":"first","affiliation":[{"name":"QuSoft & CWI, Science Park 123 1098 XG Amsterdam, The Netherlands"},{"name":"QuTech, Delft University of Technology, Lorentzweg 1, 2628 CJ Delft, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maarten","family":"Stroeks","sequence":"additional","affiliation":[{"name":"QuTech, Delft University of Technology, Lorentzweg 1, 2628 CJ Delft, The Netherlands"},{"name":"EEMCS Faculty, Delft University of Technology, Van Mourik Broekmanweg 6, 2628 XE, Delft, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jonas","family":"Helsen","sequence":"additional","affiliation":[{"name":"QuSoft & CWI, Science Park 123 1098 XG Amsterdam, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Barbara","family":"Terhal","sequence":"additional","affiliation":[{"name":"QuTech, Delft University of Technology, Lorentzweg 1, 2628 CJ Delft, The Netherlands"},{"name":"EEMCS Faculty, Delft University of Technology, Van Mourik Broekmanweg 6, 2628 XE, Delft, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2023,8,10]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Arijit Haldar, Omid Tavakol, and Thomas Scaffidi. Variational wave functions for Sachdev-Ye-Kitaev models. Phys. Rev. Research, 3: 023020, 2021. URL https:\/\/doi.org\/10.1103\/PhysRevResearch.3.023020.","DOI":"10.1103\/PhysRevResearch.3.023020"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Matthew B. Hastings and Ryan O'Donnell. Optimizing strongly interacting fermionic Hamiltonians. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, page 776\u2013789, New York, NY, USA, 2022. ACM. URL https:\/\/doi.org\/10.1145\/3519935.3519960.","DOI":"10.1145\/3519935.3519960"},{"key":"2","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 (3): 159\u2013282, 2015. URL https:\/\/doi.org\/10.1561\/0400000066.","DOI":"10.1561\/0400000066"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Sergey B. Bravyi and Alexei Yu. Kitaev. Fermionic quantum computation. Annals of Physics, 298 (1): 210\u2013226, 2002. URL https:\/\/doi.org\/10.1006\/aphy.2002.6254.","DOI":"10.1006\/aphy.2002.6254"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Sanjeev Khanna, Madhu Sudan, Luca Trevisan, and David P Williamson. The approximability of constraint satisfaction problems. SIAM Journal on Computing, 30 (6): 1863\u20131920, 2001. URL https:\/\/doi.org\/10.1137\/S0097539799349948.","DOI":"10.1137\/S0097539799349948"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42 (6): 1115\u20131145, 1995. URL https:\/\/doi.org\/10.1145\/227683.227684.","DOI":"10.1145\/227683.227684"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Christina V Kraus and J Ignacio Cirac. Generalized Hartree\u2013Fock theory for interacting fermions in lattices: numerical methods. New Journal of Physics, 12 (11): 113004, 2010. URL https:\/\/doi.org\/10.1088\/1367-2630\/12\/11\/113004.","DOI":"10.1088\/1367-2630\/12\/11\/113004"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Sergey Bravyi and David Gosset. Complexity of quantum impurity problems. Communications in Mathematical Physics, 356 (2): 451\u2013500, 2017. URL https:\/\/doi.org\/10.1007\/s00220-017-2976-9.","DOI":"10.1007\/s00220-017-2976-9"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Sergey Bravyi and Robert Koenig. Classical simulation of dissipative fermionic linear optics. Quant. Inf. Comp., 12 (11\u201312): 925\u2013943, 2012. URL https:\/\/doi.org\/10.48550\/arXiv.1112.2184.","DOI":"10.48550\/arXiv.1112.2184"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Fernando de Melo, Piotr \u0106wikli\u0144ski, and Barbara M Terhal. The power of noisy fermionic quantum computation. New Journal of Physics, 15 (1): 013015, 2013. URL https:\/\/doi.org\/10.1088\/1367-2630\/15\/1\/013015.","DOI":"10.1088\/1367-2630\/15\/1\/013015"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Elliott H. Lieb. The classical limit of quantum spin systems. Communications in Mathematical Physics, 31 (4): 327 \u2013 340, 1973. URL https:\/\/doi.org\/10.1007\/BF01646493.","DOI":"10.1007\/BF01646493"},{"key":"11","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 (3): 032203, 2019. URL https:\/\/doi.org\/10.1063\/1.5085428.","DOI":"10.1063\/1.5085428"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Nikhil Bansal, Sergey Bravyi, and Barbara M Terhal. Classical approximation schemes for the ground-state energy of quantum and classical Ising spin Hamiltonians on planar graphs. Quantum Inf. Comp., 9 (7-8): 701\u2013720, 2009. URL https:\/\/doi.org\/10.48550\/arXiv.0705.1115.","DOI":"10.48550\/arXiv.0705.1115"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Sevag Gharibian and Julia Kempe. Approximation algorithms for QMA-complete problems. SIAM Journal on Computing, 41 (4): 1028\u20131050, 2012. URL https:\/\/doi.org\/10.1137\/110842272.","DOI":"10.1137\/110842272"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Fernando G.S.L. Brandao and Aram W. Harrow. Product-state approximations to quantum ground states. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC '13, page 871\u2013880, New York, NY, USA, 2013. Association for Computing Machinery. ISBN 9781450320290. URL https:\/\/doi.org\/10.1145\/2488608.2488719.","DOI":"10.1145\/2488608.2488719"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Aram W. Harrow and Ashley Montanaro. Extremal eigenvalues of local Hamiltonians. Quantum, 1: 6, April 2017. URL https:\/\/doi.org\/10.22331\/q-2017-04-25-6.","DOI":"10.22331\/q-2017-04-25-6"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Thiago Bergamaschi. Improved product-state approximation algorithms for quantum local Hamiltonians, 2022. URL https:\/\/doi.org\/10.48550\/arXiv.2210.08680.","DOI":"10.48550\/arXiv.2210.08680"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Sevag Gharibian and Ojas Parekh. Almost optimal classical approximation algorithms for a quantum generalization of max-cut. 2019. URL https:\/\/doi.org\/10.4230\/LIPICS.APPROX-RANDOM.2019.31.","DOI":"10.4230\/LIPICS.APPROX-RANDOM.2019.31"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Noga Alon, Konstantin Makarychev, Yury Makarychev, and Assaf Naor. Quadratic forms on graphs. Inventiones mathematicae, 163 (3): 499\u2013522, 2006. URL https:\/\/doi.org\/10.1007\/s00222-005-0465-9.","DOI":"10.1007\/s00222-005-0465-9"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Shenglong Xu, Leonard Susskind, Yuan Su, and Brian Swingle. A sparse model of quantum holography, 2020. URL https:\/\/doi.org\/10.48550\/arXiv.2008.02303.","DOI":"10.48550\/arXiv.2008.02303"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Antonio M. Garc\u00eda-Garc\u00eda, Yiyang Jia, Dario Rosa, and Jacobus J. M. Verbaarschot. Sparse Sachdev-Ye-Kitaev model, quantum chaos, and gravity duals. Phys. Rev. D, 103: 106002, 2021. URL https:\/\/doi.org\/10.1103\/PhysRevD.103.106002.","DOI":"10.1103\/PhysRevD.103.106002"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Alan Frieze and Micha\u0142 Karo\u0144ski. Introduction to random graphs. Cambridge University Press, 2016. URL https:\/\/doi.org\/10.1017\/CBO9781316339831.","DOI":"10.1017\/CBO9781316339831"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Dorit Aharonov, Itai Arad, and Thomas Vidick. The quantum PCP conjecture. ACM SIGACT News, 44: 47\u201379, 2013. URL https:\/\/doi.org\/10.48550\/arXiv.1309.7495.","DOI":"10.48550\/arXiv.1309.7495"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Sergey Bravyi, Anirban Chowdhury, David Gosset, and Pawel Wocjan. On the complexity of quantum partition functions, 2021. URL https:\/\/doi.org\/10.48550\/arXiv.2110.15466.","DOI":"10.48550\/arXiv.2110.15466"},{"key":"24","doi-asserted-by":"publisher","unstructured":"St\u00e9phane Boucheron, G\u00e1bor Lugosi, and Pascal Massart. Concentration inequalities using the entropy method. The Annals of Probability, 31 (3): 1583\u20131614, 2003. URL https:\/\/doi.org\/10.1214\/aop\/1055425791.","DOI":"10.1214\/aop\/1055425791"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Ryota Tomioka and Taiji Suzuki. Spectral norm of random tensors. arXiv, 2014. URL https:\/\/doi.org\/10.48550\/arXiv.1407.1870.","DOI":"10.48550\/arXiv.1407.1870"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Anurag Anshu, David Gosset, Karen J. Morenz Korol, and Mehdi Soleimanifar. Improved approximation algorithms for bounded-degree local Hamiltonians. Phys. Rev. Lett., 127: 250502, 2021. URL https:\/\/doi.org\/10.1103\/PhysRevLett.127.250502.","DOI":"10.1103\/PhysRevLett.127.250502"},{"key":"27","doi-asserted-by":"publisher","unstructured":"B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. The Annals of Statistics, 28 (5): 1302 \u2013 1338, 2000. URL https:\/\/doi.org\/10.1214\/aos\/1015957395.","DOI":"10.1214\/aos\/1015957395"},{"key":"28","doi-asserted-by":"publisher","unstructured":"B\u00e9la Bollob\u00e1s. Modern Graph Theory. Graduate Texts in Mathematics 184. Springer-Verlag New York, 1998. URL https:\/\/doi.org\/10.1007\/978-1-4612-0619-4.","DOI":"10.1007\/978-1-4612-0619-4"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Gabriel Andrew Dirac. Some theorems on abstract graphs. Proceedings of the London Mathematical Society, 3 (1): 69\u201381, 1952. URL https:\/\/doi.org\/10.1112\/plms\/s3-2.1.69.","DOI":"10.1112\/plms\/s3-2.1.69"},{"key":"30","unstructured":"Milton Abramowitz and Irene A. Stegun. Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. Dover, New York, 1964. ISBN 0-486-61272-4."},{"key":"31","doi-asserted-by":"publisher","unstructured":"Rafal Latala. Estimates of moments and tails of Gaussian chaoses. The Annals of Probability, 34 (6), nov 2006. URL https:\/\/doi.org\/10.1214\/009117906000000421.","DOI":"10.1214\/009117906000000421"},{"key":"32","doi-asserted-by":"publisher","unstructured":"V. H. de la Pena, S. J. Montgomery-Smith, and Jerzy Szulga. Contraction and decoupling inequalities for multilinear forms and u-statistics. The Annals of Probability, 22 (4): 1745\u20131765, 1994. URL https:\/\/doi.org\/10.48550\/arXiv.math\/9406214.","DOI":"10.48550\/arXiv.math\/9406214"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Rados\u0142aw Adamczak and Pawe\u0142 Wolff. Concentration inequalities for non-lipschitz functions with bounded derivatives of higher order. Probability Theory and Related Fields, 162 (3): 531\u2013586, 2015. URL https:\/\/doi.org\/10.1007\/s00440-014-0579-3.","DOI":"10.1007\/s00440-014-0579-3"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-08-10-1081\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,8,10]],"date-time":"2023-08-10T12:48:16Z","timestamp":1691671696000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-08-10-1081\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,10]]},"references-count":34,"URL":"https:\/\/doi.org\/10.22331\/q-2023-08-10-1081","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,10]]},"article-number":"1081"}}