8.2. A Framework for Scalable Graph Rewriting
With this chapter we have arrived at the core of this thesis: a proposal for a new quantum compilation framework. In summary, our claim is that given
- the challenge of scaling up quantum programs sizes to make the most of the computational capabilities of upcoming hardware (cf. sections 2.1 and 2.3) and
- the modularity and expressiveness that quantum compilers will require to simultaneoulsy express higher level abstractions, hardware primitives and interleaved quantum classical computation (cf. sections 3.3, 2.4, and 2.5),
graph rewriting is uniquely positioned to serve as the backbone of a quantum compilation framework.
Our proposal draws much from the design and techniques of classical compilers (cf. sections 5.2 and 3.3). Quantum, however, distinguishes itself in two ways, forming the cornerstones of our design. The focus on small, local graph transformations for quantum optimisation is justified by the groundbreaking work by Clément et al Cléme., 2023. 2023. A Complete Equational Theory for Quantum Circuits. In 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), June 2023. IEEE, 1--13. doi: 10.1109/lics56636.2023.10175801 Cléme., 2024. 2024. Minimal Equational Theories for Quantum Circuits. In Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, July 2024. ACM, 1--14. doi: 10.1145/3661814.3662088. They showed that the rich algebraic structure of quantum circuits can be fully captured and expressed using local rewrite rules1. Our compiler can therefore restrict program manipulation to local transformations without losing expressiveness. This design choice in turn opens the door for large scale optimisation and compilation on parallel or even distributed hardware.
Equally important, the linear types of quantum computing (cf. section 3.3) significantly constrain the space of possible program transformations. Our contributions in this thesis highlight how these restrictions can be leveraged to create quantum-specific variants of classical compilation techniques that scale much more favourably. This makes approaches that are too expensive for classical compilers (cf. section 5.2) perfectly feasible2 in the context of quantum compilation.