Chapter 1

Introduction

Quantum computing is the computational model that arises from the quantum mechanical manipulation of finite dimensional physical systems. Realising this new computing paradigm requires an entirely new technology stack: most obviously, new dedicated hardware, but also an extensive collection of software tools that transform the intents of a human user into a symphony of electric pulses that operate all components of the hardware installation (lasers, magnetic fields, currents, photodetectors, etc.).

Turning human-readable code into machine instructions is the realm of compilers, a problem as old as classical¹ computer science itself. By analogy, the same problem in the quantum world was named quantum compilation.

Interestingly, whereas the term quantum compilation has been in use for the longest part of the existence of quantum computing as a field, it is only recently that the quantum compilation community has started to adopt tools, ideas and results from our classical counterparts.

Meanwhile, quantum computing has a long history of adopting diagrammatic and graph-based representations to model and reason about computations and their quantum mechanical properties. The most famous example of this is undoubtedly the quantum circuit, a quantum analogue to boolean circuits that visualises how data flows from one operation to the next (cf. section 2.1).

Going beyond circuits, the field of categorical quantum mechanics has embraced and extended diagrammatic formalisms to model a variety of quantum processes and computations. Particularly noteworthy in this line of work are the numerous advances in quantum circuit optimisation (e.g. Duncan, 2020Ross Duncan, Aleks Kissinger, Simon Perdrix and John van de Wetering. 2020. Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus. Quantum 4 (June 2020, 279). doi: 10.22331/q-2020-06-04-279 Gogioso, 2022Stefano Gogioso and Richie Yeung. 2022. Annealing Optimisation of Mixed ZX Phase Circuits. In Proceedings 19th International Conference on Quantum Physics and Logic, QPL 2022, Wolfson College, Oxford, UK, 27 June - 1 July 2022, 415--431. doi: 10.4204/EPTCS.394.20), quantum simulations (e.g. Kissin., 2022Aleks Kissinger and John van de Wetering. 2022. Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions. Quantum Science and Technology 7, 4 (July 2022, 044001). doi: 10.1088/2058-9565/ac5d20 Sutcli., 2025Matthew Sutcliffe and Aleks Kissinger. 2025. Fast classical simulation of quantum circuits via parametric rewriting in the ZX-calculus. arXiv: 2403.06777 [quant-ph]), error correction (e.g. Beaudr., 2020Niel de Beaudrap and Dominic Horsman. 2020. The ZX calculus is a language for surface code lattice surgery. Quantum 4 (January 2020, 218). doi: 10.22331/q-2020-01-09-218 Cowtan, 2024Alexander Cowtan and Simon Burton. 2024. CSS code surgery as a universal construction. Quantum 8 (May 2024, 1344). doi: 10.22331/q-2024-05-14-1344) and many more related subjects (e.g. Simmons, 2021Will Simmons. 2021. Relating Measurement Patterns to Circuits via Pauli Flow. Electronic Proceedings in Theoretical Computer Science 343 (Septempter 2021, 50--101). doi: 10.4204/eptcs.343.4 Felice, 2023Giovanni de Felice and Bob Coecke. 2023. Quantum Linear Optics via String Diagrams. In Proceedings 19th International Conference on Quantum Physics and Logic, Wolfson College, Oxford, UK, 27 June - 1 July 2022. Open Publishing Association, 83-100. doi: 10.4204/EPTCS.394.6) that the family of ZX-like calculi have enabled in the last five years alone.

A challenge in quantum compilation has been to combine the principled and abstract graph-based transformation semantics of diagrammatic reasoning with the feature set and performance requirements of practical compilation tools. General purpose tools graph rewriting tools such as Quantomatic Fagan, 2018Andrew Fagan and Ross Duncan. 2018. Optimising Clifford Circuits with Quantomatic. In Proceedings 15th International Conference on Quantum Physics and Logic, QPL 2018, Halifax, Canada, 3-7th June 2018, 85--105. doi: 10.4204/EPTCS.287.5 proved too slow for quantum circuit optimisation and other tools from the graph transformation community such as GROOVE Rensink, 2004Arend Rensink. 2004. The GROOVE Simulator: A Tool for State Space Generation. In Applications of Graph Transformations with Industrial Relevance. Springer Berlin Heidelberg, 479--485. doi: 10.1007/978-3-540-25959-6_40 and GrGen.NET Geiß, 2006Rubino Geiß, Gernot Veit Batz, Daniel Grund, Sebastian Hack and Adam Szalkowski. 2006. GrGen: A Fast SPO-Based Graph Rewriting Tool. In Graph Transformations. ICGT 2006.. Springer Berlin Heidelberg, 383--397. doi: 10.1007/11841883_27 have not been adopted.

Instead, successful graph-based tools such as PyZX Kissin., 2020Aleks Kissinger and John van de Wetering. 2020. PyZX: Large Scale Automated Diagrammatic Reasoning. In Proceedings 16th International Conference on Quantum Physics and Logic, Chapman University, Orange, CA, USA., 10-14 June 2019. Open Publishing Association, 229-241. doi: 10.4204/EPTCS.318.14 and its faster re-implementation QuiZX Kissin., 2022Aleks Kissinger, John van de Wetering and Renaud Vilmart. 2022. Classical Simulation of Quantum Circuits with Partial and Graphical Stabiliser Decompositions. In . Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi: 10.4230/LIPICS.TQC.2022.5 focused on performant rewriting for a restricted subdomain (in this case, the ZX calculus). This specialisation makes it difficult to expand these approaches to new primitives and constraints that are emerging from hardware advances within quantum computing. It also limits the interaction and sharing across field boundaries and impedes the development of tools applicable to a broader range of graph transformation domains.

The ambitious aim of this thesis is to advocate for graph transformation as a robust basis for a scalable and modular compiler platform for quantum computations – and hope that in the process, our contributions will strengthen the bridge between research in classical compilation, quantum computing and graph transformations. The key desired properties of our compilation framework can be summarised as follows:

Scalable. The compiler should handle quantum computations of the kind we realistically expect to execute within the coming decade: thousands of logical qubits, relying on possibly millions of physical qubits. Just as importantly, the compiler architecture should scale to take advantage of large classical computational resources, in order to maximise the optimisation potential when available.

Modular. The computational primitives available on present quantum hardware are wide-ranging and evolving rapidly, the programming models for end users are adapting, and hardware constraints and characteristics change from device to device. A future-proof compiler platform must therefore imperatively be extensible in its supported instruction set, its optimising cost function and the program transformation strategies.

Why is now the time for such a compiler and why are these qualities so important? We develop some arguments in section 1.1. Our concrete contributions to this goal are then summarised in section 1.2, along with an outline of the thesis.

1.1. A new compilation regime

We have introduced quantum compilation by drawing an analogy with the well-developed field of classical compilers. The novel directions in which quantum compilation is taking the field make for exciting new challenges. Three new quantum-specific properties of compilation form the core motivation for this work.

Large variations in architecture #

The vast differences between proposed hardware architectures are a first distinguishing characteristic of current quantum computing developments. Unlike classical computing, where silicon-based transistors have become the definitive physical foundation for all electronic chips, the search for the most scalable and reliable technology for quantum computing is ongoing – and doubtless one of the most burning questions for the nascent industry. This introduces an incredible variety of compilation problems.

Quantum hardware designs differ both in the types of quantum particles used to implement qubits and in the control systems employed to manipulate these particles. Suggestions for the former include charged ions Kielpi., 2002D. Kielpinski, C. Monroe and D. J. Wineland. 2002. Architecture for a large-scale ion-trap quantum computer. Nature 417, 6890 (June 2002, 709--711). doi: 10.1038/nature00784 T. Pel., 1995J. I. Cirac, T. Pellizzari and P. Zoller. 1995. Decoherence, Continuous Observation, and Quantum Computing: A Cavity QED Model. Physical Review Letters 75, 21 (November 1995, 3788--3791). doi: 10.1103/PhysRevLett.75.3788, neutral atoms Jaksch, 2000D. Jaksch, J. I. Cirac, P. Zoller, S. L. Rolston, R. Côté and M. D. Lukin. 2000. Fast Quantum Gates for Neutral Atoms. Physical Review Letters 85, 10 (Septempter 2000, 2208--2211). doi: 10.1103/physrevlett.85.2208 Deutsch, 2000Ivan H. Deutsch, Gavin K. Brennen and Poul S. Jessen. 2000. Quantum Computing with Neutral Atoms in an Optical Lattice. Fortschritte der Physik 48, 9–11 (Septempter 2000, 925--943). doi: 10.1002/1521-3978(200009)48:9/11<925::aid-prop925>3.0.co;2-a, photons Knill, 2001E. Knill, R. Laflamme and G. J. Milburn. 2001. A scheme for efficient quantum computation with linear optics. Nature 409, 6816 (January 2001, 46--52). doi: 10.1038/35051009, transmons Blais, 2007Alexandre Blais, Jay Gambetta, A. Wallraff, D. I. Schuster, S. M. Girvin, M. H. Devoret and R. J. Schoelkopf. 2007. Quantum-information processing with circuit quantum electrodynamics. Physical Review A 75, 3 (March 2007, 032329). doi: 10.1103/physreva.75.032329 and even Majorana Sau, 2010Jay D. Sau, Roman M. Lutchyn, Sumanta Tewari and S. Das Sarma. 2010. Generic New Platform for Topological Quantum Computation Using Semiconductor Heterostructures. Physical Review Letters 104, 4 (January 2010, 040502). doi: 10.1103/physrevlett.104.040502 particles. The equipment that drives the desired operations on these particles is then drawn from a jolly mixture of lasers, magnetic fields, microwaves, dilution fridges, etc. Each combination results in different trade-offs: some will render a specific computation particularly easy; others promise to scale well to large systems but are very error-prone and unreliable; others still achieve high fidelities at the expense of slow operations.

