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

Scientific Reports

Distance-based clustering using QUBO formulations

Nasa Matsumoto, Yohei Hamakawa, Kosuke Tatsumura, Kazue Kudo

Published Feb 17, 2022• 24 citations
Publisher

Abstract

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.

DOI
10.1038/s41598-022-06559-z

Related papers

Construction of SubQUBOs by K-Means Clustering of QUBO Variables

Yuko Kamishima, Shuta Kikuchi, Shu Tanaka

Ising machines are specialized solvers for combinatorial optimization problems (COPs), which are typically formulated as quadratic unconstrained binary optimization (QUBO) models. To enhance their performance, various methods have been proposed to construct subQUBOs by reducing the number of variables in the original QUBO. This study proposes a general subQUBO construction method applicable to a wide range of problems. The variables are clustered based on their interaction structure using theK-means clustering. A subQUBO is constructed from a randomly selected cluster and a pre-obtained tentative solution and then solved. This process of cluster selection and subQUBOs is performed iteratively. We evaluated the performance of the method on the quadratic assignment problem and compared it with two baselines: one that randomly reduces variables and another that directly solves the original QUBO without any variable reduction. Experimental evaluations demonstrated that the proposed method achieves high-accuracy solutions within the same computation time, particularly for large problem sizes.

IEEE Access•Jan 1, 2025•1 citation

Compressed sensing based on QUBO formulation

Kazue Kudo

Abstract Ising machines efficiently solve the combinatorial optimization problems described by the Ising model or the quadratic unconstrained binary optimization (QUBO) formulation. A hybrid method based on the QUBO formulation for compressed sensing is proposed. The proposed method comprises alternative steps of discrete and continuous optimization. In the discrete optimization step, the objective function is described by the QUBO formulation. Successful examples obtained via the proposed method are demonstrated. The performance of the proposed method depends highly on the initial conditions.

Journal of Physics Conference Series•Mar 1, 2022•1 citation

ICD2S: A Hybrid Ising-Classical-Machines Data-Driven QUBO Solver Method

Armin Abdollahi, Mehdi Kamal, Massoud Pedram

We present a heuristic algorithm designed to solve Quadratic Unconstrained Binary Optimization (QUBO) problems efficiently. The algorithm, referred to as IC-D2S, leverages a hybrid approach using Ising and classical machines to address very large problem sizes. Considering the practical limitation on the size of the Ising machine (IM), our algorithm partitions the QUBO problem into a collection of QUBO subproblems (called subQUBOs) and utilizes the IM to solve each subQUBO. Our proposed heuristic algorithm uses a set of control parameters to generate the subQUBOs and explore the search space. Also, it utilizes an annealer based on cosine waveform and applies a mutation operator at each step of the search to diversify the solution space and facilitate the process of finding the global minimum of the problem. We have evaluated the effectiveness of our IC-D2S algorithm on three large-sized problem sets and compared its efficiency in finding the (near-)optimal solution with three QUBO solvers. One of the solvers is a software-based algorithm (D2TS), while the other one (D-Wave) employs a similar approach to ours, utilizing both classical and Ising machines. The results demonstrate that for large-sized problems (≥ 5000) the proposed algorithm identifies superior solutions. Additionally, for smaller-sized problems (= 2500), IC-D2S efficiently finds the optimal solution in a significantly faster manner.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 20, 2025•2 citations

A Compressed QUBO Format for Traveling Salesperson Problems

Chu-Yuan Huang, Kazuhiko Komatsu, Makoto Onoda +3 more

Ising machines have recently gained a significant attention as a promising approach to combinatorial optimization problems, which are notoriously challenging for conventional computers to solve efficiently. In contrast to conventional computers, Ising machines operate based on the principles of the Ising model derived from statistical mechanics. Ising machines tackle combinatorial optimization problems by transforming them into Quadratic Unconstrained Binary Optimization (QUBO) formulations. The Traveling Salesperson Problem (TSP) is a prominent example of such optimization challenges and is widely recognized for its computational difficulty on conventional computers. Although Ising machines offer the potential for efficiently solving TSPs, the process of a QUBO formulation, namely the generation of a QUBO matrix that represents a TSP, demands substantial memory resources and considerable computation overheads. This study proposes a compressed QUBO format for TSP. This format reduces the dimensionality of the QUBO matrix for TSP by leveraging repetitive values, structural patterns, and sparsity within the matrix. The proposed format enhances the efficiency of data preprocessing, significantly reducing both the computational time required for QUBO matrix generation and the associated memory usage. These improvements contribute to the practical applicability of digital hardware-based Ising machines for addressing large-scale combinatorial optimization problems, thereby expanding their utility in solving complex real-world challenges.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum•Jun 3, 2025•1 citation

IC-D2S: A Hybrid Ising-Classical-Machines Data-Driven QUBO Solver Method

Armin Abdollahi, Mehdi Kamal, Massoud Pedram

We present a heuristic algorithm designed to solve Quadratic Unconstrained Binary Optimization (QUBO) problems efficiently. The algorithm, referred to as IC-D2S, leverages a hybrid approach using Ising and classical machines to address very large problem sizes. Considering the practical limitation on the size of the Ising machine(IM), our algorithm partitions the QUBO problem into a collection of QUBO subproblems (called subQUBOs) and utilizes the IM to solve each subQUBO. Our proposed heuristic algorithm uses a set of control parameters to generate the subQUBOs and explore the search space. Also, it utilizes an annealer based on cosine waveform and applies a mutation operator at each step of the search to diversify the solution space and facilitate the process of finding the global minimum of the problem. We have evaluated the effectiveness of our IC-D2S algorithm on three large-sized problem sets and compared its efficiency in finding the (near-)optimal solution with three QUBO solvers. One of the solvers is a software-based algorithm (D2TS), while the other one (D-Wave) employs a similar approach to ours, utilizing both classical and Ising machines. The results demonstrate that for large-sized problems (>= 5000) the proposed algorithm identifies superior solutions. Additionally, for smaller-sized problems (= 2500), IC-D2S efficiently finds the optimal solution in a significantly faster manner.

arXiv:2502.13947•Feb 19, 2025•0 citations

Graph Clustering Via QUBO and Digital Annealing

Pierre Miasnikof, Seo Woo Hong, Yuri Lawryshyn

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.

arXiv:2003.03872•Mar 9, 2020•2 citations
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.
Ising machines are specialized solvers for combinatorial optimization problems (COPs), which are typically formulated as quadratic unconstrained binary optimization (QUBO) models. To enhance their performance, various methods have been proposed to construct subQUBOs by reducing the number of variables in the original QUBO. This study proposes a general subQUBO construction method applicable to a wide range of problems. The variables are clustered based on their interaction structure using theK-means clustering. A subQUBO is constructed from a randomly selected cluster and a pre-obtained tentative solution and then solved. This process of cluster selection and subQUBOs is performed iteratively. We evaluated the performance of the method on the quadratic assignment problem and compared it with two baselines: one that randomly reduces variables and another that directly solves the original QUBO without any variable reduction. Experimental evaluations demonstrated that the proposed method achieves high-accuracy solutions within the same computation time, particularly for large problem sizes.
Abstract Ising machines efficiently solve the combinatorial optimization problems described by the Ising model or the quadratic unconstrained binary optimization (QUBO) formulation. A hybrid method based on the QUBO formulation for compressed sensing is proposed. The proposed method comprises alternative steps of discrete and continuous optimization. In the discrete optimization step, the objective function is described by the QUBO formulation. Successful examples obtained via the proposed method are demonstrated. The performance of the proposed method depends highly on the initial conditions.
We present a heuristic algorithm designed to solve Quadratic Unconstrained Binary Optimization (QUBO) problems efficiently. The algorithm, referred to as IC-D2S, leverages a hybrid approach using Ising and classical machines to address very large problem sizes. Considering the practical limitation on the size of the Ising machine (IM), our algorithm partitions the QUBO problem into a collection of QUBO subproblems (called subQUBOs) and utilizes the IM to solve each subQUBO. Our proposed heuristic algorithm uses a set of control parameters to generate the subQUBOs and explore the search space. Also, it utilizes an annealer based on cosine waveform and applies a mutation operator at each step of the search to diversify the solution space and facilitate the process of finding the global minimum of the problem. We have evaluated the effectiveness of our IC-D2S algorithm on three large-sized problem sets and compared its efficiency in finding the (near-)optimal solution with three QUBO solvers. One of the solvers is a software-based algorithm (D2TS), while the other one (D-Wave) employs a similar approach to ours, utilizing both classical and Ising machines. The results demonstrate that for large-sized problems (≥ 5000) the proposed algorithm identifies superior solutions. Additionally, for smaller-sized problems (= 2500), IC-D2S efficiently finds the optimal solution in a significantly faster manner.
Ising machines have recently gained a significant attention as a promising approach to combinatorial optimization problems, which are notoriously challenging for conventional computers to solve efficiently. In contrast to conventional computers, Ising machines operate based on the principles of the Ising model derived from statistical mechanics. Ising machines tackle combinatorial optimization problems by transforming them into Quadratic Unconstrained Binary Optimization (QUBO) formulations. The Traveling Salesperson Problem (TSP) is a prominent example of such optimization challenges and is widely recognized for its computational difficulty on conventional computers. Although Ising machines offer the potential for efficiently solving TSPs, the process of a QUBO formulation, namely the generation of a QUBO matrix that represents a TSP, demands substantial memory resources and considerable computation overheads. This study proposes a compressed QUBO format for TSP. This format reduces the dimensionality of the QUBO matrix for TSP by leveraging repetitive values, structural patterns, and sparsity within the matrix. The proposed format enhances the efficiency of data preprocessing, significantly reducing both the computational time required for QUBO matrix generation and the associated memory usage. These improvements contribute to the practical applicability of digital hardware-based Ising machines for addressing large-scale combinatorial optimization problems, thereby expanding their utility in solving complex real-world challenges.
We present a heuristic algorithm designed to solve Quadratic Unconstrained Binary Optimization (QUBO) problems efficiently. The algorithm, referred to as IC-D2S, leverages a hybrid approach using Ising and classical machines to address very large problem sizes. Considering the practical limitation on the size of the Ising machine(IM), our algorithm partitions the QUBO problem into a collection of QUBO subproblems (called subQUBOs) and utilizes the IM to solve each subQUBO. Our proposed heuristic algorithm uses a set of control parameters to generate the subQUBOs and explore the search space. Also, it utilizes an annealer based on cosine waveform and applies a mutation operator at each step of the search to diversify the solution space and facilitate the process of finding the global minimum of the problem. We have evaluated the effectiveness of our IC-D2S algorithm on three large-sized problem sets and compared its efficiency in finding the (near-)optimal solution with three QUBO solvers. One of the solvers is a software-based algorithm (D2TS), while the other one (D-Wave) employs a similar approach to ours, utilizing both classical and Ising machines. The results demonstrate that for large-sized problems (>= 5000) the proposed algorithm identifies superior solutions. Additionally, for smaller-sized problems (= 2500), IC-D2S efficiently finds the optimal solution in a significantly faster manner.
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.