Pathfinder Submodule¶

This module implements MQT QUBOMaker for pathfinding problems on directed and undirected graphs in the form of the PathFindingQUBOGenerator class, a specialization of the general QUBOGenerator class.

It supports a set of various constraints that can be used to model a variety of different pathfinding problems.

In addition to that, it also provides three encoding schemes that can be selected for the construction of QUBO formulations.

Finally, the GUI provides a graphical user interface for the module, which can be used to interactively define pathfinding problems.

In addition to that, the submodule accepts several input formats for the problem instance. A JSON format can be used to define problem constraints and settings. Furthermore, the established TSPLib format can be passed to the framework directly, generating the required constraints from the problem instance.

The PathFindingQUBOGenerator class can be instantiated like this:

import mqt.qubomaker.pathfinder as pf

...

generator = pf.PathFindingQUBOGenerator(
    objective_function=pf.MinimizePathLength(path_ids=[1]),
    graph=graph,
    settings=settings,
)

Here, the objective_function parameter can represent any objective function for the optimization procedure (MinimizePathLength or MaximizePathLength). The graph parameter is the graph on which the problem is defined. Finally the settings parameter is a PathFindingQUBOGeneratorSettings object that defines settings for the QUBO generator:

  • encoding_type: The encoding scheme to use for the QUBO formulation.

  • n_paths: The number of paths to be searched for.

  • max_path_length: The maximum length of a path.

  • loops: A boolean value indicating, whether the found paths should be interpreted as loops.

An example settings definition may look like:

import mqt.qubomaker.pathfinder as pf

settings = pf.PathFindingQUBOGeneratorSettings(
    encoding_type=pf.EncodingType.BINARY,
    n_paths=1,
    max_path_length=4,
    loops=False,
)

Pathfinder Features