From the perspective of a compiler engineer, this means we must equip quantum compilers to handle a wide variety of hardware primitives, multiple optimisation goals, and hardware-specific program constraints. Traditional compilation is ill-equipped to handle this considerable challenge.

A comparison of machine code for different architectures illustrates the difference between the quantum and classical worlds. Classical CPUs are dominated by two architectures, x86, used mainly by Intel and AMD, and ARM, used by a wide range of desktop and mobile chip manufacturers¹.

mov eax, 5        ; Load 5 into EAX
add eax, 3        ; Add 3 to EAX
mov [result], eax ; Store the result in memory

ldr r0, =5        ; Load 5 into R0
add r0, r0, #3    ; Add 3 to R0
ldr r1, =result   ; Load address of result
str r0, [r1]      ; Store the result in memory

There are noticeable differences between the two architectures, mostly around variable naming conventions, as well as explicit memory loads ldr and stores str instructions in the case of ARM, which in x86 are handled implicitly by mov. This simplistic example naturally ignores some of the more fine-grained considerations that can make translations hard in certain edge cases. A discussion of these can be found in Ford, 2021Blake W. Ford, Apan Qasem, Jelena Tesic and Ziliang Zong. 2021. Migrating Software from x86 to ARM Architecture: An Instruction Prediction Approach. In 2021 IEEE International Conference on Networking, Architecture and Storage (NAS), October 2021. IEEE, 1--6. doi: 10.1109/NAS51552.2021.9605443. However, overall, the instructions and capabilities of the two platforms are broadly equivalent, as is confirmed by the existence of emulation tools such as Apple Rosetta.

Let us contrast this with the difference between two quantum architectures. Consider, on the one hand, an architecture that can natively perform CX and H gates on qubits (e.g. superconducting qubits, ion traps, etc.) and, on the other hand, a platform based on photons and optical components.

h q[0];
cz q[0],q[1];

bs.h(5*pi/2, pi, pi, 2*pi) m[0], m[1];
bs.h m[2], m[3];
perm([2, 1, 3, 0]) m[1], m[2], m[3], m[4];
barrier m[0], m[1], m[2], m[3], m[4], m[5];
bs.h(1.910633) m[0], m[1];
bs.h(1.910633) m[2], m[3];
bs.h(1.910633) m[4], m[5];
perm([1, 0]) m[2], m[3];
bs.h m[3], m[4];
perm([3, 0, 1, 2]) m[1], m[2], m[3], m[4];

On the left is a quantum circuit expressed in the OpenQASM2 standard Cross, 2017Andrew W. Cross, Lev S. Bishop, John A. Smolin and Jay M. Gambetta. 2017. Open Quantum Assembly Language. arXiv: 1707.03429 [quant-ph]. The right-hand side is the equivalent linear optics circuit computed by Perceval Heurtel, 2023Nicolas Heurtel, Andreas Fyrillas, Grégoire Gliniasty, Raphaël Le Bihan, Sébastien Malherbe, Marceau Pailhas, Eric Bertasi, Boris Bourdoncle, Pierre-Emmanuel Emeriau, Rawad Mezher, Luka Music, Nadia Belabas, Benoît Valiron, Pascale Senellart, Shane Mansfield and Jean Senellart. 2023. Perceval: A Software Platform for Discrete Variable Photonic Quantum Computing. Quantum 7 (February 2023, 931). doi: 10.22331/q-2023-02-21-931, expressed in a custom, OpenQASM2-like, format. The conversion is by no means straightforward! Some of the challenges include encoding qubits into multiple photon modes and mapping quantum operations to an optically realisable procedure made of optical components and measurements Felice, 2023Giovanni de Felice and Bob Coecke. 2023. Quantum Linear Optics via String Diagrams. In Proceedings 19th International Conference on Quantum Physics and Logic, Wolfson College, Oxford, UK, 27 June - 1 July 2022. Open Publishing Association, 83-100. doi: 10.4204/EPTCS.394.6.

