Bipartite Graph Annealers¶
- Sqaod implements 3 bipartite graph annealer classes.
sqaod.py.BipartiteGraphAnnealer
Python-based reference implementation of annealing algorithms.
sqaod.cpu.BipartiteGraphAnnealer
Parallelized CPU implementation by using OpenMP.
sqaod.cuda.BipartiteGraphAnnealer
Parallelized and accelearted by using NVIDIA GPU, CUDA.
Factory function¶
Every solver class has its own factory function in the same package. For example, sqaod.py.BipartiteGraphAnnealer is instantiated by sqaod.py.bipartite_graph_annealer.
Method calling sequence¶
Below is a psudo-code to run annealer.
import sqaod as sq
# Assumption
# N0, N1 : problem size.
# m : number of trotters.
# dtype : np.float32. Numerical precision is assumed to be np.float32.
# 1. Preparing QUBO matrix, W.
# QUBO energy is defined as E = b0 * x0.T + b1 * x1.T + x1 * W * x0.T
b0 = ... # vector(length = N0)
b1 = ... # vector(length = N1)
W = ... # matrix, shape == (N1, N0)
# 2. define number of trotters.
m = number of trotters ...
# 3. instantiate annaler
# The initial value of m is given as m = N / 2.
ann = sqaod.py.bipartite_graph_annealer(b0, b1, W, m, sq.minimize, dtype)
# Alternatively, you're able to set W and m as shown below.
#
# ann = sqaod.py.bipartite_graph_annealer(dtype)
# ann.set_qubo(b0, b1, W, sq.minimize)
# ann.set_preference(n_trotters = m)
# 4. (optional)
# Set preferences. You're able to select annealing algorithm,
# number of trotters and so on.
# Preferences are given as **kwargs.
#
# ann.set_preference(n_trotters = m, algorithm = sqaod.coloring)
#
# You're also able to set a seed value for psudo random number generator.
# ann.set_seed(2391102)
# 5. prepare to run annealing
# Before calling prepare(), QUBO and m must be given.
ann.prepare()
# 6. randomize spins
# Randomize and initialize spins as initial values for annealing.
ann.randomize_spins()
# Alternatively, you are able to set spins you generated.
# Value type of spin should be np.int8.
#
# Setting initial spins. q_init is a vector.
# q_init = (q0, q1) # array of numpy.int8, len(q0) == N0, len(q1) == N1.
# ann.set_q(q_init)
#
# or
#
# Setting a set of initial spins. The qset_init is a list of tuple
# storing np.int8 arrays of q0 and q1.
# qset_init = (q0, q1) # array of numpy.int8, len(q0) == N0, len(q1) == N1.
# qset_init = [(q00, q10), (q01, q11), ... ] # len(qset_init) == m
# ann.set_qset(qset_init)
beta = ... # set inverse temperature.
# 7. run annealing loop
while run : # loop while run == True
G = ... # updating G for this iteration.
# 8. anneal.
# One call of anneal_one_step() makes tries to flip N x m spins
ann.anneal_one_step(G, beta)
# 9. (optional) calculate and get QUBO energy if needed.
# E is a vector of QUBO energy for all trotters.
E = ann.get_E();
# doing something with E.
# 10. get solution
x = ann.get_x() # list of tuples, x0 and x1.
# x0 and x1 are bit arrays storing solution
E = ann.get_E()
classes and functions¶
sqaod.py.bipartite_graph_annealer¶
-
sqaod.py.
bipartite_graph_annealer
(b0=None, b1=None, W=None, optimize=<sqaod.common.preference.Minimize object>, **prefs)[source]¶ factory function for sqaod.py.BipartiteGraphAnnealer.
Parameters: - b0, b1, W (numpy.ndarray) – QUBO
- optimize – specify optimize direction, sqaod.maximize or sqaod.minimize.
- prefs – preference as **kwargs
Returns: annealer instance
Return type:
sqaod.py.BipartiteGraphAnnealer¶
-
class
sqaod.py.
BipartiteGraphAnnealer
(b0, b1, W, optimize, prefdict)[source]¶ python implementation of bipartite graph annealer.
This class is a reference implementation of bipartite graph annealers. All algorithms are written in python.
-
seed
(seed)[source]¶ set a seed value for random number generators.
Parameters: seed (int or long) – seed value Note
sqaod.py annealer uses global random number genrator, so seed value is ignored. For annealers in other packages, given seed value is used as documented.
-
get_problem_size
()[source]¶ get problem size.
Problem size is defined as a number of bits of QUBO.
Returns: tuple containing problem size, (N0, N1).
-
set_qubo
(b0, b1, W, optimize=<sqaod.common.preference.Minimize object>)[source]¶ set QUBO.
Parameters: - b0, b1, W (numpy.ndarray) – QUBO.
- optimize – optimize direction, sqaod.maximize, sqaod.minimize.
-
set_hamiltonian
(h0, h1, J, c)[source]¶ set Hamiltonian.
Parameters: - numpy.ndarray – h0(vector), h1(vector), J(matrix)
- point number (floating) – c
- for h0, h1, J must be (Shapes) –
-
set_preferences
(prefdict=None, **prefs)[source]¶ set solver preferences.
Parameters: - prefdict (dict) – preference dictionary.
- prefs (dict) – preference dictionary as **kwargs.
References
-
get_preferences
()[source]¶ get solver preferences.
Returns: preference dictionary. Return type: dict References
-
get_optimize_dir
()[source]¶ get optimize direction
Returns: optimize direction, sqaod.maximize, sqaod.minimize.
-
get_E
()[source]¶ get QUBO energy.
Returns: QUBO energy. Return type: array of floating point number Calculates and returns QUBO energy for all trotters. len(E) is m.
-
get_x
()[source]¶ get bits.
Returns: list of tuples. Each tuple contains 2 numpy.int8 arrays of x0 and x1 x0 and x1 are arrays of bits, {0, 1}.
-
get_hamiltonian
()[source]¶ get hamiltonian.
- Returns: tuple of Hamiltonian variables
- h0(vector), h1(vector), J(matrix), c(scalar)
-
get_q
()[source]¶ get spins.
Returns: tuple for (q0, q1). The q0 and q1 are numpy.int8 arrays whose lengths are N0 and N1 respectively.
-
calculate_E
()[source]¶ calculate QUBO energy. This method calculates QUBO energy, and caches it. This method can be empty if a class does not cache qubo energy.
Note
A call to this method can be asynchronous.
-
prepare
()[source]¶ preparation of internal resources.
Note
prepare() should be called prior to run annealing loop.
-
make_solution
()[source]¶ make bit arrays(x) and calculate QUBO energy.
This method calculates QUBO energy, and prepare solution as a bit array, and caches them. This method can be empty if a class does not cache solution.
Note
A call to this method can be asynchronous.
-
sqaod.cpu.bipartite_graph_annealer¶
-
sqaod.cpu.
bipartite_graph_annealer
(b0=None, b1=None, W=None, optimize=<sqaod.common.preference.Minimize object>, dtype=<class 'numpy.float64'>, **prefs)[source]¶ factory function for sqaod.cpu.BipartiteGraphAnnealer.
Parameters: - b0, b1, W (numpy.ndarray) – QUBO
- optimize –
specify optimize direction, sqaod.maximize or sqaod.minimize.
- prefs –
preference as **kwargs
Returns: annealer instance
Return type:
sqaod.cpu.BipartiteGraphAnnealer¶
sqaod.cuda.bipartite_graph_annealer¶
-
sqaod.cuda.
bipartite_graph_annealer
(b0=None, b1=None, W=None, optimize=<sqaod.common.preference.Minimize object>, dtype=<class 'numpy.float64'>, **prefs)[source]¶ factory function for sqaod.cuda.BipartiteGraphAnnealer.
Parameters: - b0, b1, W (numpy.ndarray) – QUBO
- optimize –
specify optimize direction, sqaod.maximize or sqaod.minimize.
- prefs –
preference as **kwargs
Returns: annealer instance
Return type: