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.03740

Quantum Max Cut for complete tripartite graphs

Tea Štrekelj

quant-phmath.COSubmitted Dec 3, 2025• Announced Dec 4, 2025• 0 citations
arXivHTMLPDF

Abstract

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$.

Comments
15 pages

Related papers

Quantum Max d-Cut via qudit swap operators

Igor Klep, Tea Štrekelj, Jurij Volčič

Quantum Max Cut (QMC) problem for systems of qubits is an example of a 2-local Hamiltonian problem, and a prominent paradigm in computational complexity theory. This paper investigates the algebraic structure of a higher-dimensional analog of the QMC problem for systems of qudits. The Quantum Max d -Cut ( d -QMC) problem asks for the largest eigenvalue of a Hamiltonian on a graph with n vertices whose edges correspond to swap operators acting on ( C d ) ⊗ n . The algebra generated by the swap operators is identified as a quotient of a free algebra modulo symmetric group relations and a single additional relation of degree d . This presentation leads to a tailored hierarchy of semidefinite programs, leveraging noncommutative polynomial optimization (NPO) methods, that converges to the solution of the d -QMC problem. For a large class of complete bipartite graphs, exact solutions for the d -QMC problem are derived using the representation theory of symmetric groups and Littlewood-Richardson coefficients. Lastly, the paper addresses a refined d -QMC problem focused on finding the largest eigenvalue within each isotypic component (irreducible block) of the graph Hamiltonian. It is shown that the spectrum of the star graph Hamiltonian distinguishes between isotypic components of the 3 -QMC problem. For general d , low-degree relations for separating isotypic components are presented, enabling adaptation of the global NPO hierarchy to efficiently compute the largest eigenvalue in each isotypic component.

arXiv:2503.20942•Quantum•Sep 3, 2026•0 citations

Improved approximation ratios for the Quantum Max-Cut problem on general, triangle-free and bipartite graphs

Sander Gribling, Lennart Sinjorgo, Renata Sotirov

We study polynomial-time approximation algorithms for the Quantum Max-Cut (QMC) problem. Given an edge-weighted graph $G$ on n vertices, the QMC problem is to determine the largest eigenvalue of a particular $2^n \times 2^n$ matrix that corresponds to $G$. We provide a sharpened analysis of the currently best-known QMC approximation algorithm for general graphs. This algorithm achieves an approximation ratio of $0.599$, which our analysis improves to $0.603$. Additionally, we propose two new approximation algorithms for the QMC problem on triangle-free and bipartite graphs, that achieve approximation ratios of $0.61383$ and $0.8162$, respectively. These are the best-known approximation ratios for their respective graph classes.

arXiv:2504.11120•Apr 15, 2025•0 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

Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap Operators

Adam Bene Watts, Anirban Ch Narayan Chowdhury, Aidan Epperly +2 more

The Quantum Max Cut (QMC) problem has emerged as a test-problem for designing approximation algorithms for local Hamiltonian problems. In this paper we attack this problem using the algebraic structure of QMC, in particular the relationship between the quantum max cut Hamiltonian and the representation theory of the symmetric group. The first major contribution of this paper is an extension of non-commutative Sum of Squares (ncSoS) optimization techniques to give a new hierarchy of relaxations to Quantum Max Cut. The hierarchy we present is based on optimizations over polynomials in the qubit swap operators. This is in contrast to the "standard" quantum Lasserre Hierarchy, which is based on polynomials expressed in terms of the Pauli matrices. To prove correctness of this hierarchy, we exploit a finite presentation of the algebra generated by the qubit swap operators. This presentation allows for the use of computer algebraic techniques to manipulate and simplify polynomials written in terms of the swap operators, and may be of independent interest. Surprisingly, we find that level-2 of this new hierarchy is numerically exact (up to tolerance 10^(-7)) on all QMC instances with uniform edge weights on graphs with at most 8 vertices. The second major contribution of this paper is a polynomial-time algorithm that computes (in exact arithmetic) the maximum eigenvalue of the QMC Hamiltonian for certain graphs, including graphs that can be "decomposed" as a signed combination of cliques. A special case of the latter are complete bipartite graphs with uniform edge-weights, for which exact solutions are known from the work of Lieb and Mattis. Our methods, which use representation theory of the symmetric group, can be seen as a generalization of the Lieb-Mattis result.

