rustworkx icon indicating copy to clipboard operation
rustworkx copied to clipboard

Add implementation of PatternMatch to rustworkx

Open mtreinish opened this issue 4 years ago • 1 comments

What is the expected enhancement?

Add a retworkx algorithm function for the PatternMatch algorithm from: https://arxiv.org/pdf/1909.05270.pdf

In qiskit terra there is a python implementation of this algorithm built using an inner retworkx PyDiGraph. Specifically it uses a DAGDependency data structure: https://github.com/Qiskit/qiskit-terra/blob/master/qiskit/dagcircuit/dagdependency.py which is built on a PyDiGraph and uses that to run the algorithm here: https://github.com/Qiskit/qiskit-terra/blob/master/qiskit/transpiler/passes/optimization/template_matching/template_matching.py ideally we'd be able to replace most of terra implementation with a retworkx function.

For places in the algorithm that look at the attributes of a vertex we'll need to rely on python callback functions that will be passed the vertex object and return the data in a format retworkx can use (you can refer to other algorithm functions like max_weight_matching, floyd_warshall_numpy, etc for examples of this), but we might need multiple different functions passed to retworkx.

mtreinish avatar Mar 03 '21 19:03 mtreinish

Also, as discussed in https://github.com/Qiskit/qiskit-terra/issues/5775#issuecomment-789808980 it would be good if this implementation could handle the peephole optimization special case outlined in section 5.4.2 of the paper (the actual optimization will be done outside of retworkx, but the special case for block finding should be handled in retworkx).

mtreinish avatar Mar 03 '21 19:03 mtreinish