Bipartite Graph Annealers

Sqaod implements 3 bipartite graph annealer classes.

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:
Returns:

annealer instance

Return type:

sqaod.py.BipartiteGraphAnnealer

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:
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

preference

get_preferences()[source]

get solver preferences.

Returns:preference dictionary.
Return type:dict

References

preference

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.

randomize_spin()[source]

randomize spin.

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.

anneal_one_step(G, beta)[source]

Run annealing one step.

Parameters:
  • G (floating point number) – G in SQA, kT in SA.
  • beta (floating point number) – inverse temperature. SA algorithms ignore this parameter.
anneal_one_step_naive(G, beta)[source]

(sqaod.py only) sqaod.algorithm.naive version of SQA

anneal_one_step_coloring(G, beta)[source]

(sqaod.py only) try to flip spins in a colored plane.

anneal_one_step_sa_naive(kT, _)[source]

(sqaod.py only) sqaod.algorithm.sa_naive version of SA

anneal_one_step_sa_coloring(kT, _)[source]

(sqaod.py only) sqaod.algorithm.sa_coloring version of SA

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:
Returns:

annealer instance

Return type:

sqaod.cpu.BipartiteGraphAnnealer

sqaod.cpu.BipartiteGraphAnnealer

class sqaod.cpu.BipartiteGraphAnnealer(b0, b1, W, optimize, dtype, prefdict)[source]

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:
Returns:

annealer instance

Return type:

sqaod.cuda.BipartiteGraphAnnealer

sqaod.cuda.BipartiteGraphAnnealer

class sqaod.cuda.BipartiteGraphAnnealer(b0, b1, W, optimize, dtype, prefdict)[source]