`minimize_space` breaks runnability for patterns that are inconsistent with their graph flow

[thierry-martinez]

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]

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]

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!

[thierry-martinez]

Note that this bug can occur even for a deterministic pattern. The following example shows a pattern with causal flow for which minimize_space breaks runnability.

from graphix import Pattern
from graphix.command import N, E, M, X, Z
from graphix.gflow import flow_from_pattern

p = Pattern(
    input_nodes=[3],
    cmds=[
        N(1),
        E((1, 3)),
        N(4),
        E((1, 4)),
        N(0),
        E((3, 0)),
        M(3),
        M(1, s_domain={3}),
        N(2),
        E((0, 2)),
        M(0),
        N(5),
        E((4, 5)),
        M(4, s_domain={1}, t_domain={3}),
        Z(5, {1}),
        X(2, {0}),
        X(5, {4}),
    ],
    output_nodes=[2, 5],
)

print(flow_from_pattern(p))
# ({3: {1}, 1: {4}, 0: {2}, 4: {5}}, {0: 3, 3: 3, 1: 2, 4: 1, 2: 0, 5: 0})

p.minimize_space()

print(p)
# X(5,{4}) X(2,{0}) Z(4,{3}) Z(5,{1}) [M(4)]{1} E(4,5) N(5) M(0) E(0,2) N(2) M(3) E(3,0) N(0) [M(1)]{3} E(1,4) N(4) E(1,3) N(1)

p.simulate_pattern()
# KeyError: 3

The problem is closely linked with the discussion in #280 (#280 (comment)): the issue is that Pattern.get_measurement_order_from_flow calls find_flow instead of pattern_from_flow.

The underlying open graph of the pattern given in this example admits two causal flows: one going from 3 to 1 and one going from 3 to 0. The function find_flow finds the flow from 3 to 0, and in this case, M(1) is independent from M(3) and can go first. However, the pattern uses the other correction strategy, where M(1) is dependent from M(3): since minimize_space considers the wrong correction strategy and chooses to measure M(1) first, the runnability is broken.

[mgarnier59]

What's the status on this? Recent refactors should solve the problem? Let's discuss it.