CSample
Overview
QCI's CSample software is a heuristic solver for minimizing quadratic unconstrained binary optimization (QUBO) problems of the form
,
where and .
CSample implements a parallel version of the well-known Tabu search algorithm developed by Fred Glover in 1986.
Brief summary of Tabu search
Tabu search is a metaheuristic optimization algorithm that can be used for solving combinatorial optimization problems such as QUBOs. Local (neighborhood) searches take a potential solution to a problem and check its immediate neighbors in the hope of finding an improved solution. Local search methods have a tendency to become stuck in suboptimal regions or on plateaus where many solutions are equally fit. To overcome this limitation, Tabu search works by maintaining a tabu list, a set of solutions that have been recently visited. The search is forbidden to visit any solutions that are in the tabu list. This prevents the search from getting stuck in a local minimum.
The search starts at a random solution and then iteratively moves to a neighboring solution that is not in the tabu list. If no neighboring solution is found, the search is restarted at a new random solution. CSample speeds up this process by initially selecting many random starting solutions and running the search iterations in parallel, checking the best results intermediately, and finally returning the best results from across the parallel solvers.
CSample solution distribution
Unlike many optimization engines, CSample returns a distribution of the top solutions to the user. It does this by keeping track of the best solutions found and recording how many times each one was found in the search. This give the user a set of solutions that behave very much like the probability distribution from many shots taken on a quantum computer. This can be useful when prototyping algorithms that assume a distribution of solutions.