Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Leibniz international proceedings in informatics

An Approximation Algorithm for the MAX-2-Local Hamiltonian Problem

Hallgren, Sean, Lee, Eunou, Ojas Parekh

Published Jan 1, 2020• 7 citations
Publisher

Abstract

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.

DOI
10.4230/lipics.approx/random.2020.59

Related papers

Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian Problems.

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.

arXiv:2012.12347•Leibniz international proceedings in informatics•Aug 1, 2021•17 citations

Approximation Algorithms for QMA-Complete Problems

Sevag Gharibian, Julia Kempe

Approximation algorithms for classical constraint satisfaction problems are one of the main research areas in theoretical computer science. Here we define a natural approximation version of the QMA-complete local Hamiltonian problem and initiate its study. We present two main results. The first shows that a non-trivial approximation ratio can be obtained in the class NP using product states. The second result (which builds on the first one), gives a polynomial time (classical) algorithm providing a similar approximation ratio for dense instances of the problem. The latter result is based on an adaptation of the "exhaustive sampling method" by Arora et al. [J. Comp. Sys. Sci. 58, p.193 (1999)] to the quantum setting, and might be of independent interest.

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2011•11 citations

Approximation Algorithms for QMA-Complete Problems

Sevag Gharibian, Julia Kempe

Approximation algorithms for classical constraint satisfaction problems are one of the main research areas in theoretical computer science. Here we define a natural approximation version of the QMA-complete local Hamiltonian problem (where QMA stands for Quantum Merlin Arthur) and initiate its study. We present two main results. The first shows that a nontrivial approximation ratio can be obtained in the class NP using product states. The second result (which builds on the first one) gives a polynomial time (classical) algorithm providing a similar approximation ratio for dense instances of the problem. The latter result is based on an adaptation of the “exhaustive sampling method” by Arora, Karger, and Karpinski [J. Comput. System Sci., 58 (1999), p. 193] to the quantum setting and might be of independent interest.

arXiv:1101.3884•SIAM Journal on Computing•Jan 1, 2012•48 citations

Product-state approximations to quantum ground states

Fernando G. S. L. Brandão, Aram W. Harrow

The local Hamiltonian problem consists of estimating the ground-state energy (given by the minimum eigenvalue) of a local quantum Hamiltonian. It can be considered as a quantum generalization of constraint satisfaction problems (CSPs) and has a key role in quantum complexity theory, being the first and most natural QMA-complete problem known. An interesting regime for the local Hamiltonian problem is that of extensive error, where one is interested in estimating the mean ground-state energy to constant accuracy. The problem is NP-hard by the PCP theorem, but whether it is QMA-hard is an important open question in quantum complexity theory. A positive solution would represent a quantum analogue of the PCP theorem. A key feature that distinguishes quantum Hamiltonians from classical CSPs is that the solutions may involve complicated entangled states. In this paper, we demonstrate several large classes of Hamiltonians for which product (i.e. unentangled) states can approximate the ground state energy to within a small extensive error.

arXiv:1310.0017•ACM Symposium on Theory of Computing (STOC)•May 28, 2013•62 citations

An Optimal Product-State Approximation for 2-Local Quantum Hamiltonians with Positive Terms

Ojas Parekh, Thompson, Kevin

We resolve the approximability of the maximum energy of the Quantum Max Cut (QMC) problem using product states. A classical 0.498-approximation, using a basic semidefinite programming relaxation, is known for QMC, paralleling the celebrated 0.878-approximation for classical Max Cut. For Max Cut, improving the 0.878-approximation is Unique-Games-hard (UG-hard), and one might expect that improving the 0.498-approximation is UG-hard for QMC. In contrast, we give a classical 1/2-approximation for QMC that is unconditionally optimal, since simple examples exhibit a gap of 1/2 between the energies of an optimal product state and general quantum state. Our result relies on a new nonlinear monogamy of entanglement inequality on a triangle that is derived from the second level of the quantum Lasserre hierarchy. This inequality also applies to the quantum Heisenberg model, and our results generalize to instances of Max 2-Local Hamiltonian where each term is positive and has no 1-local parts. Finally, we give further evidence that product states are essential for approximations of 2-Local Hamiltonian.

arXiv:2206.08342•Jun 16, 2022•50 citations

Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut

Sevag Gharibian, Ojas Parekh

