TeamGraphix / graphix

measurement-based quantum computing (MBQC) compiler and simulator

https://graphix.readthedocs.io

Apache License 2.0

55 stars 20 forks source link

Gflow finding algorithm #81

Closed masa10-f closed 8 months ago

masa10-f commented 10 months ago

Before submitting, please check the following:

Make sure you have tests for the new code and that test passes (run pytest)
format added code and tests by black -l 120 <filename>
If applicable, add a line to the [unreleased] part of CHANGELOG.md, following keep-a-changelog.

Then, please fill in below:

Context (if applicable):

Description of the change:

Fix a conditional branch in gflow finding algorithm (See #80 for details)
Add a GF(2) solver tailored for gflow finding algorithm
Add an option whether to write down all possible gflow or not
Require meas_plane argument every time to find flow or gflow
Remove z3-solver from dependency

Related issue:

80

also see that checks (github actions) pass. If lint check keeps failing, try installing black==22.8.0 as behavior seems to vary across versions.

shinich1 commented 10 months ago

thanks, I will take a look at the code!

let's write in changelog.md, specifically highlighting the breaking change of interface (meas_plane is now required).
please paste the benchmark plot here, so people can see the benefit of new code.
perhaps @pafloxy can also take a look and provide comments where necessary?

masa10-f commented 10 months ago

gflow_finding_time

This is a benchmark compared with the previous implementation. Performance has been improved for graphs with moderate size.

shinich1 commented 10 months ago

This is a benchmark compared with the previous implementation. Performance has been improved for graphs with moderate size.

really nice! maybe worth comparing with pyzx implementation of gflow-finding algorithm? up to you!

masa10-f commented 10 months ago

maybe worth comparing with pyzx implementation of gflow-finding algorithm? up to you!

In this PR, I originally intended to fix the conditional branch of gflow algorithm, not to improve performance, actually, I didn't improve the core of the linear equations solver. I don't really want to compare it with another package now.

masa10-f commented 9 months ago

I have resolved conflicts with the main branch. Would you review all the changes again? @shinich1 @pafloxy If everything looks good, I'll merge this PR.

pafloxy commented 9 months ago

Sure. Nice work 👏

masa10-f commented 8 months ago

@shinich1 I have just completed all the modifications. Could you review the whole code again?

masa10-f commented 8 months ago

@shinich1 Thanks!