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

Graph Clustering Via QUBO and Digital Annealing

Pierre Miasnikof, Seo Woo Hong, Yuri Lawryshyn

Published Mar 9, 2020• 2 citations
arXivHTMLPDF

Abstract

This article empirically examines the computational cost of solving a known hard problem, graph clustering, using novel purpose-built computer hardware. We express the graph clustering problem as an intra-cluster distance or dissimilarity minimization problem. We formulate our poblem as a quadratic unconstrained binary optimization problem and employ a novel computer architecture to obtain a numerical solution. Our starting point is a clustering formulation from the literature. This formulation is then converted to a quadratic unconstrained binary optimization formulation. Finally, we use a novel purpose-built computer architecture to obtain numerical solutions. For benchmarking purposes, we also compare computational performances to those obtained using a commercial solver, Gurobi, running on conventional hardware. Our initial results indicate the purpose-built hardware provides equivalent solutions to the commercial solver, but in a very small fraction of the time required.

DOI
10.48550/arxiv.2003.03872

Related papers

Cluster-based Index Tracking Via QUBO and Digital Annealing

Seo Woo Hong

The cardinality constrained index-tracking problem seeks to find a combination of financial assets to replicate the return of a broad market index while using only a small subset of the asset universe. However, finding this combination of assets is NP-hard. In this thesis, we show the computational efficacy of solving a quadratic unconstrained binary optimization (QUBO) problem using purpose-built hardware Digital Annealer. We express an intra-cluster distance minimization problem as a QUBO problem and examine the computational performance between Digital Annealer and a commercial solver Gurobi running on conventional hardware. Moreover, we develop a new framework to solve the cardinality constrained index-tracking problem using the quadratic k-medoids clustering method on a market graph. To circumvent the nature of NP-hardness, we use the penalty method to formulate the problem as a QUBO problem, allowing us to utilize purpose-built hardware to solve the problem.

•Mar 1, 2021•0 citations

Binary matrix factorization on special purpose hardware

Osman Asif Malik, Hayato Ushijima‐Mwesigwa, Arnab Roy +2 more

Many fundamental problems in data mining can be reduced to one or more NP-hard combinatorial optimization problems. Recent advances in novel technologies such as quantum and quantum-inspired hardware promise a substantial speedup for solving these problems compared to when using general purpose computers but often require the problem to be modeled in a special form, such as an Ising or quadratic unconstrained binary optimization (QUBO) model, in order to take advantage of these devices. In this work, we focus on the important binary matrix factorization (BMF) problem which has many applications in data mining. We propose two QUBO formulations for BMF. We show how clustering constraints can easily be incorporated into these formulations. The special purpose hardware we consider is limited in the number of variables it can handle which presents a challenge when factorizing large matrices. We propose a sampling based approach to overcome this challenge, allowing us to factorize large rectangular matrices. In addition to these methods, we also propose a simple baseline algorithm which outperforms our more sophisticated methods in a few situations. We run experiments on the Fujitsu Digital Annealer, a quantum-inspired complementary metal-oxide-semiconductor (CMOS) annealer, on both synthetic and real data, including gene expression data. These experiments show that our approach is able to produce more accurate BMFs than competing methods.

arXiv:2010.08693•PLoS ONE•Dec 16, 2021•6 citations

Distance-based clustering using QUBO formulations

Nasa Matsumoto, Yohei Hamakawa, Kosuke Tatsumura +1 more

In computer science, clustering is a technique for grouping data. Ising machines can solve distance-based clustering problems described by quadratic unconstrained binary optimization (QUBO) formulations. A typical simple method using an Ising machine makes each cluster size equal and is not suitable for clustering unevenly distributed data. We propose a new clustering method that provides better performance than the simple method, especially for unevenly distributed data. The proposed method is a hybrid algorithm including an iterative process that comprises solving a discrete optimization problem with an Ising machine and calculating parameters with a general-purpose computer. To minimize the communication overhead between the Ising machine and the general-purpose computer, we employed a low-latency Ising machine implementing the simulated bifurcation algorithm with a field-programmable gate array attached to a local server. The proposed method results in clustering 200 unevenly distributed data points with a clustering score 18% higher than that of the simple method. The discrete optimization with 2000 variables is performed 100 times per iteration, and the overhead time is reduced to approximately 20% of the total execution time. These results suggest that hybrid algorithms using Ising machines can efficiently solve practical optimization problems.

Scientific Reports•Feb 17, 2022•24 citations

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

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

