Extremal eigenvalues of local Hamiltonians

Aram W. Harrow; Ashley Montanaro

doi:10.22331/q-2017-04-25-6

Extremal eigenvalues of local Hamiltonians

Aram W. Harrow¹ and Ashley Montanaro²

¹Center for Theoretical Physics, Department of Physics, MIT
²School of Mathematics, University of Bristol, UK

Published:	2017-04-25, volume 1, page 6
Eprint:	arXiv:1507.00739v4
Doi:	https://doi.org/10.22331/q-2017-04-25-6
Citation:	Quantum 1, 6 (2017).

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

Abstract

We apply classical algorithms for approximately solving constraint satisfaction problems to find bounds on extremal eigenvalues of local Hamiltonians. We consider spin Hamiltonians for which we have an upper bound on the number of terms in which each spin participates, and find extensive bounds for the operator norm and ground-state energy of such Hamiltonians under this constraint. In each case the bound is achieved by a product state which can be found efficiently using a classical algorithm.

► BibTeX data

@article{Harrow2017extremaleigenvalues,
  doi = {10.22331/q-2017-04-25-6},
  url = {https://doi.org/10.22331/q-2017-04-25-6},
  title = {Extremal eigenvalues of local {H}amiltonians},
  author = {Harrow, Aram W. and Montanaro, Ashley},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {1},
  pages = {6},
  month = apr,
  year = {2017}
}

► References

[1] N. Bansal, S. Bravyi, and B. Terhal. Classical approximation schemes for the ground-state energy of quantum and classical Ising spin hamiltonians on planar graphs. Quantum Inf. Comput., 9(8):0701–0720, 2009, arXiv:0705.1115.
arXiv:0705.1115

[2] B. Barak, A. Moitra, R. O'Donnell, P. Raghavendra, O. Regev, D. Steurer, L. Trevisan, A. Vijayaraghavan, D. Witmer, and J. Wright. Beating the random assignment on constraint satisfaction problems of bounded degree, 2015, arXiv:1505.03424.
arXiv:1505.03424

[3] F. G. S. L. Brandão and A. W. Harrow. Product-state approximations to quantum ground states. Communications in Mathematical Physics, 342(1):47–80, 2006. arXiv:1310.0017.
https://doi.org/10.1007/s00220-016-2575-1
arXiv:1310.0017

[4] F. G. S. L. Brandao and M. Cramer. Equivalence of statistical mechanical ensembles for non-critical quantum systems, 2015, arXiv:1502.03263.
arXiv:1502.03263

[5] P. Delsarte, J. Goethals, and J. Seidel. Spherical codes and designs. Geometriae Dedicata, 6(3):363–388, 1977.
https://doi.org/10.1007/BF03187604

[6] I. Dinur, E. Friedgut, G. Kindler, and R. O'Donnell. On the Fourier tails of bounded functions over the discrete cube. Israel Journal of Mathematics, 160:389–412, 2007.
https://doi.org/10.1007/s11856-007-0068-9

[7] E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm. Technical Report MIT-CTP/4610, MIT, 2014, arXiv:1411.4028.
arXiv:1411.4028

[8] E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem. Technical Report MIT-CTP/4628, MIT, 2014, arXiv:1412.6062.
arXiv:1412.6062

[9] M. H. Freedman and M. B. Hastings. Quantum systems on non-$k$-hyperfinite complexes: A generalization of classical statistical mechanics on expander graphs, 2013, arXiv:1301.1363.
arXiv:1301.1363

[10] M. Hartmann, G. Mahler, and O. Hess. Gaussian quantum fluctuations in interacting many particle systems. Letters in Mathematical Physics, 68(2):103–112, 2004, arXiv:math-ph/0312045.
https://doi.org/10.1023/B:MATH.0000043321.00896.86
arXiv:math-ph/0312045

[11] A. Montanaro. Some applications of hypercontractive inequalities in quantum information theory. Journal of Mathematical Physics, 53(12):122206, 2012, arXiv:1208.0161.
https://doi.org/10.1063/1.4769269
arXiv:1208.0161

[12] R. O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014.

[13] J. Renes, R. Blume-Kohout, A. J. Scott, and C. Caves. Symmetric informationally complete quantum measurements. J. Math. Phys., 45(6):2171–2180, 2003. quant-ph/0310075.
https://doi.org/10.1063/1.1737053
arXiv:quant-ph/0310075

[14] J. Håstad. On bounded occurrence constraint satisfaction. Inf. Proc. Lett., 74:1–6, 2000.
https://doi.org/10.1016/S0020-0190(00)00032-6

[15] J. Håstad. Improved bounds for bounded occurrence constraint satisfaction, 2015. http://www.csc.kth.se/ johanh/bounded2.pdf.
http://www.csc.kth.se/~johanh/bounded2.pdf

[16] J. Řeháček, B.-G. Englert, and D. Kaszlikowski. Minimal qubit tomography. Phys. Rev. A, 70:052321, 2004. quant-ph/0405084.
https://doi.org/10.1103/PhysRevA.70.052321
arXiv:quant-ph/0405084

Cited by

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

[2] Brian Swingle and Mike Winer, "Bosonic model of quantum holography", Physical Review B 109 9, 094206 (2024).

[3] Elias X. Huber, Benjamin Y. L. Tan, Paul R. Griffin, and Dimitris G. Angelakis, "Exponential qubit reduction in optimization for financial transaction settlement", EPJ Quantum Technology 11 1, 52 (2024).

[4] Anurag Anshu, David Gosset, Karen J. Morenz Korol, and Mehdi Soleimanifar, "Improved Approximation Algorithms for Bounded-Degree Local Hamiltonians", Physical Review Letters 127 25, 250502 (2021).

[5] Adam Bene Watts, Anirban Chowdhury, Aidan Epperly, J. William Helton, and Igor Klep, "Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap Operators", Quantum 8, 1352 (2024).

[6] Ayaka Usui, Anna Sanpera, and María García Díaz, "Simplifying the simulation of local Hamiltonian dynamics", Physical Review Research 6 2, 023243 (2024).

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

[8] Bryce Fuller, Charles Hadfield, Jennifer R. Glick, Takashi Imamichi, Toshinari Itoko, Richard J. Thompson, Yang Jiao, Marna M. Kagele, Adriana W. Blom-Schieber, Rudy Raymond, and Antonio Mezzacapo, "Approximate Solutions of Combinatorial Problems via Quantum Relaxations", IEEE Transactions on Quantum Engineering 5, 1 (2024).

[9] Hsin-Yuan Huang, Sitan Chen, and John Preskill, "Learning to Predict Arbitrary Quantum Processes", PRX Quantum 4 4, 040337 (2023).

[10] Naphan Benchasattabuse, Andreas Bärtschi, Luis Pedro García-Pintos, John Golden, Nathan Lemons, and Stephan Eidenbenz, "Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios", Physical Review A 111 6, 062411 (2025).

[11] Yaroslav Herasymenko, Maarten Stroeks, Jonas Helsen, and Barbara Terhal, "Optimizing sparse fermionic Hamiltonians", Quantum 7, 1081 (2023).

[12] Lauren Preston and Shivashankar, Lecture Notes in Computer Science 14077, 56 (2023) ISBN:978-3-031-36029-9.

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

[14] Roy Araiza, Yidong Chen, Marius Junge, and Peixue Wu, "Resource-Dependent Complexity of Quantum Channels", Quantum 10, 1960 (2026).

[15] A. Roggero and A. Baroni, "Short-depth circuits for efficient expectation-value estimation", Physical Review A 101 2, 022328 (2020).

[16] Cedric Yen-Yu Lin and Yechao Zhu, "Performance of QAOA on Typical Instances of Constraint Satisfaction Problems with Bounded Degree", arXiv:1601.01744, (2016).

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

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

[19] Thiago Bergamaschi, "Improved Product-state Approximation Algorithms for Quantum Local Hamiltonians", arXiv:2210.08680, (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2026-07-15 07:54:29) and SAO/NASA ADS (last updated successfully 2026-07-14 16:28:36). 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-15 07:54:29: 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.