arXiv:2307.15661•Jul 28, 2023•1 citation

Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap Operators

Adam Bene Watts, Anirban Ch Narayan Chowdhury, Aidan Epperly +2 more

The Quantum Max Cut (QMC) problem has emerged as a test-problem for designing approximation algorithms for local Hamiltonian problems. In this paper we attack this problem using the algebraic structure of QMC, in particular the relationship between the quantum max cut Hamiltonian and the representation theory of the symmetric group.The first major contribution of this paper is an extension of non-commutative Sum of Squares (ncSoS) optimization techniques to give a new hierarchy of relaxations to Quantum Max Cut. The hierarchy we present is based on optimizations over polynomials in the qubit swap operators. This is in contrast to the "standard" quantum Lasserre Hierarchy, which is based on polynomials expressed in terms of the Pauli matrices. To prove correctness of this hierarchy, we exploit a finite presentation of the algebra generated by the qubit swap operators. This presentation allows for the use of computer algebraic techniques to manipulate and simplify polynomials written in terms of the swap operators, and may be of independent interest. Surprisingly, we find that level-2 of this new hierarchy is numerically exact (up to tolerance 10−7 ) on all QMC instances with uniform edge weights on graphs with at most 8 vertices.The second major contribution of this paper is a polynomial-time algorithm that computes (in exact arithmetic) the maximum eigenvalue of the QMC Hamiltonian for certain graphs, including graphs that can be "decomposed" as a signed combination of cliques. A special case of the latter are complete bipartite graphs with uniform edge-weights, for which exact solutions are known from the work of Lieb and Mattis \cite{lieb1962ordering}. Our methods, which use representation theory of the symmetric group, can be seen as a generalization of the Lieb-Mattis result.

Quantum•May 22, 2024•4 citations

Classical Algorithms for Bipartite Quantum Max-Cut on Dense Expanders

Stuart Wayland, Zackary Jorquera, Alexandra Kolla

Quantum Max-Cut is a well-studied local Hamiltonian problem for which the classical complexity of the bipartite case remains open. We give a polynomial-time classical randomized algorithm for the spin-$\tfrac12$ antiferromagnetic Heisenberg model, equivalently Quantum Max-Cut, on dense balanced bipartite expanders. This class includes $G(n,n,p)$ with high probability for every fixed $p>0$. The algorithm estimates the ground energy and any ground state edge correlation to additive error $\varepsilon$ in time polynomial in $n$ and $1/\varepsilon$. We construct a Markov chain on perfect matchings of the complete bipartite graph, each matching representing a product of singlets, that converges to the ground state, and use the expansion of the graph to show that polynomially many steps and samples of this chain suffice.