Other architectures, such as neutral atoms, may broadly support qubit-based operations but might not offer control over individual qubits and, instead require any operations to be applied in parallel to large groups of qubits Bluvst., 2022Dolev Bluvstein, Harry Levine, Giulia Semeghini, Tout T. Wang, Sepehr Ebadi, Marcin Kalinowski, Alexander Keesling, Nishad Maskara, Hannes Pichler, Markus Greiner, Vladan Vuletić and Mikhail D. Lukin. 2022. A quantum processor based on coherent transport of entangled atom arrays. Nature 604, 7906 (April 2022, 451--456). doi: 10.1038/s41586-022-04592-6. Finally, it is to be expected that error-correcting codes that individual platforms will introduce to reduce error rates at the hardware level will introduce further constraints and new instruction sets yet again.

It is noteworthy that current trends in the classical world are also pushing compilers towards more heterogenous architectures that may include GPUs, FPGAs and other accelerators. This has led to significant changes in the design of current compilers, which we will touch upon later. Nonetheless, this shift has, so far, mostly “limited” itself to new forms of parallelism and the introduction of more specialised instruction sets rather than a fundamental redesign of existing tools and computing paradigms. The breadth of technologies and trade-offs that quantum compilers must face have no equivalent in the classical world – at least for the time being.

Asymmetric computational resources #

A second exciting paradigm shift in compilation that quantum is driving forward is cross-compilation. A common assumption in compilation is that the program is executed on the same machine (or at least the same architecture) on which it was compiled. By contrast, in cross-compilation, the compiler and the compiled binary program run on different machines, possibly with different architectures. An instance of this would be using a recent ARM system-on-chip machine to create a binary program for a traditional Windows PC with an Intel CPU. This is a supported feature of most modern compilers (and made easier by the relative similarities between processor architectures, as seen above), but such tasks are by no means trivial and can be laborious to get to work well in practice².

The situation is very different for quantum computing. Quantum computational resources are so limited that native compilation, in which the program is compiled and run on the same machine, is unfeasible – and will remain so for the foreseeable future³. When we put the possibility of pure-quantum compilation aside, we are left with a cross-compilation problem that is entirely the realm of classical computer science; the output of which happens to be destined to run on a quantum computer. This is simliar to how in classical computing, GPU programs are typically compiled on CPUs before being uploaded and executed on the GPU.

Cross-compilation presents significant challenges. As quantum programs grow in size and complexity, debugging and verifying their correctness without access to the target hardware becomes increasingly difficult Rovara, 2024Damian Rovara, Lukas Burgholzer and Robert Wille. 2024. A Framework for Debugging Quantum Programs. arXiv: 2412.12269 [quant-ph], as we hit the limits of what can be simulated classically. Quantum simulation is a vibrant research area that is the subject of theses (e.g. Flanni., 2020Stuart Flannigan. 2020. The application of quantum simulation to topological and open many-body systems. PhD Thesis. University of Strathclyde Azad, 2024Fariha Azad. 2024. Tensor networks for classical andquantum simulation of open and closedquantum systems. PhD Thesis. University College London.) in its own right.

