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 · 2021
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.