[Simulator] Do the simple DP in reversed order and update the benchmark for DP

quantum-compiler / quartz

The Quartz Quantum Compiler

Apache License 2.0

76 stars 19 forks source link

[Simulator] Do the simple DP in reversed order and update the benchmark for DP #140

Closed xumingkuan closed 10 months ago

xumingkuan commented 10 months ago

Previously the simple DP had both time and space complexity O(n^2) where n is the number of gates. This PR reduces the space complexity to O(n) by doing the DP in reversed order.

Also removed the randomized part in benchmark_dp and added some code for NWQBench.