Implement a faster Pauli-flow finding algorithm

[mgarnier59]

A novel and faster algorithm has recently been proposed for finding Pauli flow on open graphs, see Mitosek and Backens, An algebraic interpretation of Pauli flow, leading to faster flow-finding algorithms, arXiv: 2410.23439 (preprint).

An efficient implementation of this algorithm would be a good feature for Graphix. Additionally a thorough profiling of the implementation together with a benchmark against the previous algorithm would allow to check if there are any issues coming up in practice.

[Newtech66]

Hi, could you suggest how I could test my implementation? Any example problems or ways to generate random data for benchmarking?

Edit: I just realised unit tests exist already. But I'm open to other suggestions.

[thierry-martinez]

It would be interesting to benchmark your implementation against fastflow, which implements the same algorithm currently used in Graphix. Although this algorithm has suboptimal complexity, fastflow is written in Rust rather than Python, and thus offers better performance than the Graphix implementation.

To evaluate the benefits of your improved complexity, you could measure how both implementations perform as the size of the input graphs increases. For example, Figure 1 in this paper (https://arxiv.org/abs/1705.01535) provides an infinite family of graphs with gflow that could be useful for such benchmarking.

[Newtech66]

I have a question: a node cannot simultaneously be an input and an output node, right?

[thierry-martinez]

Yes, indeed, input and output node sets may overlap.

[Newtech66]

There's something I can't seem to resolve. Consider the test case on this line. According to the definition of the flow-demand matrix $M$ in Definition 3.4 on page 8, the flow-demand matrix of this test case should be

$$ M = \begin{array}{c c} & \begin{array}{c c c c} 1 & 2 & 3 & 4 \\ \end{array} \\ \begin{array}{c c c c} 0 \\ 1\\ 2\\ 3 \end{array} & \left[ \begin{array}{c c cc} 0&0&0&0\\ 1&0&0&0\\ 0&1&0&0\\ 0&0&1&1\\ \end{array} \right] \end{array} $$

But this is not invertible and therefore a Pauli flow should not exist according to Algorithm 2 on page 35. But this is marked as a test case which does have a Pauli flow. I can't figure out the inconsistency.

Edit: To make things even worse, the order-demand matrix is identically zero.

$$ N = \begin{array}{c c} & \begin{array}{c c c c} 1 & 2 & 3 & 4 \\ \end{array} \\ \begin{array}{c c c c} 0 \\ 1\\ 2\\ 3 \end{array} & \left[ \begin{array}{c c cc} 0&0&0&0\\ 0&0&0&0\\ 0&0&0&0\\ 0&0&0&0\\ \end{array} \right] \end{array} $$

[mgarnier59]

Hi, thanks for your message. Looking at _graph8 here,

The graph is

nodes = [0, 1, 2, 3, 4]
edges = [(0, 1), (0, 2), (0, 4), (3, 4)]
inputs = {0}
 outputs = {4}

With measurements

meas_planes = {
        0: Plane.YZ,
        1: Plane.XZ,
        2: Plane.XY,
        3: Plane.YZ,
    }
    meas_angles = {0: 0.5, 1: 0, 2: 0.5, 3: 0}

These measurement have not yet been converted in Pauli measurements but will be soon so we just have to translate them by hand. Graphix follows the same convention as most MBQC papers (eg here and here i.e.

• for the XY plane: angle 0 corresponds to the $X$ basis and $\pi/2$ to the $Y$ basis
• for the XZ plane: angle 0 corresponds to the $Z$ basis and $\pi/2$ to the $X$ basis
• for the YZ plane: angle 0 corresponds to the $Z$ basis and $\pi/2$ to the $Y$ basis

So the measurement are now: {0: Y, 1: Z, 2: Y, 3: Z}.

Lets build the flow-demand matrix $M$ row by row (keeping your basis choice):

• node 0 is an input node and is measured in the $Y$ basis. Hence we use the third bullet of Def 3.4 p.9. As an input node, it doesn't appear in the column space of the matrix ($M_{00}$ doesn't exist). Hence we fill the rest with the adjacency matrix. Since node 0 is connected to nodes 1, 2, 4 we get the row $(1 1 0 1)$.
• node 1 is neither input nor output and is measured in the $Z$ basis, hence we use the second bullet point. $M_{11}$ exists so we set it to 1. And the rest is set to 0. Hence the row $(1 0 0 0)$.
• node 2 is neither input nor output and is measured in the $Y$ basis, hence we use the third bullet point. $M_{22}$ exists so we set it to 1. And we set the rest as the adjacency matrix. However node 2 is only connected to node 0 which is an input node and does not belong to the column space of $M$ hence all other entries are 0. We get $(0 1 0 0)$.
• node 3 is neither input nor output and is measured in the $Z$ basis, hence second bullet point again. $M_{33}$ exists so we set it to 1. And all other entries are set to 0. We get $(0 0 1 0)$.

All in all I get the flow-demand matrix

$$ M = \begin{pmatrix} 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \end{pmatrix} $$

which has non-zero determinant but differs from the one you found. So maybe there's an error there. Provided the one I gave is correct, I let you correct it as well as the order-demand matrix $N$ and everything should be fine!

[Newtech66]

I see where the error is: It's because the get_pauli_nodes method in gflow.py is incorrect. See here. Specifically, the cases for the $YZ$ plane are switched. After correcting it, my code outputs the flow-demand matrix you found. I can correct this in my PR. But why wasn't this error caught in any tests? The currently implemented flow-finding algorithm should have detected the non-existence of a Pauli flow, and even if it did output one, verify_pauliflow should have caught it. Maybe they are all dependent on the incorrect get_pauli_nodes method.

[thierry-martinez]

Thank you, @Newtech66, for reporting the bug on plane $YZ$. I've created a dedicated PR (#297) to address the issue. Since the PauliMeasurement.try_from constructor already implements the logic for computing the axis from a Pauli measurement, it’s better to use it here.

[Newtech66]

Is it always true that a random graph generated by get_rand_graph has a Pauli flow?

[Newtech66]

I don't think so: if the number of input nodes is greater than the number of output nodes then a flow should not exist. But get_rand_graph does generate such graphs. Section 4.2 of the linked reference states that a flow does not exist if the number of output nodes is strictly less than the number of input nodes.

There are other issues with the function, but this one is the biggest problem. In light of this, the tests with the old Pauli flow implementation should never have passed, I think.

[Newtech66]

Figure 1 in this paper (https://arxiv.org/abs/1705.01535) provides an infinite family of graphs with gflow that could be useful for such benchmarking.

But it's for gflow. It lacks the specification of measurement planes and angles. How could I add those such that the graph has Pauli flow?

From page 2 of (https://arxiv.org/abs/2410.23439), am I correct in saying that, I can assign measurement planes at random to the vertices and the resulting graph will have Pauli flow?

Edit: No, what I just said is not true.

[Newtech66]

The function verify_pauliflow might not be implemented correctly. From the reference, I see that we should be checking $Odd(c(u))$, but the code has odd_flow[node], which translates to $Odd(u)$, if I'm understanding it correctly.

Edit: I was wrong about this, please disregard what I said above.