"fuse spiders" rule should fuse all fusable spiders in the selection

[dlyongemallo]

If the user selects two vertices which can be fused, the "fuse spiders" button is enabled, and clicking it fuses the two vertices. So far, so good.

If the user selects more than two vertices, among which are vertices which can be fused, the "fuse spiders" button is enabled, but clicking it fuses just a subset of the possible vertices which may be fused. For example, picking three vertices which can be fused results in fusing two out of the three. If multiple groups of fusion are possible, one pair is fused out of each group. It appears to be the two vertices with the lowest labels, so selecting the corresponding set of vertices on two isomorphic graphs don't result in the same set of fusions.

Is the intended behaviour that all of the selected vertices should be fused as much as possible? If so, that doesn't appear to be what it's doing.

(If only two vertices are fused, I think the animation should be like the fuse animation added in #123 where the final vertex ends up at the average of the coordinates of the initial vertices. For multiple vertices, maybe they should end up at the centroid. But the animation is a cosmetic thing and incidental to this issue.)

[RazinShaikh]

This is because the rule matcher for fusion in PyZX (link) only matches pairs of non-interacting vertices. Ideally, it would be nice if clicking fuse fused everything in the selection. Perhaps @jvdwetering can comment why it is implemented this way in PyZX?

[jvdwetering]

Razin is right that this is how this works. I think the more logical behaviour in this case would be to fuse all of them. This would require a little bit more work though (like making a fuse_simp that keeps fusing spiders until nothing more can be fused).

[dlyongemallo]

Is there no more efficient algorithm than that?

[jvdwetering]

There is, but that would require more code-writing. The solution I gave is one that would be very simple. Since all the rewrites currently work with a 'apply rewrite to all non-overlapping parts' this is something we might want to do for more rewrites. Maybe we want a distinction between 'apply this rewrite once' and 'apply to selection until it can't be applied any more'.

[RazinShaikh]

I am not sure if we need this distinction. Applying the rewrite once is the same as selecting the exact two spiders and clicking fuse spiders which fuses everything in the selection.

[dlyongemallo]

PR #187 added a side panel with a tree of rewrite buttons, where "fuse spiders" under "Basic rules" maintains the existing behaviour described in this issue (applies the rewrite once to non-overlapping subgraphs), and "spider fusion" under "Simplification routines" implements the suggested behaviour (applies to selection until it can't be applied any more).

If that's the intended UI and behaviour, this issue can be closed.

Incidentally, I noticed that the "bialgebra" option under "Simplification routines" is broken. Is this also intended to be the "applies to selection until it can't be applied any more" options? (The "bialgebra" option under "Basic rules" still works, and only applies the rewrite once.) Should an issue be filed about this, or is a fix already in development?

[RazinShaikh]

Would it make more sense for the spider fusion simplification routine to be the default option for fusing spiders?

[jvdwetering]

I think so. With regards to the "bialgebra" under the simplification routines. I think this one can just be removed.

[dlyongemallo]

Is this also intended to be the "applies to selection until it can't be applied any more" options?

I was playing with this and saw immediately that the "apply bialgebra until it can't be applied any more" wouldn't work as the graph just keeps getting more and more complicated.

The way that the bialgebra rule works as coded is it takes a subgraph with, e.g., 2 vertices, and turns it into a subgraph with 4 vertices. Intuitively, that doesn't seem like a simplification to me (obviously as the result has more rather than fewer vertices!), but maybe this is because I'm not that familiar with how zx-based simplifications work yet. I have a couple of questions about this:

1. Is there supposed to be a reverse version of the rule that goes in the other direction? Is going in that direction (with fewer vertices) ever useful for simplification, or does it get stuck in, say, a local minimum? (By this, I mean that even though the resulting graph has fewer vertices, there are better ways to optimise the original graph with other rules which are then made impossible by applying this one.)
2. Does the application of the bialgebra rule (adding more vertices) reveal structure that allows for optimisations which would otherwise have been hidden? That is, the bialgebra rule would be an intermediate step where you take a 2-vertices subgraph and turn it into a 4-vertices subgraph, but then the resulting overall graph allows you to perform, e.g., a spider fusion that results in a simpler graph than the original graph.
3. Or is the rule mostly used theoretically for proofs and not practically for circuit simplification?

This is probably the sort of thing that would be best explained in person in front of a whiteboard. As that's not an option at the moment, can you point me to any examples of the bialgebra rule being used in a simplification step in, say, a paper or lectures slides? Probably I just need to see a few examples of how it's used in real life to understand its application.

(Sorry this is slightly off-tangent from the original issue with fusion, but it's related in that I'm trying to understand the organisation of the rewrite buttons and how the rewrites relate to each other.)

[RazinShaikh]

1. There is supposed to be a reversed version for bialgebra that goes from 4 to 2 vertices. There was an open issue long time ago (see Implement bialgebra in the other direction #20 ) but when I implemented custom rewrites, I got too excited and closed it. However, it is useful to have this rewrite rule in implemented as a PyZX function that works for arbitrary arity. So we should reopen the issue.
2. Yes, the bialgebra that goes from 2 to 4 could be an intermediate step that actually reduces the number of total vertices. It is part of the routine that takes a clifford circuit and simplifies it to the clifford normal form. Here's an example (figure produced by tikz export of zxlive):
   
3. Both directions of the bialgebra rule are used all the time. I don't think there is a general rule for which direction of bialgebra to apply and it is common to end up using both directions within the same proof.,

[dlyongemallo]

Thanks for the explanation, that clarifies things a lot.

One thing I'm slightly confused about. In the issue you linked, it says:

Right now we can only apply bialgebra in only one direction, which reduces the number of nodes.

Isn't the bialgebra operation as implemented the other direction, i.e., the one which increases the number of nodes?

If I'm not mistaken, it's possible to select a group of vertices such that the bialgebra rule could be applied to them in either direction. Is this correct? How should this be handled in the UI?

[RazinShaikh]

I am not sure why it says "which reduces the number of nodes"

We should have two rules in the UI, one for each direction of the bialgebra. Then the user can click on the appropriate button based on what they want to do.