TeamGraphix / graphix

measurement-based quantum computing (MBQC) compiler and simulator
https://graphix.readthedocs.io
Apache License 2.0
55 stars 20 forks source link

[Bug]: `minimize_space` breaks runnability for patterns that are inconsistent with their graph flow #157

Open thierry-martinez opened 1 month ago

thierry-martinez commented 1 month ago

Describe the bug If a pattern has a graph with a flow but is not consistent with this flow, minimize_space leads to a pattern with is not runnable anymore.

To Reproduce

import graphix
pattern = graphix.pattern.Pattern(input_nodes=[0])
pattern.add(["N", 1])
pattern.add(["N", 2])
pattern.add(["E", (0, 1)])
pattern.add(["E", (1, 2)])
pattern.add(["M", 1, "XY", 0, [], []])
pattern.add(["M", 0, "XY", 0, [1], []])
pattern.add(["Z", 2, [0]])
pattern.simulate_pattern() # OK
pattern.minimize_space()
pattern.simulate_pattern() # KeyError: 1

Expected behavior minimize_space should preserve pattern runnability.

masa10-f commented 2 weeks ago

Is it emergency to support non-deterministic pattern? We can resolve this bug by removing get_measurement_order_from_flow but I'm not really willing to remove it because there's a performance drawback(@nabe98 is tackling the performance issue but it will take more time).

For temporal solution, we can patch this by adding a new option to use flow based minimizing or not. Do you agree with this?

mgarnier59 commented 2 weeks ago

It is not an emergency but it is a common issue in Graphix. We need to know if the pattern is consistent with a gflow before applying some operations. If it turns out not to be the case then problems arise.

I think @shinich1 had an example. I planned on diving into what exactly happens in the graphical version of Elliott et al. but since you know that better than I do, might be a good idea. Another topic we can adress in July!