CommutationAnalysis needs to be refactored

[1ucian0]

in 2018, #1500 introduced CommutationAnalysis pass. The pass does the trick while working with CommutativeCancellation. However, there are some aspects that are not very well covered and I think it is time to sit again with it and think it over again. Here there are a list of the problems:

property commutation_set is a messy dict

The property property_set['commutation_set'] is a non-uniformly typed dict:

from qiskit import QuantumCircuit

circuit = QuantumCircuit(1)
circuit.h(0)

from qiskit.transpiler.passes import CommutationAnalysis

property_set = {}
CommutationAnalysis()(circuit, property_set)

for k,v in property_set['commutation_set'].items():
    print(type(k), type(v))

<class 'qiskit.circuit.quantumregister.Qubit'> <class 'list'>
<class 'tuple'> <class 'int'>
<class 'tuple'> <class 'int'>
<class 'tuple'> <class 'int'>

suggested solution: property_set['commutation_set'] should be a qiskit.dagcircuit.dagdependency.DAGDependency.

does not handle intransitivity

The current commutation analysis assumes transitivity (I think), while the relation is intransitive. For example H commutes with I and I commutes with Z, but H does not commute with Z. This is not reflected in the commutative set:

from qiskit.circuit import Qubit
from qiskit.dagcircuit import DAGOpNode

def pp_commutation_set(property_commutation_set):
    # pretty printer of the commutation set
    for qbit, sets in property_commutation_set.items():
        if not isinstance(qbit, Qubit):
            continue
        print(qbit.index)
        for commutation_set in sets:
            r=[]
            for node in commutation_set:
                if isinstance(node, DAGOpNode):
                    r.append(f"{node.op.name}_{node._node_id}{[arg.index for arg in node.qargs]}")
            if r:
                print('\t', r)

from qiskit import QuantumCircuit

circuit = QuantumCircuit(1)
circuit.h(0)
circuit.id(0)
circuit.z(0)

from qiskit.transpiler.passes import CommutationAnalysis

property_set = {}
CommutationAnalysis()(circuit, property_set)

pp_commutation_set(property_set['commutation_set'])

0
	 ['h_2[0]', 'id_3[0]', 'z_4[0]']

There is a lot of duplication with DAGDependency

The qiskit.dagcircuit.dagdependency.DAGDependency seems to do the same as qiskit.transpiler.passes.optimization.commutation_analysis.CommutationAnalysis. For example qiskit.dagcircuit.dagdependency._does_commute and qiskit.transpiler.passes.optimization.commutation_analysis._commute are similar in their goal, but one of them has a cache system that makes it better.

[Randl]

In continuation of #8056, the following test currently fails due to unsound optimization:

    def test_intransitive_non_commutative_circuit1(self):
        """Test simple intransitive non-commutative circuit on 1 qubit"""
        circ = QuantumCircuit(1)

        circ.x(0)
        circ.i(0)
        circ.h(0)
        circ.i(0)
        circ.x(0)

        passmanager = PassManager()
        passmanager.append(CommutativeCancellation())
        ccirc = passmanager.run(circ)
        self.assertEqual(Operator(circ), Operator(ccirc))

due to transitivity assumption.

The following test is an example of missed optimization in case of naive fix:

    def test_non_pairwise_commutative_circuit1(self):
        """Test simple circuit where we can simplify though operators not commute pairwise on 1 qubit"""
        circ = QuantumCircuit(1)

        circ.x(0)
        circ.i(0)
        circ.z(0)
        circ.i(0)

        passmanager = PassManager()
        passmanager.append(CommutativeCancellation())
        ccirc = passmanager.run(circ)

        expected = QuantumCircuit(1)
        expected.x(0)
        expected.z(0)

        self.assertEqual(Operator(circ), Operator(ccirc))
        self.assertEqual(ccirc, expected)

[alexanderivrii]

A few questions.

1. The caching mechanism of qiskit.transpiler.passes.optimization.commutation_analysis._commute seems extremely useful. However (if I am not mistaken) the cached information that x(1) and cx(0, 1) commute would not help to detect that x(42) and cx(50, 42) commute (same gates up to relabeling qubits). Would be nice to avoid caching a quadratic amount of information. Also I am not sure whether this would detect that cx(0, 1) and x(1) commute (same gates, but in different order).
   UPDATE: I was mistaken, CommutativeAnalysis actually does both of the above.
2. If I understand correctly, in qiskit.dagcircuit.dagdependency we compute and store the lists of predecessors and successors for every node in DagDependency, and it seems that this may require a lot of memory for long and wide circuits. Is this correct or does retworks do something clever when storing such lists? The algorithm to construct DagDependency can be easily modified to reason about direct_predecessors only, however it seems that predecessors are also needed for the template matching algorithm.

[ShellyGarion]

Copying the comment from https://qiskit.org/documentation/stubs/qiskit.transpiler.passes.CommutationAnalysis.html:

TODO: the current pass determines commutativity through matrix multiplication. A rule-based analysis would be potentially faster, but more limited.

At least it's worth adding some simple rule-based commuting relations between standard gates.
Perhaps make a "commuting library" similar to the equivalence library.