Open 1ucian0 opened 2 years ago
In continuation of https://github.com/Qiskit/qiskit-terra/pull/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)
A few questions.
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.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.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.
in 2018, #1500 introduced
CommutationAnalysis
pass. The pass does the trick while working withCommutativeCancellation
. 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 dictThe property
property_set['commutation_set']
is a non-uniformly typed dict:suggested solution:
property_set['commutation_set']
should be aqiskit.dagcircuit.dagdependency.DAGDependency
.does not handle intransitivity
The current commutation analysis assumes transitivity (I think), while the relation is intransitive. For example
H
commutes withI
andI
commutes withZ
, butH
does not commute withZ
. This is not reflected in the commutative set:There is a lot of duplication with
DAGDependency
The
qiskit.dagcircuit.dagdependency.DAGDependency
seems to do the same asqiskit.transpiler.passes.optimization.commutation_analysis.CommutationAnalysis
. For exampleqiskit.dagcircuit.dagdependency._does_commute
andqiskit.transpiler.passes.optimization.commutation_analysis._commute
are similar in their goal, but one of them has a cache system that makes it better.