Optimizing sparse fermionic Hamiltonians

Yaroslav Herasymenko; Maarten Stroeks; Jonas Helsen; Barbara Terhal

doi:10.22331/q-2023-08-10-1081

Optimizing sparse fermionic Hamiltonians

Yaroslav Herasymenko^1,2, Maarten Stroeks^2,3, Jonas Helsen¹, and Barbara Terhal^2,3

¹QuSoft & CWI, Science Park 123 1098 XG Amsterdam, The Netherlands
²QuTech, Delft University of Technology, Lorentzweg 1, 2628 CJ Delft, The Netherlands
³EEMCS Faculty, Delft University of Technology, Van Mourik Broekmanweg 6, 2628 XE, Delft, The Netherlands

Published:	2023-08-10, volume 7, page 1081
Eprint:	arXiv:2211.16518v2
Doi:	https://doi.org/10.22331/q-2023-08-10-1081
Citation:	Quantum 7, 1081 (2023).

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

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$-local $\rm {\textit {sparse}}$ 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$-local means that each term involves exactly $q$ 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$-local interactions (sparse SYK-$4$ model). In each setting we show that the Gaussian state can be efficiently determined. Finally, we prove that the $O(n^{-1/2})$ Gaussian approximation ratio for the normal (dense) SYK-$4$ model extends to SYK-$q$ for even $q\gt4$, with an approximation ratio of $O(n^{1/2 – q/4})$. Our results identify non-sparseness as the prime reason that the SYK-$4$ model can fail to have a constant approximation ratio [1, 2].

Featured image: An illustration of our key construction to achieve the finite approximation ratio for sparse Hamiltonians. The desired Gaussian state comes from a particular pairing of Majorana operators, understood graph theoretically as a vertex matching. The figure displays the two-stage process in constructing an appropriate matching.

In the first stage, Hamiltonian interactions (displayed as hyperedges on Majorana vertices) are split into subsets — colors — of "well-separated" terms. In the second stage, a vertex matching is constructed that is only "consistent" with interactions from one selected subset (highlighted color). Consistency with an interaction means that all edges of the matching are either outside or inside the respective hyper-edge.

For a Gaussian state coming from the resulting matching, only the selected interaction subset contributes to the energy. Frustration is avoided due to interactions in the subset being "well-separated". By an optimized choice of the subset, a constant approximation ratio can be guaranteed.

► BibTeX data

