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

Solving the MAX-$k$-CUT problem for hypergraphs with quantum computing

V. S. Yarmus, Kh. P. Gnatenko

quant-phSubmitted Oct 30, 2026• Announced Nov 2, 2026
arXivHTMLPDF

Abstract

We investigate the MAX-$k$-CUT problem on hypergraphs by considering their representation as spin systems with Ising interactions. The corresponding cost Hamiltonian for MAX-$k$-CUT problem on hypergraphs is reduced to an Ising Hamiltonian with pairwise interactions. This reduction simplifies the solution of the MAX-$k$-CUT problem using quantum computing. As illustrative examples, a 3-uniform tight-star hypergraph and a sunflower hypergraph are considered. The corresponding Hamiltonians are constructed, and quantum protocols for the MAX-$k$-CUT problems are presented. The MAX-3-CUT and MAX-4-CUT instances are investigated for these hypergraphs by varying the number of Quantum Approximate Optimization Algorithm (QAOA) layers from (p=2) to (p=15) with quantum computing on IBM's Qiskit AerSimulator.

AI Summary

The paper studies QAOA formulations of MAX-$k$-CUT on hypergraphs using pairwise Ising interactions. Each hyperedge is replaced by a weighted clique, and contributions from overlapping hyperedges are combined. The resulting objective maximizes the weighted number of separated vertex pairs within hyperedges, favoring balanced splits of individual hyperedges rather than simply counting nonmonochromatic hyperedges. For a hyperedge of size $n$ split into groups of sizes $n_1,n_2$, the Ising energy is $\omega_e[\binom{n}{2}-2n_1n_2]$, minimized by an equal or near-equal split. For $k$ groups, the construction uses one-hot encoding with $k|V|$ qubits, an initial product of $W_k$ states, and a parity-partitioned ring $XY$ mixer that preserves feasibility. After combining repeated pairs, the interaction graph has at most $\binom{|V|}{2}$ distinct vertex pairs. Numerical tests use Qiskit AerSimulator, COBYLA with at most 2,000 iterations, and 10,000 shots, on a five-vertex 3-uniform tight star and a six-vertex sunflower, with $k=3,4$ and depths $p=2,5,10,15$. Reported approximation ratios are $0.73$–$0.82$ and $0.88$–$0.94$ for the tight star at $k=3,4$, respectively; sunflower ratios are $0.67$–$0.86$ and $0.75$. Some runs have an optimal assignment as the most frequent measurement outcome, although their expected cut values remain suboptimal. The paper identifies trapping in local minima as a limitation: increasing depth does not consistently improve performance. Evidence consists of these small simulator examples rather than hardware experiments or general approximation guarantees.

Little sign of AI-generated textIncrementalSmall numerics onlyMissing comparisonPossible error

Central claim may not hold: The proposed pairwise Hamiltonian optimizes separated vertex pairs within hyperedges, which can select a suboptimal solution for standard hypergraph MAX-k-CUT, where each nonmonochromatic hyperedge contributes its weight once. The reported approximation ratios apply to the clique-expanded pair-counting objective and are not established as approximation ratios for standard hypergraph MAX-k-CUT.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Constructing Dynamical Systems to Model Higher Order Ising Spin Interactions and their Application in Solving Combinatorial Optimization Problems

Mohammad Khairul Bashar, Nikhil Shukla

The Ising model provides a natural mapping for many computationally hard combinatorial optimization problems (COPs). Consequently, dynamical system-inspired computing models and hardware platforms that minimize the Ising Hamiltonian, have recently been proposed as a potential candidate for solving COPs, with the promise of significant performance benefit. However, the Ising model, and consequently, the corresponding dynamical system-based computational models primarily consider quadratic interactions among the nodes. Computational models considering higher order interactions among Ising spins remain largely unexplored. Therefore, in this work, we propose dynamical-system-based computational models to consider higher order (>2) interactions among the Ising spins, which subsequently, enables us to propose computational models to directly solve many COPs that entail such higher order interactions (COPs on hypergraphs). Specifically, we demonstrate our approach by developing dynamical systems to compute the solution for the Boolean NAE-K-SAT (K is greater than 3) problem as well as solve the Max-K-Cut of a hypergraph. Our work advances the potential of the physics-inspired 'toolbox' for solving COPs.

arXiv:2211.05365•Nov 10, 2022•1 citation

Edge-based quantum approximate optimization algorithm for MAX-CUT problem

Youngjin Seo, Jun Heo