Abstract Quadratic unconstrained binary optimization (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 2000 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.

arXiv:2507.22117•New Journal of Physics•Jun 5, 2026•0 citations

Constrained-optimization Approach Delivers Superior Classical Performance for Graph Partitioning via Quantum-ready Method

Uchenna Chukwu, Raouf Dridi, Jesse Berwald +5 more

Graph partitioning is one of an important set of well-known compute-intense (NP-hard) graph problems that devolve to discrete constrained optimization. We sampled solutions to the problem via two different quantum-ready methods to understand the strengths and weaknesses of each method. First we formulated and sampled the problem as a quadratic unconstrained binary optimization (QUBO) problem, via the best known QUBO formulation, using a best-in-class QUBO sampler running purely classically. Second, we formulated the problem at a higher level, as a set of constraints and an objective function, and sampled it with a recently developed constrained-optimization sampler (which generates QUBOs and also samples them classically). We find that both approaches often deliver better partitions than the purpose-built classical graph partitioners. Further, we find that the constrained-optimization approach is often able to deliver better partitions in less time than the bespoke-QUBO approach, without specific knowledge of the graph-partitioning problem. Stepping back from graph partitioning itself, one key question is whether bespoke algorithms for high-value problems or general tools for classes of problems are more likely to deliver the power of QCs to a broad market of real-world users. We believe this early evidence, though anecdotal, supports the proposition that general tools may contribute significant benefit to a range of problems, expanding the impact of QCs on industry and society. The fact that this benefit is independent of the low-level sampler employed, whether classical software or one of a variety of QC architectures, reinforces the need for further work on high-level optimization. The commercial availability in the cloud of such software today, delivering superior classical performance for some problems, enables quantum-forward organizations to migrate to quantum-ready methods now, accelerating progress toward quantum advantage and ensuring sampler software evolves to address the problems such organizations value.

arXiv:2006.15067•IEEE High Performance Extreme Computing Conference•Sep 22, 2020•9 citations

Logical and Inequality Implications for Reducing the Size and Complexity of Quadratic Unconstrained Binary Optimization Problems

Fred Glover, Mark W. Lewis, Gary A. Kochenberger

The quadratic unconstrained binary optimization (QUBO) problem arises in diverse optimization applications ranging from Ising spin problems to classical problems in graph theory and binary discrete optimization. The use of preprocessing to transform the graph representing the QUBO problem into a smaller equivalent graph is important for improving solution quality and time for both exact and metaheuristic algorithms and is a step towards mapping large scale QUBO to hardware graphs used in quantum annealing computers. In an earlier paper (Lewis and Glover, 2016) a set of rules was introduced that achieved significant QUBO reductions as verified through computational testing. Here this work is extended with additional rules that provide further reductions that succeed in exactly solving 10% of the benchmark QUBO problems. An algorithm and associated data structures to efficiently implement the entire set of rules is detailed and computational experiments are reported that demonstrate their efficacy.

arXiv:1705.09545•May 26, 2017•0 citations
This article empirically examines the computational cost of solving a known hard problem, graph clustering, using novel purpose-built computer hardware. We express the graph clustering problem as an intra-cluster distance or dissimilarity minimization problem. We formulate our poblem as a quadratic unconstrained binary optimization problem and employ a novel computer architecture to obtain a numerical solution. Our starting point is a clustering formulation from the literature. This formulation is then converted to a quadratic unconstrained binary optimization formulation. Finally, we use a novel purpose-built computer architecture to obtain numerical solutions. For benchmarking purposes, we also compare computational performances to those obtained using a commercial solver, Gurobi, running on conventional hardware. Our initial results indicate the purpose-built hardware provides equivalent solutions to the commercial solver, but in a very small fraction of the time required.
The cardinality constrained index-tracking problem seeks to find a combination of financial assets to replicate the return of a broad market index while using only a small subset of the asset universe. However, finding this combination of assets is NP-hard. In this thesis, we show the computational efficacy of solving a quadratic unconstrained binary optimization (QUBO) problem using purpose-built hardware Digital Annealer. We express an intra-cluster distance minimization problem as a QUBO problem and examine the computational performance between Digital Annealer and a commercial solver Gurobi running on conventional hardware. Moreover, we develop a new framework to solve the cardinality constrained index-tracking problem using the quadratic k-medoids clustering method on a market graph. To circumvent the nature of NP-hardness, we use the penalty method to formulate the problem as a QUBO problem, allowing us to utilize purpose-built hardware to solve the problem.
Many fundamental problems in data mining can be reduced to one or more NP-hard combinatorial optimization problems. Recent advances in novel technologies such as quantum and quantum-inspired hardware promise a substantial speedup for solving these problems compared to when using general purpose computers but often require the problem to be modeled in a special form, such as an Ising or quadratic unconstrained binary optimization (QUBO) model, in order to take advantage of these devices. In this work, we focus on the important binary matrix factorization (BMF) problem which has many applications in data mining. We propose two QUBO formulations for BMF. We show how clustering constraints can easily be incorporated into these formulations. The special purpose hardware we consider is limited in the number of variables it can handle which presents a challenge when factorizing large matrices. We propose a sampling based approach to overcome this challenge, allowing us to factorize large rectangular matrices. In addition to these methods, we also propose a simple baseline algorithm which outperforms our more sophisticated methods in a few situations. We run experiments on the Fujitsu Digital Annealer, a quantum-inspired complementary metal-oxide-semiconductor (CMOS) annealer, on both synthetic and real data, including gene expression data. These experiments show that our approach is able to produce more accurate BMFs than competing methods.
In computer science, clustering is a technique for grouping data. Ising machines can solve distance-based clustering problems described by quadratic unconstrained binary optimization (QUBO) formulations. A typical simple method using an Ising machine makes each cluster size equal and is not suitable for clustering unevenly distributed data. We propose a new clustering method that provides better performance than the simple method, especially for unevenly distributed data. The proposed method is a hybrid algorithm including an iterative process that comprises solving a discrete optimization problem with an Ising machine and calculating parameters with a general-purpose computer. To minimize the communication overhead between the Ising machine and the general-purpose computer, we employed a low-latency Ising machine implementing the simulated bifurcation algorithm with a field-programmable gate array attached to a local server. The proposed method results in clustering 200 unevenly distributed data points with a clustering score 18% higher than that of the simple method. The discrete optimization with 2000 variables is performed 100 times per iteration, and the overhead time is reduced to approximately 20% of the total execution time. These results suggest that hybrid algorithms using Ising machines can efficiently solve practical optimization problems.
Abstract Quadratic unconstrained binary optimization (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 2000 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.
Graph partitioning is one of an important set of well-known compute-intense (NP-hard) graph problems that devolve to discrete constrained optimization. We sampled solutions to the problem via two different quantum-ready methods to understand the strengths and weaknesses of each method. First we formulated and sampled the problem as a quadratic unconstrained binary optimization (QUBO) problem, via the best known QUBO formulation, using a best-in-class QUBO sampler running purely classically. Second, we formulated the problem at a higher level, as a set of constraints and an objective function, and sampled it with a recently developed constrained-optimization sampler (which generates QUBOs and also samples them classically). We find that both approaches often deliver better partitions than the purpose-built classical graph partitioners. Further, we find that the constrained-optimization approach is often able to deliver better partitions in less time than the bespoke-QUBO approach, without specific knowledge of the graph-partitioning problem. Stepping back from graph partitioning itself, one key question is whether bespoke algorithms for high-value problems or general tools for classes of problems are more likely to deliver the power of QCs to a broad market of real-world users. We believe this early evidence, though anecdotal, supports the proposition that general tools may contribute significant benefit to a range of problems, expanding the impact of QCs on industry and society. The fact that this benefit is independent of the low-level sampler employed, whether classical software or one of a variety of QC architectures, reinforces the need for further work on high-level optimization. The commercial availability in the cloud of such software today, delivering superior classical performance for some problems, enables quantum-forward organizations to migrate to quantum-ready methods now, accelerating progress toward quantum advantage and ensuring sampler software evolves to address the problems such organizations value.
The quadratic unconstrained binary optimization (QUBO) problem arises in diverse optimization applications ranging from Ising spin problems to classical problems in graph theory and binary discrete optimization. The use of preprocessing to transform the graph representing the QUBO problem into a smaller equivalent graph is important for improving solution quality and time for both exact and metaheuristic algorithms and is a step towards mapping large scale QUBO to hardware graphs used in quantum annealing computers. In an earlier paper (Lewis and Glover, 2016) a set of rules was introduced that achieved significant QUBO reductions as verified through computational testing. Here this work is extended with additional rules that provide further reductions that succeed in exactly solving 10% of the benchmark QUBO problems. An algorithm and associated data structures to efficiently implement the entire set of rules is detailed and computational experiments are reported that demonstrate their efficacy.