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:2401.13004 · Lecture notes in computer science

Utilizing Graph Sparsification for Pre-processing in Max Cut QUBO Solver

Vorapong Suppakitpaisarn, Jin‐Kao Hao

Published Jan 1, 2024• 1 citation
arXivHTMLPDF
DOI
10.1007/978-3-031-62912-9_22

Related papers

Quantum approximate optimization algorithm for the Max-Cut problem: a case study for random graph topologies

Καράς, Αλέξανδρος Α., Καράς, Αλέξανδρος Α.

•Jan 1, 2025•0 citations

From Maximum Cut to Maximum Independent Set

Chuixiong Wu, Jianan Wang, Fen Zuo

The Maximum Cut (Max-Cut) problem could be naturally expressed either in a Quadratic Unconstrained Binary Optimization (QUBO) formulation, or as an Ising model. It has long been known that the Maximum Independent Set (MIS) problem could also be related to a specific Ising model. Therefore, it would be natural to attack MIS with various Max-Cut/Ising solvers. It turns out that this strategy greatly improves the approximation for the independence number of random Erdős-Rényi graphs. It also exhibits perfect performance on a benchmark arising from coding theory. These results pave the way for further development of approximate quantum algorithms on MIS, and specifically on the corresponding coding problems.

arXiv:2408.06758•Aug 13, 2024•1 citation

Penalty and partitioning techniques to improve performance of QUBO solvers

Amit Verma, Mark W. Lewis

Discrete Optimization•Jun 29, 2020•77 citations

An FPGA Implementation of Fast 2D-Ising-Model Solver for the Max-Cut Problem

Hidenori Gyoten, Masayuki Hiromoto, Satō Takashi

IEICE Technical Report; IEICE Tech. Rep.•Feb 22, 2016•2 citations

An FPGA Implementation of Fast 2D-Ising-Model Solver for the Max-Cut Problem

英範 業天, 正之 廣本, 高史 佐藤

IEICE technical report. Speech•Feb 29, 2016•2 citations

A comprehensive benchmark of an Ising machine on the Max-Cut problem

Salwa Shaglel, Markus Kirsch, Mårten Winkler +4 more

QUBO formulations of combinatorial optimization problems allow for solving them using various quantum heuristics. While large-scale quantum computations are currently still out of reach, we can already numerically test such QUBO formulations on a perhaps surprisingly large scale. In this work, we benchmark Fujitsu’s Digital Annealer (DA) on the Max-Cut problem, which captures the main complexity of the QUBO problem. We make a comprehensive benchmark against leading other heuristic algorithms on graphs with up to 53,000 variables by focusing on the wall-clock time. Moreover, we compare the DA performance against published performance results of the D-Wave hybrid quantum-classical annealer and the recently proposed QIS3 heuristic. Based on performance statistics for over 2,000 graphs from the MQLib, we find that the DA yields competitive results. We hope that this benchmark demonstrates the extent to which large QUBO instances can be heuristically solved today, yielding consistent results across different solvers.

•Oct 21, 2025•0 citations
The Maximum Cut (Max-Cut) problem could be naturally expressed either in a Quadratic Unconstrained Binary Optimization (QUBO) formulation, or as an Ising model. It has long been known that the Maximum Independent Set (MIS) problem could also be related to a specific Ising model. Therefore, it would be natural to attack MIS with various Max-Cut/Ising solvers. It turns out that this strategy greatly improves the approximation for the independence number of random Erdős-Rényi graphs. It also exhibits perfect performance on a benchmark arising from coding theory. These results pave the way for further development of approximate quantum algorithms on MIS, and specifically on the corresponding coding problems.
QUBO formulations of combinatorial optimization problems allow for solving them using various quantum heuristics. While large-scale quantum computations are currently still out of reach, we can already numerically test such QUBO formulations on a perhaps surprisingly large scale. In this work, we benchmark Fujitsu’s Digital Annealer (DA) on the Max-Cut problem, which captures the main complexity of the QUBO problem. We make a comprehensive benchmark against leading other heuristic algorithms on graphs with up to 53,000 variables by focusing on the wall-clock time. Moreover, we compare the DA performance against published performance results of the D-Wave hybrid quantum-classical annealer and the recently proposed QIS3 heuristic. Based on performance statistics for over 2,000 graphs from the MQLib, we find that the DA yields competitive results. We hope that this benchmark demonstrates the extent to which large QUBO instances can be heuristically solved today, yielding consistent results across different solvers.