MQT QUBOMaker: Automatic Generation of QUBO Formulations from Optimization Problem Specifications

MQT QUBOMaker is a framework that can be used to automatically generate QUBO formulations for various optimization problems based on a selection of constraints that define the problem. It is developed by the Chair for Design Automation at the Technical University of Munich as part of the Munich Quantum Toolkit (MQT).

The tool allows users to create QUBO formulations, and, thus, interact with quantum algorithms, without requiring any background knowledge in the field of quantum computing. End-users can stay entirely within their domain of expertise while being shielded from the complex and error-prone mathematical tasks of QUBO reformulation.

Furthermore, MQT QUBOMaker supports a variety of different encodings. End users can easily switch between the encodings for evaluation purposes without any additional effort, a task that would otherwise require a large amount of tedious mathematical reformulation.

Currently, MQT QUBOMaker provides the following submodule:

• Pathfinder: This submodule provides a specialization of the QUBOMaker class for the solution of optimization problems involving the search for paths in a directed graph. It provides a large set of pathfinding-related constraints that are used to define individual problem instances.

The Pathfinder submodule also has a supporting GUI to further facilitate its use.

For more details, please refer to:

If you have any questions, feel free to create a discussion or an issue on GitHub.

Getting Started

mqt-qubomaker is available via PyPI.

(venv) $ pip install mqt.qubomaker

The following code gives an example of the usage with the pathfinder submodule:

import mqt.qubomaker as qm
import mqt.qubomaker.pathfinder as pf

# define an example graph to investigate.
graph = qm.Graph.from_adjacency_matrix(
    [
        [0, 1, 3, 4],
        [2, 0, 4, 2],
        [1, 5, 0, 3],
        [3, 8, 1, 0],
    ]
)

# select the settings for the QUBO formulation.
settings = pf.PathFindingQUBOGeneratorSettings(
    encoding_type=pf.EncodingType.ONE_HOT, n_paths=1, max_path_length=4, loops=True
)

# define the generator to be used for the QUBO formulation.
generator = pf.PathFindingQUBOGenerator(
    objective_function=pf.MinimizePathLength(path_ids=[1]),
    graph=graph,
    settings=settings,
)

# add the constraints that define the problem instance.
generator.add_constraint(pf.PathIsValid(path_ids=[1]))
generator.add_constraint(
    pf.PathContainsVerticesExactlyOnce(vertex_ids=graph.all_vertices, path_ids=[1])
)

# generate and view the QUBO formulation as a QUBO matrix.
print(generator.construct_qubo_matrix())

Detailed documentation and examples are available at ReadTheDocs.

References

MQT QUBOMaker has been developed based on methods proposed in the following paper:

• D. Rovara, N. Quetschlich, and R. Wille "A Framework to Formulate Pathfinding Problems for Quantum Computing", arXiv, 2024

Acknowledgements

The Munich Quantum Toolkit has been supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No. 101001318), the Bavarian State Ministry for Science and Arts through the Distinguished Professorship Program, as well as the Munich Quantum Valley, which is supported by the Bavarian state government with funds from the Hightech Agenda Bayern Plus.