Note

This project is currently in low maintenance mode. We will still fix bugs and accept pull requests, but we will not actively develop new features.

MQT QuSAT - A Tool for Utilizing SAT in Quantum Computing

A tool for utilizing satisfiablity testing (SAT) techniques in quantum computing developed as part of the Munich Quantum Toolkit (MQT) by the Chair for Design Automation at the Technical University of Munich based on methods proposed in:

• [1] L. Berent, L. Burgholzer, and R. Wille. Towards a Satisfiability Encoding for Quantum Circuits. 2022.

QuSAT builds upon MQT Core, which forms the backbone of the MQT.

The project can be used to

• Encode Clifford circuits in SAT
• Check the equivalence of Clifford circuits using SAT

If you have any questions, feel free to contact us via [email protected] or by creating an issue on GitHub.

Towards a Satisfiability Encoding for Quantum Circuits

The results from the paper can be reproduced by first building the project as described below and then executing the resulting qusat_test executable in the build directory. In order to replicate the full range of results, the test/test_satencoder.cpp needs to be modified before building the project. The corresponding lines to be changed are marked with a // Paper Evaluation: comment.

Running the executable, produces several .json files containing the experimental data. The python script /results/visualizer.py can be used to plot the respective data.

Note that, as we use a randomized procedure to generate input data, the exact experimental data will slightly vary every time the benchmarks are run. The experimental data used in the paper is available in /results directory.

System Requirements

Building (and running) is continuously tested under Linux, MacOS, and Windows using the latest available system versions for GitHub Actions. However, the implementation should be compatible with any current C++ compiler supporting C++17 and a minimum CMake version of 3.19.

The SMT Solver Z3 >= 4.8.3 has to be installed and the dynamic linker has to be able to find the library. This can be accomplished in a multitude of ways:

• Under Ubuntu 20.04 and newer: sudo apt-get install libz3-dev
• Under macOS: brew install z3
• Alternatively: pip install z3-solver and then append the corresponding path to the library path (LD_LIBRARY_PATH under Linux, DYLD_LIBRARY_PATH under macOS), e.g. via

  export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:$(python -c "import z3; print(z3.__path__[0]+'/lib')")

• Download pre-built binaries from https://github.com/Z3Prover/z3/releases and copy the files to the respective system directories
• Build Z3 from source and install it to the system

Configuration and Build

To start off, clone this repository using

git clone https://github.com/cda-tum/mqt-qusat --recursive

Note the --recursive flag. It is required to also clone all the required submodules. If you happen to forget passing the flag on your initial clone, you can initialize all the submodules by executing git submodule update --init --recursive in the main project directory.

The project uses CMake as the main build configuration tool. Building a project using CMake is a two-stage process. First, CMake needs to be configured by calling

cmake -S . -B build -DBUILD_MQT_QUSAT_TESTS=ON -DZ3_ROOT=/path/to/z3/

This tells CMake to search the current directory . (passed via -S) for a CMakeLists.txt file and process it into a directory build (passed via -B). If your installation of Z3 is recent enough, the Z3_ROOT can typically be omitted.

After configuring with CMake, the library can be built by calling

cmake --build build

This tries to build the project in the build directory (passed via --build). Some operating systems and developer environments explicitly require a configuration to be set, which is why the --config flag is also passed to the build command. The flag --parallel <NUMBER_OF_THREADS> may be added to trigger a parallel build.

Reference

If you use our tool for your research, we would appreciate if you refer to it by citing the appropriate publication:

@inproceedings{berent2022sat,
      title={Towards a SAT Encoding for Quantum Circuits: A Journey From Classical Circuits to Clifford Circuits and Beyond},
      author={Lucas Berent and Lukas Burgholzer and Robert Wille},
      year={2022},
      booktitle={International Conference on Theory and Applications of Satisfiability Testing}
}

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.