Extremal eigenvalues of local Hamiltonians

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.

5 pages; v4: uses standard journal style

References in corpus (3)

• A Quantum Approximate Optimization Algorithm
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Equivalence of Statistical Mechanical Ensembles for Non-Critical Quantum Systems

Cited by in corpus (13)

• Approximation algorithms for quantum many-body problems
• Performance of QAOA on Typical Instances of Constraint Satisfaction Problems with Bounded Degree
• Short-depth circuits for efficient expectation value estimation
• Optimizing sparse fermionic Hamiltonians
• Improved approximation algorithms for bounded-degree local Hamiltonians
• Beyond product state approximations for a quantum analogue of Max Cut
• Sparse random Hamiltonians are quantumly easy
• Exponential Qubit Reduction in Optimization for Financial Transaction Settlement
• Bounds on the ground state energy of quantum $p$-spin Hamiltonians
• Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap Operators
• Simplifying the simulation of local Hamiltonian dynamics
• Resource-Dependent Complexity of Quantum Channels
• Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios