Add implementation of PatternMatch to retworkx

[IvanIsCoding]

Description

retworkx is a high-performance graph library used internally by Qiskit, PennyLane, and other projects. retworkx contains efficient implementations of graph algorithms, and Qiskit Terra leverages those algorithms to efficiently manipulate quantum circuits internally.

This project is about implementing Exact and practical pattern matching for quantum circuit optimization by Iten et al. using retworkx. Qiskit Terra has an implementation of Pattern Matching (https://github.com/Qiskit/qiskit-terra/blob/master/qiskit/transpiler/passes/optimization/template_matching/template_matching.py) which is built on top of DAGDependency (https://github.com/Qiskit/qiskit-terra/blob/master/qiskit/dagcircuit/dagdependency.py).

Ideally we'd be able to replace most of current implementation with a retworkx function, such that the transpile pass can be executed faster and included as a default in Qiskit Terra. We note that maybe not all of the Python code can be ported, hence using Cython or mypyc might also became part of the project if desired.

Deliverables

• Contribute new functions to retworkx implementing the matching algorithms described in the paper
• A Pull Request to qiskit-terra replacing the old Python code with the new retworkx methods

Mentors details

• Mentor 1
  • Name: Ivan Carvalho
  • GitHub ID: @IvanIsCoding
  • What they do: Retworkx Developer

Number of mentees

1

Type of mentees

• Mentee 1
  • Required:
  • Good knowledge of graphs and graph algorithms
  • Interested in learning a new programming language (Rust)
  • Nice to have:
  • Experience programming in compiled languages (C++, Rust, etc)
  • Experience using Qiskit Terra transpiler passes

[HuangJunye]

Closing this issue as it was not paired with any mentee. Thank you for suggesting the project idea!