[BUG] Unable to calculate depth of circuit with same operation used twice

[albi3ro]

Expected behavior

I expect the below code to output 2.

Actual behavior

sort encounters a cycle. Traceback below.

Additional information

PR #4398 does not fix the problem.

Source code

op = qml.PauliX(0)
tape = qml.tape.QuantumScript([op, op], [qml.expval(qml.PauliZ(0))])
tape.graph.get_depth()

Tracebacks

---------------------------------------------------------------------------
DAGHasCycle                               Traceback (most recent call last)
Cell In[2], line 3
      1 op = qml.PauliX(0)
      2 tape = qml.tape.QuantumScript([op, op], [qml.expval(qml.PauliZ(0))])
----> 3 tape.graph.get_depth()

File ~/Prog/pennylane/pennylane/circuit_graph.py:466, in CircuitGraph.get_depth(self)
    461         self._operation_graph = self._graph.subgraph(
    462             list(self._indices[id(node)] for node in self.operations)
    463         )
    464         self._extend_graph(self._operation_graph)
    465         self._depth = (
--> 466             rx.dag_longest_path_length(
    467                 self._operation_graph, weight_fn=lambda _, __, w: self._weight_func(w)
    468             )
    469             + 1
    470         )
    471 return self._depth

DAGHasCycle: Sort encountered a cycle

System information

master

Existing GitHub issues

• I have searched existing GitHub issues to make sure the issue does not already exist.

[che-burashco]

I'm playing around with Pennylane and thought I could try to tackle the issue as a part of the learning process if you don't mind. So far upon investigation it seems that the problem occurs because the operators passed to the QuantumScript point to the same object in memory and that causes an incorrect CircuitGraph to be built.

For example if you do something like this then you would get back the expected result:

op1 = qml.PauliX(0)
op2 = qml.PauliX(0)
tape = qml.tape.QuantumScript([op1, op2], [qml.expval(qml.PauliZ(0))])
tape.graph.get_depth()

There are quite a few things that seem to be going wrong in the code when the same object is used:

1. queue_idx is being set incorrectly here. In the example attached to the ticket both of the elements in the ops array will be pointing to the same object in memory and will have queue_idx of 1 (the first path in the loop will set it to 0 and the second one will set it to 1)
2. call to id on the operator will cause the same ID of the Operator object to be returned. This causes a problem here when we set the edge. In the example above since nodes for both observables will have the same ID we will actually have just one node in the graph for observables and we will create an edge that connects the node to itself. The last part is what's causing the DAGHasCycle exception.

I can see a few possible solutions and this is where I would need some feedback:

1. duplicate operators that are being passed in: this would allow to have separate objects in memory, but the problem here would be that it would be hard to compare with the reference to the original operator
2. track queue_idx outside of the operator (as far as I can see, it's not really used anywhere outside of CircuitGraph) on the CircuitGraph object itself and use a combo of object ID and queue_idx as a unique identifier for the operator when building the graph.

[albi3ro]

Thanks for the excellent analysis @che-burashco .

CircuitGraph is one of the older, less actively maintained pieces of code in our package. Because of this, it makes certain assumptions (like every operator being a different instance) that we are loosening in other parts of the code base. This bug only really came up because of me trying to unit-test things.

Queuing, how we capture the contents of a quantum function, still requires operator to be a unique instance, but we're pushing to loosen that restriction in internal code. We just haven't loosened the restriction in CircuitGraph yet.

Option 1 (copying duplicate operators) would solve the problem, but we would end up doing a bunch of additional work (copying things) we don't necessarily want to do.

I definitely favour Option 2, and that was exactly what I was thinking to solve the problem whenever I had time.

Instead of having each operator be a node, in the rustworkx.PyDiGraph, we could have something like (queue_idx, op) and remove queue_idx from Operator.

[che-burashco]

Thanks for a quick reply @albi3ro. I can take a stab at implementing the second approach this week if there are no objections

[albi3ro]

No objections. That'd be great :)

We might actually be able to just store the queue_idx as the rustworkx node. Then the original operation can always easily be acessed by self._queue[queue_idx]. This may involve making queue = ops+obs a private class property.

Just a general heads up that we are going to be changing the definitions for Operator.__eq__ and Operator.__hash__ soon to that we have qml.S(0) == qml.S(0), so we do not want to rely on their definitions for anything.

[albi3ro]

This issue has come up again, in the example of:

HAMILTONIAN = qml.dot([1.0, -0.5], [qml.X(0) @ qml.Y(1), qml.Y(0) @ qml.Y(1)])
ops = qml.TrotterProduct(HAMILTONIAN, time=1.0, n=4, order=2).decomposition()
tape = qml.tape.QuantumScript(ops, [qml.state()])
tape.graph.get_depth()

We may finally need to address this issue.