Skip to content

Search Algorithms

The Dialectic Search Solver uses a path search between two states representing the thesis and antithesis. A greedy search is used to reduce the energy by applying bit flips in an attempt to find the solution.

The Dialectic Search algorithm operates through two distinct phases:

  1. Antithesis: Generates a complementary solution designed to explore different regions of the solution space
  2. Synthesis: Creates new solutions by exploring paths between thesis and antithesis

Each phase uses tabu search with potentially different parameter settings to guide the exploration process. This approach is particularly effective for problems with complex landscapes containing many local optima.

Compatible Backends

Backend Default
DWave

Initialization

Python
from luna_quantum.solve.parameters.algorithms.base_params.decomposer import Decomposer
from luna_quantum.solve.parameters.algorithms.base_params.tabu_search_params import TabuSearchBaseParams
from luna_quantum.solve.parameters.algorithms.search_algorithms.dialectic_search import DialecticSearch

algorithm = DialecticSearch(
    backend=None,
    antithesis_tabu_params=TabuSearchBaseParams(
        num_reads=None,
        tenure=None,
        timeout=100
    ),
    synthesis_tabu_params=TabuSearchBaseParams(
        num_reads=None,
        tenure=None,
        timeout=100
    ),
    decomposer=Decomposer(
        size=10,
        min_gain=None,
        rolling=True,
        rolling_history=1.0,
        silent_rewind=True,
        traversal='energy'
    ),
    max_iter=100,
    max_time=5,
    convergence=3,
    target=None,
    rtol=1e-05,
    atol=1e-08,
    max_tries=100
)

Usage

Python
from luna_quantum.algorithms import DialecticSearch

algorithm = DialecticSearch()
solve_job = algorithm.run(model, name="my-solve-job")

QBSolv Like Tabu Search breaks down the problem and solves the parts individually using a classic solver that uses Tabu Search. This particular implementation uses hybrid.TabuSubproblemSampler as a sampler for the subproblems to achieve a QBSolv like behaviour.

Note

This solver is only available for commercial and academic licenses.

Compatible Backends

Backend Default
DWave

Initialization

Python
from luna_quantum.solve.parameters.algorithms.base_params.tabu_search_params import TabuSearchBaseParams
from luna_quantum.solve.parameters.algorithms.search_algorithms.qbsolv_like_tabu_search import QBSolvLikeTabuSearch

algorithm = QBSolvLikeTabuSearch(
    backend=None,
    decomposer_size=50,
    rolling=True,
    rolling_history=0.15,
    max_iter=100,
    max_time=5,
    convergence=3,
    target=None,
    rtol=1e-05,
    atol=1e-08,
    tabu_search_params=TabuSearchBaseParams(
        num_reads=None,
        tenure=None,
        timeout=100
    )
)

Usage

Python
from luna_quantum.algorithms import QBSolvLikeTabuSearch

algorithm = QBSolvLikeTabuSearch()
solve_job = algorithm.run(model, name="my-solve-job")

Tabu Search is a heuristic optimization method that works with the help of a tabu list. Initially, random states are chosen in the solution landscape. Afterwards, an iterative search for energetically better states in the neighborhood is started from these states. According to a tabu strategy, states are added to the tabu list that are not allowed to be selected as successor states for a tabu duration. The tabu search ends as soon as there are no better successor states in the neighborhood. The resulting state is therefore the solution to the problem.

Compatible Backends

Backend Default
DWave

Initialization

Python
from luna_quantum.solve.parameters.algorithms.search_algorithms.tabu_search import TabuSearch

algorithm = TabuSearch(
    backend=None,
    num_reads=None,
    tenure=None,
    timeout=100,
    seed=None,
    num_restarts=1000000,
    energy_threshold=None,
    coefficient_z_first=None,
    coefficient_z_restart=None,
    lower_bound_z=None,
    initial_states=None,
    initial_states_generator='random'
)

Usage

Python
from luna_quantum.algorithms import TabuSearch

algorithm = TabuSearch()
solve_job = algorithm.run(model, name="my-solve-job")