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

arXiv:2411.04120

Second order cone relaxations for quantum Max Cut

Felix Huber, Kevin Thompson, Ojas Parekh, Sevag Gharibian

Published Nov 6, 2024• 0 citations
arXivHTMLPDF

Abstract

Quantum Max Cut (QMC), also known as the quantum anti-ferromagnetic Heisenberg model, is a QMA-complete problem relevant to quantum many-body physics and computer science. Semidefinite programming relaxations have been fruitful in designing theoretical approximation algorithms for QMC, but are computationally expensive for systems beyond tens of qubits. We give a second order cone relaxation for QMC, which optimizes over the set of mutually consistent three-qubit reduced density matrices. In combination with Pauli level-$1$ of the quantum Lasserre hierarchy, the relaxation achieves an approximation ratio of $0.526$ to the ground state energy. Our relaxation is solvable on systems with hundreds of qubits and paves the way to computationally efficient lower and upper bounds on the ground state energy of large-scale quantum spin systems.

DOI
10.48550/arxiv.2411.04120

Related papers

A 0.651-approximation to quantum Max Cut via Rydberg atoms

Tomás Crosta, Matthieu Saubanere, Felix Huber

Quantum Max Cut, also known as the anti-ferromagnetic Heisenberg Hamiltonian, is a QMA-complete problem which serves as a benchmark for approximation algorithms in quantum physics. Here we develop a hybrid approximation algorithm to quantum Max Cut, which uses the natural quantum dynamics of Rydberg atom systems in combination with semidefinite programming and randomized rounding. It achieves a conditional approximation ratio of $0.651$, compared to the best-known ratio of $0.614$ that relies on semidefinite programming alone. The algorithm is robust in the sense that the advantage persists even if the annealing procedure of the Rydberg atom system obtains a state whose energy is only $89\%$ of its true ground state energy. Our approach opens a new route for hybrid quantum-classical algorithms that combine quantum with classical optimization methods.

quant-pharXiv:2606.27224•Jun 26, 2026•0 citations

Application of the Level-2 Quantum Lasserre Hierarchy in Quantum Approximation Algorithms.

Ojas Parekh, Kevin Thompson

The Lasserre Hierarchy is a set of semidefinite programs which yield increasingly tight bounds on optimal solutions to many NP-hard optimization problems. The hierarchy is parameterized by levels, with a higher level corresponding to a more accurate relaxation. High level programs have proven to be invaluable components of approximation algorithms for many NP-hard optimization problems. There is a natural analogous quantum hierarchy, which is also parameterized by level and provides a relaxation of many (QMA-hard) quantum problems of interest. In contrast to the classical case, however, there is only one approximation algorithm which makes use of higher levels of the hierarchy. Here we provide the first ever use of the level-$2$ hierarchy in an approximation algorithm for a particular QMA-complete problem, so-called Quantum Max Cut. We obtain modest improvements on state-of-the-art approximation factors for this problem, as well as demonstrate that the level-$2$ hierarchy satisfies many physically-motivated constraints that the level-$1$ does not satisfy. Indeed, this observation is at the heart of our analysis and indicates that higher levels of the quantum Lasserre Hierarchy may be very useful tools in the design of approximation algorithms for QMA-complete problems.

•Jun 1, 2021•4 citations

Application of the Level-222 Quantum Lasserre Hierarchy in Quantum Approximation Algorithms

Ojas Parekh, Kevin Thompson

The Lasserre Hierarchy is a set of semidefinite programs which yield increasingly tight bounds on optimal solutions to many NP-hard optimization problems. The hierarchy is parameterized by levels, with a higher level corresponding to a more accurate relaxation. High level programs have proven to be invaluable components of approximation algorithms for many NP-hard optimization problems. There is a natural analogous quantum hierarchy, which is also parameterized by level and provides a relaxation of many (QMA-hard) quantum problems of interest. In contrast to the classical case, however, there is only one approximation algorithm which makes use of higher levels of the hierarchy. Here we provide the first ever use of the level-$2$ hierarchy in an approximation algorithm for a particular QMA-complete problem, so-called Quantum Max Cut. We obtain modest improvements on state-of-the-art approximation factors for this problem, as well as demonstrate that the level-$2$ hierarchy satisfies many physically-motivated constraints that the level-$1$ does not satisfy. Indeed, this observation is at the heart of our analysis and indicates that higher levels of the quantum Lasserre Hierarchy may be very useful tools in the design of approximation algorithms for QMA-complete problems.

arXiv:2105.05698•Leibniz international proceedings in informatics•Jan 1, 2021•6 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•6 citations

Lovász theta and Shearer lower bounds on Quantum Max Cut

Felix Huber

Quantum Max Cut is a problem relevant to computer science and many-body quantum physics due to its links to classical Max Cut and the anti-ferromagnetic Heisenberg Hamiltonian. We prove a lower bound to quantum Max Cut of a graph in terms of the Lovász theta function of its complement. For a graph with $m$ edges, $\text{qmc}(G) \geq \tfrac{m}{4}\big( 1 + \tfrac{8}{3π}\tfrac{1}{\vartheta(\bar{G}) -1} \big)$, with the bound achieved by a product state. The proof can be strenghtened by the vector chromatic number and extends a result by Balla, Janzer, and Sudakov on classical Max Cut. A relaxed bound follows from $\vartheta(\bar{G}) - 1 \leq Δ$ for graphs with maximum degree $Δ$, making it interesting for practically relevant quantum many-body systems. We also extend results by Carlson et al. and Shearer and show that $\text{qmc}(G) \geq \frac{m}{4} + \frac{2m^{3/4}}{3 π}$ for all triangle-free graphs with $m$ edges.

quant-pharXiv:2512.20326•Dec 24, 2025•0 citations

The classical limit of Quantum Max-Cut

Vir B. Bulchandani, Stephen Piddock

It is well-known in physics that the limit of large quantum spin $S$ should be understood as a semiclassical limit. This raises the question of whether such emergent classicality facilitates the approximation of computationally hard quantum optimization problems, such as the local Hamiltonian problem. We demonstrate this explicitly for spin-$S$ generalizations of Quantum Max-Cut ($\mathrm{QMaxCut}_S$), equivalent to the problem of finding the ground state energy of an arbitrary spin-$S$ quantum Heisenberg antiferromagnet ($\mathrm{QHA}_S$). We prove that approximating the value of $\mathrm{QHA}_S$ to inverse polynomial accuracy is QMA-complete for all $S$, extending previous results for $S=1/2$. We also present two distinct families of classical approximation algorithms for $\mathrm{QMaxCut}_S$ based on rounding the output of a semidefinite program to a product of Bloch coherent states. The approximation ratios for both our proposed algorithms strictly increase with $S$ and converge to the Briët-Oliveira-Vallentin approximation ratio $α_{\mathrm{BOV}} \approx 0.956$ from below as $S \to \infty$.

