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 Symposium on Parallel & Distributed Processing, Workshops and Phd Forum

A Work-Time Optimal Parallel Exhaustive Search Algorithm for the QUBO and the Ising model, with GPU implementation

Masaki Tao, Koji Nakano, Yasuaki Ito, Ryota Yasudo, Masaru Tatekawa, Ryota Katsuki, Takashi Yazane, Yoko Inaba

Published May 1, 2020• 16 citations
Publisher

Abstract

The main contribution of this paper is to present a simple exhaustive search algorithm for the quadratic unconstraint binary optimization (QUBO) problem. It computes the values of the objective function E(X) for all n-bit input vector X in O(2n) time. Since Ω(2n) time is necessary to output E(X) for all 2nvectors X, this sequential algorithm is optimal. We also present a work-time optimal parallel algorithm running O(log n) time using 2n/ log n processors on the CREW-PRAM. This parallel algorithm is work optimal, because the total number of computational operations is equal to the running time of the optimal sequential algorithm. Also, it is time optimal because any parallel algorithm using any large number of processors takes at least Ω(log n) time for evaluating E(X). Further, we have implemented this parallel algorithm to run on the GPU. The experimental results on NVIDIA GeForce RTX 2080Ti GPU show that our GPU implementation runs more than 1000 times faster than the sequential algorithm running on Intel Corei7-8700K CPU(3.70GHz) for the QUBO with nbit vector whenever n ≥ 33. We also compare our exhaustive search parallel algorithm with several non-exhaustive search approaches for solving the QUBO including D-Wave 2000Q quantum annealer, simulated annealing algorithm, and Gurobi optimizer.

DOI
10.1109/ipdpsw50202.2020.00098

Related papers

Adaptive Bulk Search: Solving Quadratic Unconstrained Binary Optimization Problems on Multiple GPUs

Ryota Yasudo, Koji Nakano, Yasuaki Ito +4 more

The quadratic unconstrained binary optimization (QUBO) is recently gathering attention in conjunction with quantum annealing (QA), since it is equivalent to finding the ground state of an Ising model. Due to the limitation of current QA systems, classical computers may outperform them. Researchers have thus been proposed to solve QUBO on FPGAs, GPUs, and special purpose processors. In this paper, we propose an adaptive bulk search (ABS), a framework for solving QUBO that can perform many searches in parallel on multiple GPUs. It supports fully-connected Ising models with up to 32k spins and 16-bit weights. In our ABS, a CPU host performs genetic algorithm (GA) while GPUs asynchronously perform local searches. A bottleneck for solving QUBO exists in the evaluation of the energy function, which requires computational cost for each solution. We show this can be reduced to in our ABS. The experimental results show that, with four NVIDIA GeForce RTX 2080 Ti GPUs, our framework can search up to 1.24 × 1012 solutions per second. We also show that our system quickly solves maximum cut and traveling salesman problems.

Proceedings of the International Conference on Parallel Processing•Aug 9, 2020•12 citations

Solving the sparse QUBO on multiple GPUs for Simulating a Quantum Annealer

Tomohiro Imanaga, Koji Nakano, Ryota Yasudo +6 more

Quadratic Unconstraint Binary Optimization (QUBO) is a combinatorial optimization problem such that an$n\times n$upper triangle matrix$W$is given and the objective is to find an n-bit vector$X$that minimizes the energy value$E(X)=X^{T}WX$. A QUBO instance$W$is sparse if instance$W$has few non-zero elements. The D-Wave 2000$Q$is a quantum annealer that can solve 2048-bit sparse QUBO instances represented as a Chimera graph topology. We present a sparse QUBO solver running on GPUs for 2048-bit sparse QUBO with a Chimera graph topology. We have evaluated the performance of our sparse QUBO solver and the D-Wave 2000Q for solving 2048-bit QUBO instances with various resolutions. The experimental results show that our sparse QUBO solver running on a GPU cloud server with 8 NVIDIA A100 GPUs can find optimal solutions in less than 3ms for all instances while the D-Wave 2000$Q$cannot find them in 996.7ms. Hence, our QUBO solver can find better solutions than the D-Wave 2000Q in less than 1/300 running time. We can think that our QUBO solver is a quantum annealer simulator with better performance in terms of the accuracy of solutions and the running time. Our result implies that quantum annealer D-Wave 2000$Q$does not achieve quantum supremacy yet.

International Symposium on Computing and Networking•Nov 1, 2021•9 citations

Diverse Adaptive Bulk Search: a Framework for Solving QUBO Problems on Multiple GPUs

Koji Nakano, Daisuke Takafuji, Yasuaki Ito +5 more