On the flip side, using classical hardware for quantum program compilation comes with a giant opportunity for compilers: the classical computational resources available to the compiler, measured in the size of the memory and the number of operations that can be handled, are many orders of magnitude larger (and cheaper!) than what the quantum hardware that will execute the program is capable of. We can today execute tens to hundreds of billions of operations per second (GFLOPS) on desktop computers, up to the “exascale”, i.e. $10^{15}$ FLOPS, for the largest supercomputers Dongar., 2024Strohmaier, E., Simon, H., Meuer, H. Dongarra. 2024. TOP500 List. (November 2024). Retrieved on 30/12/2024 from https://top500.org/lists/top500/list/2024/11/. Quantum hardware, on the other hand, will not be executing programs with sizes beyond 1000 error-corrected gates, or 10,000 physical gates, for another three years – that is believing the most optimistic roadmaps in the industry IBM, 2024 IBM. 2024. Expanding the IBM Quantum roadmap to anticipate the future of quantum-centric supercomputing. Retrieved on 30/12/2024 from https://www.ibm.com/quantum/blog/ibm-quantum-roadmap-2025 Quanti., 2024 Quantinuum. 2024. Quantinuum Unveils Accelerated Roadmap to Achieve Universal, Fully Fault-Tolerant Quantum Computing by 2030. Retrieved on 30/12/2024 from https://www.quantinuum.com/press-releases/quantinuum-unveils-accelerated-roadmap-to-achieve-universal-fault-tolerant-quantum-computing-by-2030.

It is expected that even a few thousand quantum gates will suffice to solve problems that our largest supercomputers struggle with. Meanwhile, every gate that must be performed comes at a high cost: it may fail, introduce errors, or take a long time to complete. It therefore behoves us to use all the classical resources at our disposal to reduce quantum operations to a minimum.

Given the strict hardware limitations, all near-term architectures are expected to face, quantum compilation must evolve into cross-compilers that are able to utilise the full power of classical hardware available to them; doing so will push the boundaries of what is possible with quantum computing just a bit further – in a field where every marginal gain may unlock new applications.

The confluence of classical and quantum compilation #

Finally, quantum compilation also stands in front of some momentous engineering challenges. As we will see in section 2.2, significant research efforts have focused on the compilation and optimisation of quantum programs expressed as quantum circuits (cf. section 2.1). This formalism has its roots in quantum information theory, the field that gave birth to quantum computing and makes for an ideal framework to develop the theory and optimisation techniques. However, it does not include any of the fundaments of compiler and programming language design that make classical software as composable and scalable as it is today.

For example, there is no concept of subroutine or function calls; neither can a program execution be branching or looping based on runtime values. This makes code reuse impossible, resulting in huge program sizes and unsurmountable challenges for scaling up compilation to problems of real-world interest Ittah, 2022David Ittah, Thomas Häner, Vadym Kliuchnikov and Torsten Hoefler. 2022. QIRO: A Static Single Assignment-based Quantum Program Representation for Optimization. ACM Transactions on Quantum Computing 3, 3 (June 2022, 1--32). doi: 10.1145/3491247. The absence of code abstractions is being felt even more acutely with the emergence of hybrid quantum-classical computations, as we discuss in section 2.3.

With applications of quantum computing that cannot be expressed as quantum circuits proliferating, a move away from circuit-based representations is becoming unavoidable Hossei., 2023Lev Bishop, Yudong Cao, Andrew Cross, Niel Hossein Ajallooiean. 2023. OpenQASM 3.0 Specification. Retrieved on 15/03/2025 from https://openqasm.com/versions/3.0/intro.html QIR Al., 2021 QIR Alliance. 2021. QIR Specification v0.1. Retrieved on 31/12/24 from https://www.qir-alliance.org/. This is also an opportunity to incorporate learnings from the decades of experience that have been gathered in classical computer science. Many of the tools and software that were originally developed for classical computations are thus being adopted and adapted to the specificities of quantum. This convergence of quantum computing and classical compiler technologies is heralding new opportunities – but also pose important questions around how to represent quantum programs and optimise them.

1.2. Contributions and thesis outline

Preliminaries #

The thesis starts in chapter 2 with a review of the main concepts on which the rest of the thesis is built. Aside from a short introduction to quantum computations (section 2.1) and a survey of the major quantum circuit optimisation techniques (section 2.2), this chapter makes two observations that impart a research direction to the rest of the thesis:

1. The emergence of hybrid quantum-classical computations is rendering the quantum circuit obsolete as the main representation of quantum computations within compilers (section 2.3).
2. The best optimisation outcomes will combine classical and quantum compiler optimisations. This can be achieved by adopting abstractions that are interoperable with classical compiler infrastructure (section 2.4).

A graph transformation formalism for quantum computations #

Chapters 3, 4, and 5 form the core of this thesis and present our main contributions. The results in chapter 3 are crucial stepping stones for the rest of the thesis. Chapters 4 and 5 meanwhile present our most significant contributions to the state of the art.

In chapter 3, we propose minIR, a new graph-based intermediate representation (IR) for quantum computations. MinIR is a minimal subset of the Hierarchical Unified Graph Representation (HUGR), recently presented in joint work Mark K., 2025Seyon Sivarajah, Alan Lawrence, Alec Edgington, Douglas Wilson, Craig Roy, Luca Mondada, Lukas Heidemann, Ross Duncan Mark Koch. 2025. HUGR: A Quantum-Classical Intermediate Representation. Retrieved (talk recording) from https://www.youtube.com/live/D8esZrt7ogk?feature=shared&t=5217 and the subject of ongoing development. It is to our knowledge the first compiler IR with support for linear types – required to model the restrictions that quantum mechanics imposes on quantum computations.

Unlike quantum circuits, minIR (and HUGR) programs can model computations that act on arbitrary combinations of classical (bits) and quantum data (qubits) within a single, unified representation. It represents the best of two worlds: it combines the safety guarantees of quantum-specific representations such as quantum circuits (i.e. it is impossible to declare physically unrealisable computations), whilst at the same time being interoperable with classical compiler IRs.

Graph-based representations of computations, known as computation graphs in deep learning and dataflow graphs within the compiler community, are common in these fields. Our original contribution is in the formalisation of the IR transformation semantics: whereas classical compilers typically define IR transformations in terms of the values that they depend on and the values that they overwrite, this approach implicitly relies on value copying and discarding and thus does not generalise to linear values. Instead, we define graph rewriting semantics on minIR and show sufficient conditions for which minIR transformations preserve the validity of the program, and in particular the linearity conditions.

The encoding of quantum computations as graphs sets the stage for quantum compilation and optimisation using graph transformation systems (GTS), in which the set of transformations that the compiler is allowed to perform is expressed by a set of graph transformation rules. This is in effect a generalisation of an approach first proposed in Xu, 2022Mingkuan Xu, Zikun Li, Oded Padon, Sina Lin, Jessica Pointing, Auguste Hirth, Henry Ma, Jens Palsberg, Alex Aiken, Umut A. Acar and Zhihao Jia. 2022. Quartz: Superoptimization of Quantum Circuits. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation, June 2022. Association for Computing Machinery, 625--640. doi: 10.1145/3519939.3523433 in the context of quantum circuits. We improve on this work with two major contributions that resolve critical issues that concerning the scaling of the technique to large numbers of transformation rules and large inputs respectively.

Pattern matching #

Our first major contribution is a pattern matching algorithm, presented in chapter 4. The main result is a runtime complexity bound independent of the number of patterns being matched, achieved using a one-off pre-computation. This is to our knowledge the first pattern matching algorithm for quantum circuits that does not depend on the number of patterns. Whilst similar multi-pattern matching techniques have been explored in other domains such as RETE networks Forgy, 1982Charles L. Forgy. 1982. Rete: A fast algorithm for the many pattern/many object pattern match problem. Artificial Intelligence 19, 1 (Septempter 1982, 17--37). doi: 10.1016/0004-3702(82)90020-0 Varró, 2013Gergely Varró and Frederik Deckwerth. 2013. A Rete Network Construction Algorithm for Incremental Pattern Matching Ian, 2003Wright Ian and James A. R. Marshall. 2003. The execution kernel of RC++: RETE*, a faster RETE with TREAT as a special case. International Journal of Intelligent Games and Simulation 2, 1 (Feb 2003, 36-48) and computational biology Danos, 2007Vincent Danos, Jérôme Feret, Walter Fontana and Jean Krivine. 2007. Scalable Simulation of Cellular Signaling Networks Boutil., 2017Pierre Boutillier, Thomas Ehrhard and Jean Krivine. 2017. Incremental Update for Graph Rewriting, no algorithm is known with provable sub-exponential worst-case complexity. These results were published in Mondada, 2025Luca Mondada and Pablo Andrés-Martínez. 2025. Scalable Pattern Matching in Computation Graphs. Electronic Proceedings in Theoretical Computer Science 417 (March 2025, 71--95). doi: 10.4204/eptcs.417.5.

The proved complexity bound applies to computations with only linear values¹, of which quantum circuits are a special case. The result is expressed in terms of maximal pattern width $w$ and depth $d$, two measures of pattern size defined in section 4.2. The main result, presented in Proposition ., is reproduced here:

The runtime complexity is dominated by an exponential scaling in maximal pattern width $w$. Meanwhile, the advantage of our approach over matching one pattern at a time grows with the number of patterns $\ell$. It is thus of particular interest for matching numerous small width patterns.

We illustrate this point by comparing our approach to a standard algorithm that matches one pattern at a time Jiang, 1998Xiaoyi Jiang and Horst Bunke. 1998. Marked subgraph isomorphism of ordered graphs. In Advances in Pattern Recognition, Berlin, Heidelberg. Springer Berlin Heidelberg, 122--131. doi: 10.1007/bfb0033230, with runtime complexity $O(\ell \cdot |P| \cdot |G|)$. Using $|P| \leq w\cdot d$ (cf. section 4.2), and comparing to eq. (1), we thus have a speedup in the regime $\Theta(c^w / w^{3/2}) < \ell$. On the other hand, $\ell$ is upper bounded by the maximum number $N_{w, d}$ of patterns of bounded width and depth. Using a crude lower-bound for $N_{w,d}$ derived in Appendix , we obtain a computational advantage for our approach when

In the case of quantum circuits, the width of the patterns is given by the number of qubits. The low-qubit regime where our approach shines coincides exactly with the typical applications of GTSs in quantum compilation: in Xu, 2022Mingkuan Xu, Zikun Li, Oded Padon, Sina Lin, Jessica Pointing, Auguste Hirth, Henry Ma, Jens Palsberg, Alex Aiken, Umut A. Acar and Zhihao Jia. 2022. Quartz: Superoptimization of Quantum Circuits. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation, June 2022. Association for Computing Machinery, 625--640. doi: 10.1145/3519939.3523433 and Xu, 2023Amanda Xu, Abtin Molavi, Lauren Pick, Swamit Tannu and Aws Albarghouthi. 2023. Synthesizing Quantum-Circuit Optimizers. Proceedings of the ACM on Programming Languages 7, PLDI (June 2023, 835--859). doi: 10.1145/3591254, all rules used have at most 4 qubits.

We present benchmarks on a real world dataset of 10,000 quantum circuits in section 4.7, showing a 20x speedup over a leading C++ implementation of pattern matching for quantum circuits.

Confluently persistent graph rewriting #

Our second major contribution, in chapter 5, uses a well-known construction in GTSs, the unfolding Baldan, 1999Paolo Baldan, Andrea Corradini and Ugo Montanari. 1999. Unfolding and Event Structure Semantics for Graph Grammars. In Foundations of Software Science and Computation Structures, Berlin, Heidelberg. Springer Berlin Heidelberg, 73--89. doi: 10.1007/3-540-49019-1_6, to derive a novel data structure $\mathcal{D}$ that compresses the representation of the space $\mathcal{G}$ of all graphs reachable from an input within a GTS. We call $\mathcal{D}$ the factorised search space of $\mathcal{G}$. Optimisation problems over the space of reachable graphs in a GTS can then equivalently be expressed as optimisation problems over $\mathcal{D}$.

We show in section 5.5 that under some assumptions on the GTS and input, there is an exponential complexity separation in the input size between the size of the factorised search space $\mathcal{D}$ – which admits an asymptotically linear upper bound – and the size of the rewrite space $\mathcal{G}$ that it encodes – which grows at least exponentially.

$\mathcal{D}$ is furthermore the first confluently persistent data structure Drisco., 1994James R. Driscoll, Daniel D. K. Sleator and Robert E. Tarjan. 1994. Fully persistent lists with catenation. Journal of the ACM 41, 5 (Septempter 1994, 943--959). doi: 10.1145/185675.185791 Fiat, 2003Amos Fiat and Haim Kaplan. 2003. Making data structures confluently persistent. Journal of Algorithms 48, 1 (August 2003, 16--58). doi: 10.1016/s0196-6774(03)00044-0 [?] it performs non-destructive rewrites on immutable graph objects by maintaining an explicit history of all graph rewrites and their dependencies. This allows concurrent application of multiple rewrites and can merge rewritten graphs that were obtained independently. This represents an exciting development in its own right that opens the door to functional programming and massively parallelised approaches to graph rewriting (see section 6.2).

The intuition behind the exponential reduction in search space size is as follows: if rewrites $r_1, \dots, r_n$ apply to disjoint subgraphs of a common graph $G$, then $\mathcal{D}$ will be of size $n$, storing the set possible rewrites, rather than the up to $2^n$ distinct graphs in $\mathcal{G}$ obtained by applying a subset of the rewrites. To generalise to arbitrary rewrites, the data structure $\mathcal{D}$ must keep track of the dependencies and overlaps between rewrites and update these as more rewrites are added to $\mathcal{D}$.

