Dense Graph Annealers

Sqaod implements 3 dense graph annealer classes.

Factory function

Every solver class has its own factory function in the same package. For example, sqaod.py.DenseGraphAnnealer is instantiated by sqaod.py.dense_graph_annealer.

Method calling sequence

Below is a psudo-code to run annealer.

import sqaod as sq

# Assumption
# N     : problem size.
# m     : number of trotters.
# dtype : np.float32. Numerical precision is assumed to be np.float32.

# 1. Preparing QUBO matrix, W.
#    W is a matrix whose shape is (N, N).
#    W should be a upper/lower triangular or symmetrix matrix.
W = create QUBO ...

# 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.dense_graph_annealer(W, m, sq.minimize, dtype)

# Alternatively, you're able to set W and m as shown below.
#
# ann = sqaod.py.dense_graph_annealer(dtype)
# ann.set_qubo(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 = <array of numpy.int8, len(q_init) == N>
# ann.set_q(q_init)
#
# or
#
# Setting a set of initial spins.  qset_init is a list of numpy.int8 vector.
# qset_init = [q0, q1, ... ]   # 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()
E = ann.get_E()

classes and functions

sqaod.py.dense_graph_annealer

sqaod.py.dense_graph_annealer(W=None, optimize=<sqaod.common.preference.Minimize object>, **prefs)[source]

factory function for sqaod.py.DenseGraphAnnealer.

Parameters:
Returns:

annealer instance
Return type:

sqaod.py.DenseGraphAnnealer

sqaod.py.DenseGraphAnnealer

class sqaod.py.DenseGraphAnnealer(W, optimize, prefdict)[source]

python implementation of dense graph annealer.

This class is a reference implementation of dense 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:problem size.
Return type:int
set_qubo(W, optimize=<sqaod.common.preference.Minimize object>)[source]

set QUBO.

Parameters:
  • W (numpy.ndarray) – QUBO matrix. W should be a sqaure matrix. Upper/Lower triangular matrices or symmetric matrices are accepted.
  • optimize – optimize direction, sqaod.maximize, sqaod.minimize <preference.html#sqaod-maximize-sqaod-minimize>
set_hamiltonian(h, J, c)[source]

set Hamiltonian.

Parameters:
  • numpy.ndarray – h(vector), J(matrix)
  • point number (floating) – c
  • for h, J must be (Shapes) –
  • must be a upper/lower triangular or symmetric matrix. (J) –
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:array of bit {0, 1}.
Return type:numpy.int8

x is a list of int8 arrays. len(x) is m, and len(int8 array) is N.

set_q(q)[source]

set spins.

Parameters:q (np.array of np.int8) – array (length = N) of spin {-1, 1}.
set_qset(q)[source]

set “array of” spins.

Parameters:qset (list of np.int8 array) – list of array of spin {-1, 1}.

qset is a list (length = m) of int8 array (length = N).

get_hamiltonian()[source]

get hamiltonian.

Returns: tuple of Hamiltonian variables
h(vector), J(symmeric matrix), c(scalar)
get_q()[source]

get spins.

Returns:array of spin {-1, 1}.
Return type:numpy.int8
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_colored_plane(G, beta, offset)[source]

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

anneal_one_step_coloring(G, beta)[source]

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

anneal_one_step_sa_naive(kT, _)[source]

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

sqaod.cpu.dense_graph_annealer

sqaod.cpu.dense_graph_annealer(W=None, optimize=<sqaod.common.preference.Minimize object>, dtype=<class 'numpy.float64'>, **prefs)[source]

factory function for sqaod.cpu.DenseGraphAnnealer.

Parameters:
Returns:

annealer instance
Return type:

sqaod.cpu.DenseGraphAnnealer

sqaod.cpu.DenseGraphAnnealer

class sqaod.cpu.DenseGraphAnnealer(W, optimize, dtype, prefdict)[source]

CPU-based dense graph annealer

sqaod.cuda.dense_graph_annealer

sqaod.cuda.dense_graph_annealer(W=None, optimize=<sqaod.common.preference.Minimize object>, dtype=<class 'numpy.float64'>, **prefs)[source]

factory function for sqaod.cuda.DenseGraphAnnealer.

Parameters:
Returns:

annealer instance
Return type:

sqaod.cuda.DenseGraphAnnealer

sqaod.cuda.DenseGraphAnnealer

class sqaod.cuda.DenseGraphAnnealer(W, optimize, dtype, prefdict)[source]

CUDA-based Dense graph annealer