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

IEEE International Conference on Quantum Computing and Engineering (QCE)

Non-zero Coefficients Removing Method to Improve the Ising Machine Solving Performance

Kinya Iwata, Masashi Tawada, Nozomu Togawa

Published Sep 15, 2024• 2 citations
Publisher

Abstract

The performance of an Ising machine in solving combinatorial optimization problems is significantly influenced by the energy landscape of an input quadratic unconstrained binary optimization (QUBO). Previous studies have shown that the number of non-zero terms in QUBO can control the energy landscape. In this paper, we propose a QUBO conversion method, which efficiently removes non-zero coefficient terms in QUBO to improve the solving performance of Ising machines. Our pro-posed method uses the removal ratio parameter, which defines the amount of removed non-zero terms, and efficiently removes the non-zero coefficient terms in QUBO. We confirm the effectiveness of the proposed method compared to the conventional method using the capacitated vehicle routing problem (CVRP) on an Ising machine. Experimental results demonstrate that our proposed method improves the path length in CVRP up to 17% compared to the conventional method.

DOI
10.1109/qce60285.2024.10339

Related papers

QUBO Simplification by Singular Value Decomposition and Coefficient Elimination for Ising Machines

Shinnosuke Inaba, Takeru Ota, Nozomu Togawa

Ising machines, including quantum annealing machines, can efficiently solve combinatorial optimization problems by formulating them as Quadratic Unconstrained Binary Optimization (QUBO). However, it is known that the solving performance of Ising machines deteriorates as the energy landscape represented by the QUBObecomes more complex. Simplifying the coefficients of QUBOmatrix can improve the performance of solving combinatorial optimization problems using an Ising machine. In this paper, we propose QUBO simplification methods for Ising machines using singular value decomposition (SVD) and coefficient elimination based on their absolute value (ABS). The proposed SVD method simplifies QUBO by capturing the global structure of the QUBO matrix. QUBO is further simplified by combining it with the simple ABS method. The simplified QUBO is expected to have a less complex energy landscape, while maintaining the global structure of the original, enabling the Ising machine to efficiently find the (semi-)ground state.We demonstrate the numerical experiments using an Ising machine to evaluate the effectiveness of the SVD method alone, the ABS method alone, and the two methods combined.

IEEE Access•Jan 1, 2026•0 citations

A Constraint Partition Method for Combinatorial Optimization Problems

Makoto Onoda, Kazuhiko Komatsu, Masahito Kumagai +2 more

Ising machines have attracted much attention in recent years because of their potential in solving combinatorial optimization problems that are difficult to be solved using conventional computers. Ising machines solve the optimization problem that can be transformed into a quadratic unconstrained binary optimization (QUBO) problem. In the case of a problem with constraints, named a constraint problem, an objective function and constraint function with penalty coefficients are combined into a single Hamiltonian of a QUBO problem. When solving a constraint problem, the accuracy of the solution decreases compared to a QUBO problem with an objective function only. This is because penalty coefficients are set to excessively large values to prevent constraint violations. As a result, it becomes difficult to minimize the objective function. To solve this problem, this paper proposes a method that partitions constraint functions and reduces the value of the penalty coefficients. The performance evaluation using the traveling salesperson problem (TSP) with one-hot constraints demonstrates that the proposed method can improve the solution accuracy compared to the conventional method.

IEEE International Symposium on Embedded Multicore/Many-core Systems-on-Chip (MCSoC)•Dec 18, 2023•2 citations

Linearizing Binary Optimization Problems Using Variable Posets for Ising Machines

Kentaro Ohno, Nozomu Togawa

Ising machines are next-generation computers expected to efficiently sample near-optimal solutions of combinatorial optimization problems. Combinatorial optimization problems are modeled as quadratic unconstrained binary optimization (QUBO) problems to apply an Ising machine. However, current state-of-the-art Ising machines still often fail to output nearoptimal solutions due to the complicated energy landscape of QUBO problems. Furthermore, the physical implementation of Ising machines severely restricts the size of QUBO problems to be input as a result of limited hardware graph structures. In this study, we take a new approach to these challenges by injecting auxiliary penalties preserving the optimum, which reduces quadratic terms in QUBO objective functions. The process simultaneously simplifies the energy landscape of QUBO problems, allowing the search for near-optimal solutions, and makes QUBO problems sparser, facilitating encoding into Ising machines with restriction on the hardware graph structure. We propose linearization of QUBO problems using variable posets as an outcome of the approach. By applying the proposed method to synthetic QUBO instances and to multi-dimensional knapsack problems, we empirically validate the effects on enhancing minorembedding of QUBO problems and the performance of Ising machines.

arXiv:2307.05125•IEEE Transactions on Emerging Topics in Computing•May 30, 2024•4 citations

QUBO Simplification Method for Improving Solution Convergence Speed Using an Ising Machine

Shinnosuke Inaba, Takeru Ota, Chihiro Dogo +2 more

