Optimizing sparse fermionic Hamiltonians

Yaroslav Herasymenko1,2, Maarten Stroeks2,3, Jonas Helsen1, and Barbara Terhal2,3

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

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

► BibTeX data

► 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] 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).

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

[3] 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).

[4] 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).

[5] Babak Tarighi, Reyhaneh Khasseh, and M. A. Rajabpour, "Efficient Representation of Gaussian Fermionic Pure States in Non-Computational Bases", arXiv:2403.03289, (2024).

[6] 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).

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

[8] J. Eisert, "A note on lower bounds to variational problems with guarantees", arXiv:2301.06142, (2023).

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

The above citations are from Crossref's cited-by service (last updated successfully 2024-06-22 09:24:33) and SAO/NASA ADS (last updated successfully 2024-06-22 09:24:34). The list may be incomplete as not all publishers provide suitable and complete citation data.