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• 11 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•21 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•16 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•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•1 citation

Solving the Traveling Salesman Problem on the D-Wave Quantum Computer

Siddharth Jain

The traveling salesman problem is a well-known NP-hard problem in combinatorial optimization. This paper shows how to solve it on an Ising Hamiltonian based quantum annealer by casting it as a quadratic unconstrained binary optimization (QUBO) problem. Results of practical experiments are also presented using D-Wave’s 5,000 qubit Advantage 1.1 quantum annealer and the performance is compared to a classical solver. It is found the quantum annealer can only handle a problem size of 8 or less nodes and its performance is subpar compared to the classical solver both in terms of time and accuracy.

Frontiers in Physics•Nov 12, 2021•56 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.
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.
The traveling salesman problem is a well-known NP-hard problem in combinatorial optimization. This paper shows how to solve it on an Ising Hamiltonian based quantum annealer by casting it as a quadratic unconstrained binary optimization (QUBO) problem. Results of practical experiments are also presented using D-Wave’s 5,000 qubit Advantage 1.1 quantum annealer and the performance is compared to a classical solver. It is found the quantum annealer can only handle a problem size of 8 or less nodes and its performance is subpar compared to the classical solver both in terms of time and accuracy.