Quantum computing has emerged as a promising paradigm to tackle computationally intensive problems that classical computers struggle with. In this study, we explore the application of the Edge-based quantum approximate optimization algorithm (QAOA) to the MAX-CUT problem, a well-known combinatorial optimization challenge. MAX-CUT aims to partition the vertices of a graph into two subsets such that the number of edges between the subsets is maximized. We define the edge-based MAX-CUT problem and propose a method for applying QAOA specifically tailored to this formulation. We conduct simulations using IBM’s Qiskit framework, examining both vertex-based and edge-based QAOA implementations across various graph structures. Our results highlight the comparative performance of these approaches in terms of solution quality and computational efficiency. Specifically, we analyze the impact of different graph sizes and edge densities on the complexity and CNOT gate counts of the proposed algorithms. This analysis provides insights into leveraging quantum computing for combinatorial optimization tasks, particularly focusing on the implications for practical applications and future research directions.

Quantum Information Processing•Sep 23, 2025•1 citation

The Quantum Overlap Gap Property and Algorithmic Hardness for the Quantum Hypergraph Max-Cut Problem

Mikhail Mints, Eric R. Anschuetz

In this work, we analyze the average-case hardness of approximation for the Quantum Hypergraph Max-Cut problem using the theoretical framework of the Quantum Overlap Gap Property (QOGP). We establish two main results. Our first result applies to a wide class of stable quantum algorithms, satisfying a Lipschitz property with respect to the quantum Wasserstein distance of order $2$. We show a weak hardness result, demonstrating that for any Lipschitz constant $L$, there is some $k$ such that $L$-stable algorithms cannot approximate the optimal solution to Quantum Hypergraph Max-Cut on $k$-uniform hypergraphs in the average case. Additionally, we establish a strong hardness result where $k$ is independent of $L$, but only for a more restricted class of local quantum algorithms defined using the quantum Wasserstein distance of order $\infty$. We apply these results to establish concrete depth lower bounds for popular quantum algorithms for preparing near-optimal states for this problem.

quant-pharXiv:2609.10838•Sep 11, 2026•0 citations

Solving Maximum-Cut problem using Neutral atom quantum computer

Chen Junxi

This work investigates approaches for solving the Maximum-Cut (Max-cut) problem, a nondeterministic polynomial-hard (NP-hard) combinatorial optimization problem, on a neutral-atom quantum computing platform. The Max-cut problem can be mapped to an Ising model, making it a representative candidate for demonstrating quantum computational advantage. We explore two algorithmic pathways: first, a quantum algorithm based on quantum phase estimation and a modified Grover's search for solution space exploration, which was numerically simulated using the Qiskit library. Second, the Quantum Approximate Optimization Algorithm (QAOA) is employed. We simulate QAOA for a four-atom model under conditions relevant to neutral-atom platforms, evaluating the solution quality via the approximation ratio Ra=1/S_max ∑_i▒〖p_i S_i 〗 (p_i is the probability of a particular bit-string, S_i is the number of edge cuts for the bit string, and S_max is the maximum cut number.) for circuit depths p = 1, 2, 3. Furthermore, numerical simulations of the neutral-atom platform model are conducted using the Pulser library. The results provide algorithmic foundations and numerical validation for demonstrating quantum utility in physical systems like neutral atoms and for tackling practical problems such as routing.

LaserPhys Youth School-Conference•Jan 1, 2025•0 citations

A Max K-Cut Implementation for QAOA in the Measurement Based Quantum Computing Formalism

Sebastiano Corli, Daniele Dragoni, Massimiliano Proietti +3 more

The MaxCut is a combinatorial problem which belongs to the NP-hard class. The algorithm to solve it can be mapped into a quantum system, where the optimal configuration matches the ground state of a target Hamiltonian. It is possible to implement the adiabatic theorem into the circuit model via the QAOA algorithm, by arbitrarily choosing from both the gate-based and the measurement-based quantum computing (MBQC) settings. Recently, the MaxCut problem has been generalized to the Max K-Cut version also in the MBQC frame, where K stands for the number of cuts to implement. Here, the QAOA algorithm for a Max K-Cut is solved for a graph with arbitrary number of vertices V and number of cuts K scaling as a power of 2, along with the circuit depth p. The problem is solved on a emulator based on classical HPC resources. In order to test the performances of a Max K-cut implemented in the MBQC frame, we report how the average runtime and the approximation ratio scale by increasing V, K and p, comparing the results from two different topologies of graphs, 2-regular graphs with null weights on the diagonals versus the the fully-connected graphs. Eventually, the approximation ratio, evaluated as a parameter of success, is shown to yield optimal performances.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•12 citations

Hybrid Quantum-HPC Solutions for Max-Cut: Bridging Classical and Quantum Algorithms