Approximation algorithms for constraint satisfaction problems (CSPs) are a central direction of study in theoretical computer science. In this work, we study classical product state approximation algorithms for a physically motivated quantum generalization of Max-Cut, known as the quantum Heisenberg model. This model is notoriously difficult to solve exactly, even on bipartite graphs, in stark contrast to the classical setting of Max-Cut. Here we show, for any interaction graph, how to classically and efficiently obtain approximation ratios 0.649 (anti-feromagnetic XY model) and 0.498 (anti-ferromagnetic Heisenberg XYZ model). These are almost optimal; we show that the best possible ratios achievable by a product state for these models is 2/3 and 1/2, respectively.

arXiv:1909.08846•Leibniz international proceedings in informatics•Jan 1, 2019•50 citations
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.
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.
Approximation algorithms for classical constraint satisfaction problems are one of the main research areas in theoretical computer science. Here we define a natural approximation version of the QMA-complete local Hamiltonian problem and initiate its study. We present two main results. The first shows that a non-trivial approximation ratio can be obtained in the class NP using product states. The second result (which builds on the first one), gives a polynomial time (classical) algorithm providing a similar approximation ratio for dense instances of the problem. The latter result is based on an adaptation of the "exhaustive sampling method" by Arora et al. [J. Comp. Sys. Sci. 58, p.193 (1999)] to the quantum setting, and might be of independent interest.
Approximation algorithms for classical constraint satisfaction problems are one of the main research areas in theoretical computer science. Here we define a natural approximation version of the QMA-complete local Hamiltonian problem (where QMA stands for Quantum Merlin Arthur) and initiate its study. We present two main results. The first shows that a nontrivial approximation ratio can be obtained in the class NP using product states. The second result (which builds on the first one) gives a polynomial time (classical) algorithm providing a similar approximation ratio for dense instances of the problem. The latter result is based on an adaptation of the “exhaustive sampling method” by Arora, Karger, and Karpinski [J. Comput. System Sci., 58 (1999), p. 193] to the quantum setting and might be of independent interest.
The local Hamiltonian problem consists of estimating the ground-state energy (given by the minimum eigenvalue) of a local quantum Hamiltonian. It can be considered as a quantum generalization of constraint satisfaction problems (CSPs) and has a key role in quantum complexity theory, being the first and most natural QMA-complete problem known. An interesting regime for the local Hamiltonian problem is that of extensive error, where one is interested in estimating the mean ground-state energy to constant accuracy. The problem is NP-hard by the PCP theorem, but whether it is QMA-hard is an important open question in quantum complexity theory. A positive solution would represent a quantum analogue of the PCP theorem. A key feature that distinguishes quantum Hamiltonians from classical CSPs is that the solutions may involve complicated entangled states. In this paper, we demonstrate several large classes of Hamiltonians for which product (i.e. unentangled) states can approximate the ground state energy to within a small extensive error.
We resolve the approximability of the maximum energy of the Quantum Max Cut (QMC) problem using product states. A classical 0.498-approximation, using a basic semidefinite programming relaxation, is known for QMC, paralleling the celebrated 0.878-approximation for classical Max Cut. For Max Cut, improving the 0.878-approximation is Unique-Games-hard (UG-hard), and one might expect that improving the 0.498-approximation is UG-hard for QMC. In contrast, we give a classical 1/2-approximation for QMC that is unconditionally optimal, since simple examples exhibit a gap of 1/2 between the energies of an optimal product state and general quantum state. Our result relies on a new nonlinear monogamy of entanglement inequality on a triangle that is derived from the second level of the quantum Lasserre hierarchy. This inequality also applies to the quantum Heisenberg model, and our results generalize to instances of Max 2-Local Hamiltonian where each term is positive and has no 1-local parts. Finally, we give further evidence that product states are essential for approximations of 2-Local Hamiltonian.
Approximation algorithms for constraint satisfaction problems (CSPs) are a central direction of study in theoretical computer science. In this work, we study classical product state approximation algorithms for a physically motivated quantum generalization of Max-Cut, known as the quantum Heisenberg model. This model is notoriously difficult to solve exactly, even on bipartite graphs, in stark contrast to the classical setting of Max-Cut. Here we show, for any interaction graph, how to classically and efficiently obtain approximation ratios 0.649 (anti-feromagnetic XY model) and 0.498 (anti-ferromagnetic Heisenberg XYZ model). These are almost optimal; we show that the best possible ratios achievable by a product state for these models is 2/3 and 1/2, respectively.