IC-D 2 S: A Hybrid Ising-Classical-Machines Data-Driven QUBO Solver Method
Armin Abdollahi, Mehdi Kamal, Massoud Pedram · 2025
Read IC-D 2 S: A Hybrid Ising-Classical-Machines Data-Driven QUBO Solver Method by Armin Abdollahi, Mehdi Kamal, Massoud Pedram (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-13947.txt.
Introduction
Armin Abdollahi, Mehdi Kamal, and Massoud Pedram wrote a 2025 computing paper on solving very large binary optimization problems by splitting them between quantum style and classical hardware. Such problems, known as QUBO, cover scheduling, routing, and chip design, but Ising machines that attack them have limited size.
Their method, IC-D2S, slices a big problem into sub problems sized for the Ising machine, then stitches the answers together. A set of control parameters steers how the slices are made, and a cosine shaped annealing schedule plus a mutation step keep the search from getting stuck. On three large problem sets, the method matched or beat a software solver and a commercial quantum hybrid service. The work targets problems too big for any single machine.
Catalog record
| CREATOR | Armin Abdollahi, Mehdi Kamal, Massoud Pedram |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-13947
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
IC-D 2 S: A Hybrid Ising-Classical-Machines Data-Driven QUBO Solver Method Armin Abdollahi, Mehdi Kamal, Massoud Pedram Abstract . We present a heuristic algorithm designed to solve Quadratic Unconstrained Binary Optimization (QUBO) problems efficiently. The algorithm, referred to as IC-D 2 S, 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-D 2 S 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 (D 2 TS), 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 \geq 5000 ) the proposed algorithm identifies superior solutions. Additionally, for smaller-sized problems ( = 2500 =2500 ), IC-D 2 S efficiently finds the optimal solution in a significantly faster manner. Conference: 30th Asia and South Pacific Design Automation Conference; January 20–23, 2025; Tokyo, Japan 30th Asia and South Pacific Design Automation Conference (ASPDAC ’25), January 20–23, 2025, Tokyo, Japan DOI: 10.1145/3658617.3697777 ISBN: 979-8-4007-0635-6/25/01 CCS: Theory of computation Theory and algorithms for application domains CCS: Computing methodologies Distributed computing methodologies CCS: Hardware Emerging technologies 1. Introduction Quadratic Unconstrained Binary Optimization (QUBO) problems involve optimizing a quadratic objective function with binary variables, making them relevant to many real-world scenarios. As NP-complete problems, they lack efficient polynomial-time algorithms for exact solutions ( 1 ) . Many NP-complete problems, such as the graph coloring, Traveling Salesman, exact cover, and knapsack problems, can be mapped to QUBO ( 2 ) ( 1 ) . Finding the optimal binary values to minimize or maximize the quadratic objective function is computationally intractable, highlighting the difficulty of QUBO optimization. Traditional methods for solving QUBO problems include branch-and-bound and stochastic optimization strategies like Tabu Search ( 3 , 4 ) , Ant Colony ( 5 ) , and Genetic Algorithms ( 6 ) , all performed on conventional computing machines. Ising machines are specialized computational devices inspired by the Ising model from statistical physics, designed to solve optimization and combinatorial problems cast as QUBO problems. These machines employ an array of interconnected nodes, typically binary elements or quantum bits (qubits), to search for optimal solutions by manipulating their nodes’ states (e.g., the qubit’s spin in a quantum Ising machine.) Ising machines find a configuration of nodes’ states that minimizes a system’s energy, making them a promising tool for tackling complex optimization challenges. By mapping QUBO problems to the Ising formulation, the QUBO could be solved directly on the Ising machine hardware. Due to the applicability and efficiency of the Ising machine, hardware structures using MOS devices (e.g., ( 7 , 8 , 9 , 10 , 11 ) ), memristor-based systems (e.g., ( 12 ) ), quantum devices (e.g., ( 13 ) ), classical superconductor devices e.g., ( 14 ) ), and optical devices (e.g., ( 15 , 16 , 17 ) ) have been suggested. However, these machines are limited by the relatively small number of nodes (spins) that can be modeled, prompting exploring alternative strategies, such as decomposing a large QUBO problem into a plurality of sub-problems (which we call the subQUBO approach.) For example, the D-Wave quantum computer has only 5,000 nodes with a limited number of couplers ( 18 ) , which limits the size of QUBO problems that can be directly solved on it. The subQUBO approach employs a hybrid framework, combining various optimization techniques with awareness about the hardware limits to navigate the complete QUBO solution space ( 19 ) , wherein a portion of the QUBO problem is dispatched to the hardware in each iteration, with this iterative process continuing until a complete solution is obtained ( 13 ) . This paper presents a data-driven heuristic search algorithm (called IC-D 2 S) to solve QUBO Problems on a hybrid fabric comprising Ising and conventional processing machines. Using a set of control parameters, this search algorithm uses Tabu search to generate subQUBOs to be mapped onto the Ising machine. These parameters also apply efficient mutation operators to escape local minima. The remainder of this paper is organized as follows. Section 2 will provide Background knowledge and review some related works. Section 3 explains the proposed algorithm’s details. Sections 4 and 5 discuss the results and conclude the paper. 2. Background and Related Works 2.1. QUBO Problem Equation ( 1 ) presents the general formulation of the QUBO problem. In this equation, the matrix Q (i.e., weight matrix), sized n\times n , comprises integer values that encompass both positive and negative integers. The vector x , also of size n , consists of binary values, with each element x_{i} being either one or zero. Thus, the objective is to determine the solution that minimizes the x^{T}Qx problem, effectively solving the QUBO problem. Thus, the primary aim is to identify the vector x that minimizes the function f(x) . (1) \small f(x)=\sum_{i=1}^{n}Q_{ii}x_{i}+\sum_{i=1}^{n}\sum_{j\neq i}^{n}Q_{ij}x_{i}x_{j}\ 2.2. Ising formulation Equation ( 2 ) shows the general Ising formulation, where E represents the system’s energy. i and j are indices for individual spins (nodes). J_{ij} is a coupling constant determining the interaction strength between spins i and j . It is typically a symmetric matrix describing the interactions between all spins. s_{i} and s_{j} are individual spin values, often taking values of +1 or -1 . h_{i} represents the strength of an external magnetic field acting on spin i . The transformation from Ising to QUBO is easy, and the \{0,1\} -valued variables of QUBO can be transformed to \{-1,1\} -valued variables of Ising formulation as shown in Equation ( 3 ). (2) \small E=-\sum_{i}\sum_{j}J_{ij}s_{i}s_{j}-\sum_{i}h_{i}s_{i} (3) \small s_{i}=2\times x_{i}-1 2.3. Related Work We review prior works on hybridizing classical processors and Ising machines to solve the QUBO problems. It should be stated that there are prior works on solving QUBO using only classical processors, such as ( 3 ) and ( 5 ) . In ( 3 ) , a search algorithm denoted as D 2 TS, has been proposed. This paper proposes a fast and efficient modified Tabu search while utilizing a unique perturbation-based diversification strategy. It shows promising results in solving large-size QUBO problems on a classical machine with few search epochs. In ( 13 ) , a subQUBO approach was presented to solve the QUBO optimization problem. This approach uses multiple Quantum annealer hardware to solve the subQUBO problems in combination with a Tabu search and a randomizer to find the solution for the QUBO. Another subQUBO approach for solving the Trip Planning Problems (TPP) using Ising machines has been introduced in