An approximation algorithm for the MAX-2-Local Hamiltonian problem.

Eunwoo Lee

Hallgren, Sean, Lee, Eunou, Ojas Parekh

We present a classical approximation algorithm for the MAX-2-Local Hamiltonian problem. This is a maximization version of the QMA-complete 2-Local Hamiltonian problem in quantum computing, with the additional assumption that each local term is positive semidefinite. The MAX-2-Local Hamiltonian problem generalizes NP-hard constraint satisfaction problems, and our results may be viewed as generalizations of approximation approaches for the MAX-2-CSP problem. We work in the product state space and extend the framework of Goemans and Williamson for approximating MAX-2-CSPs. The key difference is that in the product state setting, a solution consists of a set of normalized 3-dimensional vectors rather than boolean numbers, and we leverage approximation results for rank-constrained Grothendieck inequalities. For MAX-2-Local Hamiltonian we achieve an approximation ratio of 0.328. This is the first example of an approximation algorithm beating the random quantum assignment ratio of 0.25 by a constant factor.

Ojas Parekh, Kevin Thompson

The quantum k-Local Hamiltonian problem is a natural generalization of classical constraint satisfaction problems (k-CSP) and is complete for QMA, a quantum analog of NP. Although the complexity of k-Local Hamiltonian problems has been well studied, only a handful of approximation results are known. For Max 2-Local Hamiltonian where each term is a rank 3 projector, a natural quantum generalization of classical Max 2-SAT, the best known approximation algorithm was the trivial random assignment, yielding a 0.75-approximation. We present the first approximation algorithm beating this bound, a classical polynomial-time 0.764-approximation. For strictly quadratic instances, which are maximally entangled instances, we provide a 0.801 approximation algorithm, and numerically demonstrate that our algorithm is likely a 0.821-approximation. We conjecture these are the hardest instances to approximate. We also give improved approximations for quantum generalizations of other related classical 2-CSPs. Finally, we exploit quantum connections to a generalization of the Grothendieck problem to obtain a classical constant-factor approximation for the physically relevant special case of strictly quadratic traceless 2-Local Hamiltonians on bipartite interaction graphs, where a inverse logarithmic approximation was the best previously known (for general interaction graphs). Our work employs recently developed techniques for analyzing classical approximations of CSPs and is intended to be accessible to both quantum information scientists and classical computer scientists.

Julia Kempe, Alexei Kitaev, Oded Regev

S. Narayanaswami

Sergey Bravyi, David Gosset, Robert König +1 more

We discuss classical algorithms for approximating the largest eigenvalue of quantum spin and fermionic Hamiltonians based on semidefinite programming relaxation methods. First, we consider traceless 2-local Hamiltonians H describing a system of n qubits. We give an efficient algorithm that outputs a separable state whose energy is at least λmax/O(log n), where λmax is the maximum eigenvalue of H. We also give a simplified proof of a theorem due to Lieb that establishes the existence of a separable state with energy at least λmax/9. Second, we consider a system of n fermionic modes and traceless Hamiltonians composed of quadratic and quartic fermionic operators. We give an efficient algorithm that outputs a fermionic Gaussian state whose energy is at least λmax/O(n log n). Finally, we show that Gaussian states can vastly outperform Slater determinant states commonly used in the Hartree-Fock method. We give a simple family of Hamiltonians for which Gaussian states and Slater determinants approximate λmax within a fraction 1 − O(n−1) and O(n−1), respectively.