A lot of parallels can be drawn between this approach and equality saturation, a technique for term rewriting with applications in classical compilers. We explore these connections in section 5.2.

Unlike the results of chapter 4, the construction and bounds proven in chapter 5 can be applied to a wide range of graph rewriting domains. It has particularly significant implications for applications of GTSs that are unable to derive rewriting strategies from first principles, and hence have to resort to an exhaustive (or heuristic) exploration of the rewrite space $\mathcal{G}$. They can proceed as follows:

1. Exploration phase. Construct the factorised search space $\mathcal{D}$ by finding and applying rewrites, in time proportional to $|\mathcal{D}|$. With our results, this results in an exponential speedup over the naive exploration of $\mathcal{G}$ (section 5.3).

2. Extraction phase. Unlike the case of $\mathcal{G}$ where the optimal solution is an element $G_{opt} \in \mathcal{G}$, constructing the optimal solution $\mathcal{D} \rightarrow G_{opt}$ in $\mathcal{D}$ is a non-trivial extraction problem. We show in section 5.4 that the extraction can be expressed as a boolean satisfiability (SAT) problem; depending on the cost function, the optimisation can then be encoded as a side condition on SAT or by a generalisation of the problem to Satisfiability Modulo Theories (SMT).

In the worst case, SAT and SMT problems will require exponential time to solve Cook, 1971Stephen A. Cook. 1971. The complexity of theorem-proving procedures. In Proceedings of the third annual ACM symposium on Theory of computing - STOC ’71. ACM Press, 151--158. doi: 10.1145/800157.805047 Moskew., 2001Matthew W. Moskewicz, Conor F. Madigan, Ying Zhao, Lintao Zhang and Sharad Malik. 2001. Chaff: engineering an efficient SAT solver. In Proceedings of the 38th conference on Design automation - DAC ’01. ACM Press, 530--535. doi: 10.1145/378239.379017 Biere, 2021Armin Biere, Marijn J. H. Heule, Hans Maaren and Toby Walsh. 2021. Handbook of satisfiability (Second edition ed.). IOS Press, Amsterdam, thus cancelling the exponential compression of the search space $\mathcal{G} \rightarrow \mathcal{D}$. However, SAT and SMT are standardised problems for which heavily optimised solvers and optimisers have been developed Moura, 2008Leonardo de Moura and Nikolaj Bjørner. 2008. Z3: An Efficient SMT Solver. In Tools and Algorithms for the Construction and Analysis of Systems. Springer Berlin Heidelberg, 337--340. doi: 10.1007/978-3-540-78800-3_24 Sebast., 2015Roberto Sebastiani and Patrick Trentin. 2015. OptiMathSAT: A Tool for Optimization Modulo Theories. In Computer Aided Verification. Springer International Publishing, 447--454. doi: 10.1007/978-3-319-21690-4_27. We expect that the instances of SAT and SMT that encode the extraction problem will scale well in practice:

• Clauses in the problem encode local properties that SAT solvers are well-suited to solve Zulkos., 2018Edward Zulkoski. 2018. Understanding and Enhancing CDCL-based SAT Solvers. PhD Thesis. University of Waterloo​: the boolean variables represent rewrites, which only impose restrictions on other rewrites that apply in the same neighbourhood of the graph.
• Furthermore, in quantum compilation applications, $\mathcal{D}$ can be sparsified: most rewrties in $\mathcal{D}$ do not change the cost function (think of IR transformations that reorder operations but do not reduce the runtime) and thus do not need to be encoded in the SAT problem.

In a first exploratory analysis, we present some empirical results that support our claims: by searching over the factorised search space instead of the naive search space, the optimiser is able to find the global optimum for circuits that are twice as large. Our results also exhibit a linear scaling in the size of the factorised search space, confirming that the approach should scale well to larger problems.

Conclusion #

The thesis concludes in chapter 6 with a discussion on how our contributions serve our overall goal of a scalable and modular quantum compiler platform. We discuss in particular two extensions of our work that we see as particularly promising: the generalisation of fast multi-pattern matching to non-linear values and to the persistent data structure $\mathcal{D}$ of chapter 5 (section 6.1) and the deployment of confluently persistent graph rewriting to a massively parallel distributed compute architecture (section 6.2).