Flow and GFlow verifier

[masa10-f]

Before submitting, please check the following:

• Make sure you have tests for the new code and that test passes (run tox)
• format added code 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:

Create flow and gflow checker.

TODO in this PR

• [x] Create flow and gflow checker
• [x] Make unittest for them
• [x] Add type hint to the other methods in gflow.py

Related issue:

99

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]

(optional) we could also test with patterns (graphs) transpiled from random circuits or after perform_pauli_measurments.

'opt' transpile with Rzz gate (phase gadget) shouldn't have a flow so might be a good 'gflow-but-not-flow' graph example to add?

[masa10-f]

Thanks for your comment!

(optional) we could also test with patterns (graphs) transpiled from random circuits or after perform_pauli_measurments.

I will add it to the flow check test. But we cannot know pauli-node measured graph always has no flow(Pauli measured graph sometimes has a flow)

'opt' transpile with Rzz gate (phase gadget) shouldn't have a flow so might be a good 'gflow-but-not-flow' graph example to add?

Yes, it's the case. But this is covered with the current 'gflow-but-not-flow' case. The extended Rzz gate pattern has only YZ plane measurement but the current test has all the measurement planes. But, unit graphs with each single measurement plane could be a good unit test, so I will consider it.

[masa10-f]

It seems that the node order of matrix representation needs to be considered more carefully since the current get_layers_from_flow does not work well to make flow matrix or oddneighbor matrix upper triangular. Maybe dynamic reordering is necessary?

[masa10-f]

Or it could be feasible to reconstruct an effective order from both (g)flow and Odd(f/g). I plan to explore this approach soon

[masa10-f]

I've included odd neighbor into get_layers_from_flow. As a result, the flow checker test with random circuit now works correctly. However, the gflow checker test still fails. Investigating the test graph, I discovered that gflow returns an incorrect gflow, where gflow is not a partial order. This could be attributed to either gflow or get_meas_planes. Therefore, I plan to investigate the bug in the gflow finding function tomorrow.

[masa10-f]

In this graph, M(49) = YZ, M(61) = XZ XYand

\begin{align*}
g(49) = (49, 28)\\
g(61) = (49)\\
Odd(g(49)) = (8, 61)\\
Odd(g(61)) = (61)
\end{align*}

So, it violates gflow condition.

[pafloxy]

I see :/. In the picture does the index of the node respect the partial order $\prec$ imposed by the gflow ?

[masa10-f]

I see :/. In the picture does the index of the node respect the partial order imposed by the gflow ?

I think the answer would be no. This graph was generated from a random circuit and perform_pauli_measurements, and it inherited the node index from the original graph, which did not include Pauli measurements. In such cases, gflow is not generally consistent with the original index order.

[pafloxy]

I think the answer would be no. ...

Ahn okay I see.

As much I understand the gflow is incorrect beacuse $g(v{61})$ does not contain $v{49}$ which should have been the case as per the rule for $\lambda = XZ$. Right ? Now adding a vertex to its own correction set is not dependent with the rest of the graph-structure I guess, no ? (I haven't delved deeper into the code yet , sorry :/ ). I mean, my guess is the problem did not arise from the non-solvability of the the linear-equations involved, what do you say :?

[masa10-f]

@pafloxy Sorry, I made a mistake. The measurement plane of node 61 is XY. Therefore, g and odd(g) are correct in the sense of measurement plane. However, according to the definition of gflow (g1) and (g2), we get 61 < 49 from $g(61) = (49)$, but also 49 < 61 from $Odd(g(49) = (8, 61)$. This is not a valid partial order.

https://quantum-journal.org/papers/q-2021-03-25-421/ See Definition 2.36

[pafloxy]

Ahn okay, I didn't have access to the $\prec$ in the diagram you provided so couldn't have guessed that. But if this is indeed the case then perhaps it has t do with the solver I believe. No ?

PS. : Btw I usually have theorems from this paper right on top of my head so for convenience in future discussions just put the theorem index and I'll take it from there :)

[masa10-f]

But if this is indeed the case then perhaps it has t do with the solver I believe. No ?

Yes, I guess that the cause lies in the solver. Sorry, I missed the generation code for generating the above graph.

By changing depth and width of get_rand_circuit, we can probably find a same kind of bug.

seed = 30
circ = get_rand_circuit(5, 5, seed=seed)
pattern = circ.transpile()
pattern.standardize()
pattern.shift_signals()
pattern.perform_pauli_measurements()
nodes, edges = pattern.get_graph()
graph = nx.Graph()
graph.add_nodes_from(nodes)
graph.add_edges_from(edges)
input = set()
output = set(pattern.output_nodes)
meas_planes = pattern.get_meas_plane()
g, l_k = gflow(graph, input, output, meas_planes)

[pafloxy]

Sorry for replying late but I'll try to reproduce the same errors on my end.

I was going to ask you to add more algebra tools to the linalg.py module but I realised you added a few in this PR wrt 80-bug-gflow-finding ... I was wondering if it would be convenient to inherit methods from galois.GF2 directly since it has lot os useful ones.

For the incorrect gflow you mentioned above, was the gflow.check_gflow() able to recognise the error ? I'm asking to make sure that atleast there is no issue with the checker. I was going through the code of it and it seemed alright from up-front, tried it on some examples too and they seemed to work as well.

[pafloxy]

@masa10-f So could you manage to find the errors in the implementation of gflow.gflow()

[masa10-f]

@pafloxy Sorry for my late reply. I found the cause and just fixed. The error stems from the permutation inconsistency in MatGF2.forward_eliminate and related methods.

I was wondering if it would be convenient to inherit methods from galois.GF2 directly since it has lot os useful ones.

I agree with your suggestion. I'll create an issue about this.

[pafloxy]

Thanks a lot!

I found the cause and just fixed. The error stems from the permutation inconsistency in MatGF2.forward_eliminate and related methods.

Where can I find the updated version? Did you commit it somewhere?

[shinich1]

Thanks a lot!

I found the cause and just fixed. The error stems from the permutation inconsistency in MatGF2.forward_eliminate and related methods.

Where can I find the updated version? Did you commit it somewhere?

perhaps this commit? https://github.com/TeamGraphix/graphix/pull/112/commits/655c99f404d3ec3b559953a82e801c8c049815da

I will complete the review soon so this can be merged in, please add comments if you have any @pafloxy .

[masa10-f]

@pafloxy @shinich1 Thanks! I fixed in this commit

perhaps this commit? https://github.com/TeamGraphix/graphix/commit/655c99f404d3ec3b559953a82e801c8c049815da

[shinich1]

@masa10-f talked with @mgarnier59 re this PR, please squash and merge!