Quadratic Unconstrained Binary Optimization (QUBO) is a combinatorial optimization to find an optimal binary solution vector that minimizes the energy value defined by a quadratic formula of binary variables in the vector. As many NP-hard problems can be reduced to QUBO problems, considerable research has gone into developing QUBO solvers running on various computing platforms such as quantum devices, ASICs, FPGAs, GPUs, and optical fibers. This paper presents a framework called Diverse Adaptive Bulk Search (DABS), which has the potential to find optimal solutions of many types of QUBO problems. Our DABS solver employs a genetic algorithm-based search algorithm featuring three diverse strategies: multiple search algorithms, multiple genetic operations, and multiple solution pools. During the execution of the solver, search algorithms and genetic operations that succeeded in finding good solutions are automatically selected to obtain better solutions. Moreover, search algorithms traverse between different solution pools to find good solutions. We have implemented our DABS solver to run on multiple GPUs. Experimental evaluations using eight NVIDIA A100 GPUs confirm that our DABS solver succeeds in finding optimal or potentially optimal solutions for three types of QUBO problems.

arXiv:2207.03069•IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum•May 1, 2023•20 citations

Graph-theoretic Formulation of QUBO for Scalable Local Search on GPUs

Ryota Yasudo, Koji Nakano, Yasuaki Ito +5 more

Heuristic solvers of the Quadratic Unconstrained Binary Optimization (QUBO) problems have been rapidly studied because of their potentialities to solve a wide range of com-binatorial optimization problems in a unified manner. QUBO solvers, however, face a limitation in the numbers of variables. To overcome this limitation, we reformulate QUBO as a maximum weight induced subgraph problem (MISG) and propose a graph-theoretic approach for solving MISG. It is a problem to find an induced subgraph with the maximum total weight for a given edge-weighted undirected graph. Naive local search that updates only one vertex at a time requires many iterations to obtain good solutions for large-scale problems. To accelerate it, we introduce a new technique to update multiple vertices that can improve the solution at the same time. We have implemented a MISG solver based on our algorithm on NVIDIA A100 GPUs, where flip operations are parallelized with GPU multithreaded computing. Our solver is scalable and supports up to 230(1G) variables. Our results show that our algorithm outperforms the Gurobi optimizer in terms of solution qualities and the execution time.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum•May 1, 2022•6 citations

Solving QUBO on the Loihi 2 Neuromorphic Processor

A.R. De Pierro, Philipp Stratmann, G. A. Fonseca Guerra +4 more

In this article, we describe an algorithm for solving Quadratic Unconstrained Binary Optimization problems on the Intel Loihi 2 neuromorphic processor. The solver is based on a hardware-aware fine-grained parallel simulated annealing algorithm developed for Intel's neuromorphic research chip Loihi 2. Preliminary results show that our approach can generate feasible solutions in as little as 1 ms and up to 37x more energy efficient compared to two baseline solvers running on a CPU. These advantages could be especially relevant for size-, weight-, and power-constrained edge computing applications.

arXiv:2408.03076•Aug 6, 2024•2 citations

Binary optimization by momentum annealing

Takuya Okuyama, Tomohiro Sonobe, Ken‐ichi Kawarabayashi +1 more

One of the vital roles of computing is to solve large-scale combinatorial optimization problems in a short time. In recent years, methods have been proposed that map optimization problems to ones of searching for the ground state of an Ising model by using a stochastic process. Simulated annealing (SA) is a representative algorithm. However, it is inherently difficult to perform a parallel search. Here we propose an algorithm called momentum annealing (MA), which, unlike SA, updates all spins of fully connected Ising models simultaneously and can be implemented on GPUs that are widely used for scientific computing. MA running in parallel on GPUs is 250 times faster than SA running on a modern CPU at solving problems involving 100 000 spin Ising models.

