Bipartite Graph Brute-force Searcher¶
- Sqaod implements 3 bipartite graph brute-force searcher classes.
sqaod.py.BipartiteGraphBFSearcher
Python-based reference implementation of bipartite graph brute-force search.
sqaod.cpu.BipartiteGraphBFSearcher
Parallelized CPU implementation by using OpenMP.
sqaod.cuda.BipartiteGraphBFSearcher
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_bf_searcher.
Method calling sequence¶
Below is a psudo-code to run bipartite graph brute-force searcher.
import sqaod as sq
# Assumption
# N0, N1 : problem size.
# 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. instantiate brute-force searcher
searcher = sqaod.py.bipartite_graph_bf_searcher(W, sq.minimize, dtype)
# Alternatively, you're able to set QUBO as shown below.
#
# searcher = sqaod.py.bipartite_graph_bf_searcher(dtype)
# searcher.set_qubo(b0, b1, W, sq.minimize)
# 3. (optional)
# Set preferences. You're able to select tile size.
# Preferences are given as **kwargs.
#
# searcher.set_preference(tile_size_0 = 1024, tile_size_1 = 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 is a list of tuples. Each tuple contains pair of bit arrays (x0, x1).
# E is a vector of QUBO energy.
x = searcher.get_x()
E = searcher.get_E()
classes and functions¶
sqaod.py.bipartite_graph_bf_searcher¶
-
sqaod.py.
bipartite_graph_bf_searcher
(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.BipartiteGraphBFSearcher¶
-
class
sqaod.py.
BipartiteGraphBFSearcher
(W, b0, b1, optimize, prefdict)[source]¶ Bipartite graph brute-force searcher
-
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.
checkers.bipartite_graph.qubo(b0, b1, W)
-
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}.
-
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.
-
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.
-
sqaod.cpu.bipartite_graph_bf_searcher¶
-
sqaod.cpu.
bipartite_graph_bf_searcher
(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.BipartiteGraphBFSearcher¶
sqaod.cuda.bipartite_graph_bf_searcher¶
-
sqaod.cuda.
bipartite_graph_bf_searcher
(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: