Qiskit / qiskit-terra / 5753596164

86%

main: 87%

push

github

Fix potential non-determinism in DAGOpNode sort key (#9569)

* Fix potential non-determinism in DAGOpNode sort key

This commit fixes potential source of non-determinism when topologically
sorting a DAGCircuit object. The lexicographical_topological_sort()
function we're using from rustworkx takes a sort key callback that
returns a string which is used for tie breaking in the topological sort.
The string used for op nodes was previously `str(qargs)`, but this is
potentially problematic for standalone Qubit objects. The repr for a
qubit without a register set will include the memory address of the bit
object. This could result in the topological sort differing between
executions of the same program which could lead to unexpected results.
This commit fixes this by changing the sort key to be a string of the
qubit indices in the dag instead of the qubit objects in qargs.

This commit will likely introduce a small performance regression because
we're adding overhead on every DAGOpNode creation. This regression can
be addressed when #9389 is implemented because we can just pass the data
structure mapping bit objects to indices to the constructor instead of
having to build that mapping on each op node.

Additionally, some test cases were fixed as part of this commit, because
several DAGCircuit test cases were incorrectly calling
apply_operation_back() and setting clbits as qargs which will now fail
because of the index lookup on qubits.

* Update sort_key creation to use DAGCircuit.find_bit

* 0 pad integer indices and include cargs in sort key

This commit updates the sort key construction to do two things, first it
updates the integer indices used in the sort key to be 0 padded so that
the sort order is more intuitive. At the same time the sort key is not
including the cargs for an operation to ensure that's being factored
into the sort order.

Co-authored-by: Jake Lishman <jake.lishman@ibm.com>

---------

Co-authored-by: Jake Lishman <jake.lishman@ibm.com>

8 of 8 new or added lines in 2 files covered. (100.0%)

73082 of 85066 relevant lines covered (85.91%)

60956.29 hits per line