search

cda-tum / mqt-qcec

MQT QCEC - A tool for Quantum Circuit Equivalence Checking
https://mqt.readthedocs.io/projects/qcec
MIT License
87 stars 20 forks source link

✨ Partial equivalence checking #375

Closed reb-ddm closed 4 months ago

reb-ddm commented 4 months ago

Description

Added a flag checkPartialEquivalence in order to decide whether to check for total equivalence or for partial equivalence. Two circuits are partially equivalent if, for each possible initial input state, they have the same probability for each measurement outcome. Therefore the state of not measured qubits (= garbage qubits), or phases are ignored.

The Construction Checker and the Simulation Checker implement this by reducing the contribution of garbage qubits in the matrix/vector representation of the circuit. Additionally, all weights in the DD representation are set to their magnitude, such that different phases don't influence the result.

The Alternating Checker implements it by checking that the resulting matrix representation is equal to a diagonal matrix, modulo garbage qubits (instead of checking that it is equal to the identity matrix).

For more information, there is documentation in the file PartialEquivalence.ipynb.

An additional feature are the automatically generated benchmarks for partial equivalence. The function generatePartiallyEquivalentCircuits generates pairs of circuits which are partially equivalent, following the method described in the paper Partial Equivalence Checking of Quantum Circuits in Section VI. B.

Fixes issue #155

Checklist:

codecov[bot] commented 4 months ago

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Project coverage is 96.4%. Comparing base (a46794a) to head (faf7d2e).

Additional details and impacted files [![Impacted file tree graph](https://app.codecov.io/gh/cda-tum/mqt-qcec/pull/375/graphs/tree.svg?width=650&height=150&src=pr&token=eKL7Ya7iep&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=cda-tum)](https://app.codecov.io/gh/cda-tum/mqt-qcec/pull/375?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 #375 +/- ## ======================================= + Coverage 96.2% 96.4% +0.1% ======================================= Files 34 34 Lines 1753 1763 +10 Branches 215 217 +2 ======================================= + Hits 1688 1701 +13 + Misses 65 62 -3 ``` | [Flag](https://app.codecov.io/gh/cda-tum/mqt-qcec/pull/375/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-qcec/pull/375/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=cda-tum) | `96.2% <100.0%> (+0.2%)` | :arrow_up: | | [python](https://app.codecov.io/gh/cda-tum/mqt-qcec/pull/375/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=cda-tum) | `97.2% <100.0%> (+<0.1%)` | :arrow_up: | | [Files](https://app.codecov.io/gh/cda-tum/mqt-qcec/pull/375?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/Configuration.hpp](https://app.codecov.io/gh/cda-tum/mqt-qcec/pull/375?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=cda-tum#diff-aW5jbHVkZS9Db25maWd1cmF0aW9uLmhwcA==) | `96.4% <100.0%> (+<0.1%)` | :arrow_up: | | [include/EquivalenceCheckingManager.hpp](https://app.codecov.io/gh/cda-tum/mqt-qcec/pull/375?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=cda-tum#diff-aW5jbHVkZS9FcXVpdmFsZW5jZUNoZWNraW5nTWFuYWdlci5ocHA=) | `100.0% <100.0%> (ø)` | | | [include/checker/dd/TaskManager.hpp](https://app.codecov.io/gh/cda-tum/mqt-qcec/pull/375?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=cda-tum#diff-aW5jbHVkZS9jaGVja2VyL2RkL1Rhc2tNYW5hZ2VyLmhwcA==) | `98.4% <100.0%> (ø)` | | | [src/EquivalenceCheckingManager.cpp](https://app.codecov.io/gh/cda-tum/mqt-qcec/pull/375?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=cda-tum#diff-c3JjL0VxdWl2YWxlbmNlQ2hlY2tpbmdNYW5hZ2VyLmNwcA==) | `94.3% <100.0%> (+<0.1%)` | :arrow_up: | | [src/checker/dd/DDAlternatingChecker.cpp](https://app.codecov.io/gh/cda-tum/mqt-qcec/pull/375?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=cda-tum#diff-c3JjL2NoZWNrZXIvZGQvRERBbHRlcm5hdGluZ0NoZWNrZXIuY3Bw) | `92.0% <100.0%> (+0.2%)` | :arrow_up: | | [src/checker/dd/DDEquivalenceChecker.cpp](https://app.codecov.io/gh/cda-tum/mqt-qcec/pull/375?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=cda-tum#diff-c3JjL2NoZWNrZXIvZGQvRERFcXVpdmFsZW5jZUNoZWNrZXIuY3Bw) | `92.8% <100.0%> (+0.9%)` | :arrow_up: | | [src/mqt/qcec/configuration.py](https://app.codecov.io/gh/cda-tum/mqt-qcec/pull/375?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=cda-tum#diff-c3JjL21xdC9xY2VjL2NvbmZpZ3VyYXRpb24ucHk=) | `100.0% <100.0%> (ø)` | | ... and [1 file with indirect coverage changes](https://app.codecov.io/gh/cda-tum/mqt-qcec/pull/375/indirect-changes?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=cda-tum)
burgholzer commented 4 months ago

Hey @reb-ddm 👋🏼

Many thanks for all the work here! I took the liberty to rework some bits and pieces, but overall this is looking great and ready to merge. Once CI is all-green here, I'll start by merging the mqt-core PR and changing back the submodule pointers from the fork to the main repository. After that, this should be good to go 🎉