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 $qgt4$, 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.
[embedded content]
► 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, Andrew Lucas, and Chao Yin, “Speed limits and locality in many-body quantum dynamics”, arXiv:2303.07386, (2023).
[2] Daniel Hothem, Ojas Parekh, and Kevin Thompson, “Improved Approximations for Extremal Eigenvalues of Sparse Hamiltonians”, arXiv:2301.04627, (2023).
[3] J. Eisert, “A note on lower bounds to variational problems with guarantees”, arXiv:2301.06142, (2023).
[4] Yaroslav Herasymenko, Anurag Anshu, Barbara Terhal, and Jonas Helsen, “Fermionic Hamiltonians without trivial low-energy states”, arXiv:2307.13730, (2023).
The above citations are from SAO/NASA ADS (last updated successfully 2023-08-10 12:44:57). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch Crossref cited-by data during last attempt 2023-08-10 12:44:56: Could not fetch cited-by data for 10.22331/q-2023-08-10-1081 from Crossref. This is normal if the DOI was registered recently.
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.
- SEO Powered Content & PR Distribution. Get Amplified Today.
- PlatoData.Network Vertical Generative Ai. Empower Yourself. Access Here.
- PlatoAiStream. Web3 Intelligence. Knowledge Amplified. Access Here.
- PlatoESG. Automotive / EVs, Carbon, CleanTech, Energy, Environment, Solar, Waste Management. Access Here.
- BlockOffsets. Modernizing Environmental Offset Ownership. Access Here.
- Source: https://quantum-journal.org/papers/q-2023-08-10-1081/
