Dense Graph Brute-force Searcher

Sqaod implements 3 dense graph brute-force searcher classes.

Factory function

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

Method calling sequence

Below is a psudo-code to run dense graph brute-force searcher.

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. instantiate dense graph brute-force searcher
searcher = sqaod.py.dense_graph_bf_searcher(W, sq.minimize, dtype)

# Alternatively, you're able to set QUBO as shown below.
#
# searcher = sqaod.py.dense_graph_bf_searcher(dtype)
# searcher.set_qubo(W, sq.minimize)

# 3. (optional)
#    Set preferences. You're able to select tile size.
#    Preferences are given as **kwargs.
#
# searcher.set_preference(tile_size = 1024)

# 4. prepare to run search
#    Before calling prepare(), QUBO and m must be given.
searcher.prepare()

# 5. run search
# If a problem is big, search needs long time, proportional to 2^N.
# search_range() method will make stepwise search,
# which limits execution time of one call.
while searcher.search_range() :
   # do your job, such as breaking this loop.
   pass

# Alternatively, you can use one line for search, searcher.search().
#
# searcher.search()   # run whole search.

# 6. get solution
x = searcher.get_x()
# x is a list of tuples.  Each tuple contains pair of  bit arrays (x0, x1).
# E is a vector of QUBO energy.
E = searcher.get_E()

classes and functions

sqaod.py.dense_graph_bf_searcher

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

factory function for sqaod.py.DenseGraphAnnealer.

Parameters:
Returns:

brute-force searcher instance
Return type:

sqaod.py.DenseGraphBFSearcher

sqaod.py.DenseGraphBFSearcher

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

Dense graph brute-force searcher

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_preferences(prefdict=None, **prefs)[source]

set solver preferences.

Parameters:
  • prefdict (dict) – preference dictionary.
  • prefs (dict) – preference dictionary as **kwargs.

References

preference

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).
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:tuple of 2 numpy.int8 arrays

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

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 bit arrays, and caches them. This method can be empty if a class does not cache solution.

Note

A call to this method can be asynchronous.

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.

search_range()[source]

Search minimum of QUBO energy within a range.

Returns:True if search completed, False otherwise.

This method enables stepwise minimum QUBO energy search. One method call covers a range specified by ‘tile_size’. When a given problem is big, whole search takes very long time. By using this method, you can do searches stepwise.

search()[source]

One liner for brute-force search.

sqaod.cpu.dense_graph_bf_searcher

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

factory function for sqaod.cpu.DenseGraphAnnealer.

Parameters:
Returns:

brute-force searcher instance
Return type:

sqaod.cpu.DenseGraphBFSearcher

sqaod.cpu.DenseGraphBFSearcher

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

sqaod.cuda.dense_graph_bf_searcher

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

factory function for sqaod.cuda.DenseGraphAnnealer.

Parameters:
Returns:

brute-force searcher instance
Return type:

sqaod.cuda.DenseGraphBFSearcher

sqaod.cuda.DenseGraphBFSearcher

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