Quantum Max Cut for complete tripartite graphs

Tea Štrekelj · 2025

Read Quantum Max Cut for complete tripartite graphs by Tea Štrekelj (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-03740.txt.

Introduction

Tea Štrekelj, a mathematician working in Slovenia, tackles a quantum version of a classic graph problem in this 2025 preprint. The classical Max-Cut problem asks how to split a graph's vertices to maximise crossing edges. Its quantum analogue replaces that splitting question with finding the largest eigenvalue of a Hamiltonian built from swap operators on the graph.

Recent progress on this problem has come from studying the algebra behind the Hamiltonian rather than brute computation. Building on that line, Štrekelj settles the quantum Max-d-Cut problem completely for complete tripartite graphs, where vertices fall into three mutually connected groups. The result covers small local dimensions, up to three levels per site. It adds one fully solved graph family to a problem where exact answers remain rare.

Catalog record

CREATORTea Štrekelj
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE16 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-03740

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Quantum Max Cut for complete tripartite graphs Thanks: The author was supported by the Slovenian Research and Innovation Agency grant J1-60011. Tea Štrekelj Abstract . The Quantum Max- d d -Cut ( d d -QMC) problem is a special instance of a 2 2 -local Hamiltonian problem, representing the quantum analog of the classical Max- d d -Cut problem. The d d -QMC problem seeks the largest eigenvalue of a Hamiltonian defined on a graph with n n vertices, where edges correspond to swap operators acting on ( ℂ d ) ⊗ n (\mathbb{C}^{d})^{\otimes n} . In recent years, progress has been made by investigating the algebraic structure of the d d -QMC Hamiltonian. Building on this approach, this article solves the d d -QMC problem for complete tripartite graphs for small local dimensions, d ≤ 3 d\leq 3 . 2020 Mathematics Subject Classification 46N50, 05E15, 20C30, 81P45, 81R05, 82B20, 68R10 1. Introduction The k -local Hamiltonian problem is a central problem in quantum complexity theory. The goal is to determine the smallest eigenvalue (or ground state energy) of a Hamiltonian H , which is a self-adjoint matrix acting on the space of n qubits, (\mathbb{C}^{2})^{\otimes n} . This matrix, of dimension 2^{n}\times 2^{n} , is structured as a sum of local terms. In fact, for a chosen k\leq n, H=\sum_{\begin{subarray}{c}S\subseteq\{1,\ldots,n\}\\[1.42262pt] |S|=k\end{subarray}}H_{S}, where each H_{S} acts nontrivially on a subset (of S ) of at most k qubits and as the identity on the rest. Such an H is called a k -local Hamiltonian. We investigate generalizations of the Quantum Max Cut (QMC) problem, a special instance of the 2 -local Hamiltonian problem. Named by Gharibian and Parekh [ GP19 ] , QMC serves as a quantum analogue of the classical Max Cut (MC) problem, with its corresponding input matrix known as the QMC Hamiltonian. The problem arises naturally in physics, where it corresponds to finding the ground state energy of the anti-ferromagnetic Heisenberg model. This model is crucial for describing the magnetic properties of insular crystals under the 2 -local assumption that only nearest-neighbour interactions are significant [ Aue , BDZ ] . Beyond its physics origins, the QMC problem has garnered significant attention in computational complexity theory. As a simple prototype of a QMA-complete problem [ PM17 ] , it has become a valuable testbed for designing approximation algorithms for other QMA-hard problems [ AMG20 , PT21 , PT22 , Lee22 , Kin23 ] . Progress on solving the QMC problem includes exact analytical solutions for specific graph families, such as complete bipartite graphs [ LM62 ] and one-dimensional chains [ LM16 ] . More recently, second-order cone relaxations that provide approximations for large graphs [ HTPG ] were developed. In this article, we address the d -QMC problem, a generalization of the QMC problem to systems of n qudits. The Hamiltonian for this problem acts on the space (\mathbb{C}^{d})^{\otimes n} . The motivation for studying the d -QMC problem stems from the challenge of determining the ground state energies of \operatorname{SU}(d) -Heisenberg models on lattices [ KT , BAMC , PM21 ] . Furthermore, it serves as the quantum analogue of both the classical Max- d -Cut problem, which concerns finding maximum d -colorable subgraphs, and the anti-ferromagnetic d -state Potts model [ FJ ] . The focus of this paper is on the d -QMC problem pertaining to a specific family of graphs, namely complete tripartite graphs. We tackle the special case where the local dimension d is small, i.e., d\leq 3. 1.1. Quantum Max d -Cut and swap matrices A QMC Hamiltonian pertains to a given graph G on say n vertices. Throughout, we denote the vertex set of G by V (G) and the edge set of G by E (G). To address the d -QMC problem, we investigate the algebraic structure of the QMC Hamiltonian, following the approach of [ BCEHK24 , TRZ , KSV+ ] . This approach starts by expressing the QMC Hamiltonian in terms of the swap matrices Swap {}_{ij}^{(d)}. 1 1 1 In physics literature, these are often called SWAP or exchange operators [ NC ] . Definition 1.1 . Fix n and 1\leq i<j\leq n. The ( qudit ) swap matrix Swap {}_{ij}^{(d)} is defined by its action on rank one tensors as \text{Swap}_{ij}^{(d)}(v_{1}\otimes\cdots\otimes v_{i}\otimes\cdots\otimes v_{j}\otimes\cdots\otimes v_{n})=v_{1}\otimes\cdots\otimes v_{j}\otimes\cdots\otimes v_{i}\otimes\cdots\otimes v_{n} for any v_{1},\ldots,v_{n}\in\mathbb{C}^{d}. The action of swap matrices on a qudit space defines a representation \rho_{n}^{(d)} of the symmetric group S_{n} on (\mathbb{C}^{d})^{\otimes n} defined by \rho_{n}^{(d)}(\pi)(v_{1}\otimes\cdots\otimes v_{n})=v_{\pi^{-1}(1)}\otimes\cdots\otimes v_{\pi^{-1}(n)}. Denoting by \mathbb{C}[S_{n}] the group algebra of S_{n}, the image \rho_{n}^{(d)}\big(\mathbb{C}[S_{n}]\big) is a subalgebra of M_{d^{n}}(\mathbb{C}). We denote it by M^{\text{Sw}_{d}}_{n}(\mathbb{C}) and call it the d -swap algebra . Definition 1.2 . For a graph G on n vertices, the Quantum Max d -Cut Hamiltonian ( d -QMC Hamiltonian) pertaining to G is defined as ( H_{G}^{d} ) H_{G}^{d}=\sum_{(i,j)\in\EE(G)}2\left(I-\textnormal{Swap}^{(d)}_{ij}\right). The d -QMC problem is about determining the largest eigenvalue of the d -QMC Hamiltonian H_{G}^{d} in ( H G d ). The original QMC problem, for local dimension d=2 , was formulated with a Hamiltonian built from Pauli matrices. This approach was later generalized to d>2 by [ CJKKW23+ ] , who employed Gell-Mann matrices as a natural higher-dimensional extension of the Pauli matrices. The alternative formulation using swap matrices as in Definition 1.2 was first studied in [ BCEHK24 ] for d=2 and subsequently by [ KSV+ ] for general d. The QMC (and d -QMC) problem, as an instance of the general 2 -local Hamiltonian problem, is known to be computationally intractable. It belongs to the Quantum Merlin Arthur (QMA)-hard complexity class [ KSV02 , KKR06 ] , the quantum analogue of NP-hard. Given that the QMC problem is hard to solve, research has focused on restricted cases, such as finding exact solutions for specific instances [ LM62 ] , designing efficient high-precision approximation algorithms for the largest eigenvalue [ LVV15 ] , or achieving constant-factor approximations [ GK12 , BH13 , BGKT19 , HM17 ] . Other work has explored the hardness of computing ground state properties [ GH ] . In this paper, we leverage the algebraic structure of swap matrices to solve the d -QMC problem for d=2,3 on the family of complete tripartite graphs K_{p,q,r} with p\geq q\geq r. Theorem 1.3 . Let n,p,q,r\in\mathbb{N} be such that p\geq q\geq r>0 and p+q+r=n. (1) The solution to the 2 -QMC problem for K_{p,q,r} is (a) 2(n-p)(p+1) if p\geq q+r; (b) 4k^{2}-1 if n=2k and p<q+r; (c) 4k(k+1)-3 if n=2k+1 and p<q+r. (2) The solution to the 3 -QMC problem for K_{p,q,r} is 2n(2+p+q)-2(p^{2}+q+q^{2}+p(2+q)). While the above theorem captures the essence of the main result, the proper statement requires additional background. We dedicate the following two subsections to the requisite combinatorial theory. 1.2. Partitions and irreducible representations of S_{n} The d -swap algebra M^{\text{Sw}_{d}}_{n}(\mathbb{C}) is semisimple as it is the image of a representation of \mathbb{C}[S_{n}]. It hence decomposes into a direct sum of (simple) matrix algebras that are images of some of the irreducible representations (irreps) of S_{n}. It is well-known that the irreps of S_{n} are indexed by partitions \lambda of n (denoted by \lambda\vdash n ), where \lambda=(\lambda_{1},\ldots,\lambda_{k})\in\mathbb{N}^{k},\quad\lambda_{1}\geq\cdots\geq\lambda_{k}>0,\quad\sum_{i=1}^{k}\lambda_{i}=n. The number k is

Read the complete text