Sqaod solvers

Sqaod is a colletion of solvers for simulated quantum annealing.

QUBO Graphs

Every solver accepts QUBO as its input, and maximize or minimize energy. Solvers are able to deal with 2 types of graphs, dense graph and bipartite graph.

Dense graph

Dense grapn is the most general case, and QUBO is defined as show below:

\[E = \mathbf{x} \mathbf{W} \mathbf{x}^T,\]

where x is an array of values, { 0, 1 }, and its length is N. W is a symmetric matrix whose size is (N, N). Typically QUBOs for TRA are represented as dense graph.

Bipartite graph

Bipartite graph is a case that has limitted connections between nodes as shown below:

\[E = \mathbf{b_0} \mathbf{x_0}^T + \mathbf{b_1} \mathbf{x_1}^T + \mathbf{b_1} \mathbf{W} \mathbf{b_0}^T,\]

where x0 and x1 are arrays of values, { 0, 1 }, and its length is N0 and N1 respectively. W is a matrix whose size is (N1, N0). One notable example is RBM.

Solver algorithm

Sqaod solvers employ 2 algorithms, simulated quantum annealing and brute-force search.

Simulated quantum annealing

Solvers are implemented by using path-integral monte-carlo.

(To be filled.)

Devices

Sqaod utilizes CPU and CUDA (with NVIDIA GPU) to accelerate solvers. Sqaod also has the simple reference implementation for annealing algorithms written in python.

Solvers are implemented in packages of sqaod.py, sqaod.cpu and sqaod.cuda. Solvers for an algorithm with different devices have the same class interface, so they are exchangeable.

package sqaod.py

Python-based solvers for reference implmentation.

This package is aiming at showing solver algorithms. Algorithms of solvers in other packages are based on those implemented in sqaod.py solvers.

package sqaod.cpu

Solvers are Parallelized and accelerated by using OpenMP.

Please use CPU-accelerated solvers with 1 socket of CPU especially for dense graph annealers. NUMA is not considered, and execution with multi CPU sockets may degrade performance. If you’re using a multi-socket system, please use taskset or numacto to limit muluti-CPU-socket usage.

package sqaod.cuda

Solvers are parallelized and acclerated by using CUDA

NVIDIA CUDA GPUs are required. GPUs of compute capability 3.5 (2nd-gen Kepler) or above are supported. Recommendation is compute capability 5.0(Maxwell) or above. Please visit CUDA GPUs at developer.nvidia.com to check compute capabiity of your GPU.

in version 1.0, sqaod uses 1 GPU whose device no is 0, and multi-GPU is not supported. To choose a GPU, please use CUDA_VISIBLE_DEVICES environement variable.

export CUDA_VISIBLE_DEVICES=1
python your-script.py