With the increasing emphasis on energy efficiency and sustainability, optimizing the energy supply of base stations, the major energy consumers in communication networks, has become a critical problem. In addition, for real-time and scalable energy optimization in sustainable base station systems, it is necessary to obtain highly-efficient solutions in a shorter time. We formulate the base station power optimization problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem, where the goal is to minimize a combination of power costs while satisfying operational constraints. Furthermore, to improve computational efficiency, we propose a QUBO simplification method that cuts down QUBO coefficients with small absolute values to zero. We solve both the original and simplified QUBOs using an Ising machine. Experimental results show that our QUBO simplification approach accelerates computation by up to 10 X on large-scale instances, with minimal degradation in solution quality.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations

Techniques to enhance a QUBO solver for permutation-based combinatorial optimization

Siong Thye Goh, Jianyuan Bo, Sabrish Gopalakrishnan +1 more

Many combinatorial optimization problems can be formulated as a problem to determine the order of sequence or to find a corresponding mapping of the objects. We call such problems permutation-based optimization problems. Many such problems can be formulated as a quadratic unconstrained binary optimization (QUBO) or Ising model by introducing a penalty coefficient to the permutation constraint terms. While classical and quantum annealing approaches have been proposed to solve QUBOs to date, they face issues with optimality and feasibility. Here we treat a given QUBO solver as a black box and propose techniques to enhance its performance. First, to ensure an effective search for good quality solutions, a smooth energy landscape is needed; we propose a data scaling approach that reduces the amplitudes of the input without compromising optimality. Second, we need to tune the penalty coefficient. In this paper, we illustrate that for certain problems, it suffices to tune the parameter by performing random sampling on the penalty coefficients to achieve good performance. Finally, to handle possible infeasibility of the solution, we introduce a polynomial-time projection algorithm. We apply these techniques along with a divide-and-conquer strategy to solve some large-scale permutation-based problems and present results for TSP and QAP.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 9, 2022•10 citations

An Ising-Machine-Based Solver of Vehicle Routing Problem With Balanced Pick-Up

Siya Bao, Masashi Tawada, Shu Tanaka +1 more

Vehicle routing applications are ubiquitous in the field of pick-up and delivery service. We focus on the vehicle routing problem with balanced pick-up called VRPBP which originates from the package pick-up service. The aim of the problem is not only to efficiently explore the shortest travel route but also to balance loads between depots and vehicles. These problems can be regarded as optimization problems, and recent developments in Ising machines, including quantum annealing machines, bring us a new opportunity to solve complex real-world optimization problems. In this paper, a two-phase method and a three-phase method using Ising machines are proposed for solving the VRPBP. As the applicability of current Ising machines is limited due to the small size of Ising spins and connectivities, we partition the complex problem into two or three sub-problems, and the key elements of each sub-problem are mapped onto quadratic unconstrained binary optimization (QUBO) models to fit in the structure of the Ising machines. We first compared the performances of the Ising machine on the standard TSP and CVRP datasets with a conventional state-of-the-art solver and three conventional methods. Then, we evaluated the performances of the proposed methods compared with five conventional method for solving the VRPBP. The results confirm the effectiveness of the two proposed methods in solving vehicle-routing-related optimization problems.