arXiv:2401.12968•Jan 23, 2024•0 citations
Quantum Max Cut (QMC), also known as the quantum anti-ferromagnetic Heisenberg model, is a QMA-complete problem relevant to quantum many-body physics and computer science. Semidefinite programming relaxations have been fruitful in designing theoretical approximation algorithms for QMC, but are computationally expensive for systems beyond tens of qubits. We give a second order cone relaxation for QMC, which optimizes over the set of mutually consistent three-qubit reduced density matrices. In combination with Pauli level-111 of the quantum Lasserre hierarchy, the relaxation achieves an approximation ratio of 0.5260.5260.526 to the ground state energy. Our relaxation is solvable on systems with hundreds of qubits and paves the way to computationally efficient lower and upper bounds on the ground state energy of large-scale quantum spin systems.
Quantum Max Cut, also known as the anti-ferromagnetic Heisenberg Hamiltonian, is a QMA-complete problem which serves as a benchmark for approximation algorithms in quantum physics. Here we develop a hybrid approximation algorithm to quantum Max Cut, which uses the natural quantum dynamics of Rydberg atom systems in combination with semidefinite programming and randomized rounding. It achieves a conditional approximation ratio of 0.6510.6510.651, compared to the best-known ratio of 0.6140.6140.614 that relies on semidefinite programming alone. The algorithm is robust in the sense that the advantage persists even if the annealing procedure of the Rydberg atom system obtains a state whose energy is only 89%89\%89% of its true ground state energy. Our approach opens a new route for hybrid quantum-classical algorithms that combine quantum with classical optimization methods.
The Lasserre Hierarchy is a set of semidefinite programs which yield increasingly tight bounds on optimal solutions to many NP-hard optimization problems. The hierarchy is parameterized by levels, with a higher level corresponding to a more accurate relaxation. High level programs have proven to be invaluable components of approximation algorithms for many NP-hard optimization problems. There is a natural analogous quantum hierarchy, which is also parameterized by level and provides a relaxation of many (QMA-hard) quantum problems of interest. In contrast to the classical case, however, there is only one approximation algorithm which makes use of higher levels of the hierarchy. Here we provide the first ever use of the level-222 hierarchy in an approximation algorithm for a particular QMA-complete problem, so-called Quantum Max Cut. We obtain modest improvements on state-of-the-art approximation factors for this problem, as well as demonstrate that the level-222 hierarchy satisfies many physically-motivated constraints that the level-111 does not satisfy. Indeed, this observation is at the heart of our analysis and indicates that higher levels of the quantum Lasserre Hierarchy may be very useful tools in the design of approximation algorithms for QMA-complete problems.
The Lasserre Hierarchy is a set of semidefinite programs which yield increasingly tight bounds on optimal solutions to many NP-hard optimization problems. The hierarchy is parameterized by levels, with a higher level corresponding to a more accurate relaxation. High level programs have proven to be invaluable components of approximation algorithms for many NP-hard optimization problems. There is a natural analogous quantum hierarchy, which is also parameterized by level and provides a relaxation of many (QMA-hard) quantum problems of interest. In contrast to the classical case, however, there is only one approximation algorithm which makes use of higher levels of the hierarchy. Here we provide the first ever use of the level-222 hierarchy in an approximation algorithm for a particular QMA-complete problem, so-called Quantum Max Cut. We obtain modest improvements on state-of-the-art approximation factors for this problem, as well as demonstrate that the level-222 hierarchy satisfies many physically-motivated constraints that the level-111 does not satisfy. Indeed, this observation is at the heart of our analysis and indicates that higher levels of the quantum Lasserre Hierarchy may be very useful tools in the design of approximation algorithms for QMA-complete problems.
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.
Quantum Max Cut is a problem relevant to computer science and many-body quantum physics due to its links to classical Max Cut and the anti-ferromagnetic Heisenberg Hamiltonian. We prove a lower bound to quantum Max Cut of a graph in terms of the Lovász theta function of its complement. For a graph with mmm edges, qmc(G)≥m4(1+83π1ϑ(Gˉ)−1)\text{qmc}(G) \geq \tfrac{m}{4}\big( 1 + \tfrac{8}{3π}\tfrac{1}{\vartheta(\bar{G}) -1} \big)qmc(G)≥4m​(1+3π8​ϑ(Gˉ)−11​), with the bound achieved by a product state. The proof can be strenghtened by the vector chromatic number and extends a result by Balla, Janzer, and Sudakov on classical Max Cut. A relaxed bound follows from ϑ(Gˉ)−1≤Δ\vartheta(\bar{G}) - 1 \leq Δϑ(Gˉ)−1≤Δ for graphs with maximum degree ΔΔΔ, making it interesting for practically relevant quantum many-body systems. We also extend results by Carlson et al. and Shearer and show that qmc(G)≥m4+2m3/43π\text{qmc}(G) \geq \frac{m}{4} + \frac{2m^{3/4}}{3 π}qmc(G)≥4m​+3π2m3/4​ for all triangle-free graphs with mmm edges.
It is well-known in physics that the limit of large quantum spin SSS should be understood as a semiclassical limit. This raises the question of whether such emergent classicality facilitates the approximation of computationally hard quantum optimization problems, such as the local Hamiltonian problem. We demonstrate this explicitly for spin-SSS generalizations of Quantum Max-Cut (QMaxCutS\mathrm{QMaxCut}_SQMaxCutS​), equivalent to the problem of finding the ground state energy of an arbitrary spin-SSS quantum Heisenberg antiferromagnet (QHAS\mathrm{QHA}_SQHAS​). We prove that approximating the value of QHAS\mathrm{QHA}_SQHAS​ to inverse polynomial accuracy is QMA-complete for all SSS, extending previous results for S=1/2S=1/2S=1/2. We also present two distinct families of classical approximation algorithms for QMaxCutS\mathrm{QMaxCut}_SQMaxCutS​ based on rounding the output of a semidefinite program to a product of Bloch coherent states. The approximation ratios for both our proposed algorithms strictly increase with SSS and converge to the Briët-Oliveira-Vallentin approximation ratio αBOV≈0.956α_{\mathrm{BOV}} \approx 0.956αBOV​≈0.956 from below as S→∞S \to \inftyS→∞.