Physical review. E•Jul 10, 2019•92 citations
The main contribution of this paper is to present a simple exhaustive search algorithm for the quadratic unconstraint binary optimization (QUBO) problem. It computes the values of the objective function E(X) for all n-bit input vector X in O(2n) time. Since Ω(2n) time is necessary to output E(X) for all 2nvectors X, this sequential algorithm is optimal. We also present a work-time optimal parallel algorithm running O(log n) time using 2n/ log n processors on the CREW-PRAM. This parallel algorithm is work optimal, because the total number of computational operations is equal to the running time of the optimal sequential algorithm. Also, it is time optimal because any parallel algorithm using any large number of processors takes at least Ω(log n) time for evaluating E(X). Further, we have implemented this parallel algorithm to run on the GPU. The experimental results on NVIDIA GeForce RTX 2080Ti GPU show that our GPU implementation runs more than 1000 times faster than the sequential algorithm running on Intel Corei7-8700K CPU(3.70GHz) for the QUBO with nbit vector whenever n ≥ 33. We also compare our exhaustive search parallel algorithm with several non-exhaustive search approaches for solving the QUBO including D-Wave 2000Q quantum annealer, simulated annealing algorithm, and Gurobi optimizer.
The quadratic unconstrained binary optimization (QUBO) is recently gathering attention in conjunction with quantum annealing (QA), since it is equivalent to finding the ground state of an Ising model. Due to the limitation of current QA systems, classical computers may outperform them. Researchers have thus been proposed to solve QUBO on FPGAs, GPUs, and special purpose processors. In this paper, we propose an adaptive bulk search (ABS), a framework for solving QUBO that can perform many searches in parallel on multiple GPUs. It supports fully-connected Ising models with up to 32k spins and 16-bit weights. In our ABS, a CPU host performs genetic algorithm (GA) while GPUs asynchronously perform local searches. A bottleneck for solving QUBO exists in the evaluation of the energy function, which requires computational cost for each solution. We show this can be reduced to in our ABS. The experimental results show that, with four NVIDIA GeForce RTX 2080 Ti GPUs, our framework can search up to 1.24 × 1012 solutions per second. We also show that our system quickly solves maximum cut and traveling salesman problems.
Quadratic Unconstraint Binary Optimization (QUBO) is a combinatorial optimization problem such that ann×nn\times nn×nupper triangle matrixWWWis given and the objective is to find an n-bit vectorXXXthat minimizes the energy valueE(X)=XTWXE(X)=X^{T}WXE(X)=XTWX. A QUBO instanceWWWis sparse if instanceWWWhas few non-zero elements. The D-Wave 2000QQQis a quantum annealer that can solve 2048-bit sparse QUBO instances represented as a Chimera graph topology. We present a sparse QUBO solver running on GPUs for 2048-bit sparse QUBO with a Chimera graph topology. We have evaluated the performance of our sparse QUBO solver and the D-Wave 2000Q for solving 2048-bit QUBO instances with various resolutions. The experimental results show that our sparse QUBO solver running on a GPU cloud server with 8 NVIDIA A100 GPUs can find optimal solutions in less than 3ms for all instances while the D-Wave 2000QQQcannot find them in 996.7ms. Hence, our QUBO solver can find better solutions than the D-Wave 2000Q in less than 1/300 running time. We can think that our QUBO solver is a quantum annealer simulator with better performance in terms of the accuracy of solutions and the running time. Our result implies that quantum annealer D-Wave 2000QQQdoes not achieve quantum supremacy yet.
Quadratic Unconstrained Binary Optimization (QUBO) is a combinatorial optimization to find an optimal binary solution vector that minimizes the energy value defined by a quadratic formula of binary variables in the vector. As many NP-hard problems can be reduced to QUBO problems, considerable research has gone into developing QUBO solvers running on various computing platforms such as quantum devices, ASICs, FPGAs, GPUs, and optical fibers. This paper presents a framework called Diverse Adaptive Bulk Search (DABS), which has the potential to find optimal solutions of many types of QUBO problems. Our DABS solver employs a genetic algorithm-based search algorithm featuring three diverse strategies: multiple search algorithms, multiple genetic operations, and multiple solution pools. During the execution of the solver, search algorithms and genetic operations that succeeded in finding good solutions are automatically selected to obtain better solutions. Moreover, search algorithms traverse between different solution pools to find good solutions. We have implemented our DABS solver to run on multiple GPUs. Experimental evaluations using eight NVIDIA A100 GPUs confirm that our DABS solver succeeds in finding optimal or potentially optimal solutions for three types of QUBO problems.
Heuristic solvers of the Quadratic Unconstrained Binary Optimization (QUBO) problems have been rapidly studied because of their potentialities to solve a wide range of com-binatorial optimization problems in a unified manner. QUBO solvers, however, face a limitation in the numbers of variables. To overcome this limitation, we reformulate QUBO as a maximum weight induced subgraph problem (MISG) and propose a graph-theoretic approach for solving MISG. It is a problem to find an induced subgraph with the maximum total weight for a given edge-weighted undirected graph. Naive local search that updates only one vertex at a time requires many iterations to obtain good solutions for large-scale problems. To accelerate it, we introduce a new technique to update multiple vertices that can improve the solution at the same time. We have implemented a MISG solver based on our algorithm on NVIDIA A100 GPUs, where flip operations are parallelized with GPU multithreaded computing. Our solver is scalable and supports up to 230(1G) variables. Our results show that our algorithm outperforms the Gurobi optimizer in terms of solution qualities and the execution time.
In this article, we describe an algorithm for solving Quadratic Unconstrained Binary Optimization problems on the Intel Loihi 2 neuromorphic processor. The solver is based on a hardware-aware fine-grained parallel simulated annealing algorithm developed for Intel's neuromorphic research chip Loihi 2. Preliminary results show that our approach can generate feasible solutions in as little as 1 ms and up to 37x more energy efficient compared to two baseline solvers running on a CPU. These advantages could be especially relevant for size-, weight-, and power-constrained edge computing applications.
One of the vital roles of computing is to solve large-scale combinatorial optimization problems in a short time. In recent years, methods have been proposed that map optimization problems to ones of searching for the ground state of an Ising model by using a stochastic process. Simulated annealing (SA) is a representative algorithm. However, it is inherently difficult to perform a parallel search. Here we propose an algorithm called momentum annealing (MA), which, unlike SA, updates all spins of fully connected Ising models simultaneously and can be implemented on GPUs that are widely used for scientific computing. MA running in parallel on GPUs is 250 times faster than SA running on a modern CPU at solving problems involving 100 000 spin Ising models.