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

AIP conference proceedings

Solving NP-hard problems by using approximation methods on semidefinite programming

Fadhl Jawad Kadhim, Ahmed Sabah Al-Jilawi

Published Jan 1, 2026• 0 citations
Publisher

Abstract

We study one of the most important NP-hard problem in combinatorial optimization problems, which is the maximum cut problem (Max-Cut). The combinatorial optimization problems can be solved by many methods; this paper was focused on two methods to solving the Max-Cut, the extended alternating direction method of multipliers (ADMM) and the branch and bound method (B&B). Numerical results from ADMM and B&B are obtained to find approximate solutions to Max-Cut with huge numbers of vertices and edges on several graphs. The groundwork of a study is to find the solution from the faster method of them. Finally, the ADMM is faster convergence than the B&B to get the approximate solution to Max-Cut.

DOI
10.1063/5.0329915

Related papers

Semidefinite programming approaches for stable set and max-cut problems

Lennart Sinjorgo

This thesis investigates the use of semidefinite programming (SDP) for solving (variants of) the well-known stable set and max-cut problems. Chapter 2 considers a generalization of the stable set problem, and a corresponding SDP relaxation. Similarly, Chapter 3 considers a generalization of the max-cut problem that involves complex roots of unity. Various complex SDP relaxations of this generalized max-cut problem are studied. Chapter 4 provides approximation algorithms for the quantum generalization of the max-cut problem. These approximation algorithms employ a hierarchy of SDP relaxations for noncommutative polynomial optimization problems. Chapter 5 provides an SDP algorithm for computing bounds on the stability numbers of graphs. Chapter 6 provides an SDP algorithm for solving the MAX-SAT problem. Chapters 5 and 6 provide extensive numerical results on these algorithms.

•Jan 20, 2026•0 citations

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

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

Faster exact solution of sparse MaxCut and QUBO problems

Daniel Rehfeldt, Thorsten Koch, Yuji Shinano

Abstract The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems—by using mathematical programming techniques. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse maximum-cut and quadratic unconstrained binary optimization instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality.

Mathematical Programming Computation•Apr 15, 2023•38 citations

Faster exact solution of sparse MaxCut and QUBO problems

Daniel Rehfeldt, Thorsten Koch, Yuji Shinano

The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems -- by using mathematical programming techniques on digital computers. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse MaxCut and QUBO instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality.

arXiv:2202.02305•Feb 4, 2022•1 citation

SOLVING THE MAX-CUT PROBLEM USING THE QASPA ALGORITHM

Д. О. САПОЖНИК

A novel quantum algorithm named the Quantum Approximate Shift-Phase Algorithm (QASPA) is proposed for the approximate solution of the Max-Cut problem. The Max-Cut problem consists in partitioning the set of vertices into two subsets in such a way that the total weight of the edges connecting vertices from different subsets is maximized. This problem is known to be NP-complete and represents a combinatorial challenge. Classical solution algorithms require excessive computational time, rendering them inefficient for medium and large graphs. Approximate solution methods offer guaranteed approximation ratios but still face significant limitations in terms of accuracy and performance on larger graphs. The proposed algorithm features a simple scheme and a minimal number of optimized parameters. The input graph is represented by an adjacency matrix, after which the edge weights are linearly normalized to fixed phase angles. The quantum circuit begins by applying a Hadamard transform to each qubit, thereby creating an equal superposition of all possible partitions. Subsequently, for each pair of adjacent vertices, a sequence comprising a controlled NOT gate, a single-qubit rotation around the Y-axis by an angle proportional to the edge weight, and a second controlled NOT gate is applied. This encodes the phase information about the edge weights into the quantum state of the system. After circuit execution, the qubits are measured in the standard computational basis, and the resulting probability distribution allows the selection of the most probable partition as an approximate solution to the problem. Experimental studies conducted on quantum processor simulators have demonstrated that the proposed algorithm achieves accuracy comparable to the Variational Quantum Approximate Optimization Algorithm (QAOA) while significantly reducing computation time due to the absence of iterative parameter optimization. Moreover, as the graph size increases, the algorithm's runtime grows considerably slower compared to classical brute-force approaches and QAOA, confirming its potential for solving medium-sized Max-Cut problems.

Bulletin of National Technical University KhPI Series System Analysis Control and Information Technologies•Dec 29, 2025•0 citations
We study one of the most important NP-hard problem in combinatorial optimization problems, which is the maximum cut problem (Max-Cut). The combinatorial optimization problems can be solved by many methods; this paper was focused on two methods to solving the Max-Cut, the extended alternating direction method of multipliers (ADMM) and the branch and bound method (B&B). Numerical results from ADMM and B&B are obtained to find approximate solutions to Max-Cut with huge numbers of vertices and edges on several graphs. The groundwork of a study is to find the solution from the faster method of them. Finally, the ADMM is faster convergence than the B&B to get the approximate solution to Max-Cut.
This thesis investigates the use of semidefinite programming (SDP) for solving (variants of) the well-known stable set and max-cut problems. Chapter 2 considers a generalization of the stable set problem, and a corresponding SDP relaxation. Similarly, Chapter 3 considers a generalization of the max-cut problem that involves complex roots of unity. Various complex SDP relaxations of this generalized max-cut problem are studied. Chapter 4 provides approximation algorithms for the quantum generalization of the max-cut problem. These approximation algorithms employ a hierarchy of SDP relaxations for noncommutative polynomial optimization problems. Chapter 5 provides an SDP algorithm for computing bounds on the stability numbers of graphs. Chapter 6 provides an SDP algorithm for solving the MAX-SAT problem. Chapters 5 and 6 provide extensive numerical results on these algorithms.
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.
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.
Abstract The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems—by using mathematical programming techniques. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse maximum-cut and quadratic unconstrained binary optimization instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality.
The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems -- by using mathematical programming techniques on digital computers. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse MaxCut and QUBO instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality.
A novel quantum algorithm named the Quantum Approximate Shift-Phase Algorithm (QASPA) is proposed for the approximate solution of the Max-Cut problem. The Max-Cut problem consists in partitioning the set of vertices into two subsets in such a way that the total weight of the edges connecting vertices from different subsets is maximized. This problem is known to be NP-complete and represents a combinatorial challenge. Classical solution algorithms require excessive computational time, rendering them inefficient for medium and large graphs. Approximate solution methods offer guaranteed approximation ratios but still face significant limitations in terms of accuracy and performance on larger graphs. The proposed algorithm features a simple scheme and a minimal number of optimized parameters. The input graph is represented by an adjacency matrix, after which the edge weights are linearly normalized to fixed phase angles. The quantum circuit begins by applying a Hadamard transform to each qubit, thereby creating an equal superposition of all possible partitions. Subsequently, for each pair of adjacent vertices, a sequence comprising a controlled NOT gate, a single-qubit rotation around the Y-axis by an angle proportional to the edge weight, and a second controlled NOT gate is applied. This encodes the phase information about the edge weights into the quantum state of the system. After circuit execution, the qubits are measured in the standard computational basis, and the resulting probability distribution allows the selection of the most probable partition as an approximate solution to the problem. Experimental studies conducted on quantum processor simulators have demonstrated that the proposed algorithm achieves accuracy comparable to the Variational Quantum Approximate Optimization Algorithm (QAOA) while significantly reducing computation time due to the absence of iterative parameter optimization. Moreover, as the graph size increases, the algorithm's runtime grows considerably slower compared to classical brute-force approaches and QAOA, confirming its potential for solving medium-sized Max-Cut problems.