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:2512.20326

A Lovász theta lower bound on Quantum Max Cut

Felix Huber

quant-phmath.COSubmitted Dec 23, 2025• Announced Dec 24, 2025• 0 citations
v1 · Dec 23, 2025v2 · Jun 24, 2026
arXivHTMLPDF

Abstract

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 extends a result by Balla, Janzer, and Sudakov on classical Max Cut and is also inspired by the randomized rounding method of Gharibian and Parekh. The bound outperforms the classical bound when applied to quantum Max Cut.

Comments
5 pages, comments welcome

Related papers

Second order cone relaxations for quantum Max Cut

Felix Huber, Kevin Thompson, Ojas Parekh +1 more

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.

arXiv:2411.04120•Nov 6, 2024•0 citations

An improved Quantum Max Cut approximation via matching

Eunou Lee, Parekh, Ojas

Finding a high (or low) energy state of a given quantum Hamiltonian is a potential area to gain a provable and practical quantum advantage. A line of recent studies focuses on Quantum Max Cut, where one is asked to find a high energy state of a given antiferromagnetic Heisenberg Hamiltonian. In this work, we present a classical approximation algorithm for Quantum Max Cut that achieves an approximation ratio of 0.595, outperforming the previous best algorithms of Lee [Lee, 2022] (0.562, generic input graph) and King [King, 2023] (0.582, triangle-free input graph). The algorithm is based on finding the maximum weighted matching of an input graph and outputs a product of at most 2-qubit states, which is simpler than the fully entangled output states of the previous best algorithms.

arXiv:2401.03616•Jan 8, 2024•0 citations

Quantum Max Cut for complete tripartite graphs

Tea Štrekelj

The Quantum Max-$d$-Cut ($d$-QMC) problem is a special instance of a $2$-local Hamiltonian problem, representing the quantum analog of the classical Max-$d$-Cut problem. The $d$-QMC problem seeks the largest eigenvalue of a Hamiltonian defined on a graph with $n$ vertices, where edges correspond to swap operators acting on $(\mathbb{C}^d)^{\otimes n}$. In recent years, progress has been made by investigating the algebraic structure of the $d$-QMC Hamiltonian. Building on this approach, this article solves the $d$-QMC problem for complete tripartite graphs for small local dimensions, $d \le 3$.

quant-pharXiv:2512.03740•Dec 4, 2025•0 citations

Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut

Ainesh Bakshi, Arpon Basu, Pravesh Kothari +1 more

We prove that the maximum eigenvalue of the (both signed and unsigned) Laplacian of level $k$ Kikuchi graph of any graph $G$ with $m$ edges is at most $m+k$. This confirms four recent conjectures of Apte, Parekh, and Sud. As applications, we obtain that tensor products of one and two qubit product states achieve an approximation ratio of $5/8$ for Quantum Max Cut and $5/7$ for the XY Hamiltonian. Moreover, combining our bounds with the algorithms analyzed by Apte, Parekh, and Sud, yields efficient algorithms achieving an approximation ratio of $0.614$ for Quantum Max Cut and $0.674$ for the XY Hamiltonian. Finally, we also make modest progress on Brouwer's conjecture and improve Lew's bound on the sum of the top-$k$ eigenvalues of a Graph Laplacian.

quant-pharXiv:2605.14994•May 15, 2026•0 citations

An Improved Quantum Max Cut Approximation via Maximum Matching

Eunou Lee, Ojas Parekh

Finding a high (or low) energy state of a given quantum Hamiltonian is a potential area to gain a provable and practical quantum advantage. A line of recent studies focuses on Quantum Max Cut, where one is asked to find a high energy state of a given antiferromagnetic Heisenberg Hamiltonian. In this work, we present a classical approximation algorithm for Quantum Max Cut that achieves an approximation ratio of 0.595, outperforming the previous best algorithms of Lee [Eunou Lee, 2022] (0.562, generic input graph) and King [King, 2023] (0.582, triangle-free input graph). The algorithm is based on finding the maximum weighted matching of an input graph and outputs a product of at most 2-qubit states, which is simpler than the fully entangled output states of the previous best algorithms.

Leibniz international proceedings in informatics•Jan 1, 2024•0 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•16 citations
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 extends a result by Balla, Janzer, and Sudakov on classical Max Cut and is also inspired by the randomized rounding method of Gharibian and Parekh. The bound outperforms the classical bound when applied to quantum Max Cut.
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.
Finding a high (or low) energy state of a given quantum Hamiltonian is a potential area to gain a provable and practical quantum advantage. A line of recent studies focuses on Quantum Max Cut, where one is asked to find a high energy state of a given antiferromagnetic Heisenberg Hamiltonian. In this work, we present a classical approximation algorithm for Quantum Max Cut that achieves an approximation ratio of 0.595, outperforming the previous best algorithms of Lee [Lee, 2022] (0.562, generic input graph) and King [King, 2023] (0.582, triangle-free input graph). The algorithm is based on finding the maximum weighted matching of an input graph and outputs a product of at most 2-qubit states, which is simpler than the fully entangled output states of the previous best algorithms.
The Quantum Max-ddd-Cut (ddd-QMC) problem is a special instance of a 222-local Hamiltonian problem, representing the quantum analog of the classical Max-ddd-Cut problem. The ddd-QMC problem seeks the largest eigenvalue of a Hamiltonian defined on a graph with nnn vertices, where edges correspond to swap operators acting on (Cd)⊗n(\mathbb{C}^d)^{\otimes n}(Cd)⊗n. In recent years, progress has been made by investigating the algebraic structure of the ddd-QMC Hamiltonian. Building on this approach, this article solves the ddd-QMC problem for complete tripartite graphs for small local dimensions, d≤3d \le 3d≤3.
We prove that the maximum eigenvalue of the (both signed and unsigned) Laplacian of level kkk Kikuchi graph of any graph GGG with mmm edges is at most m+km+km+k. This confirms four recent conjectures of Apte, Parekh, and Sud. As applications, we obtain that tensor products of one and two qubit product states achieve an approximation ratio of 5/85/85/8 for Quantum Max Cut and 5/75/75/7 for the XY Hamiltonian. Moreover, combining our bounds with the algorithms analyzed by Apte, Parekh, and Sud, yields efficient algorithms achieving an approximation ratio of 0.6140.6140.614 for Quantum Max Cut and 0.6740.6740.674 for the XY Hamiltonian. Finally, we also make modest progress on Brouwer's conjecture and improve Lew's bound on the sum of the top-kkk eigenvalues of a Graph Laplacian.
Finding a high (or low) energy state of a given quantum Hamiltonian is a potential area to gain a provable and practical quantum advantage. A line of recent studies focuses on Quantum Max Cut, where one is asked to find a high energy state of a given antiferromagnetic Heisenberg Hamiltonian. In this work, we present a classical approximation algorithm for Quantum Max Cut that achieves an approximation ratio of 0.595, outperforming the previous best algorithms of Lee [Eunou Lee, 2022] (0.562, generic input graph) and King [King, 2023] (0.582, triangle-free input graph). The algorithm is based on finding the maximum weighted matching of an input graph and outputs a product of at most 2-qubit states, which is simpler than the fully entangled output states of the previous best algorithms.
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.