# Extremal eigenvalues of local Hamiltonians

Aram W. Harrow1 and Ashley Montanaro2

1Center for Theoretical Physics, Department of Physics, MIT
2School of Mathematics, University of Bristol, UK

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.

### ► 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