[Bug]: Gflow finding algorithm

[masa10-f]

Describe the bug

As per the proposed (expanded) gflow finding algorithm outlined in M. Backens et al., there is an issue with the current implementation within the graphix.gflow.gflow module.

To Reproduce

For instance, consider the underlying graph provided below. While this graph possesses a gflow, the current method fails to identify it.

Nodes = {0, 1, 2, 3, 4, 5}
Edegs = {(0, 1), (0, 2), (0, 4), (1, 2), (1, 4), (2, 4), (4, 3), (4, 5)}
Measurement planes = {0: "XY", 1: "XZ", 3: "XY", 4: "XY}
Input = {0, 3}
Output = {2, 5}

The root cause of this issue is that the current implementation's handling of conditional branches in measurement planes does not align with the gflow definition.

Expected behavior

One of the solutions is like,

0: {1},
1: {1, 2},
3: {1, 4},
4: {5}

Environment (please complete the following information):

• OS: Ubuntu 20.04
• Python version: 3.8.10
• Related module versions if applicable: graphix==0.2.0

Additional context

Currently, graphix depends on z3-solver for gflow identification. However, this dependency could be substituted with a solver tailored for boolean system of equations. Such a solver can be efficiently implemented using only numpy.

[pafloxy]

Hello @masa10-f ,

The root cause of this issue is that the current implementation's handling of conditional branches in measurement planes does not align with the gflow definition.

Could you maybe elaborate a bit more on this, specifically which part of the implementation you are reffering to ?

Currently, graphix depends on z3-solver for gflow identification. However, this dependency could be substituted with a solver tailored for boolean system of equations. Such a solver can be efficiently implemented using only numpy.

Actually I did look for efficient means of solving linear equations on GF2, but the methods I found were rather sophisticated (Gaussian Elimination ?) moreover I was not convinced if they could find all possible solutions to the set of equations either. (for the current implementatio solbebool finds just one). I would be interested in knowing how you plan to approach this problem. :)

[masa10-f]

Hi @pafloxy ,

Could you maybe elaborate a bit more on this, specifically which part of the implementation you are reffering to ?

I referred to the following part(graphix.gflow l.192-203).

for u in iter(v_rem):
    if meas_plane[u] == "Z":
        c_set = c_set | {u}
        g[u] = set()
        l_k[u] = k
        continue
    elif meas_plane[u] in ["XY", "XZ", "X", "Y"]:
        Iu = np.zeros(n, dtype=np.int8)
        Iu[v_rem_list.index(u)] = 1
    elif meas_plane[u] == "YZ":
        Iu = np.ones(n, dtype=np.int8)
        Iu[v_rem_list.index(u)] = 0

According to Appendix D. of M. Backens et al., a precise conditional branch differs slightly from the current one. Let U be a node-set corresponding to the right-hand side of a boolean system of equations(Ax = u), that emerges when finding gflow.

For each node, the precise conditional branch for U is as follows:

• XY: $U = set(\text{node}) $
• XZ: $U = (OddNeighbor(\text{node}) \cap \overline{O}) \cup set(\text{node})$
• YZ: $U = OddNeighbor(\text{node}) \cap \overline{O}.$

Moreover, the branches for "X," "Y," and "Z" should be removed since gflow does not depend on measurement angles.

Actually I did look for efficient means of solving linear equations on GF2, but the methods I found were rather sophisticated (Gaussian Elimination ?) moreover I was not convinced if they could find all possible solutions to the set of equations either. (for the current implementatio solbebool finds just one). I would be interested in knowing how you plan to approach this problem. :)

Finding gflow is essentially equivalent to solving for x in the equation Ax = u, where the coefficient matrix A is typically non-square. So, I'm developing a solver for such a non-square system of equations. As you mentioned, this solver uses Gauss-Jordan elimination and column pivoting. The uncertainty of gflow appears as a kernel of the coefficient matrix A. Therefore, we can write down all possible solutions for maximally delayed gflow. While I've completed the core implementation, I'm debugging and refactoring the code. Maybe I'll push it in the next few days.

[pafloxy]

Moreover, the branches for "X," "Y," and "Z" should be removed since gflow does not depend on measurement angles.

I agree.

Thanks a lot for the implementation, I will be happy to use it after you have updated it in the repo. :)