Circuit extraction says graph is not fully reduced even after applying full_reduce

[zickgraf]

The following example throws an error:

import pyzx as zx
g = zx.Graph.from_json('{"wire_vertices": {"b0": {"annotation": {"boundary": true, "coord": [-0.322, 0.634], "input": true, "output": false}}, "b1": {"annotation": {"boundary": true, "coord": [2.098, 0.794], "input": false, "output": true}}}, "node_vertices": {"v0": {"annotation": {"coord": [0.978, 0.734]}, "data": {"type": "hadamard", "is_edge": "false", "value": "\\\\pi"}}}, "undir_edges": {"e0": {"src": "b0", "tgt": "v0"}, "e1": {"src": "b1", "tgt": "v0"}}, "scalar": "{\\"power2\\": 0, \\"phase\\": \\"0\\"}"}')
zx.full_reduce(g)
zx.draw(g)
zx.extract_circuit(g)

Output:

File ~/envname/src/pyzx/pyzx/extract.py:704, in extract_circuit(g, optimize_czs, optimize_cnots, up_to_perm, quiet)
    702 # Since we were extracting from right to left, we reverse the order of the gates
    703 c.gates = list(reversed(c.gates))
--> 704 return graph_to_swaps(g, up_to_perm) + c

File ~/envname/src/pyzx/pyzx/extract.py:789, in graph_to_swaps(g, no_swaps)
    787 inp = list(g.neighbors(v))[0]
    788 if inp not in inputs: 
--> 789     raise TypeError("Algorithm failed: Graph is not fully reduced")
    790     return c
    791 if g.edge_type(g.edge(v,inp)) == EdgeType.HADAMARD:

TypeError: Algorithm failed: Graph is not fully reduced

Since I explicitly called full_reduce, this error is unexpected for me. Is this a bug or am I misinterpreting things?

Additionally note that the failed circuit extraction actually seems to change g: Calling zx.draw(g) after this error draws a circuit where the hadamard node has a phase of 0.

PyZX Version: commit e4fe332 (current master at the time of writing)

[dlyongemallo]

Just to make things maybe easier to understand, the above g seems to be equivalent to the following:

g = zx.Graph()
g.add_vertex(zx.VertexType.H_BOX, qubit = 0, row = 1)
g.add_vertex(zx.VertexType.BOUNDARY, qubit = 0, row = 0)
g.add_vertex(zx.VertexType.BOUNDARY, qubit = 0, row = 2)
g.add_edge((0,1))
g.add_edge((0,2))
g.auto_detect_io()

Using this g reproduces the error. The graph_to_swaps docstring says:

"""Converts a graph containing only normal and Hadamard edges into a circuit of Hadamard
and SWAP gates. If 'no_swaps' is True, only add Hadamards where needed"""

I think the intended meaning of "only normal and Hadamard edges" is "no vertices other than inputs and outputs" (since there are no other kinds of edges). The function (implicitly) assumes that the only neighbours of the outputs are inputs, and the above g violates that assumption by having a H_BOX in between. However, the following graph g2, which is let's say spiritually the same as g, satisfies the assumption (and won't raise the error):

g2 = zx.Graph()
g2.add_vertex(zx.VertexType.BOUNDARY, qubit = 0, row = 0)
g2.add_vertex(zx.VertexType.BOUNDARY, qubit = 0, row = 1)
g2.add_edge((0,1), edgetype=zx.EdgeType.HADAMARD)
g2.auto_detect_io()

So I'm guessing that at some point, your g should've been converted into the g2 form, presumably in full_reduce. Or, if the input is in the wrong format and the user is expected to make such conversions, that should've been caught earlier with an assert upstream.

[zickgraf]

Thanks for the analysis! Turning all Hadamard nodes into Hadamard edges (which in the json simply means replacing is_edge := "false" by is_edge := "true") indeed seems to avoid the error. Maybe full_reduce should turn all Hadamard nodes into Hadamard edges?

[jvdwetering]

full_reduce indeed assumes the diagram is a ZX-diagram, and hence does not have H_BOXes. The 2-ary H-boxes are maybe a bit confusing since they also correspond to the regular Hadamard generators in ZX-diagrams, although they were not intended to be used this way in PyZX. Perhaps we can add a call of hsimplify.from_hypergraph_form to full_reduce to ensure all 2-ary H-boxes are H-edges.

[zickgraf]

full_reduce indeed assumes the diagram is a ZX-diagram, and hence does not have H_BOXes.

Thanks for the confirmation! Then the workaround of replacing is_edge := "false" by is_edge := "true" in the json should indeed do the trick, I guess.