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

International Symposium on Computing and Networking

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

Tomohiro Imanaga, Koji Nakano, Ryota Yasudo, Yasuaki Ito, Yuya Kawamata, Ryota Katsuki, Shiro Ozaki, Takashi Yazane, Kenichiro Hamano

Published Nov 1, 2021• 9 citations
Publisher

Abstract

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.

DOI
10.1109/candar53791.2021.00011

Related papers

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

VeloxQ: A Fast and Efficient QUBO Solver

Jakub Pawłowski, Jan Tuziemski, Paweł Tarasiuk +5 more

We introduce VeloxQ, a fast solver for Quadratic Unconstrained Binary Optimization (QUBO) problems, which are central to many real-world optimization tasks. Unlike approaches that depend on emerging quantum hardware, VeloxQ can be deployed on conventional computing infrastructure. We benchmark VeloxQ against state-of-the-art QUBO solvers from several families. These include quantum annealers, specifically D-Wave's Advantage and Advantage2 platforms; the digital-quantum BF-DCQO algorithm for Higher-Order Unconstrained Binary Optimization (HUBO) developed by Kipu Quantum; physics-inspired algorithms including Simulated Bifurcation, Parallel Annealing, and tropical tensor networks; and conventional methods including CPLEX, brute force, BEIT's Chimera solver, and Branch-and-Bound variants. The benchmark suite covers native quantum-annealer topologies, embedded all-to-all instances, HUBO-derived instances, planted-solution instances, certified-solver regimes, and dense Branch-and-Bound test cases. Across the benchmark suite, VeloxQ delivers competitive solution quality and runtime, and in several regimes outperforms the compared solvers. VeloxQ also demonstrates strong scalability. Among the solvers considered in this study, it was the only method we could run on the largest sparse instances within our computational budget, including problems with up to $10^{8}$ sparsely connected variables. These findings position VeloxQ as a competitive and practical tool for tackling large-scale QUBO/HUBO problems, offering a practical alternative to existing quantum and classical optimization methods.

arXiv:2501.19221•Jan 31, 2025•2 citations

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

Masaki Tao, Koji Nakano, Yasuaki Ito +5 more

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.

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

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

Multi-objective QUBO solver

Mayowa Ayodele, Richard Allmendinger, Manuel López‐Ibáñez +1 more

Quantum and quantum-inspired optimisation algorithms are designed to solve problems represented in binary, quadratic and unconstrained form. Combinatorial optimisation problems are therefore often formulated as Quadratic Unconstrained Binary Optimisation Problems (QUBO) to solve them with these algorithms. Moreover, these QUBO solvers are often implemented using specialised hardware to achieve enormous speedups, e.g. Fujitsu's Digital Annealer (DA) and D-Wave's Quantum Annealer. However, these are single-objective solvers, while many real-world problems feature multiple conflicting objectives. Thus, a common practice when using these QUBO solvers is to scalarise such multi-objective problems into a sequence of single-objective problems. Due to design trade-offs of these solvers, formulating each scalarisation may require more time than finding a local optimum. We present the first attempt to extend the algorithm supporting a commercial QUBO solver as a multi-objective solver that is not based on scalarisation. The proposed multi-objective DA algorithm is validated on the bi-objective Quadratic Assignment Problem. We observe that algorithm performance significantly depends on the archiving strategy adopted, and that combining DA with non-scalarisation methods to optimise multiple objectives outperforms the current scalarised version of the DA in terms of final solution quality.

arXiv:2205.13399•Genetic and Evolutionary Computation Conference (GECCO)•Jul 8, 2022•13 citations

Comparative Evaluation of PyTorch, JAX, SciPy, and Neal for Solving QUBO Problems at Scale

Yang, Pei-Kun

Quadratic Unconstrained Binary Optimization (QUBO) is a versatile framework for modeling combinatorial optimization problems. This study benchmarks five software-based QUBO solvers: Neal, PyTorch (CPU), PyTorch (GPU), JAX, and SciPy, on randomly generated QUBO matrices ranging from 1000x1000 to 45000x45000, under six convergence thresholds from 10^-1 to 10^-6. We evaluate their performance in terms of solution quality (energy) and computational time. Among the solvers tested, Neal achieved the lowest energy values but was limited to problems with up to 6000 variables due to high memory consumption. PyTorch produced slightly higher energy results than Neal but demonstrated superior scalability, solving instances with up to 45000 variables. Its support for GPU acceleration and CPU multi-threading also resulted in significantly shorter runtimes. JAX yielded energy values slightly above those of PyTorch and was limited to 25000 variables, with runtimes comparable to PyTorch on GPU. SciPy was the most constrained solver, handling only up to 6000 variables and consistently producing the highest energy values with the longest computation times. These findings highlight trade-offs between solution quality, scalability, and runtime efficiency, and suggest that PyTorch is the most balanced choice for large-scale QUBO problems when computational resources permit.