Ishan Patwardhan, Akhil Akkapelli

This research explores the integration of the Quantum Approximate Optimization Algorithm (QAOA) into Hybrid Quantum-HPC systems for solving the Max-Cut problem, comparing its performance with classical algorithms like brute-force search and greedy heuristics. We develop a theoretical model to analyze the time complexity, scalability, and communication overhead in hybrid systems. Using simulations, we evaluate QAOA's performance on small-scale Max-Cut instances, benchmarking its runtime, solution accuracy, and resource utilization. The study also investigates the scalability of QAOA with increasing problem size, offering insights into its potential advantages over classical methods for large-scale combinatorial optimization problems, with implications for future Quantum computing applications in HPC environments.

arXiv:2410.15626•Oct 21, 2024•0 citations
Solving the MAX-kkk-CUT problem for hypergraphs with quantum computing
We investigate the MAX-kkk-CUT problem on hypergraphs by considering their representation as spin systems with Ising interactions. The corresponding cost Hamiltonian for MAX-kkk-CUT problem on hypergraphs is reduced to an Ising Hamiltonian with pairwise interactions. This reduction simplifies the solution of the MAX-kkk-CUT problem using quantum computing. As illustrative examples, a 3-uniform tight-star hypergraph and a sunflower hypergraph are considered. The corresponding Hamiltonians are constructed, and quantum protocols for the MAX-kkk-CUT problems are presented. The MAX-3-CUT and MAX-4-CUT instances are investigated for these hypergraphs by varying the number of Quantum Approximate Optimization Algorithm (QAOA) layers from (p=2) to (p=15) with quantum computing on IBM's Qiskit AerSimulator.
The paper studies QAOA formulations of MAX-kkk-CUT on hypergraphs using pairwise Ising interactions. Each hyperedge is replaced by a weighted clique, and contributions from overlapping hyperedges are combined. The resulting objective maximizes the weighted number of separated vertex pairs within hyperedges, favoring balanced splits of individual hyperedges rather than simply counting nonmonochromatic hyperedges. For a hyperedge of size nnn split into groups of sizes n1,n2n_1,n_2n1​,n2​, the Ising energy is ωe[(n2)−2n1n2]\omega_e[\binom{n}{2}-2n_1n_2]ωe​[(2n​)−2n1​n2​], minimized by an equal or near-equal split.
For kkk groups, the construction uses one-hot encoding with k∣V∣k|V|k∣V∣ qubits, an initial product of WkW_kWk​ states, and a parity-partitioned ring XYXYXY mixer that preserves feasibility. After combining repeated pairs, the interaction graph has at most (∣V∣2)\binom{|V|}{2}(2∣V∣​) distinct vertex pairs. Numerical tests use Qiskit AerSimulator, COBYLA with at most 2,000 iterations, and 10,000 shots, on a five-vertex 3-uniform tight star and a six-vertex sunflower, with k=3,4k=3,4k=3,4 and depths p=2,5,10,15p=2,5,10,15p=2,5,10,15.
Reported approximation ratios are 0.730.730.73–0.820.820.82 and 0.880.880.88–0.940.940.94 for the tight star at k=3,4k=3,4k=3,4, respectively; sunflower ratios are 0.670.670.67–0.860.860.86 and 0.750.750.75. Some runs have an optimal assignment as the most frequent measurement outcome, although their expected cut values remain suboptimal. The paper identifies trapping in local minima as a limitation: increasing depth does not consistently improve performance. Evidence consists of these small simulator examples rather than hardware experiments or general approximation guarantees.
The Ising model provides a natural mapping for many computationally hard combinatorial optimization problems (COPs). Consequently, dynamical system-inspired computing models and hardware platforms that minimize the Ising Hamiltonian, have recently been proposed as a potential candidate for solving COPs, with the promise of significant performance benefit. However, the Ising model, and consequently, the corresponding dynamical system-based computational models primarily consider quadratic interactions among the nodes. Computational models considering higher order interactions among Ising spins remain largely unexplored. Therefore, in this work, we propose dynamical-system-based computational models to consider higher order (>2) interactions among the Ising spins, which subsequently, enables us to propose computational models to directly solve many COPs that entail such higher order interactions (COPs on hypergraphs). Specifically, we demonstrate our approach by developing dynamical systems to compute the solution for the Boolean NAE-K-SAT (K is greater than 3) problem as well as solve the Max-K-Cut of a hypergraph. Our work advances the potential of the physics-inspired 'toolbox' for solving COPs.
Quantum computing has emerged as a promising paradigm to tackle computationally intensive problems that classical computers struggle with. In this study, we explore the application of the Edge-based quantum approximate optimization algorithm (QAOA) to the MAX-CUT problem, a well-known combinatorial optimization challenge. MAX-CUT aims to partition the vertices of a graph into two subsets such that the number of edges between the subsets is maximized. We define the edge-based MAX-CUT problem and propose a method for applying QAOA specifically tailored to this formulation. We conduct simulations using IBM’s Qiskit framework, examining both vertex-based and edge-based QAOA implementations across various graph structures. Our results highlight the comparative performance of these approaches in terms of solution quality and computational efficiency. Specifically, we analyze the impact of different graph sizes and edge densities on the complexity and CNOT gate counts of the proposed algorithms. This analysis provides insights into leveraging quantum computing for combinatorial optimization tasks, particularly focusing on the implications for practical applications and future research directions.
In this work, we analyze the average-case hardness of approximation for the Quantum Hypergraph Max-Cut problem using the theoretical framework of the Quantum Overlap Gap Property (QOGP). We establish two main results. Our first result applies to a wide class of stable quantum algorithms, satisfying a Lipschitz property with respect to the quantum Wasserstein distance of order 222. We show a weak hardness result, demonstrating that for any Lipschitz constant LLL, there is some kkk such that LLL-stable algorithms cannot approximate the optimal solution to Quantum Hypergraph Max-Cut on kkk-uniform hypergraphs in the average case. Additionally, we establish a strong hardness result where kkk is independent of LLL, but only for a more restricted class of local quantum algorithms defined using the quantum Wasserstein distance of order ∞\infty∞. We apply these results to establish concrete depth lower bounds for popular quantum algorithms for preparing near-optimal states for this problem.
This work investigates approaches for solving the Maximum-Cut (Max-cut) problem, a nondeterministic polynomial-hard (NP-hard) combinatorial optimization problem, on a neutral-atom quantum computing platform. The Max-cut problem can be mapped to an Ising model, making it a representative candidate for demonstrating quantum computational advantage. We explore two algorithmic pathways: first, a quantum algorithm based on quantum phase estimation and a modified Grover's search for solution space exploration, which was numerically simulated using the Qiskit library. Second, the Quantum Approximate Optimization Algorithm (QAOA) is employed. We simulate QAOA for a four-atom model under conditions relevant to neutral-atom platforms, evaluating the solution quality via the approximation ratio Ra=1/S_max ∑_i▒〖p_i S_i 〗 (p_i is the probability of a particular bit-string, S_i is the number of edge cuts for the bit string, and S_max is the maximum cut number.) for circuit depths p = 1, 2, 3. Furthermore, numerical simulations of the neutral-atom platform model are conducted using the Pulser library. The results provide algorithmic foundations and numerical validation for demonstrating quantum utility in physical systems like neutral atoms and for tackling practical problems such as routing.
The MaxCut is a combinatorial problem which belongs to the NP-hard class. The algorithm to solve it can be mapped into a quantum system, where the optimal configuration matches the ground state of a target Hamiltonian. It is possible to implement the adiabatic theorem into the circuit model via the QAOA algorithm, by arbitrarily choosing from both the gate-based and the measurement-based quantum computing (MBQC) settings. Recently, the MaxCut problem has been generalized to the Max K-Cut version also in the MBQC frame, where K stands for the number of cuts to implement. Here, the QAOA algorithm for a Max K-Cut is solved for a graph with arbitrary number of vertices V and number of cuts K scaling as a power of 2, along with the circuit depth p. The problem is solved on a emulator based on classical HPC resources. In order to test the performances of a Max K-cut implemented in the MBQC frame, we report how the average runtime and the approximation ratio scale by increasing V, K and p, comparing the results from two different topologies of graphs, 2-regular graphs with null weights on the diagonals versus the the fully-connected graphs. Eventually, the approximation ratio, evaluated as a parameter of success, is shown to yield optimal performances.
This research explores the integration of the Quantum Approximate Optimization Algorithm (QAOA) into Hybrid Quantum-HPC systems for solving the Max-Cut problem, comparing its performance with classical algorithms like brute-force search and greedy heuristics. We develop a theoretical model to analyze the time complexity, scalability, and communication overhead in hybrid systems. Using simulations, we evaluate QAOA's performance on small-scale Max-Cut instances, benchmarking its runtime, solution accuracy, and resource utilization. The study also investigates the scalability of QAOA with increasing problem size, offering insights into its potential advantages over classical methods for large-scale combinatorial optimization problems, with implications for future Quantum computing applications in HPC environments.