Is spider rule likely buggy?

[rcasjimenez]

I have executed a set of rules to a circuit which is in this repository ('mod5_4_before'). After applying a spider rule to this circuit with several previous transformations, I have noticed that after applying it the resulting tensor is not equivalent to the original. Am I missing something? I attach an execution in which I checked it:

fname = os.path.join('..','circuits','Fast', 'mod5_4_before')
circ = zx.Circuit.load(fname).to_basic_gates()

x = circ.to_graph() # We first have to convert the circuit into a ZX-graph
graph = x.copy()

zx.to_gh(graph)
print('--------------------------------------')
match_spider = zx.rules.match_spider_parallel(graph.copy())
zx.rules.apply_rule(graph, zx.rules.spider, [match_spider[6]])
print(compare_tensors(tensorfy(x.copy()), tensorfy(graph.copy())))
print('--------------------------------------')
match_spider = zx.rules.match_spider_parallel(graph.copy())
zx.rules.apply_rule(graph, zx.rules.spider, [match_spider[7]])
print(compare_tensors(tensorfy(x.copy()), tensorfy(graph.copy())))
print('--------------------------------------')
match_id = zx.rules.match_ids_parallel(graph.copy())
zx.rules.apply_rule(graph, zx.rules.remove_ids, [match_id[1]])
print(compare_tensors(tensorfy(x.copy()), tensorfy(graph.copy())))
print('--------------------------------------')
match_spider = zx.rules.match_spider_parallel(graph.copy())
zx.rules.apply_rule(graph, zx.rules.spider, [match_spider[3]])
print(compare_tensors(tensorfy(x.copy()), tensorfy(graph.copy())))
print('--------------------------------------')
print(compare_tensors(tensorfy(x.copy()), tensorfy(graph.copy())))
print(compare_tensors(x.copy(), graph.copy()))
match_spider = zx.rules.match_spider_parallel(graph.copy())            # wrong ?
print(match_spider)
zx.rules.apply_rule(graph, zx.rules.spider, [match_spider[11]])
print(compare_tensors(tensorfy(x.copy()), tensorfy(graph.copy())))
print(compare_tensors(x.copy(), graph.copy()))

Output:

--------------------------------------
True
--------------------------------------
True
--------------------------------------
True
--------------------------------------
True
--------------------------------------
True
True
[(17, 21), (48, 54), (87, 91), (27, 36), (79, 83), (66, 68), (37, 44), (64, 70), (35, 39), (5, 6), (14, 18), (51, 60)]
False
False

[jvdwetering]

Not sure if this is what is causing it, but you are applying the matcher to a copy of the graph and not the original graph. The copy does not have to have the same labelling of vertices, so then when you apply a rewrite to the original graph it might be applying it to the wrong set. If you remove the .copy() everywhere, is it then correct?

[rcasjimenez]

Thanks @jvdwetering!, you're right, that was the issue. I didn't know about the relabeling feature in the copy function.

I have continued testing by applying transformations individually, not making previous copies of the graph and I have reached a step ('13-False') in which the result I obtain does not seem satisfactory to me when applying the transformation relative to 'pivot' considering a matcher called 'pivot_boundary'. I attach the result obtained:

x = circ.to_graph() # We first have to convert the circuit into a ZX-graph
graph = copy.deepcopy(x)
zx.to_gh(graph)
print('--------------------------------------')
match_spider = zx.rules.match_spider_parallel(graph)
zx.rules.apply_rule(graph, zx.rules.spider, [match_spider[6]])
print(f'1-{compare_tensors(tensorfy(x), tensorfy(graph))}')
print('--------------------------------------')
match_spider = zx.rules.match_spider_parallel(graph)
zx.rules.apply_rule(graph, zx.rules.spider, [match_spider[7]])
print(f'2-{compare_tensors(tensorfy(x), tensorfy(graph))}')
print('--------------------------------------')
match_id = zx.rules.match_ids_parallel(graph)
zx.rules.apply_rule(graph, zx.rules.remove_ids, [match_id[1]])
print(f'3-{compare_tensors(tensorfy(x), tensorfy(graph))}')
print('--------------------------------------')
match_spider = zx.rules.match_spider_parallel(graph)
zx.rules.apply_rule(graph, zx.rules.spider, [match_spider[3]])
print(f'4-{compare_tensors(tensorfy(x), tensorfy(graph))}')
print('--------------------------------------')
match_spider = zx.rules.match_spider_parallel(graph)
zx.rules.apply_rule(graph, zx.rules.spider, [match_spider[11]])
print(f'5-{compare_tensors(tensorfy(x), tensorfy(graph))}')
print('-----------------------------------------')
match_spider = zx.rules.match_spider_parallel(graph)
zx.rules.apply_rule(graph, zx.rules.spider, [match_spider[10]])
print(f'6-{compare_tensors(tensorfy(x), tensorfy(graph))}')
print('-----------------------------------------')
match_spider = zx.rules.match_spider_parallel(graph)
zx.rules.apply_rule(graph, zx.rules.spider, [match_spider[7]])
print(f'7-{compare_tensors(tensorfy(x), tensorfy(graph))}')
print('-----------------------------------------')
match_spider = zx.rules.match_spider_parallel(graph)
zx.rules.apply_rule(graph, zx.rules.spider, [match_spider[5]])
print(f'4-{compare_tensors(tensorfy(x), tensorfy(graph))}')
print('-----------------------------------------')
match_pivot_parallel = zx.rules.match_pivot_parallel(graph)
zx.rules.apply_rule(graph, zx.rules.pivot, [match_pivot_parallel[1]])
print(f'9-{compare_tensors(tensorfy(x), tensorfy(graph))}')
print('-----------------------------------------')
match_spider_parallel = zx.rules.match_spider_parallel(graph)
zx.rules.apply_rule(graph, zx.rules.spider, [match_spider_parallel[7]])
print(f'10-{compare_tensors(tensorfy(x), tensorfy(graph))}')
print('-----------------------------------------')
match_spider_parallel = zx.rules.match_spider_parallel(graph)
zx.rules.apply_rule(graph, zx.rules.spider, [match_spider_parallel[2]])
zx.draw(graph, labels=True)
print(f'11-{compare_tensors(tensorfy(x), tensorfy(graph))}')
print('-----------------------------------------')
print(f'12-{compare_tensors(tensorfy(x), tensorfy(graph))}')
match_pivot_boundary = zx.rules.match_pivot_boundary(graph)
print(match_pivot_boundary)
print(f'match_pivot_boundary[0]:{match_pivot_boundary[0]}')
zx.rules.apply_rule(graph, zx.rules.pivot, [match_pivot_boundary[0]])
zx.draw(graph, labels=True)
print(f'13-{compare_tensors(tensorfy(x), tensorfy(graph))}')

Output:

Maybe, the resulting graph is not what I should expect. What do you think could be my mistake or assumption that causes the graphs to not be equivalent?

[jvdwetering]

So there is a part in pyzx which is less nice, which is that some of the matchers are a bit hacky and change the graph in place. I believe match_pivot_boundary is one of these. So then if you don't apply all the matches you find, you might get a graph that has the wrong semantics. There is a current PR that would fix this. Can you check whether the matcher for match_pivot_boundary finds multiple matches?

[rcasjimenez]

Thanks for replying @jvdwetering.

• I saw in the code (v0.8) what you are saying regarding some matchers. As far as I know, if I'm not mistaken, the matchers that perform an in-place modification of the graph are two:

  • match_pivot_boundary
  • match_pivot_gadget
  • match_phase_gadgets

• Yes, in relation to your request, in the same trace that I attached you can see two possible values for that matcher: [(6, 5, [ ], [4]), (10, 11, [ ], [0])]

  In the next line, I selected the first one of them: (6, 5, [ ], [4])

If you want me to perform any other type of test, please, let me know.

[jvdwetering]

It looks like in your final step the graph that you are applying the pivot to is not graph-like (it has unfused regular edges between spiders). Pivot assumes the diagram is in graph-like form (all spiders fused that can be fused). So it could be that that's causing an error.

[rcasjimenez]

Yes, now I see. The graph is not graph-like and I cannot apply the 'pivot' operation.

@jvdwetering , so considering this, in order to apply the 'pivot' operation, I´d like to ask you the following questions:

• Are the 'to_gh' and 'spider_simp' operations the only ones I need to make sure the 'pivot' operation is applied?
• Another question that arises is when applying the 'pivot' operation to a 'graph-like' graph. Is the resulting graph also 'graph-like' by definition?
• Moreover, if we consider other operations to be applied, such as the 'bialgebra' operation. Does the graph have to be of the "graph-like" type in order to apply the rule?

[jvdwetering]

Yes, to_gh and spider_simp make a diagram graph-like. Applying pivots (and local complementations) preserves it being graph-like. Bialgebra works on z and x spiders and hence never applies on graph-like diagram. You can think of a pivot as the version of bialgebra that applies on graph-like diagrams.

[rcasjimenez]

I understand, thank you @jvdwetering.

A naive question: How can I know if a transformation (any other transformation other than 'pivot', 'lcomp' and 'bialgebra' already mentioned) requires that the graph on which it is applied must be “graph-like” or not? Is it written down or specified somewhere?

[jvdwetering]

It should usually be specified in the docstring of the function. If it isn't, then it should probably be added.

[rcasjimenez]

I am afraid that there are no references to the need to comply with that condition. If I take a look at the files: rules.py, simplify.py, hrules and hsimplify no reference to graph-like condition is mentioned. :\

[jvdwetering]

Hmm, I must have imagined this being clearly stated somewhere. Yes, it would be good if this would be added. You can create an issue if you want.

[jvdwetering]

I'm closing this as it's clear that this is not a bug, but a lack of documentation.