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:2503.20942 · Quantum

Quantum Max d-Cut via qudit swap operators

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

Published Sep 3, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.22331/q-2026-09-03-2203

Related papers

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

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

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

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

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

An SU(2)-symmetric Semidefinite Programming Hierarchy for Quantum Max Cut

Jun Takahashi, Sankara Sai Chaithanya Rayudu, Cunlu Zhou +3 more

Understanding and approximating extremal energy states of local Hamiltonians is a central problem in quantum physics and complexity theory. Recent work has focused on developing approximation algorithms for local Hamiltonians, and in particular the ``Quantum Max Cut'' (QMax-Cut) problem, which is closely related to the antiferromagnetic Heisenberg model. In this work, we introduce a family of semidefinite programming (SDP) relaxations based on the Navascues-Pironio-Acin (NPA) hierarchy which is tailored for QMaxCut by taking into account its SU(2) symmetry. We show that the hierarchy converges to the optimal QMaxCut value at a finite level, which is based on a new characterization of the algebra of SWAP operators. We give several analytic proofs and computational results showing exactness/inexactness of our hierarchy at the lowest level on several important families of graphs. We also discuss relationships between SDP approaches for QMaxCut and frustration-freeness in condensed matter physics and numerically demonstrate that the SDP-solvability practically becomes an efficiently-computable generalization of frustration-freeness. Furthermore, by numerical demonstration we show the potential of SDP algorithms to perform as an approximate method to compute physical quantities and capture physical features of some Heisenberg-type statistical mechanics models even away from the frustration-free regions.

arXiv:2307.15688•Jul 28, 2023•3 citations
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.
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-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.
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 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.
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.
Understanding and approximating extremal energy states of local Hamiltonians is a central problem in quantum physics and complexity theory. Recent work has focused on developing approximation algorithms for local Hamiltonians, and in particular the ``Quantum Max Cut'' (QMax-Cut) problem, which is closely related to the antiferromagnetic Heisenberg model. In this work, we introduce a family of semidefinite programming (SDP) relaxations based on the Navascues-Pironio-Acin (NPA) hierarchy which is tailored for QMaxCut by taking into account its SU(2) symmetry. We show that the hierarchy converges to the optimal QMaxCut value at a finite level, which is based on a new characterization of the algebra of SWAP operators. We give several analytic proofs and computational results showing exactness/inexactness of our hierarchy at the lowest level on several important families of graphs. We also discuss relationships between SDP approaches for QMaxCut and frustration-freeness in condensed matter physics and numerically demonstrate that the SDP-solvability practically becomes an efficiently-computable generalization of frustration-freeness. Furthermore, by numerical demonstration we show the potential of SDP algorithms to perform as an approximate method to compute physical quantities and capture physical features of some Heisenberg-type statistical mechanics models even away from the frustration-free regions.