Add a function that checks if a pattern implements a given flow

[thierry-martinez]

We are missing a function that checks whether a given pattern conforms to a given flow.

This function would be complementary to the open issue #120, which proposes extending generate_from_pattern to enable it to generate a pattern from a given open graph and a given flow.

[EarlMilktea]

@thierry-martinez (CC: @mgarnier59 )

I'm working on this in the new PR (takeover of #280) and now encountering some problems.
Please let me know your comments on them.

• On .get_layers

Is .get_layers guaranteed to give the minimum number of distinct layers?
If so, is it consistent with maximally-delayed flow/gflow (can we always find a corresponding correction set)?

• How to fix layers

Is the algorithm .get_layers the only way to find layers?

[thierry-martinez]

I'm working on this in the new PR (takeover of #280) and now encountering some problems.

I’m happy that you’re working on this new issue, but it does not necessarily have to be solved in the same PR as the integration with fastflow. From my perspective, #280 was quite close to being merged: my only remarks were mainly to revert the introduction of gflow_shim and the change in the signature of the find_flow functions. It would be better, in my opinion, to avoid postponing the merge and to keep the PR manageable. However, before the merge, it would be good to have benchmarks that show the performance gain compared to the previous find_flow implementations.

Is .get_layers guaranteed to give the minimum number of distinct layers?

A priori, yes: taking for each layer the nodes that are minimal once we remove the nodes placed in previous layers is optimal.

If so, is it consistent with maximally-delayed flow/gflow (can we always find a corresponding correction set)?

No, we have neither uniqueness of maximally-delayed flow nor uniqueness of layering for a given flow.

I think the right approach to check whether a pattern implements a given flow is:

• To check that the pattern is runnable (that is to say, that N command prepare fresh nodes, E and M commands are applied on prepared but not yet measured nodes, and that the domains of M, X, and Z only consist only on measured nodes).
• To check that the corrections match those implied by the flow function.

[EarlMilktea]

I've found several problems related to swiflow verification and this issue.

• min(layer) must be strictly equal to 0

We might loosen this condition, because layer in principle has translation invariance.

• cannot perform partial verification

Non-optimal flows (having redundant layers) never pass the test.

[EarlMilktea]

@thierry-martinez

Opened TeamGraphix/swiflow#18 .
I naively believe infer_layer gives maximally-delayed layers (no rigorous proof though).