Circuit Partition

[jkim971201]

Hi, I'm a graduate student from POSTECH, Korea.

I implemented a graph partitioning method for faster HSF simulation. This is based on my ASP-DAC 2023 paper, "Graph Partitioning Approach for Fast Quantum Circuit Simulation." (https://doi.org/10.1145/3566097.3567928)

1. Sicne there are many changes from the publication version, not all the features in the paper are implemented.
2. Most of the source codes are in the "CircuitPartitioner.cpp" and "CircuitPartitioner.h"
3. You can turn on the graph partitining mode by giving "--splitting_method graph_partitioning" to ddsim_simple binary.
4. I used a spectral partitioning algorithm which requires "Eigen" C++ library. (https://ieeexplore.ieee.org/document/159993)
5. Unfortunately, this is only limited to Google supremacy circuits...
6. Experimental results are below. https://docs.google.com/spreadsheets/d/1xG5sxuu01XgWhC-nbrjbg0QJdhRKAeq3-gL3XrBf6pA/edit#gid=0
7. I verified the results are correct by printing the amplitude vectors and comparing them with ddsim_vector binary. (but not all the cases)

I hope this is interesting to you. Thank you.

[burgholzer]

Hey 👋🏼 Many thanks for opening this PR! I am pretty busy at the moment, so it might take me some time to get to it. Two things up front:

• would it be possible to avoid the Eigen dependency somehow? It's a pretty heavy dependency and we would like to avoid adding it if we can. Could you maybe extract the respective method from there (assuming it's only a single method being used)?
• could you please also add tests (on the C++, but also the Python side) that make sure these functions work as intended.

Ideally, the CI checks on GitHub should be all green.

[jkim971201]

I got it. I have some other project deadline, so I think I can make CI checks all green after that.

Thanks.