Improvements for Trace Computation

[TeWas]

Description

This PR introduces improvements for the trace computation:

1. Adds a compute table for storing results of eliminated nodes during (partial) trace computation
   • this allows the full trace computation to scale linearly with the number of nodes
   • however, the partial trace computation still scales with the number of paths in the DD if the bottom qubits are to be eliminated: non-eliminated nodes cannot be stored in the compute table, as this would prevent their proper elimination in subsequent trace calls
2. Normalizes the result

Fixes #336

Checklist:

• [x] The pull request only contains commits that are related to it.
• [x] I have added appropriate tests and documentation.
• [x] I have made sure that all CI jobs on GitHub pass.
• [x] The pull request introduces no new warnings and follows the project's style guidelines.

[codecov[bot]]

Codecov Report

Attention: Patch coverage is 95.83333% with 1 line in your changes missing coverage. Please review.

Project coverage is 91.6%. Comparing base (0e4ff9e) to head (601edfa). Report is 3 commits behind head on main.

Additional details and impacted files

[](https://app.codecov.io/gh/cda-tum/mqt-core/pull/628?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=cda-tum) ```diff @@ Coverage Diff @@ ## main #628 +/- ## ======================================= - Coverage 91.6% 91.6% -0.1% ======================================= Files 148 148 Lines 14736 14755 +19 Branches 2366 2369 +3 ======================================= + Hits 13511 13522 +11 - Misses 1225 1233 +8 ``` | [Flag](https://app.codecov.io/gh/cda-tum/mqt-core/pull/628/flags?src=pr&el=flags&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=cda-tum) | Coverage Δ | | |---|---|---| | [cpp](https://app.codecov.io/gh/cda-tum/mqt-core/pull/628/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=cda-tum) | `91.3% <95.8%> (-0.1%)` | :arrow_down: | | [python](https://app.codecov.io/gh/cda-tum/mqt-core/pull/628/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=cda-tum) | `99.7% <ø> (ø)` | | | [Files](https://app.codecov.io/gh/cda-tum/mqt-core/pull/628?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=cda-tum) | Coverage Δ | | |---|---|---| | [include/mqt-core/dd/Package.hpp](https://app.codecov.io/gh/cda-tum/mqt-core/pull/628?src=pr&el=tree&filepath=include%2Fmqt-core%2Fdd%2FPackage.hpp&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=cda-tum#diff-aW5jbHVkZS9tcXQtY29yZS9kZC9QYWNrYWdlLmhwcA==) | `97.4% <95.8%> (-0.3%)` | :arrow_down: | ... and [3 files with indirect coverage changes](https://app.codecov.io/gh/cda-tum/mqt-core/pull/628/indirect-changes?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=cda-tum)