arXiv:2507.17770•Jul 17, 2025•0 citations
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.
We introduce VeloxQ, a fast solver for Quadratic Unconstrained Binary Optimization (QUBO) problems, which are central to many real-world optimization tasks. Unlike approaches that depend on emerging quantum hardware, VeloxQ can be deployed on conventional computing infrastructure. We benchmark VeloxQ against state-of-the-art QUBO solvers from several families. These include quantum annealers, specifically D-Wave's Advantage and Advantage2 platforms; the digital-quantum BF-DCQO algorithm for Higher-Order Unconstrained Binary Optimization (HUBO) developed by Kipu Quantum; physics-inspired algorithms including Simulated Bifurcation, Parallel Annealing, and tropical tensor networks; and conventional methods including CPLEX, brute force, BEIT's Chimera solver, and Branch-and-Bound variants. The benchmark suite covers native quantum-annealer topologies, embedded all-to-all instances, HUBO-derived instances, planted-solution instances, certified-solver regimes, and dense Branch-and-Bound test cases. Across the benchmark suite, VeloxQ delivers competitive solution quality and runtime, and in several regimes outperforms the compared solvers. VeloxQ also demonstrates strong scalability. Among the solvers considered in this study, it was the only method we could run on the largest sparse instances within our computational budget, including problems with up to 10810^{8}108 sparsely connected variables. These findings position VeloxQ as a competitive and practical tool for tackling large-scale QUBO/HUBO problems, offering a practical alternative to existing quantum and classical optimization methods.
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.
Quantum and quantum-inspired optimisation algorithms are designed to solve problems represented in binary, quadratic and unconstrained form. Combinatorial optimisation problems are therefore often formulated as Quadratic Unconstrained Binary Optimisation Problems (QUBO) to solve them with these algorithms. Moreover, these QUBO solvers are often implemented using specialised hardware to achieve enormous speedups, e.g. Fujitsu's Digital Annealer (DA) and D-Wave's Quantum Annealer. However, these are single-objective solvers, while many real-world problems feature multiple conflicting objectives. Thus, a common practice when using these QUBO solvers is to scalarise such multi-objective problems into a sequence of single-objective problems. Due to design trade-offs of these solvers, formulating each scalarisation may require more time than finding a local optimum. We present the first attempt to extend the algorithm supporting a commercial QUBO solver as a multi-objective solver that is not based on scalarisation. The proposed multi-objective DA algorithm is validated on the bi-objective Quadratic Assignment Problem. We observe that algorithm performance significantly depends on the archiving strategy adopted, and that combining DA with non-scalarisation methods to optimise multiple objectives outperforms the current scalarised version of the DA in terms of final solution quality.
Quadratic Unconstrained Binary Optimization (QUBO) is a versatile framework for modeling combinatorial optimization problems. This study benchmarks five software-based QUBO solvers: Neal, PyTorch (CPU), PyTorch (GPU), JAX, and SciPy, on randomly generated QUBO matrices ranging from 1000x1000 to 45000x45000, under six convergence thresholds from 10^-1 to 10^-6. We evaluate their performance in terms of solution quality (energy) and computational time. Among the solvers tested, Neal achieved the lowest energy values but was limited to problems with up to 6000 variables due to high memory consumption. PyTorch produced slightly higher energy results than Neal but demonstrated superior scalability, solving instances with up to 45000 variables. Its support for GPU acceleration and CPU multi-threading also resulted in significantly shorter runtimes. JAX yielded energy values slightly above those of PyTorch and was limited to 25000 variables, with runtimes comparable to PyTorch on GPU. SciPy was the most constrained solver, handling only up to 6000 variables and consistently producing the highest energy values with the longest computation times. These findings highlight trade-offs between solution quality, scalability, and runtime efficiency, and suggest that PyTorch is the most balanced choice for large-scale QUBO problems when computational resources permit.