IEEE Transactions on Consumer Electronics•Nov 22, 2023•16 citations
The performance of an Ising machine in solving combinatorial optimization problems is significantly influenced by the energy landscape of an input quadratic unconstrained binary optimization (QUBO). Previous studies have shown that the number of non-zero terms in QUBO can control the energy landscape. In this paper, we propose a QUBO conversion method, which efficiently removes non-zero coefficient terms in QUBO to improve the solving performance of Ising machines. Our pro-posed method uses the removal ratio parameter, which defines the amount of removed non-zero terms, and efficiently removes the non-zero coefficient terms in QUBO. We confirm the effectiveness of the proposed method compared to the conventional method using the capacitated vehicle routing problem (CVRP) on an Ising machine. Experimental results demonstrate that our proposed method improves the path length in CVRP up to 17% compared to the conventional method.
Ising machines, including quantum annealing machines, can efficiently solve combinatorial optimization problems by formulating them as Quadratic Unconstrained Binary Optimization (QUBO). However, it is known that the solving performance of Ising machines deteriorates as the energy landscape represented by the QUBObecomes more complex. Simplifying the coefficients of QUBOmatrix can improve the performance of solving combinatorial optimization problems using an Ising machine. In this paper, we propose QUBO simplification methods for Ising machines using singular value decomposition (SVD) and coefficient elimination based on their absolute value (ABS). The proposed SVD method simplifies QUBO by capturing the global structure of the QUBO matrix. QUBO is further simplified by combining it with the simple ABS method. The simplified QUBO is expected to have a less complex energy landscape, while maintaining the global structure of the original, enabling the Ising machine to efficiently find the (semi-)ground state.We demonstrate the numerical experiments using an Ising machine to evaluate the effectiveness of the SVD method alone, the ABS method alone, and the two methods combined.
Ising machines have attracted much attention in recent years because of their potential in solving combinatorial optimization problems that are difficult to be solved using conventional computers. Ising machines solve the optimization problem that can be transformed into a quadratic unconstrained binary optimization (QUBO) problem. In the case of a problem with constraints, named a constraint problem, an objective function and constraint function with penalty coefficients are combined into a single Hamiltonian of a QUBO problem. When solving a constraint problem, the accuracy of the solution decreases compared to a QUBO problem with an objective function only. This is because penalty coefficients are set to excessively large values to prevent constraint violations. As a result, it becomes difficult to minimize the objective function. To solve this problem, this paper proposes a method that partitions constraint functions and reduces the value of the penalty coefficients. The performance evaluation using the traveling salesperson problem (TSP) with one-hot constraints demonstrates that the proposed method can improve the solution accuracy compared to the conventional method.
Ising machines are next-generation computers expected to efficiently sample near-optimal solutions of combinatorial optimization problems. Combinatorial optimization problems are modeled as quadratic unconstrained binary optimization (QUBO) problems to apply an Ising machine. However, current state-of-the-art Ising machines still often fail to output nearoptimal solutions due to the complicated energy landscape of QUBO problems. Furthermore, the physical implementation of Ising machines severely restricts the size of QUBO problems to be input as a result of limited hardware graph structures. In this study, we take a new approach to these challenges by injecting auxiliary penalties preserving the optimum, which reduces quadratic terms in QUBO objective functions. The process simultaneously simplifies the energy landscape of QUBO problems, allowing the search for near-optimal solutions, and makes QUBO problems sparser, facilitating encoding into Ising machines with restriction on the hardware graph structure. We propose linearization of QUBO problems using variable posets as an outcome of the approach. By applying the proposed method to synthetic QUBO instances and to multi-dimensional knapsack problems, we empirically validate the effects on enhancing minorembedding of QUBO problems and the performance of Ising machines.
With the increasing emphasis on energy efficiency and sustainability, optimizing the energy supply of base stations, the major energy consumers in communication networks, has become a critical problem. In addition, for real-time and scalable energy optimization in sustainable base station systems, it is necessary to obtain highly-efficient solutions in a shorter time. We formulate the base station power optimization problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem, where the goal is to minimize a combination of power costs while satisfying operational constraints. Furthermore, to improve computational efficiency, we propose a QUBO simplification method that cuts down QUBO coefficients with small absolute values to zero. We solve both the original and simplified QUBOs using an Ising machine. Experimental results show that our QUBO simplification approach accelerates computation by up to 10 X on large-scale instances, with minimal degradation in solution quality.
Many combinatorial optimization problems can be formulated as a problem to determine the order of sequence or to find a corresponding mapping of the objects. We call such problems permutation-based optimization problems. Many such problems can be formulated as a quadratic unconstrained binary optimization (QUBO) or Ising model by introducing a penalty coefficient to the permutation constraint terms. While classical and quantum annealing approaches have been proposed to solve QUBOs to date, they face issues with optimality and feasibility. Here we treat a given QUBO solver as a black box and propose techniques to enhance its performance. First, to ensure an effective search for good quality solutions, a smooth energy landscape is needed; we propose a data scaling approach that reduces the amplitudes of the input without compromising optimality. Second, we need to tune the penalty coefficient. In this paper, we illustrate that for certain problems, it suffices to tune the parameter by performing random sampling on the penalty coefficients to achieve good performance. Finally, to handle possible infeasibility of the solution, we introduce a polynomial-time projection algorithm. We apply these techniques along with a divide-and-conquer strategy to solve some large-scale permutation-based problems and present results for TSP and QAP.
Vehicle routing applications are ubiquitous in the field of pick-up and delivery service. We focus on the vehicle routing problem with balanced pick-up called VRPBP which originates from the package pick-up service. The aim of the problem is not only to efficiently explore the shortest travel route but also to balance loads between depots and vehicles. These problems can be regarded as optimization problems, and recent developments in Ising machines, including quantum annealing machines, bring us a new opportunity to solve complex real-world optimization problems. In this paper, a two-phase method and a three-phase method using Ising machines are proposed for solving the VRPBP. As the applicability of current Ising machines is limited due to the small size of Ising spins and connectivities, we partition the complex problem into two or three sub-problems, and the key elements of each sub-problem are mapped onto quadratic unconstrained binary optimization (QUBO) models to fit in the structure of the Ising machines. We first compared the performances of the Ising machine on the standard TSP and CVRP datasets with a conventional state-of-the-art solver and three conventional methods. Then, we evaluated the performances of the proposed methods compared with five conventional method for solving the VRPBP. The results confirm the effectiveness of the two proposed methods in solving vehicle-routing-related optimization problems.