MEDUSA: An MTBDD-based quantum circuit simulator

MEDUSA (Multi-Terminal Binary Decision Diagram-based Quantum Simulator) is an MTBDD-based quantum circuit simulator supporting OpenQASM circuits. It is written in C and supports multiple MTBDD backends.

Documentation: quantum.fit.vut.cz/MEDUSA, covering installation, usage and the command-line reference.

MoToBuddy is the preferred backend (make / ./MEDUSA). Sylvan is an optional C-only package for comparison with original MEDUSA; it does not support MOSF / USE_CXX=1.

Build

Dependencies:

• gmp library (libgmp-dev)
• MoToBuddy (required)
• Sylvan v1.8.1 + Lace v1.4.1 (optional, make init-sylvan)

Download and build MoToBuddy (requires git):

make init

Then build (default is MoToBuddy __float128 / f128). That also creates ./MEDUSA as a symlink to ./MEDUSA_buddy_doubles_f128:

make

make help lists all targets.

Build types

	flags	object tree	use
make (BUILD=release)	-O2 -g, LTO	obj/release	what CI tests and what benchmarks measure
make BUILD=debug	-O0 -g -fno-omit-frame-pointer	obj/debug	gdb, valgrind, gcov: every local visible, every line its own line

Both produce the same binary names (./MEDUSA_buddy_doubles_f128, ...), so a debug build overwrites the release binary; the object trees are separate, so switching back is a relink, not a rebuild. COVERAGE=1 is the debug build plus --coverage (obj/coverage); PROFILE=1 is kept as an alias for BUILD=debug. LTO=0 gives a release build without link-time optimisation; USE_CXX=1 and MEDUSA_DEBUG=1 combine with either type and get their own trees (obj/release-cxx, obj/debug-dbglog, ...).

Optional Sylvan backend (C gates only):

make init-sylvan
make sylvan_doubles          # ./MEDUSA_sylvan_doubles_f128
make sylvan_gmp              # ./MEDUSA_sylvan_gmp

Building with CMake

The CMake build is being introduced alongside the Makefile and will replace it. One configure builds every variant side by side - MoToBuddy with f32, f64, f80, f128 and GMP leaves, each with the C and the C++ gate path - and CTest runs the suites from that one tree, in parallel. MoToBuddy is fetched at the pinned commit; no make init is needed.

cmake --preset release                 # build/release: -O2 -g, LTO
cmake --build --preset release -j
ctest --preset pr -j                   # the per-PR suites (C and C++ gates)
ctest --test-dir build/release -L memory -j   # stress + valgrind

Binaries land in build/<preset>/bin/ under the Makefile's names (MEDUSA_buddy_doubles_f128, MEDUSA_buddy_gmp, ...), with a _cxx suffix for the C++ gate path. Presets: release, debug (-O0 -g), coverage (debug + gcov) and sylvan (adds the Sylvan variants). Options: MEDUSA_FLOAT_TYPES, MEDUSA_GMP, MEDUSA_CXX_GATES, MEDUSA_SYLVAN, MEDUSA_LTO, MEDUSA_DEBUG_LOG, MEDUSA_LEAF_ABS_EPS / MEDUSA_LEAF_REL_EPS. Tests a configuration cannot run (a variant left out, or no valgrind; -DVALGRIND=OFF skips the leak checks on purpose) stay registered as disabled, and configuring warns about them. Test labels: pr, cxx, memory, sylvan, nightly. Mutation testing (make test-mutation) is Makefile-only for now.

Backends

The default product is MoToBuddy, selectable at compile time by leaf type:

Target	Backend	Leaf type
make / make buddy_doubles_f128	MoToBuddy (preferred)	Complex floating-point re+im (__float128)
make buddy_gmp	MoToBuddy	Algebraic integers (exact, GMP)
make buddy_doubles_f32	MoToBuddy	Complex floating-point re+im (float)
make buddy_doubles_f64	MoToBuddy	Complex floating-point re+im (double)
make buddy_doubles_f80	MoToBuddy	Complex floating-point re+im (long double)
make buddy_doubles_all	MoToBuddy	All floating-point variants above
make sylvan_doubles	Sylvan (optional)	Same float leaves as MoToBuddy (LEAF_FLOAT_TYPE)
make sylvan_gmp	Sylvan (optional)	Algebraic integers (exact, GMP)

buddy_mpfr is not implemented. Sylvan has no C++ / MOSF path.

To enable C++ gate traversal and MOSF simulation support (experimental, MoToBuddy only):

make buddy_doubles_f128 USE_CXX=1

Tests

make test          # MoToBuddy unit + circuits + benchmarks + metamorphic
make test-sylvan   # same circuit/benchmark smokes on Sylvan, plus harder Grover/CCX
make test-all      # test + test-sylvan

See tests/README.md.

Coverage

COVERAGE=1 selects the debug build (-O0 -g) plus --coverage, so the suites record gcov data. Reports are produced with gcovr (apt install gcovr) as a Cobertura coverage.xml:

make coverage       # default product: make test + make test-grover
make coverage-all   # adds the optional Sylvan backend (needs init-sylvan)

make coverage-all is what CI measures, so its number is the one behind the Codecov badge; make coverage skips Sylvan and therefore reports slightly lower. make coverage-cxx measures the C++ gate implementations instead (USE_CXX=1); CI uploads it separately under the Codecov flag cxx, because the two builds instrument different line sets of the same sources.

This is the beginning of the README. Read the rest at the original. Read the full README ↗