@article{Herasymenko2023optimizingsparse,
  doi = {10.22331/q-2023-08-10-1081},
  url = {https://doi.org/10.22331/q-2023-08-10-1081},
  title = {Optimizing sparse fermionic {H}amiltonians},
  author = {Herasymenko, Yaroslav and Stroeks, Maarten and Helsen, Jonas and Terhal, Barbara},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {7},
  pages = {1081},
  month = aug,
  year = {2023}
}

► References

[1] 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.
https://doi.org/10.1103/PhysRevResearch.3.023020

[2] 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–789, New York, NY, USA, 2022. ACM. URL https://doi.org/10.1145/3519935.3519960.
https://doi.org/10.1145/3519935.3519960

[3] Sevag Gharibian, Yichen Huang, Zeph Landau, and Seung Woo Shin. Quantum Hamiltonian Complexity. Foundations and Trends in Theoretical Computer Science, 10 (3): 159–282, 2015. URL https://doi.org/10.1561/0400000066.
https://doi.org/10.1561/0400000066

[4] Sergey B. Bravyi and Alexei Yu. Kitaev. Fermionic quantum computation. Annals of Physics, 298 (1): 210–226, 2002. URL https://doi.org/10.1006/aphy.2002.6254.
https://doi.org/10.1006/aphy.2002.6254

[5] Sanjeev Khanna, Madhu Sudan, Luca Trevisan, and David P Williamson. The approximability of constraint satisfaction problems. SIAM Journal on Computing, 30 (6): 1863–1920, 2001. URL https://doi.org/10.1137/S0097539799349948.
https://doi.org/10.1137/S0097539799349948

[6] Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42 (6): 1115–1145, 1995. URL https://doi.org/10.1145/227683.227684.
https://doi.org/10.1145/227683.227684

[7] Christina V Kraus and J Ignacio Cirac. Generalized Hartree–Fock 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.
https://doi.org/10.1088/1367-2630/12/11/113004

[8] Sergey Bravyi and David Gosset. Complexity of quantum impurity problems. Communications in Mathematical Physics, 356 (2): 451–500, 2017. URL https://doi.org/10.1007/s00220-017-2976-9.
https://doi.org/10.1007/s00220-017-2976-9

[9] Sergey Bravyi and Robert Koenig. Classical simulation of dissipative fermionic linear optics. Quant. Inf. Comp., 12 (11–12): 925–943, 2012. URL https://doi.org/10.48550/arXiv.1112.2184.
https://doi.org/10.48550/arXiv.1112.2184

[10] Fernando de Melo, Piotr Ćwikliński, 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.
https://doi.org/10.1088/1367-2630/15/1/013015

[11] Elliott H. Lieb. The classical limit of quantum spin systems. Communications in Mathematical Physics, 31 (4): 327 – 340, 1973. URL https://doi.org/10.1007/BF01646493.
https://doi.org/10.1007/BF01646493

[12] Sergey Bravyi, David Gosset, Robert König, 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.
https://doi.org/10.1063/1.5085428

[13] 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–720, 2009. URL https://doi.org/10.48550/arXiv.0705.1115.
https://doi.org/10.48550/arXiv.0705.1115

[14] Sevag Gharibian and Julia Kempe. Approximation algorithms for QMA-complete problems. SIAM Journal on Computing, 41 (4): 1028–1050, 2012. URL https://doi.org/10.1137/110842272.
https://doi.org/10.1137/110842272

[15] 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–880, New York, NY, USA, 2013. Association for Computing Machinery. ISBN 9781450320290. URL https://doi.org/10.1145/2488608.2488719.
https://doi.org/10.1145/2488608.2488719

[16] 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.
https://doi.org/10.22331/q-2017-04-25-6

[17] Thiago Bergamaschi. Improved product-state approximation algorithms for quantum local Hamiltonians, 2022. URL https://doi.org/10.48550/arXiv.2210.08680.
https://doi.org/10.48550/arXiv.2210.08680

[18] 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.
https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2019.31

[19] Noga Alon, Konstantin Makarychev, Yury Makarychev, and Assaf Naor. Quadratic forms on graphs. Inventiones mathematicae, 163 (3): 499–522, 2006. URL https://doi.org/10.1007/s00222-005-0465-9.
https://doi.org/10.1007/s00222-005-0465-9

[20] 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.
https://doi.org/10.48550/arXiv.2008.02303

[21] Antonio M. García-García, 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.
https://doi.org/10.1103/PhysRevD.103.106002

[22] Alan Frieze and Michał Karoński. Introduction to random graphs. Cambridge University Press, 2016. URL https://doi.org/10.1017/CBO9781316339831.
https://doi.org/10.1017/CBO9781316339831

[23] Dorit Aharonov, Itai Arad, and Thomas Vidick. The quantum PCP conjecture. ACM SIGACT News, 44: 47–79, 2013. URL https://doi.org/10.48550/arXiv.1309.7495.
https://doi.org/10.48550/arXiv.1309.7495

[24] 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.
https://doi.org/10.48550/arXiv.2110.15466

[25] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities using the entropy method. The Annals of Probability, 31 (3): 1583–1614, 2003. URL https://doi.org/10.1214/aop/1055425791.
https://doi.org/10.1214/aop/1055425791

[26] Ryota Tomioka and Taiji Suzuki. Spectral norm of random tensors. arXiv, 2014. URL https://doi.org/10.48550/arXiv.1407.1870.
https://doi.org/10.48550/arXiv.1407.1870

[27] 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.
https://doi.org/10.1103/PhysRevLett.127.250502

[28] B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. The Annals of Statistics, 28 (5): 1302 – 1338, 2000. URL https://doi.org/10.1214/aos/1015957395.
https://doi.org/10.1214/aos/1015957395

[29] Béla Bollobás. Modern Graph Theory. Graduate Texts in Mathematics 184. Springer-Verlag New York, 1998. URL https://doi.org/10.1007/978-1-4612-0619-4.
https://doi.org/10.1007/978-1-4612-0619-4

[30] Gabriel Andrew Dirac. Some theorems on abstract graphs. Proceedings of the London Mathematical Society, 3 (1): 69–81, 1952. URL https://doi.org/10.1112/plms/s3-2.1.69.
https://doi.org/10.1112/plms/s3-2.1.69

[31] 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.

[32] 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.
https://doi.org/10.1214/009117906000000421

[33] 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–1765, 1994. URL https://doi.org/10.48550/arXiv.math/9406214.
https://doi.org/10.48550/arXiv.math/9406214

[34] Radosław Adamczak and Paweł Wolff. Concentration inequalities for non-lipschitz functions with bounded derivatives of higher order. Probability Theory and Related Fields, 162 (3): 531–586, 2015. URL https://doi.org/10.1007/s00440-014-0579-3.
https://doi.org/10.1007/s00440-014-0579-3

Cited by

[1] M. A. Rajabpour, M. A. Seifi Mirjafarlou, and Reyhaneh Khasseh, "Explicit Pfaffian formula for amplitudes of fermionic Gaussian pure states in arbitrary Pauli bases", Physical Review B 111 23, 235102 (2025).

[2] Matthew Ding, Robbie King, Bobak T. Kiani, and Eric R. Anschuetz, "Optimizing Sparse SYK", Quantum 10, 2029 (2026).

[3] Daniel McNulty, Susane Calegari, and Michał Oszmaniec, "Optimal Fermionic Joint Measurements for Estimating Non-Commuting Majorana Observables", Quantum 9, 1914 (2025).

[4] 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, 232 (2025).

[5] Chi-Fang Chen, Alexander M. Dalzell, Mario Berta, Fernando G. S. L. Brandão, and Joel A. Tropp, "Sparse Random Hamiltonians Are Quantumly Easy", Physical Review X 14 1, 011014 (2024).

[6] Yaroslav Herasymenko, Anurag Anshu, Barbara M. Terhal, and Jonas Helsen, "Fermionic Hamiltonians without trivial low-energy states", Physical Review A 109 5, 052431 (2024).

[7] Babak Tarighi, Reyhaneh Khasseh, and M. A. Rajabpour, "Efficient representation of Gaussian fermionic pure states in noncomputational bases", Physical Review A 109 6, 062214 (2024).

[8] Gianluca Francica, "Quantum advantage in batteries for Sachdev-Ye-Kitaev interactions", Physical Review A 110 6, 062209 (2024).

[9] J. Eisert, "Lower bounds to variational problems with guarantees", Physical Review A 113 2, 022214 (2026).

[10] Kostas Vilkelis, Antonio L. R. Manesco, Juan Daniel Torres Luna, Sebastian Miles, Michael Wimmer, and Anton R. Akhmerov, "Fermionic quantum computation with Cooper pair splitters", SciPost Physics 16 5, 135 (2024).

[11] Eric R. Anschuetz, Chi-Fang Chen, Bobak T. Kiani, and Robbie King, "Strongly Interacting Fermions Are Nontrivial yet Nonglassy", Physical Review Letters 135 3, 030602 (2025).

[12] Akshar Ramkumar, Yiyi Cai, Yu Tong, and Jiaqing Jiang, "High-Temperature Fermionic Gibbs States Are Mixtures of Gaussian States", Physical Review Letters 137 2, 020601 (2026).

[13] Andrew M Projansky, Jason Necaise, and James D Whitfield, "Gaussianity and simulability of Cliffords and matchgates", Journal of Physics A: Mathematical and Theoretical 58 19, 195302 (2025).

[14] M. A. Rajabpour, MirAdel Seifi MirJafarlou, and Reyhaneh Khasseh, "Matrix Elements of Fermionic Gaussian Operators in Arbitrary Pauli Bases: A Pfaffian Formula", arXiv:2506.02809, (2025).

[15] Chi-Fang (Anthony) Chen, Andrew Lucas, and Chao Yin, "Speed limits and locality in many-body quantum dynamics", Reports on Progress in Physics 86 11, 116001 (2023).

[16] Joao Basso, Chi-Fang Chen, and Alexander M. Dalzell, "Optimizing random local Hamiltonians by dissipation", arXiv:2411.02578, (2024).

[17] Daniel Hothem, Ojas Parekh, and Kevin Thompson, "Improved Approximations for Extremal Eigenvalues of Sparse Hamiltonians", arXiv:2301.04627, (2023).

[18] Yaroslav Herasymenko, Anurag Anshu, Barbara Terhal, and Jonas Helsen, "Fermionic Hamiltonians without trivial low-energy states", arXiv:2307.13730, (2023).

[19] Kartik Anand, "Constructing Fermionic Hamiltonians with Non-Gaussianic low-energy states", arXiv:2502.15368, (2025).

[20] Reinis Irmejs and J. Ignacio Cirac, "Efficient Simulation of Sparse, Non-Local Fermion Models", arXiv:2512.15843, (2025).

[21] 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-07-17 08:56:16) and SAO/NASA ADS (last updated successfully 2026-07-16 15:03:20). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch ADS cited-by data during last attempt 2026-07-17 08:56:16: Cannot retrieve data from ADS due to rate limitations.

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.