quant-pharXiv:2610.03670•Oct 5, 2026•0 citations
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.
Quantum Max Cut (QMC) problem for systems of qubits is an example of a 2-local Hamiltonian problem, and a prominent paradigm in computational complexity theory. This paper investigates the algebraic structure of a higher-dimensional analog of the QMC problem for systems of qudits. The Quantum Max d -Cut ( d -QMC) problem asks for the largest eigenvalue of a Hamiltonian on a graph with n vertices whose edges correspond to swap operators acting on ( C d ) ⊗ n . The algebra generated by the swap operators is identified as a quotient of a free algebra modulo symmetric group relations and a single additional relation of degree d . This presentation leads to a tailored hierarchy of semidefinite programs, leveraging noncommutative polynomial optimization (NPO) methods, that converges to the solution of the d -QMC problem. For a large class of complete bipartite graphs, exact solutions for the d -QMC problem are derived using the representation theory of symmetric groups and Littlewood-Richardson coefficients. Lastly, the paper addresses a refined d -QMC problem focused on finding the largest eigenvalue within each isotypic component (irreducible block) of the graph Hamiltonian. It is shown that the spectrum of the star graph Hamiltonian distinguishes between isotypic components of the 3 -QMC problem. For general d , low-degree relations for separating isotypic components are presented, enabling adaptation of the global NPO hierarchy to efficiently compute the largest eigenvalue in each isotypic component.
We study polynomial-time approximation algorithms for the Quantum Max-Cut (QMC) problem. Given an edge-weighted graph GGG on n vertices, the QMC problem is to determine the largest eigenvalue of a particular 2n×2n2^n \times 2^n2n×2n matrix that corresponds to GGG. We provide a sharpened analysis of the currently best-known QMC approximation algorithm for general graphs. This algorithm achieves an approximation ratio of 0.5990.5990.599, which our analysis improves to 0.6030.6030.603. Additionally, we propose two new approximation algorithms for the QMC problem on triangle-free and bipartite graphs, that achieve approximation ratios of 0.613830.613830.61383 and 0.81620.81620.8162, respectively. These are the best-known approximation ratios for their respective graph classes.
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.
The Quantum Max Cut (QMC) problem has emerged as a test-problem for designing approximation algorithms for local Hamiltonian problems. In this paper we attack this problem using the algebraic structure of QMC, in particular the relationship between the quantum max cut Hamiltonian and the representation theory of the symmetric group. The first major contribution of this paper is an extension of non-commutative Sum of Squares (ncSoS) optimization techniques to give a new hierarchy of relaxations to Quantum Max Cut. The hierarchy we present is based on optimizations over polynomials in the qubit swap operators. This is in contrast to the "standard" quantum Lasserre Hierarchy, which is based on polynomials expressed in terms of the Pauli matrices. To prove correctness of this hierarchy, we exploit a finite presentation of the algebra generated by the qubit swap operators. This presentation allows for the use of computer algebraic techniques to manipulate and simplify polynomials written in terms of the swap operators, and may be of independent interest. Surprisingly, we find that level-2 of this new hierarchy is numerically exact (up to tolerance 10^(-7)) on all QMC instances with uniform edge weights on graphs with at most 8 vertices. The second major contribution of this paper is a polynomial-time algorithm that computes (in exact arithmetic) the maximum eigenvalue of the QMC Hamiltonian for certain graphs, including graphs that can be "decomposed" as a signed combination of cliques. A special case of the latter are complete bipartite graphs with uniform edge-weights, for which exact solutions are known from the work of Lieb and Mattis. Our methods, which use representation theory of the symmetric group, can be seen as a generalization of the Lieb-Mattis result.
The Quantum Max Cut (QMC) problem has emerged as a test-problem for designing approximation algorithms for local Hamiltonian problems. In this paper we attack this problem using the algebraic structure of QMC, in particular the relationship between the quantum max cut Hamiltonian and the representation theory of the symmetric group.The first major contribution of this paper is an extension of non-commutative Sum of Squares (ncSoS) optimization techniques to give a new hierarchy of relaxations to Quantum Max Cut. The hierarchy we present is based on optimizations over polynomials in the qubit swap operators. This is in contrast to the "standard" quantum Lasserre Hierarchy, which is based on polynomials expressed in terms of the Pauli matrices. To prove correctness of this hierarchy, we exploit a finite presentation of the algebra generated by the qubit swap operators. This presentation allows for the use of computer algebraic techniques to manipulate and simplify polynomials written in terms of the swap operators, and may be of independent interest. Surprisingly, we find that level-2 of this new hierarchy is numerically exact (up to tolerance 10−7 ) on all QMC instances with uniform edge weights on graphs with at most 8 vertices.The second major contribution of this paper is a polynomial-time algorithm that computes (in exact arithmetic) the maximum eigenvalue of the QMC Hamiltonian for certain graphs, including graphs that can be "decomposed" as a signed combination of cliques. A special case of the latter are complete bipartite graphs with uniform edge-weights, for which exact solutions are known from the work of Lieb and Mattis \cite{lieb1962ordering}. Our methods, which use representation theory of the symmetric group, can be seen as a generalization of the Lieb-Mattis result.
Quantum Max-Cut is a well-studied local Hamiltonian problem for which the classical complexity of the bipartite case remains open. We give a polynomial-time classical randomized algorithm for the spin-12\tfrac1221​ antiferromagnetic Heisenberg model, equivalently Quantum Max-Cut, on dense balanced bipartite expanders. This class includes G(n,n,p)G(n,n,p)G(n,n,p) with high probability for every fixed p>0p>0p>0. The algorithm estimates the ground energy and any ground state edge correlation to additive error ε\varepsilonε in time polynomial in nnn and 1/ε1/\varepsilon1/ε. We construct a Markov chain on perfect matchings of the complete bipartite graph, each matching representing a product of singlets, that converges to the ground state, and use the expansion of the graph to show that polynomially many steps and samples of this chain suffice.