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 4.13, 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. (2), 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

$$\Theta\left(\frac{c^w}{w^{\frac32}}\right) < \ell < \left(\frac{w}{2e}\right)^{\Theta(w d)} \leq N_{w, d}.$$

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).

Chapter 2

Quantum Computing: a Computer Scientist's Perspective

Many (too many?) introductions to quantum computing have been written, so we will refrain from adding another entry to the collection. Instead, beyond the absolute basics, our focus is on the expressive power and syntax of quantum programs. This demystifies quantum compilation into program transformation problems, amounting to traditional compiler methods that will be very familiar to computer scientists.

In this chapter, we lay the groundwork for this thesis by introducing what programs meant to run on quantum computers look like today, what we expect they will look like in the (near) future, and how quantum compilers have been built to optimise them. We start in section 2.1 with a review of the basic computation primitives of quantum computers and how they are composed to form quantum circuits, the simplest form of quantum programs. This is followed by a review of the leading quantum circuit optimisation techniques in section 2.2. Finally, sections 2.3 and 2.4 introduce and discuss the impact of hybrid quantum computations, and how they challenge existing quantum compiler designs and optimisations.

2.1. Foundations of quantum computing

The most widespread computational model in quantum computing – and arguably its simplest – is built on the qubit abstraction. As its name suggests, it is the quantum analogue of the classical bit, i.e., a value that can take the values 0 or 1.

We will stick to our promise of not delving into the details of the physical realisations of qubits in real-world architectures. Nonetheless, it is important to note one fundamental difference with classical systems. Classical bit values (the famous 0s and 1s of our computers) are typically encoded using two voltages; another way of saying this is that bit values, and hence data, correspond to electrical currents in the wires¹ of a chip. Gates, i.e. the lowest level of operations that can be applied to bits, then correspond to barriers that let the electrical current flow through to outgoing wires, or block it.

We can thus picture a classical gate as a black box with n input wires going into the box and m output wires leaving it. For any combination of on and off voltages on the input wires, the box will turn on some of the output wires. The vital point to take away from this classical state of affairs is that we can think of the carriers of input and output data (i.e. the input and output wires) as physically distinct objects that can exist and can be read simultaneously.

Quantum physics rules out such an implementations of qubits. In the case of matter-based qubits, such as ions in traps or Josephson junctions on superconductors, quantum gates are operations that modify – or “mutate”, to borrow a term from programming languages – the physical qubits themselves. An input qubit to a gate is thus submitted to physical interactions that change its internal state. After the gate execution is completed, the qubits that held the input states now contain the operation’s output.

Similarly, photonic systems encode qubits using modes of the electromagnetic field. A gate in this setting acts by transforming these modes – mixing them, shifting their phases, or entangling them with ancillary modes. It is never possible to modify qubit data coherently whilst keeping access to the original input data.

This has several profound implications for quantum computing. First and foremost, every quantum gate must have the same number of inputs as outputs. Most iconic classical gates (AND, OR, XOR, etc.) are thus impossible to implement on a quantum computer without some adjustments². This also means that the number of qubits must remain unchanged throughout the computation. A computation that starts with n qubits must also end in n qubits – and have n qubits at every point throughout the computation.

At this point, taking the preservation of qubits just described seriously, we should be asking how a quantum computation can even come to be at all, given that no qubit can be created out of thin air. In our attempt to remain blissfully ignorant of physical realities, we suggest adopting the following abstracted mental model of qubits: qubits can neither be created nor deleted³, they simply i) exist at all times, and ii) can be reset to the 0 state.

For our convenience, we can ignore qubits that are unimportant to us. If all we need are n qubits, then we will limit our considerations to these and pretend none other exists. Pushing further our myopic focus on qubits with a direct utility, we can also adjust the window of qubits of interest as we progress through the computation. If, for instance, a new qubit becomes useful halfway through our program execution, we can enlarge the set of qubits we are keeping track of and refer to this as “creating” a qubit. Conversely, qubits often become irrelevant, in which case we move them outside of our field of consideration and say that the qubits were discarded.

A final consequence of mutating qubits that we will highlight is that once a gate has been applied, the input states to the gate no longer exist! In other words, any state that we reach throughout our execution can only be used at most once. Here, your classical intuition might kick in:

Let us just maintain a copy of the original state before modifying it!

This would allow us to do more than one computation from a temporary value. However, copying is a big NO in quantum computing. It is a profound restriction (or property, depending on your point of view) with deep roots in the physics of quantum mechanics. This principle, the no-cloning theorem, is one of three fundamental properties of quantum physics that quantum computing builds upon.

The physical constraints of quantum computation #

No-cloning theorem #

The no-cloning principle Wootte., 1982W. K. Wootters and W. H. Zurek. 1982. A single quantum cannot be cloned. Nature 299, 5886 (October 1982, 802--803). doi: 10.1038/299802a0 provides a formal foundation for the vague statement “qubits live forever” we made earlier. It is a fundamental tenet of quantum information, deserving a more rigorous treatment than we are giving it here. We recommend that the curious reader refers themselves to more respectful references such as Nielsen, 2016Michael A. Nielsen and Isaac L. Chuang. 2016. Quantum Computation and Quantum Information (10th Anniversary edition). Cambridge University Press.

No-cloning theorem: it is impossible to copy an arbitrary unknown state onto another (possibly known) qubit, or to copy a (possibly known) qubit to a qubit with unknown arbitrary state.

If we use $\ket{\psi}$ to denote an arbitrary state and $\ket{0}$ to denote a known state, the principle can be restated as: there are no quantum computations mapping $\ket{\psi}\ket{0} \mapsto \ket{\psi}\ket{\psi}$, nor $\ket{\psi}\ket{0} \mapsto \ket{0}\ket{0}$. The consequences of this are profound.

A consequence of the first half is what we alluded to in the previous section: any qubit states can only be used once in a computation. This statement also justifies why every quantum gate implementation, no matter the hardware specifics, will mutate its input qubits to produce the output states.

The second half of the statement is often referred to as the “no delete” theorem. Indeed, if we view $\ket{\psi}$ as a state encoding some data, we can interpret it as some amount of information. The state $\ket{0}$, on the other hand, is a fixed state and thus cannot store any information. From the perspective of information theory, the map $\ket{\psi}\ket{0} \mapsto \ket{0}\ket{0}$ thus destroys information: it turns an information storing left-hand side into a product of $\ket{0}$ states, devoid of any information.

We can also revisit the first map $\ket{\psi}\ket{0} \mapsto \ket{\psi}\ket{\psi}$ and understand it from an information theoretic perspective as an attempt to create information out of thin air! Using this interpretation, the no-cloning theorem is thus the statement that quantum information is a preserved quantity in quantum computations: its amount will never increase or decrease.

Reversibility #

The fact that the amount of quantum information can never increase by transforming quantum states matches our intuition: if no new information is added from outside the system, then the total information encoded should not be increasing. Why, however, is it impossible to erase some information and thus reduce its total? The answer is reversibility of closed quantum systems: if we exclude the option of discarding parts of the physical system, every quantum of operation is undoable. In other words, a computation must have an inverse operation that recovers the input when applied to the output.

If a quantum operation were thus to erase any information, then an inverse operation would exist that creates information from nothing! The two halves of the no-cloning theorem, as we presented it, thus state the same principle once we consider that every operation must be reversible.

Universality #

Finally, a third distinguishing property of quantum computation is how arbitrarily large computations can be generated from single-qubit gates and pairwise entangling interactions between qubits (two-qubit gates) Barenco, 1995Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin and Harald Weinfurter. 1995. Elementary gates for quantum computation. Physical Review A 52, 5 (November 1995, 3457--3467). doi: 10.1103/PhysRevA.52.3457. It is furthermore the case that the choice of a fixed two-qubit gate, along with single-qubit gates, is sufficient to generate any arbitrary quantum computation. We call a set of gates that can be used to construct any arbitrary quantum computation a universal gate set.

This is a boon for hardware design, as manipulating single-qubit systems is often much more manageable than controlling physical interactions between multiple entities. This decomposition into single-qubit and (a fixed) two-qubit gates means that the architecture i) does not need to support interactions between $n > 2$ qubits, and ii) can be specialised and hand-tuned to execute the two-qubit interaction of choice as faithfully as possible. Having a two-qubit gate as the entangling operation is not the only choice. Some architectures, such as neutral atoms, choose instead to replace it with a global entangling operation that applies to many qubits simultaneously Evered, 2023Simon J. Evered, Dolev Bluvstein, Marcin Kalinowski, Sepehr Ebadi, Tom Manovitz, Hengyun Zhou, Sophie H. Li, Alexandra A. Geim, Tout T. Wang, Nishad Maskara, Harry Levine, Giulia Semeghini, Markus Greiner, Vladan Vuletić and Mikhail D. Lukin. 2023. High-fidelity parallel entangling gates on a neutral-atom quantum computer. Nature 622, 7982 (October 2023, 268--272). doi: 10.1038/s41586-023-06481-y, resulting in a universal gate set that is more convenient to implement experimentally in their system.

Gate set universality can be generalised further to approximate universality, which is at the centre of the development of error-correcting codes. Indeed, any quantum computations can be approximated to arbitrary precision using only discrete finite sets of one and two-qubit gates Kitaev, 2002Alexei Y. Kitaev, A. H. Shen and Mikhail N. Vyalyi. 2002. Classical and Quantum Computation. American Mathematical Society Dawson, 2006Christopher M. Dawson and Michael A. Nielsen. 2006. The Solovay-Kitaev algorithm. Quantum Information and Computation 6, 1 (January 2006, 81--95). doi: 10.26421/QIC6.1-6. This represents a significant simplification for error correction, as it removes the need for continuously parametrised gates and discretises the problem space.

Leveraging quantum properties for compilation #

We have introduced the universality, reversibility and no-cloning properties of quantum computations for a reason: these laws of physics that govern quantum computations and are absent from classical computer science are an excellent foundation for developing quantum-specific computation optimisations and compilation techniques in general.

As we have just discussed, the wide variety of universal gate sets are degrees of freedom that the compiler can use. Using universality to translate computations between universal gate sets, enabling programmers to seamlessly target different hardware, is one of quantum compiler’s first and most fundamental functions Sivara., 2020Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington and Ross Duncan. 2020. t|ket⟩: a retargetable compiler for NISQ devices. Quantum Science and Technology 6, 1 (November 2020, 014003). doi: 10.1088/2058-9565/ab8e92.

Reversibility is also a source of flexibility when expressing quantum programs. Suppose the user wants to execute an operation $A$ but it is more convenient, or the hardware is only capable of executing a different gate $B$. Then, using the inverse $B^{-1}$ of $B$, it is always possible to rewrite the program as

where these diagrams should be read as operations to be executed from left to right. This is nothing but the mathematical trick of multiplying the left-hand side with the identity operation expressed as $B \circ B^{-1}$⁴.

Now, of course, this rewrite is only sensible if the operation $B^{-1} \circ A$ is reasonably cheap to perform. There are plenty of instances where this is indeed the case. Morally, the quantum compiler always has the freedom to execute any quantum operation – at the risk of producing very inefficient code – given that reversibility always guarantees that the operation can be reversed and the competition undone whenever necessary.

Finally, no-cloning is a very useful guarantee that the compiler can use to simplify reasoning about computations⁵. In chapter 4 we will see that it dramatically simplifies pattern matching, which helps identify all possible optimisations quickly. More generally, no-cloning restricts the set of programs that the compiler must consider, resulting in elegant graph transformation semantics – a topic we explore in chapter 3.

The quantum circuit representation #

We could not conclude our overview of the basics of quantum computing without mentioning the quantum circuit, a representation of quantum computation ubiquitous in the field. With the understanding that we have gained in this section, the two building blocks of the circuit model and the conventions around their graphical representation should be of no surprise to the reader:

1. Qubits are represented by straight, horizontal lines. Their evolution through time can be followed along the line from left to right: At the leftmost point on the line, the qubit is in its input state; when the qubit reaches its rightmost point, operations have mutated it into the output state of the circuit.
2. Gates on qubits are boxes placed vertically across one or multiple qubit lines. The qubits it is on represents the set that the gate may act on (and mutate), whereas the left-to-right ordering of the gates reflects their ordering in time.

A simple circuit composed of two qubits and three gates $A$, $B$ and $C$ could for instance look like this

The previous diagram was in fact also a circuit, in which each arrow pointing to the right was a segment of a qubit line. In this case, $A$ would be executed before $B$ and $C$; $A$ would act on both qubits, whereas $B$ and $C$ would only modify the first and second qubits, respectively. Note that there is no ordering specified between $B$ and $C$: because they act on disjoint sets of qubits, their relative ordering makes no difference. It is thus common to display them as acting at the same time. We could have equivalently chosen to draw them as:

All these circuits represent the same computation.

Certain quantum gates are particularly useful and appear very regularly in practice. These have standard names that are widely used in the field. The most common single qubit gates are arguably the Hadamard, represented in circuits by a $H$ box, and the $X$, $Y$ and $Z$-axis rotations, drawn as $R_x(\theta)$, $R_y(\theta)$ and $R_z(\theta)$ boxes respectively. Note that rotation gates are parametrised by an angle $0 \leqslant \theta < 4\pi$ that must be specified to execute the rotation.

There are also commonly used multi-qubit gates. For these, it becomes slightly awkward to draw them as boxes, as they may act on qubits that are not drawn next to each other in the circuit⁶ or might be applied to qubits in a specified order. As a solution, common gates were given representations that do not spell out their name but mark which qubit they are acting on and in what order. Here are the representations of three of the most famous ones, in order: the $\mathit{CX}$ (also known as CNOT) gate, the $\mathit{CZ}$ and the $\mathit{CCX}$ (also known as the three-qubit Toffoli):

You will probably notice that there seems to be a system to this graphical notation. There is, but unfortunately, explaining it would require us to discuss Pauli matrices and commutation relations and quickly lead us astray. The references in section 2.5 are a good starting point for further reading.

2.2. Quantum circuit optimisation: a review

Much of the foundations of classical computer science rely on boolean logic and discrete mathematics Lehman, 2017Eric Lehman, F. Thomson Leighton and Albert R. Meyer. 2017. Mathematics for Computer Science. Samurai Media Limited. In some regards, this is a poor man’s maths, as much of the structure that comes with continuous infinite mathematical objects is lost along the way when discretised.

In contrast, quantum computation, on the other hand, encompasses the whole breadth of (finite dimensional) quantum physical system evolution. Underlying this is a rich mathematical theory steeped in the theory of Hilbert spaces and Lie groups¹. A direct consequence of the mathematics of quantum computations is the flourishing of an entire field of research dedicated to quantum circuit optimisations Karupp., 2025Krishnageetha Karuppasamy, Varun Puram, Stevens Johnson and Johnson P. Thomas. 2025. A Comprehensive Review of Quantum Circuit Optimization: Current Trends and Future Directions. Quantum Reports 7, 1 (January 2025, 2). doi: 10.3390/quantum7010002. They leverage the unique structure and symmetries of quantum physics to reduce the noise and resource requirements of quantum computations significantly.

In this section, we will review the main optimisation techniques that established themselves within quantum compilers, focusing on the representation of quantum computations they use and their assumptions about the computations they are optimising.

Cost function #

A key point to settle first when discussing circuit optimisations is the objective of the optimisation – the cost function to be minimised. Unlike much of classical compiler research, which can rely on an established set of hardware targets and benchmarking datasets to profile the empirical, “real world” performance of compiled programs, the quantum world must often contend with simplified noise and architecture models to design proxy metrics, given the limited scale and availability of current quantum devices.

The quantum compilers research community has mostly coalesced around cost functions based on gate count statistics Karupp., 2025Krishnageetha Karuppasamy, Varun Puram, Stevens Johnson and Johnson P. Thomas. 2025. A Comprehensive Review of Quantum Circuit Optimization: Current Trends and Future Directions. Quantum Reports 7, 1 (January 2025, 2). doi: 10.3390/quantum7010002. Counting a type of gate is a simple and popular choice. Making some additional assumptions on the gate parallelism of future hardware, one may also consider cost functions based on gate depth, i.e. the length of the longest chain of gates that cannot be run simultaneously Seling., 2013Peter Selinger. 2013. Quantum circuits of T-depth one. Physical Review A 87, 4 (April 2013, 042302). doi: 10.1103/physreva.87.042302 Basile., 2024Daniel Basilewitsch, Clemens Dlaska and Wolfgang Lechner. 2024. Comparing planar quantum computing platforms at the quantum speed limit. Physical Review Research 6, 2 (April 2024, 023026). doi: 10.1103/physrevresearch.6.023026. In spite (or precisely because) of their simplicity, gate counts serve well as cost functions in many quantum compilation use cases. Most circuit optimisations target one of two hardware regimes.

On most current hardware architectures, the major challenge is achieving high accuracy on entangling operations, i.e. quantum gates that make two or more qubits interact Acharya, 2024Rajeev Acharya, Dmitry A. Abanin, Laleh Aghababaie-Beni, Igor Aleiner, Trond I. Andersen, Markus Ansmann, Frank Arute, Kunal Arya, Abraham Asfaw, Nikita Astrakhantsev, Juan Atalaya, Ryan Babbush, Dave Bacon, Brian Ballard, Joseph C. Bardin, Johannes Bausch, Andreas Bengtsson, Alexander Bilmes, Sam Blackwell, Sergio Boixo, Gina Bortoli, Alexandre Bourassa, Jenna Bovaird, Leon Brill and et al. 2024. Quantum error correction below the surface code threshold. Nature (December 2024). doi: 10.1038/s41586-024-08449-y Pino, 2021J. M. Pino, J. M. Dreiling, C. Figgatt, J. P. Gaebler, S. A. Moses, M. S. Allman, C. H. Baldwin, M. Foss-Feig, D. Hayes, K. Mayer, C. Ryan-Anderson and B. Neyenhuis. 2021. Demonstration of the trapped-ion quantum CCD computer architecture. Nature 592, 7853 (April 2021, 209--213). doi: 10.1038/s41586-021-03318-4 Koch, 2007Jens Koch, Terri M. Yu, Jay Gambetta, A. A. Houck, D. I. Schuster, J. Majer, Alexandre Blais, M. H. Devoret, S. M. Girvin and R. J. Schoelkopf. 2007. Charge-insensitive qubit design derived from the Cooper pair box. Physical Review A 76, 4 (October 2007, 042319). doi: 10.1103/PhysRevA.76.042319 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. In superconducting qubit and ion trap architectures², for example, the gate set is typically composed of one and two-qubit gate types, with error rates dominated by an order of magnitude by the latter Steiger, 2018Damian S. Steiger, Thomas Häner and Matthias Troyer. 2018. ProjectQ: an open source software framework for quantum computing. Quantum 2 (January 2018, 49). doi: 10.22331/q-2018-01-31-49 Sivara., 2020Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington and Ross Duncan. 2020. t|ket⟩: a retargetable compiler for NISQ devices. Quantum Science and Technology 6, 1 (November 2020, 014003). doi: 10.1088/2058-9565/ab8e92. Circuit optimisations for computations on such noisy hardware thus often define cost functions based on the number of two-qubit gates – typically the $\mathit{CX}$ gate, though many other two-qubit gates could be used equivalently.

On the other hand, future generations of hardware for larger scale computations are expected to be more resilient to noise, with the help of error detection and correction techniques. In this regime, the computational power of the hardware is no longer limited by hardware noise but rather by the affordances of the error-correcting code. Depending on how the quantum data is redundantly encoded in the code space, the fault-tolerant execution of specific operations may be anywhere between very straightforward and nigh-impossible. The bottleneck is widely expected to be the execution of single-qubit (non-Clifford) gates, such as the $\mathit{T}$ gate³. These cases can thus just as well be modelled by cost functions based on gate counts.

Unitary synthesis: the perfect optimisation #

The ne plus ultra of quantum circuit optimisation is unitary synthesis. It leverages the representation of a quantum computation as a square, complex-valued, unitary matrix, which is then re-synthesised as a new, equivalent (and ideally optimised!) quantum circuit. This approach thus breaks down quantum optimisation into two separate sub-problems:

1. Reduce a $n$-qubit quantum circuit into a $2^n \times 2^n$ matrix. This matrix is a unique representation of the computation, meaning that any two equivalent computations will be mapped to the same matrix.
2. Find the optimal matrix decomposition into primitive quantum gates, thus obtaining a new quantum circuit, equivalent to the original.

The uniqueness of the unitary matrix representation makes it invaluable as a resource for computation optimisation. Not only does it reduce any potentially large collection of equivalent inputs to a single form; it also – crucially – provides a sound distance metric on the space of all circuits, in the form of the Haar measure. This can be used in search-based approaches to measure the distance between synthesised circuits and thus direct a search heuristic towards the optimal solution.

Early work explored general unitary decomposition schemes obtained analytically from linear algebra. These express arbitrary unitaries as a product of unitaries that typically correspond to one and two-qubit gates in the quantum circuit model Iten, 2016Raban Iten, Roger Colbeck, Ivan Kukuljan, Jonathan Home and Matthias Christandl. 2016. Quantum circuits for isometries. Physical Review A 93, 3 (March 2016, 032318). doi: 10.1103/PhysRevA.93.032318 Iten, 2019Raban Iten, Oliver Reardon-Smith, Emanuel Malvetti, Luca Mondada, Gabrielle Pauvert, Ethan Redmond, Ravjot Singh Kohli and Roger Colbeck. 2019. Introduction to UniversalQCompiler. arXiv: 1904.01072 [quant-ph]. Approaches have been proposed using the Cosine-Sine decomposition Mött�., 2004Mikko Möttönen, Juha J. Vartiainen, Ville Bergholm and Martti M. Salomaa. 2004. Quantum Circuits for General Multiqubit Gates. Physical Review Letters 93, 13 (Septempter 2004, 130502). doi: 10.1103/PhysRevLett.93.130502, the Quantum Shanon decomposition Krol, 2022Anna M. Krol, Aritra Sarkar, Imran Ashraf, Zaid Al-Ars and Koen Bertels. 2022. Efficient Decomposition of Unitary Matrices in Quantum Circuit Compilers. Applied Sciences 12, 2 (January 2022, 759). doi: 10.3390/app12020759, and the QR decomposition Sedlák, 2008Michal Sedlák and Martin Plesch. 2008. Towards optimization of quantum circuits. Open Physics 6, 1 (March 2008, 128--134). doi: 10.2478/s11534-008-0039-8. While some schemes have been shown to be asymptotically efficient for almost all unitaries Iten, 2016Raban Iten, Roger Colbeck, Ivan Kukuljan, Jonathan Home and Matthias Christandl. 2016. Quantum circuits for isometries. Physical Review A 93, 3 (March 2016, 032318). doi: 10.1103/PhysRevA.93.032318, such strategies typically generate fixed-sized circuits and fail to synthesise short circuits when such circuits exist. The size of synthesised circuits grows exponentially with the number of qubits, making most such schemes impractical beyond three qubits.

Unitary matrix decomposition can also be combined with tools from classical circuit design: in Loke, 2014T. Loke, J. B. Wang and Y. H. Chen. 2014. OptQC : An optimized parallel quantum compiler. Computer Physics Communications 185, 12 (December 2014, 3307--3316). doi: 10.1016/j.cpc.2014.07.022, Loke et al. proposed an approach merging reversible circuit synthesis (see below), a classical compilation problem, with unitary matrix synthesis. They show that searching for decompositions $U = PU'Q$, where $P$ and $Q$ are classical reversible circuits can yield shorter circuits when using the Cosine-Sine decomposition for the unitaries $U$ and $U'$.

Search-based approaches have been developed to address the shortcomings of analytical decompositions. Unlike the algebraic approaches, the circuit decomposition problem is viewed as an optimisation problem in search-based circuit synthesis. The space of all possible quantum circuits is explored to find the one that implements the desired unitary whilst minimising the cost function. The major challenge of such methods is the gigantic (typically super-exponential) size of the search space of all possible programs. Without mitigation, most work in this space struggles to scale beyond a handful of qubits.

Up to 3 qubits, T-depth optimal circuits can be found using exhaustive brute force search first proposed in Amy, 2013M. Amy, D. Maslov, M. Mosca and M. Roetteler. 2013. A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 32, 6 (June 2013, 818--830). doi: 10.1109/TCAD.2013.2244643 and improved in Gheorg., 2022Vlad Gheorghiu, Michele Mosca and Priyanka Mukhopadhyay. 2022. A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth optimal circuits. npj Quantum Information 8, 1 (Septempter 2022). doi: 10.1038/s41534-022-00624-1. Asymptotic bounds on the number of T gates required for general unitary synthesis were recently given in Gosset, 2024David Gosset, Robin Kothari and Kewen Wu. 2024. Quantum state preparation with optimal T-count. arXiv: 2411.04790 [quant-ph].

Scaling to 4 qubits and handling gate sets with continuous parameters, required for non-fault tolerant circuits, an A* search with smart pruning heuristics was proposed in Davis, 2020Marc G. Davis, Ethan Smith, Ana Tudor, Koushik Sen, Irfan Siddiqi and Costin Iancu. 2020. Towards Optimal Topology Aware Quantum Circuit Synthesis. In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), October 2020. IEEE, 223--234. doi: 10.1109/QCE49297.2020.00036. This approach’s outputs are no longer provably optimal, but the results match optimal decompositions in all known instances. This line of work has subsequently been further refined with heuristics based on pre-defined circuit templates Smith, 2023Ethan Smith, Marc Grau Davis, Jeffrey Larson, Ed Younis, Lindsay Bassman Oftelie, Wim Lavrijsen and Costin Iancu. 2023. LEAP: Scaling Numerical Optimization Based Synthesis Using an Incremental Approach. ACM Transactions on Quantum Computing 4, 1 (February 2023, 1--23). doi: 10.1145/3548693 Madden, 2022Liam Madden and Andrea Simonetto. 2022. Best Approximate Quantum Compiling Problems. ACM Transactions on Quantum Computing 3, 2 (March 2022, 1--29). doi: 10.1145/3505181, parameter instantiation Younis, 2022Ed Younis and Costin Iancu. 2022. Quantum Circuit Optimization and Transpilation via Parameterized Circuit Instantiation. arXiv: 2206.07885 [quant-ph] Younis, 2021Ed Younis, Koushik Sen, Katherine Yelick and Costin Iancu. 2021. QFAST: Conflating Search and Numerical Optimization for Scalable Quantum Circuit Synthesis. In 2021 IEEE International Conference on Quantum Computing and Engineering (QCE), October 2021. IEEE, 232--243. doi: 10.1109/QCE52317.2021.00041 Rakyta, 2022Péter Rakyta and Zoltán Zimborás. 2022. Approaching the theoretical limit in quantum gate decomposition. Quantum 6 (May 2022, 710). doi: 10.22331/q-2022-05-11-710, machine learning Weiden, 2023Mathias Weiden, Ed Younis, Justin Kalloor, John Kubiatowicz and Costin Iancu. 2023. Improving Quantum Circuit Synthesis with Machine Learning. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE). IEEE. doi: 10.1109/QCE57702.2023.00093 and tensor networks Kuklia., 2023Alon Kukliansky, Ed Younis, Lukasz Cincio and Costin Iancu. 2023. QFactor: A Domain-Specific Optimizer for Quantum Circuit Instantiation. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), Septempter 2023. IEEE, 814--824. doi: 10.1109/QCE57702.2023.00096.

Some of these heuristics also make it possible to synthesise circuits with device constraints in mind and can trade off decomposition accuracy for shallower circuit depth and lower noise. In Wu, 2020Xin-Chuan Wu, Marc Grau Davis, Frederic T. Chong and Costin Iancu. 2020. QGo: Scalable Quantum Circuit Optimization Using Automated Synthesis. arXiv: 2012.09835 [quant-ph] Kuklia., 2023Alon Kukliansky, Ed Younis, Lukasz Cincio and Costin Iancu. 2023. QFactor: A Domain-Specific Optimizer for Quantum Circuit Instantiation. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), Septempter 2023. IEEE, 814--824. doi: 10.1109/QCE57702.2023.00096, the authors have also explored partitioning the circuit into smaller parts optimised independently to scale these techniques to large circuit sizes. Despite the reduced optimisation performance that the boundaries of the partitioned circuits introduce, the combination of circuit partitioning with the techniques listed above yields some of the best-performing circuit optimisation techniques developed to date Costin., 2025Bert Costin Iancu. 2025. Berkeley Quantum Synthesis Toolkit. Retrieved on 09/01/2025 from https://bqskit.lbl.gov/. Circuit synthesis schemes have also been extended to generate circuits on a more expressive gate set, including elementary classical operations Alam, 2024Faisal Alam and Bryan K. Clark. 2024. Learning dynamic quantum circuits for efficient state preparation. arXiv: 2410.09030 [quant-ph] Niu, 2024Siyuan Niu, Efekan Kokcu, Anupam Mitra, Aaron Szasz, Akel Hashim, Justin Kalloor, Wibe Albert de Jong, Costin Iancu and Ed Younis. 2024. AC/DC: Automated Compilation for Dynamic Circuits. arXiv: 2412.07969 [quant-ph].

However, a fundamental flaw of all unitary synthesis schemes is the $4^n$-scaling in the number of qubits $n$ of the unitary representation itself. This means that no matrix-based synthesis method, however efficient, will ever be able to handle computations with much more than a dozen qubits. Circuit partitioning schemes such as Wu, 2020Xin-Chuan Wu, Marc Grau Davis, Frederic T. Chong and Costin Iancu. 2020. QGo: Scalable Quantum Circuit Optimization Using Automated Synthesis. arXiv: 2012.09835 [quant-ph] Kuklia., 2023Alon Kukliansky, Ed Younis, Lukasz Cincio and Costin Iancu. 2023. QFactor: A Domain-Specific Optimizer for Quantum Circuit Instantiation. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), Septempter 2023. IEEE, 814--824. doi: 10.1109/QCE57702.2023.00096 effectively circumvent the problem, but they are heavily dependent on the partitioning quality.

The search for scalable representations #

Our study of unitary synthesis introduced us to a convenient two-step approach to quantum computation optimisation. First, the input circuit is transformed into a “global” representation that captures the computation as a whole, abstracting away the precise sequences of gates that compose the original circuit. This representation is then the input for the second half of the problem, which produces a circuit of the desired shape, equivalent to the original input but with reduced cost.

In addition to simplifying the original problem, such global intermediate representations are well-positioned to leverage the quantum-specific structure and symmetries in the computation. They can thus enable more advanced optimisations and are robust to varying circuit representation and local optimisation landscape.

The unitary matrix is the most common representation of quantum computations, but as we have seen, it suffers from severe scaling problems in the number of qubits. The problem is not so much that quantum computations require exponential space to be described in the worst case – after all, the space of all $n$-qubit unitaries $SU(2^n)$ is exponentially large. However, the set of unitaries implementable in practice can only be a tiny subset of $SU(2^n)$⁴ – the set of unitaries that admit a polynomial-sized circuit representation.

Another fruitful avenue of work for quantum optimisation has thus been the development of alternative representations for quantum computations that can encode polynomially sized quantum programs efficiently whilst enabling novel optimisations.

Phase Polynomials and Pauli Gadgets #

A particularly convenient global representation of many quantum circuits is as products of Pauli exponentials, also known as Pauli gadgets Cowtan, 2019Alexander Cowtan, Silas Dilkes, Ross Duncan, Will Simmons and Seyon Sivarajah. 2019. Phase Gadget Synthesis for Shallow Circuits. In Proceedings 16th International Conference on Quantum Physics and Logic, QPL 2019, Chapman University, Orange, CA, USA, June 10-14, 2019, 213--228. doi: 10.4204/EPTCS.318.13. These unitaries are of the form $$U = \prod_{s \in P} exp(i \alpha_s \cdot s)$$

where $\alpha_s \in \mathbb [0, 2\pi)$ are real coefficients and $s \in P = \{I, X, Y, Z\}^n$ are strings of length $n$ of the four Pauli matrices – so-called Pauli strings. In this formulation, $n$ fixes the number of qubits of the computation.

These exponentials are always valid $n$-qubit unitaries and can express entangling operations across any number of qubits: the qubits on which an operation $exp(i \alpha \cdot s)$ acts non-trivially are given by the indices of the characters in $s$ that are not the identity $I$. For instance, the exponential

$$exp(i \frac\pi2 XIZ)$$

is a valid quantum computation on 3 qubits, entangling the first and third qubits. Beyond useful abstractions for optimisation, such entangling operations appear naturally when simulating quantum systems, for example in quantum chemistry McClean, 2016Jarrod R McClean, Jonathan Romero, Ryan Babbush and Alán Aspuru-Guzik. 2016. The theory of variational hybrid quantum-classical algorithms. New Journal of Physics 18, 2 (February 2016, 023023). doi: 10.1088/1367-2630/18/2/023023.

The use of these primitives for quantum compilation was first explored in Cowtan, 2019Alexander Cowtan, Silas Dilkes, Ross Duncan, Will Simmons and Seyon Sivarajah. 2019. Phase Gadget Synthesis for Shallow Circuits. In Proceedings 16th International Conference on Quantum Physics and Logic, QPL 2019, Chapman University, Orange, CA, USA, June 10-14, 2019, 213--228. doi: 10.4204/EPTCS.318.13, and further generalised in Cowtan, 2020Alexander Cowtan, Will Simmons and Ross Duncan. 2020. A Generic Compilation Strategy for the Unitary Coupled Cluster Ansatz. arXiv: 2007.10515 [quant-ph]. Starting from an (unordered) sequence of Pauli gadgets, the gadgets are clustered into sets of mutually commuting gadgets. These can then be jointly synthesised into a circuit, markedly reducing the number of entangling operations as compared to naively implementing one exponential at a time.

Further improvements to this work have since been presented in Huang, 2024Qunsheng Huang, David Winderl, Arianne Meijer-van de Griend and Richie Yeung. 2024. Redefining Lexicographical Ordering: Optimizing Pauli String Decompositions for Quantum Compiling. CoRR abs/2408.00354. doi: 10.48550/ARXIV.2408.00354 and Schmitz, 2024Albert T. Schmitz, Nicolas P. D. Sawaya, Sonika Johri and A. Y. Matsuura. 2024. Graph Optimization Perspective for Low-Depth Trotter-Suzuki Decomposition. Physical Review A 109, 4 (April 2024, 042418). doi: 10.1103/PhysRevA.109.042418, where new heuristics are introduced to choose the Pauli gadget ordering. In Huang, 2024Qunsheng Huang, David Winderl, Arianne Meijer-van de Griend and Richie Yeung. 2024. Redefining Lexicographical Ordering: Optimizing Pauli String Decompositions for Quantum Compiling. CoRR abs/2408.00354. doi: 10.48550/ARXIV.2408.00354, the hardware-specific connectivity constraints between qubits are also taken into account to produce programs that can be executed on the targeted architecture without overhead.

A close relative of Pauli gadgets – a strictly smaller subset of it, to be precise – are the so-called phase polynomials Amy, 2018Matthew Amy, Parsiad Azimzadeh and Michele Mosca. 2018. On the controlled-NOT complexity of controlled-NOT–phase circuits. Quantum Science and Technology 4, 1 (Septempter 2018, 015002). doi: 10.1088/2058-9565/aad8ca, obtained when restricting the Pauli strings to combinations of Z Pauli matrices and identities: $s \in \{I, Z\}^n$ . These are particularly amenable to optimisation as in this case, the ordering of the gadgets becomes irrelevant – all exponential terms commute. This gives the compiler a lot of freedom during circuit synthesis.

The action of phase polynomials on quantum states is quite easy to understand. Instead of the exponentials of $I$ and $Z$-based Pauli string, the computation can equivalently be given by its action on the basis states. A quantum basis state – just like a classical state – is given by a bistring $b_1 \cdots b_n$ of bits $b_i \in \{0, 1\}$. Writing $e_{b_1 \cdots b_n}$ for the basis state corresponding to the bitstring $b_1 \cdots b_n$, the action of a phase polynomial $U$ on $e_{b_1 \cdots b_n}$ is given by

where $\tilde{s}_1 \cdots \tilde{s}_n$ is now also a bitstring of booleans $\tilde{s}_i \in \{0, 1\}$, and $\oplus$ denotes the boolean XOR operation. The boolean $\tilde{s}_i$ has value $1$ if and only if the $i$-th character in the Pauli string $s$ is $Z$,

The exponential expression in (2) is just a real number – indeed each term in the sum simply evaluates to either $a_s$ or $0$. A phase polynomial is thus a diagonal unitary matrix: it maps every basis state $\ket {b_1 \cdots b_n}$ to itself, multiplied by some phase $e^{i \theta}$.

Polynomially-sized circuits that implement diagonal matrices correspond to phase polynomials with $k = \mathcal{O}(n^p) \ll 2^n$ non-zero terms $a_s \neq 0$, i.e. they can represent quantum computations efficiently and scale well with the number of qubits – thus allowing efficient algorithms that scale polynomially in the number of qubits $n$.

The Graysynth algorithm, as presented in Amy, 2018Matthew Amy, Parsiad Azimzadeh and Michele Mosca. 2018. On the controlled-NOT complexity of controlled-NOT–phase circuits. Quantum Science and Technology 4, 1 (Septempter 2018, 015002). doi: 10.1088/2058-9565/aad8ca, has become the reference synthesis method for phase polynomials. The key observation made by its authors is that all terms of the sum within the exponential can be cycled through and obtained following the binary Gray codes Gray, 1953F. Gray. 1953. Pulse code communication. Retrieved from http://www.google.com/patents/US2632058. The Hamming distance of one that separates successive bitstrings in the code translates into a single two-qubit $\mathit{CX}$ gate when synthesised to a quantum circuit by Graysynth.

This approach was adapted to work with hardware connectivity constraints in Griend, 2022Arianne Meijer-van de Griend and Ross Duncan. 2022. Architecture-Aware Synthesis of Phase Polynomials for NISQ Devices. In Proceedings 19th International Conference on Quantum Physics and Logic, QPL 2022, Wolfson College, Oxford, UK, 27 June - 1 July 2022, 116--140. doi: 10.4204/EPTCS.394.8, 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 and Vandae., 2022Vivien Vandaele, Simon Martiel and Timothée Goubault de Brugière. 2022. Phase polynomials synthesis algorithms for NISQ architectures and beyond. Quantum Science and Technology 7, 4 (Septempter 2022, 045027). doi: 10.1088/2058-9565/ac5a0e. An up-to-date study of the performance of phase polynomial-based compiler optimisations and comparisons with standard approaches is performed in Meijer., 2025Arianne Meijer - van de Griend. 2025. A comparison of quantum compilers using a DAG-based or phase polynomial-based intermediate representation. Journal of Systems and Software 221 (March 2025, 112224). doi: 10.1016/j.jss.2024.112224.

The study of phase polynomials can also be generalised to arbitrary diagonal operators. Tight asymptotic bounds on the resource requirements for arbitrary diagonal operator synthesis and their implementation were recently given in Sun, 2023Xiaoming Sun, Guojing Tian, Shuai Yang, Pei Yuan and Shengyu Zhang. 2023. Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 42, 10 (October 2023, 3301--3314). doi: 10.1109/TCAD.2023.3244885. The authors propose using a smart meshing of different Gray codes in parallel and, where available, additional qubits as ancilla registers to parallelise computations further and minimise circuit depth. The resulting general-purpose decomposition of arbitrary diagonal operators yields circuits of depth $\mathcal O(\frac{2^n}{n})$ and size $\mathcal O(\frac{n^2}{\log n}) + 2^{n+3}$, as well as improved bounds in the presence of $m \geq 2n$ ancilla qubits.

Clifford synthesis #

The group of all $n$-qubit unitaries $SU(2^n)$ contains a subgroup that has become an object of study across many domains of quantum computing science: the Clifford group. We have already mentioned that it is at the centre of quantum error correction theory Bravyi, 2005Sergey Bravyi and Alexei Kitaev. 2005. Universal quantum computation with ideal Clifford gates and noisy ancillas. Physical Review A 71, 2 (February 2005, 022316). doi: 10.1103/PhysRevA.71.022316; it is also a cornerstone of measurement-based quantum computing Rausse., 2001Robert Raussendorf and Hans J. Briegel. 2001. A One-Way Quantum Computer. Physical Review Letters 86, 22 (May 2001, 5188--5191). doi: 10.1103/PhysRevLett.86.5188 and graph states Hein, 2004M. Hein, J. Eisert and H. J. Briegel. 2004. Multiparty entanglement in graph states. Physical Review A 69, 6 (June 2004, 062311). doi: 10.1103/physreva.69.062311, as well as one of the most promising approaches for fast quantum simulations Gottes., 1999Daniel Gottesman. 1999. The Heisenberg representation of quantum computers. In Group 22: Proceedings of the 12th International Colloquium onGroup Theoretical Methods in Physics,. International Press, 32--43 Bravyi, 2019Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset and Mark Howard. 2019. Simulation of quantum circuits by low-rank stabilizer decompositions. Quantum 3 (Septempter 2019, 181). doi: 10.22331/q-2019-09-02-181 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.

The Clifford subgroup of quantum circuits admits an efficient $\Theta(2n^2)$-sized program representation known as Clifford tableau Aarons., 2004Scott Aaronson and Daniel Gottesman. 2004. Improved simulation of stabilizer circuits. Physical Review A 70, 5 (November 2004, 052328). doi: 10.1103/PhysRevA.70.052328. This has been used profusely for compiler optimisation. In Aarons., 2004Scott Aaronson and Daniel Gottesman. 2004. Improved simulation of stabilizer circuits. Physical Review A 70, 5 (November 2004, 052328). doi: 10.1103/PhysRevA.70.052328 the first Clifford circuit synthesis procedure is given, using an analytical decomposition of Clifford tableaus into $O(n^2 /\log n)$ one and two-qubit gates. An improved, Bruhat-based decomposition that is optimal in the number of Hadamard gates was subsequently proposed in Maslov, 2018Dmitri Maslov and Martin Roetteler. 2018. Shorter Stabilizer Circuits via Bruhat Decomposition and Quantum Circuit Transformations. IEEE Transactions on Information Theory 64, 7 (July 2018, 4729--4738). doi: 10.1109/tit.2018.2825602. In the case of a Clifford fragment directly followed by measurements, the procedure can be further refined to replace gates with classical computation on the measurement outcomes Bravyi, 2021Sergey Bravyi and Dmitri Maslov. 2021. Hadamard-Free Circuits Expose the Structure of the Clifford Group. IEEE Transactions on Information Theory 67, 7 (July 2021, 4546--4563). doi: 10.1109/TIT.2021.3081415. Finally, an alternative normal form that is well-suited to hardware with limited nearest neighbours connectivity was also derived using a diagrammatic approach Maslov, 2023Dmitri Maslov and Willers Yang. 2023. CNOT circuits need little help to implement arbitrary Hadamard-free Clifford transformations they generate. npj Quantum Information 9, 1 (Septempter 2023). doi: 10.1038/s41534-023-00760-2.

Just as in unitary synthesis, circuit decompositions of Clifford operations more efficient than the general analytical expressions can be obtained case-by-case using search and optimisation. The pendant to the provably optimal decompositions of unitaries obtained through brute force search Amy, 2013M. Amy, D. Maslov, M. Mosca and M. Roetteler. 2013. A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 32, 6 (June 2013, 818--830). doi: 10.1109/TCAD.2013.2244643 also exists for Clifford circuits Kliuch., 2013Vadym Kliuchnikov and Dmitri Maslov. 2013. Optimization of Clifford circuits. Physical Review A 88, 5 (November 2013, 052307). doi: 10.1103/physreva.88.052307. Due to the more efficient representation and smaller search space, all optimal Clifford circuits could be found up to 6 qubits. Using modern SAT solvers, optimal Clifford synthesis has recently been pushed much further, with known optimal circuits beyond 20 qubits Peham, 2023Tom Peham, Nina Brandl, Richard Kueng, Robert Wille and Lukas Burgholzer. 2023. Depth-Optimal Synthesis of Clifford Circuits with SAT Solvers. In IEEE International Conference on Quantum Computing and Engineering, QCE 2023, Bellevue, WA, USA, September 17-22, 2023. IEEE, 802--813. doi: 10.1109/QCE57702.2023.00095 Schnei., 2023Sarah Schneider, Lukas Burgholzer and Robert Wille. 2023. A SAT Encoding for Optimal Clifford Circuit Synthesis. In Proceedings of the 28th Asia and South Pacific Design Automation Conference, January 2023. IEEE. doi: 10.1145/3566097.3567929.

Heuristic optimisation approaches have also been shown to be effective on Clifford optimisation Bravyi, 2021Sergey Bravyi and Dmitri Maslov. 2021. Hadamard-Free Circuits Expose the Structure of the Clifford Group. IEEE Transactions on Information Theory 67, 7 (July 2021, 4546--4563). doi: 10.1109/TIT.2021.3081415 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 and scale to larger systems. For Clifford computations on devices with restricted connectivity, an architecture-aware synthesis method was proposed in Winderl, 2024David Winderl, Qunsheng Huang, Arianne Meijer-van de Griend and Richie Yeung. 2024. Architecture-Aware Synthesis of Stabilizer Circuits from Clifford Tableaus. arXiv: 2309.08972 [quant-ph].

Diagrammatic representations #

Quantum computer science and quantum mechanics have a rich history in diagrammatic representations Feynman, 1949R. P. Feynman. 1949. Space-Time Approach to Quantum Electrodynamics. Physical Review 76, 6 (Septempter 1949, 769--789). doi: 10.1103/physrev.76.769 Coecke, 2017Bob Coecke and Aleks Kissinger. 2017. Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning. Cambridge University Press. doi: 10.1017/9781316219317 Backens, 2019Miriam Backens and Aleks Kissinger. 2019. ZH: A Complete Graphical Calculus for Quantum Computations Involving Classical Non-linearity. Electronic Proceedings in Theoretical Computer Science 287 (January 2019, 23--42). doi: 10.4204/EPTCS.287.2. These have allowed one to picture complex physical processes as intuitive operations in a graphical language and have – as a nice side effect – led to a plethora of state-of-the-art quantum circuit optimisation techniques!

A diagrammatic representation of quantum computation is obtained by lifting the gates that form a quantum circuit into the nodes of a more abstract graph-based graphical calculus. The most commonly used flavour of calculus for circuit optimisation is the ZX calculus Coecke, 2008Bob Coecke and Ross Duncan. 2008. Interacting Quantum Observables Coecke, 2012Bob Coecke, Ross Duncan, Aleks Kissinger and Quanlong Wang. 2012. Strong Complementarity and Non-locality in Categorical Quantum Mechanics. In 2012 27th Annual IEEE Symposium on Logic in Computer Science, June 2012. IEEE, 245--254. doi: 10.1109/lics.2012.35 Weteri., 2020John van de Wetering. 2020. ZX-calculus for the working quantum computer scientist. arXiv: 2012.13966 [quant-ph] Yeung, 2024Richie Yeung, Konstantinos Meichanetzidis, Alexandre Krajenbrink and François Charton. 2024. Teaching small transformers to rewrite ZX diagrams. MathAI submission.

By breaking up multi-qubit gates into several non-unitary tensors, the ZX calculus and related variants Roy, 2011Shibdas Roy, Dipankar Home, Guruprasad Kar and Archan S. Majumda. 2011. Towards Normal Forms for GHZ∕W Calculus. In AIP Conference Proceedings. AIP, 112--119. doi: 10.1063/1.3635852 Backens, 2019Miriam Backens and Aleks Kissinger. 2019. ZH: A Complete Graphical Calculus for Quantum Computations Involving Classical Non-linearity. Electronic Proceedings in Theoretical Computer Science 287 (January 2019, 23--42). doi: 10.4204/EPTCS.287.2 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 expose some of the symmetry and structure of quantum physics in the form of simple and intuitive graphical rules. This has enabled the discovery of many quantum optimisation techniques (e.g. Duncan, 2019Ross Duncan, Aleks Kissinger, Simon Perdrix and John van de Wetering. 2019. Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus. arXiv: 1902.03178 [quant-ph] Weteri., 2024John van de Wetering, Richie Yeung, Tuomas Laakkonen and Aleks Kissinger. 2024. Optimal compilation of parametrised quantum circuits. arXiv: 2401.12877 [quant-ph]), some of which we have already reviewed Huang, 2024Qunsheng Huang, David Winderl, Arianne Meijer-van de Griend and Richie Yeung. 2024. Redefining Lexicographical Ordering: Optimizing Pauli String Decompositions for Quantum Compiling. CoRR abs/2408.00354. doi: 10.48550/ARXIV.2408.00354 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 Griend, 2022Arianne Meijer-van de Griend and Ross Duncan. 2022. Architecture-Aware Synthesis of Phase Polynomials for NISQ Devices. In Proceedings 19th International Conference on Quantum Physics and Logic, QPL 2022, Wolfson College, Oxford, UK, 27 June - 1 July 2022, 116--140. doi: 10.4204/EPTCS.394.8 Cowtan, 2019Alexander Cowtan, Silas Dilkes, Ross Duncan, Will Simmons and Seyon Sivarajah. 2019. Phase Gadget Synthesis for Shallow Circuits. In Proceedings 16th International Conference on Quantum Physics and Logic, QPL 2019, Chapman University, Orange, CA, USA, June 10-14, 2019, 213--228. doi: 10.4204/EPTCS.318.13 Cowtan, 2020Alexander Cowtan, Will Simmons and Ross Duncan. 2020. A Generic Compilation Strategy for the Unitary Coupled Cluster Ansatz. arXiv: 2007.10515 [quant-ph]. This selection of papers is not quite exhaustive⁵ – there are currently over 300 hundred papers on the topic, as indexed by zxcalculus.com.

Aside from being an invaluable tool for research and compiler pass design, a significant contribution of these diagrammatic representations is the introduction of graph transformation systems (GTS) Ehrig, 1973Hartmut Ehrig, Michael Pfender and Hans Jürgen Schneider. 1973. Graph-Grammars: An Algebraic Approach. In 14th Annual Symposium on Switching and Automata Theory, Iowa City, Iowa, USA, October 15-17, 1973. IEEE Computer Society, 167--180. doi: 10.1109/SWAT.1973.11 Rozenb., 1997Grzegorz Rozenberg. 1997. Handbook of Graph Grammars and Computing by Graph Transformations, Volume 1: Foundations. World Scientific König, 2018Barbara König, Dennis Nolte, Julia Padberg and Arend Rensink. 2018. A Tutorial on Graph Transformation. In Graph Transformation, Specifications, and Nets - In Memory of Hartmut Ehrig. Springer, 83--104. doi: 10.1007/978-3-319-75396-6_5 to quantum computing. More on this in chapter 3 (and much of the rest of this thesis)!

Reversible classical circuits #

Many more representations have either been taken over from classical compiler optimisations or were developed for specific purposes. The last we will mention is reversible circuit synthesis, an entirely classical circuit design problem which can draw from the results of decades of research. From a quantum perspective, reversible classical circuits correspond to unitaries (and more generally, isometries) that send basis states to basis states –  and thus do not introduce any complex phase Shende, 2002V.V. Shende, A.K. Prasad, I.L. Markov and J.P. Hayes. 2002. Reversible logic circuit synthesis. In IEEE/ACM International Conference on Computer Aided Design, 2002, November 2002. IEEE, 353--360. doi: 10.1109/iccad.2002.1167558. We highlight a selection of the more recent work in the field and refer the reader to the much more complete, albeit ageing, survey of Saeedi, 2013Mehdi Saeedi and Igor L. Markov. 2013. Synthesis and optimization of reversible circuits—a survey. ACM Computing Surveys 45, 2 (February 2013, 1--34). doi: 10.1145/2431211.2431220.

Up to 4 (qu)bits, all reversible circuits and their optimal synthesis can be generated by brute force Li, 2014Zhiqiang Li, Hanwu Chen, Xiaoyu Song and Marek Perkowski. 2014. A Synthesis Algorithm for 4-Bit Reversible Logic Circuits with Minimum Quantum Cost. ACM Journal on Emerging Technologies in Computing Systems 11, 3 (December 2014, 1--19). doi: 10.1145/2629542. Viewing reversible circuits as a permutation of all $2^n$ bitstrings, Susam et al. pre-compute optimal circuits only for swaps of two bitstrings (transpositions). These can then be used as part of a standard selection sort to synthesise arbitrary permutations. The number of such permutations scales much more favourably compared to arbitrary permutation, allowing fast circuit synthesis of up to 20+ (qu)bits in a fraction of a second, with good performance.

Truth table or matrix representations of reversible circuits suffer from the same exponential scaling as unitaries. To address these, other representations that have been used include exclusive sums of product terms (ESOP) Fazel, 2007K. Fazel, M. A. Thornton and J. E. Rice. 2007. ESOP-based Toffoli Gate Cascade Generation. In 2007 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, August 2007. IEEE. doi: 10.1109/pacrim.2007.4313212 Bandyo., 2014Chandan Bandyopadhyay, Hafizur Rahaman and Rolf Drechsler. 2014. A Cube Pairing Approach for Synthesis of ESOP-Based Reversible Circuit. In 2014 IEEE 44th International Symposium on Multiple-Valued Logic, May 2014. IEEE, 109--114. doi: 10.1109/ismvl.2014.27, positive polarity Reed-Müller codes (PPRM) Jegier, 2017Jerzy Jegier and Paweł Kerntopf. 2017. PPRM-based approach to synthesis of reversible functions. In Photonics Applications in Astronomy, Communications, Industry, and High Energy Physics Experiments 2017, August 2017. SPIE, 1044523. doi: 10.1117/12.2280943 and decision diagrams Stojko., 2019Suzana Stojković, Radomir Stanković, Claudio Moraga and Milena Stanković. 2019. Reversible Circuits Synthesis from Functional Decision Diagrams by using Node Dependency Matrices. Journal of Circuits, Systems and Computers 29, 05 (August 2019, 2050079). doi: 10.1142/s0218126620500796 Wille, 2010Robert Wille and Rolf Drechsler. 2010. Effect of BDD Optimization on Synthesis of Reversible and Quantum Logic. Electronic Notes in Theoretical Computer Science 253, 6 (March 2010, 57--70). doi: 10.1016/j.entcs.2010.02.006 Pang, 2011Yu Pang, Shaoquan Wang, Zhilong He, Jinzhao Lin, Sayeeda Sultana and Katarzyna Radecka. 2011. Positive Davio-based synthesis algorithm for reversible logic. In 2011 IEEE 29th International Conference on Computer Design (ICCD), October 2011. IEEE, 212--218. doi: 10.1109/iccd.2011.6081399.

The quantum framework is strictly more general than the classical regime in which the problem was studied initially. This affords additional freedom for decomposition schemes, such as decompositions of $\textit{CCX}$ gates on 3 qubits into single and two-qubit gates Shende, 2008Vivek V. Shende and Igor L. Markov. 2008. On the CNOT-cost of TOFFOLI gates. arXiv: 0803.2316 [quant-ph]. Various optimised decompositions for sequences of Toffoli gates have also been similarly developed Scott, 2008Nathan O. Scott and Gerhard W. Dueck. 2008. Pairwise decomposition of toffoli gates in a quantum circuit. In Proceedings of the 18th ACM Great Lakes symposium on VLSI, May 2008. ACM, 231--236. doi: 10.1145/1366110.1366168 Arabza., 2010Mona Arabzadeh, Mehdi Saeedi and Morteza Saheb Zamani. 2010. Rule-based optimization of reversible circuits. In 2010 15th Asia and South Pacific Design Automation Conference (ASP-DAC), January 2010. IEEE, 849--854. doi: 10.1109/aspdac.2010.5419684 Datta, 2013Kamalika Datta, Gaurav Rathi, Robert Wille, Indranil Sengupta, Hafizur Rahaman and Rolf Drechsler. 2013. Exploiting Negative Control Lines in the Optimization of Reversible Circuits Rahman, 2014Md Zamilur Rahman and Jacqueline E. Rice. 2014. Templates for Positive and Negative Control Toffoli Networks Datta, 2015Kamalika Datta, Indranil Sengupta and Hafizur Rahaman. 2015. A Post-Synthesis Optimization Technique for Reversible Circuits Exploiting Negative Control Lines. IEEE Transactions on Computers 64, 4 (April 2015, 1208--1214). doi: 10.1109/tc.2014.2315641 Arpita, 2015Pyreddy Mary Arpita, Kamalika Datta, Rohith Vemula and Indranil Sengupta. 2015. Optimization of reversible circuits using triple-gate templates at quantum gate level. In 2015 International Conference on Electronic Design, Computer Networks & Automated Verification (EDCAV), January 2015. IEEE, 120--124. doi: 10.1109/edcav.2015.7060551 Abdess., 2016Nabila Abdessaied, Matthew Amy, Mathias Soeken and Rolf Drechsler. 2016. Technology Mapping of Reversible Circuits to Clifford+T Quantum Circuits. In 2016 IEEE 46th International Symposium on Multiple-Valued Logic (ISMVL), May 2016. IEEE, 150--155. doi: 10.1109/ismvl.2016.33 Gado, 2021Mariam Gado and Ahmed Younes. 2021. Optimization of Reversible Circuits Using Toffoli Decompositions with Negative Controls. Symmetry 13, 6 (June 2021, 1025). doi: 10.3390/sym13061025. Mohammadi and Eshghi introduced 4-valued truth tables to extend classical circuit synthesis to include $\sqrt{X}$ (also known as $\mathit{V}$) gates Mohamm., 2008Majid Mohammadi and Mohammad Eshghi. 2008. Behavioral description of quantum V and V+ gates to design quantum logic circuits. In 2008 5th International Multi-Conference on Systems, Signals and Devices, July 2008. IEEE, 1--5. doi: 10.1109/ssd.2008.4632850. References Soeken, 2012M. Soeken, Z. Sasanian, R. Wille, D. M. Miller and R. Drechsler. 2012. Optimizing the Mapping of Reversible Circuits to Four-Valued Quantum Gate Circuits. In 2012 IEEE 42nd International Symposium on Multiple-Valued Logic, May 2012. IEEE, 173--178. doi: 10.1109/ismvl.2012.64 as well as Rahman, 2012Md. Mazder Rahman, Gerhard W. Dueck and Anindita Banerjee. 2012. Optimization of Reversible Circuits Using Reconfigured Templates incorporated controlled-$\mathit{V}$ gates into template matching strategies and showed significant improvements in synthesised gate count . Finally, Maslov, 2016Dmitri Maslov. 2016. Advantages of using relative-phase Toffoli gates with an application to multiple control Toffoli optimization. Physical Review A 93, 2 (February 2016, 022311). doi: 10.1103/physreva.93.022311 proposed decomposing Toffolis only up to relative phase, introducing a lot of freedom in the quantum decompositions that are required compared to the traditional classical decompositions.

In summary, a variety of scalable representations – such as phase polynomials, Pauli gadgets, Clifford tableaus, diagrammatic calculi, and reversible circuits – have been developed to abstract computations and enable highly tailored optimisation methods. These approaches leverage the unique structure and symmetries of quantum computations, achieving significant reductions in circuit size, depth, and hardware-specific overheads. Techniques such as phase polynomial synthesis and Clifford tableau representations are widely applicable and are a cornerstone of modern quantum compilers Amy, 2019Matthew Amy. 2019. Formal methods in Quantum Circuit Design. PhD Thesis. University of Waterloo Meijer., 2025Arianne Meijer - van de Griend. 2025. A comparison of quantum compilers using a DAG-based or phase polynomial-based intermediate representation. Journal of Systems and Software 221 (March 2025, 112224). doi: 10.1016/j.jss.2024.112224. Meanwhile, diagrammatic calculi, such as the ZX calculus, provide a flexible and theoretically robust framework for optimisations, often revealing simplifications invisible in the traditional gate-based model.

2.3. Rise of hybrid quantum-classical computation

Quantum measurements #

We have, until now, skipped over a crucial part of the quantum computation process: the role of quantum measurements. Quantum data, in isolation, is inherently inaccessible to us and the broader macroscopic world. A result from a quantum computation is only of value if we can probe it and get some readout value that we can display to the user or return to whoever launched the quantum computation.

Quantum physics measurements fundamentally differ from our classical understanding of just “reading out” data that is already there. This is the famous Schrödinger’s cat thought experiment of quantum mechanics: what data is within the qubits remains undefined until a measurement is performed. The act of observation will transform the quantum data: looking inside the box will, at random, either kill the cat or spare it¹.

We thus need to add the measurement operation as a special case to our computer scientist’s model of quantum computing. Unlike purely quantum operations, measurements inherently involve interaction with the environment to produce a readout. Consequently, the no-delete and reversibility principles discussed earlier do not apply. Indeed, measurement is a lossy (and therefore irreversible) operation that projects the quantum state into one of a small subset of classical states. Which state the quantum state is projected into is non-deterministic. If one has access to an infinite supply of the same quantum state, then the whole state can be reconstructed by repeating measurements and analysing the distribution of outcomes². Given no-cloning, however, this is unlikely to be the case, and so the full quantum result is hardly ever known. Instead, we must rely on well-designed measurement schemes to extract useful information from our partial access to the quantum states.

We model measurement as an operation that takes one qubit and outputs one purely classical bit³. In the circuit formalism, measurements are often implicitly added at the end of every qubit. Suppose we wish to make them explicit or add them elsewhere in the computation. In that case, we must introduce a graphical representation for the classical bit of data the measurement produces. The field has adopted the double-wire for this, even though a “half” wire would arguably have been more appropriate to reflect the reduced information content relative to quantum wires. I present to you the measurement box:

Measurements as first-class citizens #

It is very tempting to our feeble classical brains – and admittedly, we just did it ourselves in the previous paragraphs – to view measurements as merely a readout operation, an auxiliary operation that we are forced to perform at the end of a computation for operative reasons. This could not be further from the truth! In many ways, measurements are just as powerful tools as any other quantum operation – if not more so!

One eye-opening perspective on this is the field of measurement-based quantum computing (MBQC). Raussendorf and Briegel showed indeed Rausse., 2001Robert Raussendorf and Hans J. Briegel. 2001. A One-Way Quantum Computer. Physical Review Letters 86, 22 (May 2001, 5188--5191). doi: 10.1103/PhysRevLett.86.5188 that arbitrary quantum computations can be reproduced in the MBQC framework using only some resource quantum states that can be prepared ahead of time and measurements! In other words, given entangled qubits, measurements are all you need to perform quantum operations.

We will not explore MBQC further in this chapter (nor in this thesis, for that matter). Instead, we will use this as a motivation to explore what we can achieve with measurements. We have so far spared you from any mathematical alphabet soup. As we start discussing more concrete constructions of quantum computations, some introductory linear algebra and conventions around notation will become unavoidable.

Dirac formalism. Quantum states are nearly unanimously written using kets: instead of referring to a quantum state as $\psi$, we write it wrapped in special brackets as $\ket{\psi}$. This notation is also used when referring to the $0$ and $1$ states of qubits, written $\ket{0}$ and $\ket{1}$.

Several states can be joined and considered together as one overall state. This is expressed using the tensor $\otimes$ symbol: $\ket{\psi_1} \otimes \ket{\psi_2}$ is the joint system of $\ket{\psi_1}$ and $\ket{\psi_2}$. When the states in question are all explicitly qubit states, we use the shorthand binary notation $\ket{0} \otimes \ket{1} \otimes \ket{0} = \ket{010}$.

We will introduce more notation along the way.

With this out of the way, let us look in more details at the first smart use of measurements: the block-encoding technique. Consider the following scenario: you would like to perform an operation $A$ on an arbitrary quantum state $\ket{\psi}$. Now, there are, unfortunately, many cases where implementing $A$ as a quantum circuit made of primitive gates that can be executed on hardware is very expensive⁴.

However, what we can always do is express $A$ as a matrix of dimensions $2^n \times 2^n$, where $n$ is the number of qubits in the state $\ket{\psi}$. Then, there is a neat trick that we can sometimes apply: instead of trying to execute $A$, we enlarge the matrix to a bigger $\tilde{A}$: $$\tilde{A} = \begin{pmatrix}A & G_1\\ G_2 & G_3 \end{pmatrix}$$

where $G_1, G_2$ and $G_3$ are “garbage” matrices that we do not care about, but should combine into a matrix $\tilde{A}$ that we know how to execute on a quantum computer. Quantum computations must be matrices with a row and column number that is a power of two; so at a minimum, $\tilde{A}$ must be of size $2^{n+1} \times 2^{n+1}$, i.e. be a computation on $n + 1$ qubits.

We restrict our considerations in the following to the case on $m = n + 1$ qubits – other cases are similar. We thus need to add a qubit to our $\ket\psi$ state to be able to pass it to our new operation. Such qubits that are added temporarily to facilitate a computation are a recurring feature in quantum computing and have thus earned themselves a name – ancilla qubits.

Let us take a look at the quantum states that result from executing $\tilde{A}$. If we add to $\ket \psi$ a $\ket 0$ ancilla state, our quantum operation acts as⁵

The expression $A \ket \psi$ means the operation $A$ applied to $\ket \psi$ – exactly the output state we are seeking. If we input the ancilla qubit in state $\ket 1$, we get garbage:

$$\tilde{A} (\ket 1 \otimes \ket \psi) = \ket 0 \otimes G_2 \ket \psi + \ket 1 \otimes G_3 \ket \psi.$$

So $\ket 0 \otimes \ket \psi$ is definitely the input state we are more interested in.

How can we recover $A$ from (3)? This is precisely what measurements do! When quantum states are expressed as sum of states, the terms of the sum form the possible measurement outcomes⁶. If we only measure a subset of the qubits, then the term corresponding to that measurement is isolated and all other terms disappear. Hence, if we measure the first qubit (that we introduced ourselves) in the zero state, then the remaining $n$ qubits will be precisely in the desired state $A \ket \psi.$ Success!

Using this “term isolating” property of measurements, known as state collapse, we can thus effect computations that would have been otherwise difficult or impossible to perform. There is however one important wrinkle that we cannot forget about: measurements are non-deterministic! We cannot assume that all measurements of the ancilla qubit will return the zero state. When $\ket 1$ is measured on the ancilla, the remaining qubits are left in the $G_1 \ket\psi$ state. The computation has thus failed, and the execution must be aborted and restarted. How often the block-encoding protocol that we have presented fails depends on the details of $A$ and the choices of $G_1, G_2$ and $G_3$ and is the main disadvantage of an otherwise very powerful quantum technique.

We will now explore two strategies to deal with “fails” in measurements. At the core of them is the idea of hybrid quantum-classical programs.

Who said quantum computers could not fix their mistakes #

Failed computations are an expensive mistake in quantum computing as the no-cloning theorem prevents us from keeping a “backup” of the initial state. The fact that failures are in fact unlucky measurement outputs makes matters worse, given that measurements are the only irreversible quantum operation. It is therefore impossible in general to recover from a “wrong” measurement.

There are, however, prominent cases in which the computation can be corrected based on the measurement outcome, thus yielding deterministic results. Recall equation (3) of the previous section: there is a computation $A$ on $n$ qubits, that can be probabilistically computed using $m = n + 1$ qubits using $\tilde{A}$:

$$\tilde{A} (\ket 0 \otimes \ket \psi) = \ket 0 \otimes (A\ket\psi) + \ket 1 \otimes (G\ket\psi),$$

for some “garbage” $G$. What if $G$ is a reversible operation, i.e. there is an operation $G^{-1}$ to undo $G$? Well then, we can still, at least in theory, recover $A\ket \psi$ by applying $A \circ G^{-1}$:

$$G \ket \psi \mapsto (A \circ G^{-1}) \circ G \ket \psi = A \ket \psi,$$

but only if 1 was measured on the ancilla qubit⁷!

This is the beginning of quantum-classical hybrid computing: we start by performing quantum operations followed by measurements, the outcomes of which dictate what further quantum operations must be applied. We define for this purpose a classically controlled gate: a quantum operation that is only executed if a certain classical bit (the condition) is set. This bit will typically be a value derived from a previous measurement: it could be as simple as the outcome that a previous measurement yield, or a function of multiple past outcomes that must be evaluated on classical hardware (e.g. a CPU).

Mixing classical and quantum operations is a sure way to bring the quantum circuit representation to its knees. We adopt the following representation, in which a quantum gate that has an additional classical bit wire attached to it represents a classically controlled operation that is only executed if the bit value is 1.

Quantum Teleportation #

Quantum teleportation is a simple example of performing classically controlled quantum operations to do circuit corrections based on measurement outcomes. It is also coincidentally one of the most fundamental protocols of quantum theory. Its name is slightly misleading. Think of it as data transfer for quantum data, with a mind-bending twist: at the time of the transfer, only classical data must be communicated between the sending and receiving parties. As a result of this protocol, quantum information can be transferred using plain old-school copper wires (or any other classical communication channels)!

This is predicated on one crucial action being performed before the start of the communication. For every qubit that should be transmitted, the parties must beforehand create and share among themselves a pair of qubits that will serve as the quantum resource during the protocol execution. This resource state is widespread enough that it got its name: the Bell pair state. It is written in Dirac notation as $\ket{00} + \ket{11}$. As the notation indicates, it is a state with perfectly correlated measurements: when measured, the two qubits will always yield the same outcome, either both 0 or both 1.

There turns out to be a straightforward circuit that maps the two-qubit $\ket {00}$, which every two-qubit computation starts in, into the Bell pair state:

It is enough for us to think of it as a black box – or a grey box in this case.

We are interested in “teleporting” an arbitrary, single-qubit quantum state. Such a state can always be expressed as $\ket \psi = \alpha \ket 0 + \beta \ket 1$, i.e. in the most general case, a one-qubit state will be in some superposition of the states $\ket 0$ and $\ket 1$. The paramenters $\alpha$ and $\beta$ are complex coefficients that encode the probabilities of measuring 0 or 1 – we can view them as the weights of a weighted sum.

We are now interested in combining a Bell resource state in a joint system with the arbitrary state $\ket \psi$. The resulting three-qubit state is obtained with the $\otimes$ operation, which distributes over sums just like usual multiplication:

We chose to place the Bell pair on the first two qubits and the arbitrary state on the third. The goal is to move the data that sits on that last qubit to the first qubit. Looking at the first qubit in the above expression, notice that the desired state $\ket \psi = \alpha \ket 0 + \beta \ket 1$ appears in the first qubit if we can discard the second and third terms:

$$\alpha \ket{\underline{\mathbf{0}}00} + {\color{gray}(\alpha \ket {110} + \beta \ket {001})} + \beta \ket{\underline{\mathbf{1}}11}$$

This sounds very much like the measurement operations we have used before to isolate terms – but we need to isolate two terms simultaneously. We can resolve this issue by reorganising the expression⁸

$$\begin{aligned}&\alpha \ket{000} + \alpha \ket{110} + \beta \ket {001} + \beta \ket {111}\\ =\ &\underbrace{(\alpha \ket 0 + \beta \ket 1)}_{= \ket \psi}\otimes \underbrace{( \ket {00} + \ket {11})}_{\text{Bell pair}}\\&+(\beta \ket 0 + \alpha \ket 1) \otimes (\ket {01} + \ket {10})\\&+(\alpha\ket 0 - \beta \ket 1) \otimes (\ket{01} - \ket {10})\\&+(\beta \ket 0 - \alpha \ket 1) \otimes (\ket {00} - \ket {11})\end{aligned}$$

Obtaining the $\ket \psi$ state on the first qubit is thus as simple as isolating the first of these four terms. We do not know a priori how to measure $\ket {00} + \ket{11}$ but we do know how to map that state to $\ket {00}$: that’s the inverse of the Bell pair state preparation circuit! This results in the following circuit:

This brings us to the same situation as we had for the block encoding application above: conditioned on the measurement outcome of the second and third qubits being 0, the computation performs a state “teleportation”, moving $\ket \psi$ from the third to the first qubit. We can compute the effect of $\textit{Bell}^{-1}$ on the overall expression of (4) to find all possible output states: $$\begin{aligned}\alpha \ket {000} + \alpha \ket {110} + \beta \ket {001} + \beta \ket {111} \overset{\textit{Bell}^{-1}}{\mapsto}&(\alpha \ket 0 + \beta \ket 1) \otimes \ket {00} \\&+ (\beta \ket 0 + \alpha \ket 1) \otimes \ket {01} \\& + (\alpha \ket 0 - \beta \ket 1) \otimes \ket {10} \\&+ (\beta \ket 0 - \alpha \ket 1) \otimes \ket {11}\end{aligned}$$

As expected, we do get $\ket \psi$ on the first qubit for the measurement 00 (corresponding to the state $\ket {00}$), but as it stands, this only has a $\frac{1}{4}$ probability of success.

You might notice, however, that the other states in which the first qubit can end up look remarkably similar, up to some sign flips and swaps $\ket 0 \leftrightarrow \ket 1$. In particular, all states still have the amplitudes $\alpha$ and $\beta$ somewhere, so it does not seem unfathomable that these “wrong” states can be mapped back to $\psi$.

We can use the measurement outcomes of the second and third qubit to infer which of the “mistakes” occurred, and hence what state the first qubit has ended in. The 01 measurement outcome, for instance, results in the $\beta \ket 0 + \alpha \ket 1$ state – this is just a bit flip away from $\ket \psi$! This gate is known as $X$. Its colleague the $Z$ gate on the other hand leaves $\ket 0$ states untouched but flips the sign of $\ket 1.$ This would fix the 10 outcome. Finally, 11 requires both a Z and a X correction.

Putting these observations together, we can leverage classically controlled operations to obtain a fully deterministic protocol! The correct circuit implementing quantum teleportation is given by

In the scenario where a first party (Alice) wants to send a one-qubit quantum state to Bob, they can achieve that by creating a Bell pair state, the first qubit of which is given to Bob and the second to Alice. When Alice then gets in possession of another qubit $\ket \psi$ whose data she wants to transmit to Bob, she can achieve that by executing $\textit{Bell}^{-1}$, measuring her two qubits and communicating the (classical) measurement outcomes to Bob. Bob can perform the necessary corrections and will then have state $\ket \psi$.

It is beautiful and often overlooked how one of the most fundamental protocols of quantum information theory is, in fact, a hybrid classical-quantum computation. Quantum teleportation without classical communication is physically impossible: it would let Alice communicate with Bob instantly, even though he could be light years away – in other words, it would fundamentally break relativity.

Repeat until success: If you fail, retry! #

Classical computer science has a straightforward solution whenever probabilistic computations that can fail are used: probability amplification or boosting Scheid., 2018Christian Scheideler. 2018. Probability amplification. Retrieved lecture notes, online, visited 30/12/2024 from https://cs.uni-paderborn.de/fileadmin-eim/informatik/fg/ti/Lehre/SS_2018/AA/lecture_5.pdf. The idea is so simple that it barely deserves a name: execute several independent runs of the computation and choose the most common outcome. If the probability of failure is below a certain threshold (e.g. 50% for a binary output), then with basic statistics, one can extrapolate the number of runs required to obtain any desired accuracy⁹.

We have been ignoring this approach so far since no-cloning prohibits us from repeating a procedure more than once on an input state $\ket\psi$. However, in the scenario that the computation should only be executed on a specific, known input state and the computation that prepares that state is known, we can recover from computation failures by just preparing a new state identically.

Suppose we know how to execute the quantum computation $P$ mapping $$\ket{0\cdots 0} \mapsto P \ket {0\cdots0} = \ket \psi.$$

As before, we would like to compute $A$ given an implementation of the computation $\tilde{A}$ that acts on a $n$-qubit state $\ket\psi$ and an ancilla qubit in the $\ket 0$ state. If the measurement of $\tilde{A}(\ket 0 \otimes \ket \psi)$ returns 1, then the computation failed. We can then discard all qubits and restart from the $\ket 0$ state, applying $P$ followed by $\tilde{A}$ and an ancilla measurement, repeating until we measure 0. As a pseudo-quantum circuit, we could express this as:

psi_qs = create_qubits(n)
while True:
   ancilla_q = create_qubit()
   obtain measurement m from:



    if m == 0:
        break  # success! we can exit loop and proceed
    else:
        reset_qubits(psi_qs)

At each iteration, we can either exit the loop if the state collapse was successful (m == 0), or reset the qubits to zero and try again. But pseudo circuits do not run on hardware! The only way to express this computation as an actual circuit is to unroll the loop, i.e. repeat the block within the loop as many times as we expect might be necessary¹⁰. The first two iterations would look as follows:

It should be obvious why we haven’t unrolled the loop any further – it quickly becomes unweildy. The resulting program is not only hard to display and read, but it also suffers from fundamental issues in practice. For one, the program size becomes hugely bloated, and beyond slowing down the compiler, it will also cause a host of issues on the control hardware in real-time, such as long load times, inefficient execution, and low cache efficiency.

Even more worryingly, when picking the maximum number of iterations, we face an impossible tradeoff: if the number of iterations is small, then the probability of failure will remain non-negligible. As we scale this value up, however, we are introducing more and more gates into the program to cover the odd case of multiple successive repeated failures. We do not intend to execute these gates on most computation runs. They come at a significant cost to the runtime. For each gate listed in the circuit, the condition for the gate’s execution must be checked, whether or not the gate ends up being executed. Furthermore, hardware schedulers might be forced to be pessimistic and schedule a time window for all conditional operations ahead of time. This will significantly delay any operation to be performed after the loop.

We, therefore, argue that the quantum circuit model is ill-suited as the representation for quantum programs that combine classical and quantum data. Such programs, however, are a fundamental building block towards developing meaningful large-scale quantum computations and are bound to become the norm. Beyond the examples discussed above—–including block-encodings, repeat-until-success schemes, distributed quantum computing and measurement-based quantum computing – one application of hybrid quantum-classical operations stands out as critically important for the large-scale deployment of quantum computing: quantum error correction (QEC) schemes. We discuss this use case in the next section.

2.4. Quantum compilers cannot do it alone

We have (hopefully!) by now convinced our readership that quantum programs must interface with our established classical infrastructure and should rather be understood as an interleaved execution of both classical and quantum operations. The obvious question that thus poses itself is

How do we equip quantum compilers to deal with classical operations?

The simplest solution is to adopt the extended quantum circuit formalism with support for classically controlled operations, as we have introduced in the previous section. Using this representation, the basic types available for computation are the qubit and the classical bit. We can also, at that point, introduce purely classical operations on bits, for instance, to compute boolean logic on measurement outcomes, such as “if both the first AND the second measurement outcomes are 1, then …”.

However, the circuit model is inherently designed with the no-cloning principle in mind: specifically, with the assumption that at any one time, there are exactly $n$ (for some fixed value of $n$) resources available for computation. This for example means that in the following program

in which two measurements write to the same classical bit, it would be impossible to append a gate controlled on the first measurement outcome after the $Z$ gate, as that value was overwritten on the classical wire by the second measurement. The solution could be to introduce¹ a new, fresh classical wire for each measurement and avoid overwriting outcomes. However, there are also many other ways to break this wires-based representation: suppose you have an operation with one input and two outputs, such as a copy operation $x \mapsto (x,x)$. We would need two wires for the output, but the input would only provide us with one… We now have to start creating additional wires ahead of time for this purpose and solve memory allocation problems to decide which wire should be given to which operation.

These are run-of-the-mill classical compiler problems! One might at first hope that the set of overlapping problems between classical and quantum compilers is manageably small. After all, in all the use cases we have covered so far, the amount of classical computation was very minimal, limiting itself to conditionals and loops based on simple boolean expressions. Surely the full-blown powers of a classical compiler are not required!

Unfortunately (and as usual), scientists have shown no lack of imagination in this field – and so have found very compelling use cases for complex classical computations within quantum programs. To drive this point home, let us consider the concrete example of quantum error correction.

The quantum error correction use case #

Error-correcting protocols do as their name suggests: they detect whenever data is subjected to errors and thus modified in an unexpected way. They then attempt to recover the intended valid state. In the classical world, such schemes are employed whenever the hardware is not reliable enough: this is hardly the case for computations themselves but is widespread in communications (e.g. within the TCP/IP protocol for the internet Eddy, 2022Wesley Eddy. 2022. Transmission Control Protocol (TCP). (August 2022). Retrieved as RFC 9293 from https://www.rfc-editor.org/info/rfc9293) or for memory and storage in critical applications.

No one expects to be able to manipulate matter-based qubits without introducing errors for a very long time. Photons, on the other hand, are prone to data losses throuh absorption and can only be entangled using complex and noisy schemes such as the Knill–Laflamme–Milburn protocol 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². Simply put, it is safe to assume that error correction will be found everywhere – as soon as our quantum computers manage to implement such protocols.

A sketch of quantum error correction goes roughly as follows: the data that would be stored on $k$ qubits is instead encoded in a redundant way on a larger number $n > k$ of qubits. Thus, when errors occur on a subset of the $n$ qubits, the data can be restored using the qubits that have not been corrupted. Before errors can be corrected, they must be detected. To this end, we first add fresh ancilla qubits to the program. Through smartly designed interactions with the data qubits, the ancilla qubits pick up the errors from the data. When we subsequently perform measurements on the ancilla qubits, these errors result in modified outcomes, called the error syndrome.

The challenging bit comes next: from a run of syndrome measurements, one must infer the most likely errors – a step known as syndrome decoding. This is a purely classical maximum likelihood problem that requires a non-trivial amount of computations to resolve. For small problem instances, all possible input syndromes can be tabled, and the outputs precomputed – in which case the problem at runtime is reduced to fast table lookups. However, the higher the fault tolerance we require, the more qubits must be used in the encodings, and so invariably, the problem quickly becomes very demanding computationally.

Meanwhile, these “cycles” of error detection and correction are under strict latency constraints: idling qubits waiting for corrections to be applied will accumulate new errors that must themselves be corrected – for error correction to be workable, we must be capable of detecting and correcting for errors faster than they are being introduced. The entire error correction cycle just described can be summarised by the following diagram:

The decoding time is a crucial factor in determining the overall cycle time and, thus, the clock rate of fault-tolerant quantum hardware. Consider, for example, a 32-qubit Toric code Kitaev, 2003A.Yu. Kitaev. 2003. Fault-tolerant quantum computation by anyons. Annals of Physics 303, 1 (January 2003, 2--30). doi: 10.1016/S0003-4916(02)00018-0, one of the most well-studied quantum error-correcting codes. Without going into the details of the code itself, we can use the C++ implementation made available by the MQT toolkit Burgho., 2021Lukas Burgholzer and Robert Wille. 2021. Advanced Equivalence Checking for Quantum Circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 40, 9 (Septempter 2021, 1810--1824). doi: 10.1109/tcad.2020.3032630 to study the decoder performance for this code.

Consider first a “naive” compilation of the decoder – the kind of program that we could hope to get from a quantum compiler that “understands” classical operations but only implements optimisations directly relevant to quantum computations. Such a compiler does not currently exist, but the decoder being a C++ program, we can approximate what the compiled binary would look like by turning off all optimisations from an established classical compiler³.

The runtime averaged over 1000 runs of the decoder is $0.73\pm0.06\,ms$. This is within the latency requirements of certain trapped ion architectures Ryan-A., 2021C. Ryan-Anderson, J. G. Bohnet, K. Lee, D. Gresh, A. Hankin, J. P. Gaebler, D. Francois, A. Chernoguzov, D. Lucchetti, N. C. Brown, T. M. Gatterman, S. K. Halit, K. Gilmore, J. A. Gerber, B. Neyenhuis, D. Hayes and R. P. Stutz. 2021. Realization of Real-Time Fault-Tolerant Quantum Error Correction. Physical Review X 11, 4 (December 2021, 041058). doi: 10.1103/physrevx.11.041058, but far beyond the sub-microsecond regime that will be required to make error correction a reality on superconduction-based quantum computers Carrer., 2024Almudena Carrera Vazquez, Caroline Tornow, Diego Ristè, Stefan Woerner, Maika Takita and Daniel J. Egger. 2024. Combining quantum processors with real-time classical communication. Nature 636, 8041 (November 2024, 75--79). doi: 10.1038/s41586-024-08178-2. this can be contrasted with the program output by the same compiler, but with all compiler optimisations enabled: the average runtime is reduced by a factor close to 10x to $0.078\pm0.004\,ms$ – still a factor 100x away from the required performance on superconductors, but huge gains nonetheless! The details of the experiment with all build flags, the hardware used and how to reproduce the results are available here.

There is no hope of obtaining these types of speedups without an in-depth understanding of classical hardware and battle-tested implementations for every optimisation pass under the sun – in short, the full thrust of a modern state-of-the-art compiler such as clang or gcc.

To make matters worse, such classical computations are bound to move to dedicated accelerators that require specialised compilation, such as GPUs and FPGAs, for the most time-critical subroutines: quantum error decoding using GPUs is already well-developed Bausch, 2024Johannes Bausch, Andrew W. Senior, Francisco J. H. Heras, Thomas Edlich, Alex Davies, Michael Newman, Cody Jones, Kevin Satzinger, Murphy Yuezhen Niu, Sam Blackwell, George Holland, Dvir Kafri, Juan Atalaya, Craig Gidney, Demis Hassabis, Sergio Boixo, Hartmut Neven and Pushmeet Kohli. 2024. Learning high-accuracy error decoding for quantum processors. Nature 635, 8040 (November 2024, 834--840). doi: 10.1038/s41586-024-08148-8 Cao, 2023Hanyan Cao, Feng Pan, Yijia Wang and Pan Zhang. 2023. qecGPT: decoding Quantum Error-correcting Codes with Generative Pre-trained Transformers. arXiv: 2307.09025 [quant-ph] and more esoteric platforms FPGAs Overwa., 2022Ramon W. J. Overwater, Masoud Babaie and Fabio Sebastiano. 2022. Neural-Network Decoders for Quantum Error Correction Using Surface Codes: A Space Exploration of the Hardware Cost-Performance Tradeoffs. IEEE Transactions on Quantum Engineering 3 (1--19). doi: 10.1109/tqe.2022.3174017 Meinerz, 2022Kai Meinerz, Chae-Yeun Park and Simon Trebst. 2022. Scalable Neural Decoder for Topological Surface Codes. Physical Review Letters 128, 8 (February 2022, 080505). doi: 10.1103/physrevlett.128.080505, superconducting circuits Ueno, 2021Yosuke Ueno, Masaaki Kondo, Masamitsu Tanaka, Yasunari Suzuki and Yutaka Tabuchi. 2021. QECOOL: On-Line Quantum Error Correction with a Superconducting Decoder for Surface Code. In 2021 58th ACM/IEEE Design Automation Conference (DAC), December 2021. IEEE, 451--456. doi: 10.1109/dac18074.2021.9586326 and compute-in-memory architectures Wang, 2024Hao Wang, Erjia Xiao, Songhuan He, Zhongyi Ni, Lingfeng Zhang, Xiaokun Zhan, Yifei Cui, Jinguo Liu, Cheng Wang, Zhongrui Wang and Renjing Xu. 2024. CIM-Based Parallel Fully FFNN Surface Code High-Level Decoder for Quantum Error Correction. arXiv: 2411.18090 [cs.AR] are being actively studied.

These observations should leave the reader convinced that in order to compile and realise the kind of hybrid quantum-classical programs that we expect will become the norm in the field, quantum compilers will need to embrace and encompass the full breadth and depth of classical compilers. This leaves us with no choice but to fully transform and integrate the existing quantum tooling and quantum optimisation research into the established compiler ecosystem. What this means exactly is the subject of the rest of this chapter.

A new quantum programming paradigm? #

We have seen it – quantum circuits are very limited in their expressiveness. They are well suited to presenting sequences of purely quantum operations and how the computation is parallelised across qubits, but they quickly become limiting once both quantum and classical data types are mixed and any type of control flow (conditionals, loops, function calls, etc.) is introduced.

How users express programs in the front end has deep implications for the kind of computations that the compiler must be capable of reasoning about and, hence, for the compiler’s architecture. The great merging of classical and quantum compilers is the perfect opportunity to reconcile program representations and integrate the learnings from decades of classical programming language research into quantum computing.

There have been several trailblazing initiatives to formalise quantum programming and create dedicated languages, such as QCL Ömer, 2000Bernhard Ömer. 2000. Quantum Programming in QCL. (January 2000). Retrieved from http://tph.tuwien.ac.at/ oemer/doc/quprog.pdf, Quipper Green, 2013Alexander S. Green, Peter LeFanu Lumsdaine, Neil J. Ross, Peter Selinger and Benoît Valiron. 2013. Quipper: a scalable quantum programming language. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, June 2013, New York, NY, USA. Association for Computing Machinery, 333--342. doi: 10.1145/2491956.2462177 Rios, 2018Francisco Rios and Peter Selinger. 2018. A Categorical Model for a Quantum Circuit Description Language (Extended Abstract). Electronic Proceedings in Theoretical Computer Science 266 (February 2018, 164--178). doi: 10.4204/eptcs.266.11 Fu, 2023Peng Fu, Kohei Kishida, Neil J. Ross and Peter Selinger. 2023. Proto-Quipper with Dynamic Lifting. Proceedings of the ACM on Programming Languages 7, POPL (January 2023, 309--334). doi: 10.1145/3571204, Q# Micros., 2024 Microsoft. 2024. Introduction to the quantum programming language Q#. Retrieved on 31/12/2024 from https://learn.microsoft.com/en-us/azure/quantum/qsharp-overview and Silq Bichsel, 2020Benjamin Bichsel, Maximilian Baader, Timon Gehr and Martin Vechev. 2020. Silq: a high-level quantum language with safe uncomputation and intuitive semantics. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, June 2020. ACM, 286--300. doi: 10.1145/3385412.3386007. Their adoption in the quantum ecosystem have so far remained limited, overshadowed by the popularity of python-based APIs for quantum circuit-based representations, as offered by Qiskit Javadi., 2024Ali Javadi-Abhari, Matthew Treinish, Kevin Krsulich, Christopher J. Wood, Jake Lishman, Julien Gacon, Simon Martiel, Paul D. Nation, Lev S. Bishop, Andrew W. Cross, Blake R. Johnson and Jay M. Gambetta. 2024. Quantum computing with Qiskit. arXiv: 2405.08810 [quant-ph], Pennylane Bergho., 2022Ville Bergholm, Josh Izaac, Maria Schuld, Christian Gogolin, Shahnawaz Ahmed, Vishnu Ajith, M. Sohaib Alam, Guillermo Alonso-Linaje, B. AkashNarayanan, Ali Asadi, Juan Miguel Arrazola, Utkarsh Azad, Sam Banning, Carsten Blank, Thomas R Bromley, Benjamin A. Cordier, Jack Ceroni, Alain Delgado, Olivia Di Matteo, Amintor Dusko, Tanya Garg, Diego Guala, Anthony Hayes, Ryan Hill, Aroosa Ijaz, Theodor Isacsson, David Ittah, Soran Jahangiri, Prateek Jain, Edward Jiang, Ankit Khandelwal, Korbinian Kottmann, Robert A. Lang, Christina Lee, Thomas Loke, Angus Lowe, Keri McKiernan, Johannes Jakob Meyer, J. A. Montañez-Barrera, Romain Moyard, Zeyue Niu, Lee James O'Riordan, Steven Oud, Ashish Panigrahi, Chae-Yeun Park, Daniel Polatajko, Nicolás Quesada, Chase Roberts, Nahum Sá, Isidor Schoch, Borun Shi, Shuli Shu, Sukin Sim, Arshpreet Singh, Ingrid Strandberg, Jay Soni, Antal Száva, Slimane Thabet, Rodrigo A. Vargas-Hernández, Trevor Vincent, Nicola Vitucci, Maurice Weber, David Wierichs, Roeland Wiersema, Moritz Willmann, Vincent Wong, Shaoming Zhang and Nathan Killoran. 2022. PennyLane: Automatic differentiation of hybrid quantum-classical computations. arXiv: 1811.04968 [quant-ph] and Cirq Cirq D., 2024 Cirq Developers. 2024. Cirq. There is, as a result, a justified dose of scepticism in the quantum community on how well the ideas from classical programming really translate to quantum.

It is thus all the more notable that we are seeing a new generation of quantum programming tooling being developed Koch, 2024Mark Koch, Alan Lawrence, Kartik Singhal, Seyon Sivarajah and Ross Duncan. 2024. GUPPY: Pythonic Quantum-Classical Programming. (January 2024). Retrieved (talk recording) from https://www.youtube.com/live/D8esZrt7ogk?feature=shared&t=31448 Ittah, 2024David Ittah, Ali Asadi, Erick Ochoa Lopez, Sergei Mironov, Samuel Banning, Romain Moyard, Mai Jacob Peng and Josh Izaac. 2024. Catalyst: a Python JIT compiler for auto-differentiable hybrid quantum programs. Journal of Open Source Software 9, 99 (July 2024, 6720). doi: 10.21105/joss.06720 CUDA-Q., 2024 CUDA-Q Developers. 2024. CUDA-Q Documentation. Retrieved on 31/12/24 from https://nvidia.github.io/cuda-quantum/latest/index.html, driven by the need to write more expressive programs for the improving hardware (as we have been discussing), as well as for performance reasons, to scale quantum compilation to large scale 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, accelerate quantum simulations Ittah, 2024David Ittah, Ali Asadi, Erick Ochoa Lopez, Sergei Mironov, Samuel Banning, Romain Moyard, Mai Jacob Peng and Josh Izaac. 2024. Catalyst: a Python JIT compiler for auto-differentiable hybrid quantum programs. Journal of Open Source Software 9, 99 (July 2024, 6720). doi: 10.21105/joss.06720 and integrate with classical high-performance computing (HPC) NVIDIA, 2024 NVIDIA. 2024. NVIDIA Accelerates Quantum Computing Centers Worldwide With CUDA-Q Platform. Retrieved on 31/12/2024 from https://investor.nvidia.com/news/press-release-details/2024/NVIDIA-Accelerates-Quantum-Computing-Centers-Worldwide-With-CUDA-Q-Platform/default.aspx.

The history of programming is, first and foremost, a masterclass in constructing abstractions. Many of the higher-level primitives, that have proven invaluable classically, solve problems that we expect to encounter very soon in our hybrid programs – when we have not already. Examples include

• structured control flow to simplify reasoning about branching in quantum-classical hybrid programs,
• type systems to encode program logic and catch errors at compile time – this is particularly important for quantum programs as there is no graceful way of handling runtime errors on quantum hardware: by the time the error has been propagated to the caller, all quantum data stored on qubits is probably corrupted and lost,
• memory management such as reference counting and data ownership models. Current hardware follows a static memory model, in which the number of available qubits is fixed, and every operation acts on a set of qubits assigned at compile time. This becomes impossible to keep track of in instances such as qubit allocations within loops with an unknown number of iterations at compile time. It thus becomes necessary to manage qubits dynamically, just like classical memory.

To facilitate such a large swath of abstractions, the first step quantum compilers must take is to make a distinction between the language frontend and the intermediate representation (IR) that the compiler uses to reason about the program and perform optimisations. This will be the topic of chapter 3. The graph-based IR that we introduce in that chapter will then form the foundation for the new quantum compilation techniques that will be developed throughout the remainder of the thesis.

2.5. Summary and further reading

This introductory chapter covered some of the basic principles of quantum computation and, in doing so, hopefully, made a convincing argument as to why we should expect the programs running on quantum hardware to become more complex in the future, with the intertwining of classical and quantum computations – processes we refer to as hybrid quantum-classical programs. Prior to that, we also presented quantum compilation, an emerging discipline that is introducing many new problems and ideas to the established corpus of work on compiler research.

If this quantum taster has intrigued you or you would like to learn the basics from people who actually know what they are talking about, nothing beats the reference book for quantum information and quantum computing by Nielsen and Chuang Nielsen, 2016Michael A. Nielsen and Isaac L. Chuang. 2016. Quantum Computation and Quantum Information (10th Anniversary edition). Cambridge University Press. A fascinating alternative perspective on quantum theory has also been developed within the programme of categorical quantum mechanics, for which the illustrious “Dodo book” Coecke, 2017Bob Coecke and Aleks Kissinger. 2017. Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning. Cambridge University Press. doi: 10.1017/9781316219317 would be the go-to introductory material¹.

At the risk of turning this thesis into absolutely shameless Oxford self-promotion, guess what else was a product of this university’s world-class research? The quantum circuit itself! These diagrams came from theoretical physicists (no surprise here) interested in capturing thought experiments in quantum information theory Deutsch, 1989David Deutsch. 1989. Quantum Computational Networks. In Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences. Royal Society, 73--90.

The idea caught on, and soon, software tools were created to facilitate building such diagrams. The Quantum Computation Language (QCL) was one of the first Ömer, 2000Bernhard Ömer. 2000. Quantum Programming in QCL. (January 2000). Retrieved from http://tph.tuwien.ac.at/ oemer/doc/quprog.pdf. Quantum software² has since proliferated, especially as the possibility of actually performing these thought experiments on quantum hardware became more tangible. The result were software packages for quantum computing, designed for the automatic transformation and optimisation of quantum computations for execution on real hardware Javadi., 2024Ali Javadi-Abhari, Matthew Treinish, Kevin Krsulich, Christopher J. Wood, Jake Lishman, Julien Gacon, Simon Martiel, Paul D. Nation, Lev S. Bishop, Andrew W. Cross, Blake R. Johnson and Jay M. Gambetta. 2024. Quantum computing with Qiskit. arXiv: 2405.08810 [quant-ph] Cirq D., 2024 Cirq Developers. 2024. Cirq Steiger, 2018Damian S. Steiger, Thomas Häner and Matthias Troyer. 2018. ProjectQ: an open source software framework for quantum computing. Quantum 2 (January 2018, 49). doi: 10.22331/q-2018-01-31-49 Sivara., 2020Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington and Ross Duncan. 2020. t|ket⟩: a retargetable compiler for NISQ devices. Quantum Science and Technology 6, 1 (November 2020, 014003). doi: 10.1088/2058-9565/ab8e92​ – we called them quantum compilers.

A recent development for quantum compilers focuses on scalability and first-class support for hybrid quantum-classical computations. Quantum circuits that include some form of classical control have been variously called “dynamic circuits” (e.g. Córco., 2021A. D. Córcoles, Maika Takita, Ken Inoue, Scott Lekuch, Zlatko K. Minev, Jerry M. Chow and Jay M. Gambetta. 2021. Exploiting Dynamic Quantum Circuits in a Quantum Algorithm with Superconducting Qubits. Physical Review Letters 127, 10 (August 2021, 100501). doi: 10.1103/physrevlett.127.100501), “adaptive circuits” (e.g. Smith, 2024Kevin C. Smith, Abid Khan, Bryan K. Clark, S.M. Girvin and Tzu-Chieh Wei. 2024. Constant-Depth Preparation of Matrix Product States with Adaptive Quantum Circuits. PRX Quantum 5, 3 (Septempter 2024, 030344). doi: 10.1103/prxquantum.5.030344), “circuits with measurements and feedforward” (e.g. Graham, 2023T. M. Graham, L. Phuttitarn, R. Chinnarasu, Y. Song, C. Poole, K. Jooya, J. Scott, A. Scott, P. Eichler and M. Saffman. 2023. Midcircuit Measurements on a Single-Species Neutral Alkali Atom Quantum Processor. Physical Review X 13, 4 (December 2023, 041051). doi: 10.1103/physrevx.13.041051), and “circuits assisted by local operations and classical communication” (e.g. Piroli, 2021Lorenzo Piroli, Georgios Styliaris and J. Ignacio Cirac. 2021. Quantum Circuits Assisted by Local Operations and Classical Communication: Transformations and Phases of Matter. Physical Review Letters 127, 22 (November 2021, 220503). doi: 10.1103/physrevlett.127.220503).

Besides supporting advances in quantum hardware Córco., 2021A. D. Córcoles, Maika Takita, Ken Inoue, Scott Lekuch, Zlatko K. Minev, Jerry M. Chow and Jay M. Gambetta. 2021. Exploiting Dynamic Quantum Circuits in a Quantum Algorithm with Superconducting Qubits. Physical Review Letters 127, 10 (August 2021, 100501). doi: 10.1103/physrevlett.127.100501 Graham, 2023T. M. Graham, L. Phuttitarn, R. Chinnarasu, Y. Song, C. Poole, K. Jooya, J. Scott, A. Scott, P. Eichler and M. Saffman. 2023. Midcircuit Measurements on a Single-Species Neutral Alkali Atom Quantum Processor. Physical Review X 13, 4 (December 2023, 041051). doi: 10.1103/physrevx.13.041051 Pino, 2021J. M. Pino, J. M. Dreiling, C. Figgatt, J. P. Gaebler, S. A. Moses, M. S. Allman, C. H. Baldwin, M. Foss-Feig, D. Hayes, K. Mayer, C. Ryan-Anderson and B. Neyenhuis. 2021. Demonstration of the trapped-ion quantum CCD computer architecture. Nature 592, 7853 (April 2021, 209--213). doi: 10.1038/s41586-021-03318-4, hybrid classical-quantum computations are central to many quantum computing applications. As put recently by Alam and Clark Alam, 2024Faisal Alam and Bryan K. Clark. 2024. Learning dynamic quantum circuits for efficient state preparation. arXiv: 2410.09030 [quant-ph]​:

“[…] dynamic quantum circuits are a crucial milestone on the roadmap to fault-tolerant quantum computers.”

We have covered a small subset of applications of hybrid quantum-classical computations. Quantum teleportation is undoubtedly one of the oldest Bennett, 1993Charles H. Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres and William K. Wootters. 1993. Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels. Physical Review Letters 70, 13 (March 1993, 1895--1899). doi: 10.1103/physrevlett.70.1895. The block-encoding technique that we discussed in section 2.3 is the foundation of several algorithms, including the Quantum Singular Value Decomposition (QSVT) Gilyén, 2019András Gilyén, Yuan Su, Guang Hao Low and Nathan Wiebe. 2019. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, June 2019. ACM, 193--204. doi: 10.1145/3313276.3316366 and the Linear Combination of Unitaries (LCU) Chakra., 2024Shantanav Chakraborty. 2024. Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers. Quantum 8 (October 2024, 1496). doi: 10.22331/q-2024-10-10-1496 Sze, 2025Michelle Wynne Sze, Yao Tang, Silas Dilkes, David Muñoz Ramo, Ross Duncan and Nathan Fitzpatrick. 2025. Hamiltonian dynamics simulation using linear combination of unitaries on an ion trap quantum computer. arXiv: 2501.18515 [quant-ph]. Measurement-based quantum computing (MBQC) was introduced in Rausse., 2001Robert Raussendorf and Hans J. Briegel. 2001. A One-Way Quantum Computer. Physical Review Letters 86, 22 (May 2001, 5188--5191). doi: 10.1103/PhysRevLett.86.5188 and is forming the base for some photonic quantum computing architectures Bartol., 2023Sara Bartolucci, Patrick Birchall, Hector Bombín, Hugo Cable, Chris Dawson, Mercedes Gimeno-Segovia, Eric Johnston, Konrad Kieling, Naomi Nickerson, Mihir Pant, Fernando Pastawski, Terry Rudolph and Chris Sparrow. 2023. Fusion-based quantum computation. Nature Communications 14, 1 (February 2023). doi: 10.1038/s41467-023-36493-1 Bouras., 2021J. Eli Bourassa, Rafael N. Alexander, Michael Vasmer, Ashlesha Patil, Ilan Tzitrin, Takaya Matsuura, Daiqin Su, Ben Q. Baragiola, Saikat Guha, Guillaume Dauphinais, Krishna K. Sabapathy, Nicolas C. Menicucci and Ish Dhand. 2021. Blueprint for a Scalable Photonic Fault-Tolerant Quantum Computer. Quantum 5 (February 2021, 392). doi: 10.22331/q-2021-02-04-392. Hybrid programs have also been shown to be useful for implementing the Quantum Fourier Transform (QFT) Bäumer, 2024Elisa Bäumer, Vinay Tripathi, Alireza Seif, Daniel Lidar and Derek S. Wang. 2024. Quantum Fourier Transform Using Dynamic Circuits. Physical Review Letters 133, 15 (October 2024, 150602). doi: 10.1103/physrevlett.133.150602 and the Quantum Phase Estimation (QPE) algorithms Córco., 2021A. D. Córcoles, Maika Takita, Ken Inoue, Scott Lekuch, Zlatko K. Minev, Jerry M. Chow and Jay M. Gambetta. 2021. Exploiting Dynamic Quantum Circuits in a Quantum Algorithm with Superconducting Qubits. Physical Review Letters 127, 10 (August 2021, 100501). doi: 10.1103/physrevlett.127.100501, two of the most fundamental computation primitives for quantum algorithms.

On the other hand, repeat until success schemes Paetzn., 2014Adam Paetznick and Krysta M. Svore. 2014. Repeat-until-success: non-deterministic decomposition of single-qubit unitaries. Quantum Information & Computation 14, 15–16 (November 2014, 1277–1301) are widespread in state preparation routines and will play a key role in fault-tolerant (FT) quantum computing. Arguably, the most well-known scheme for FT is magic state distillation Bravyi, 2005Sergey Bravyi and Alexei Kitaev. 2005. Universal quantum computation with ideal Clifford gates and noisy ancillas. Physical Review A 71, 2 (February 2005, 022316). doi: 10.1103/PhysRevA.71.022316, a procedure expected to be a core building block of many FT architectures. State preparation is generally a ubiquitous problem for FT, as the error-correcting codes that are employed initiate computations starting from a logical zero state, which may be expensive to prepare on the qubits of the hardware Fowler, 2012Austin G. Fowler, Matteo Mariantoni, John M. Martinis and Andrew N. Cleland. 2012. Surface codes: Towards practical large-scale quantum computation. Physical Review A 86, 3 (Septempter 2012, 032324). doi: 10.1103/physreva.86.032324.

Finally, quantum error-correcting (QEC) codes themselves must be implemented using hybrid programs. The quantum error correction (QEC) literature is vast and can get very technical very quickly, but diving into it promises bountiful rewards. The field is one of quantum information’s fastest-evolving areas of research. These work-in-progress lecture notes Gottes., 2024Daniel Gottesman. 2024. Surviving as a Quantum Computer in a Classical World. (February 2024). Retrieved on 08/01/2025 (lecture notes) from https://www.cs.umd.edu/class/spring2024/cmsc858G/QECCbook-2024-ch1-15.pdf by a coryphaeus of the field make for excellent introductory material.

Chapter 3

Quantum Compilation as a Graph Transformation Problem

The specialised optimisation techniques that we reviewed in section 2.2 are effective for the scenarios they were designed for, but they are challenging to adapt to new hardware primitives, constraints, or cost functions.

This thesis proposes interpreting quantum compilation as a graph transformation system (GTS). GTSs endow quantum compilation with well-defined semantics and strong theoretical foundations Lack, 2005Stephen Lack and Pawel Sobocinski. 2005. Adhesive and quasiadhesive categories. RAIRO - Theoretical Informatics and Applications 39, 3 (July 2005, 511--545). doi: 10.1051/ITA:2005028. They establish a practical, purely declarative framework in which compiler transformations can be defined and studied.

This allows us to decouple the semantics of quantum programs and the architecture specifics from the compiler infrastructure itself. We can thus focus on building and designing scalable and efficient graph transformation algorithms that can then be applied on a wide range of compilation problems and hardware targets.

In this chapter, we formalise quantum computation and optimisation based on graphs and graph transformations, providing the foundation for all considerations in later chapters. Albeit slightly simplified, the intermediate representation IR we propose here is based on 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, as well as ongoing development.

The words graph rewrite and graph transformation are often used interchangeably in the literature. In the context of this thesis, we will take these words to distinguish two slightly different problems:

The study of equivalences and other relations between graphs under well-defined semantics is the subject of graph transformations. For instance:

• a graph transformation rule $L \to R$ (Definition .) expresses that an instance of $L$ can always be transformed into an instance of $R$, reflecting the semantics of the system that the graph is modelling.
• a minIR equivalence class (Definition .) is an instance of a graph transformation system (GTS), which uses known semantic relations, expressed, for example, as graph transformation rules, to define how graphs can be transformed.

Graph rewriting, on the other hand, encapsulates the algorithmic procedures and data structures that mutate graphs. A rewrite (Definition 3.9) is the tuple of data required to turn a graph $G$ into a new graph $G'$.

Given matches of patterns $L$ on a graph $G$, a graph transformation system can consider the set of graph transformation rules that define the semantics of $G$ to produce a set of rewrites that can be applied to $G$ and mutate $G$.

Our contributions in the subsequent chapters are mostly preoccupied with problems of graph rewriting, i.e. the definition and application of the data required to mutate graphs, as opposed to graph transformations. This chapter nonetheless considers both, using the mature graph transformation framework as a foundation to define IR rewriting semantics.

Section 3.1 starts with a review of previous related work at the intersection of graph transformation software and quantum program optimisation. We then discuss in section 3.2 a fundamental difference between classical computation graphs and the requirements of quantum computation. This motivates a new graph-based IR tailored to quantum computation that we present in section 3.3, along with formal graph rewriting semantics based on sesqui-pushout (SqPO) transformations (section 3.4). Whilst the SqPO transformation definition is constructive, its existence is not guaranteed. We conclude the chapter in section 3.5 by discussing a more restricted “operational” notion of graph rewriting that will be useful for the rest of the thesis.

3.1. Related work

Graph rewriting on computation graphs.  Optimisation of computation graphs is a long-standing problem in computer science that is seeing renewed interest in the compiler Lattner, 2021Chris Lattner, Mehdi Amini, Uday Bondhugula, Albert Cohen, Andy Davis, Jacques Pienaar, River Riddle, Tatiana Shpeisman, Nicolas Vasilache and Oleksandr Zinenko. 2021. MLIR: Scaling Compiler Infrastructure for Domain Specific Computation. In 2021 IEEE/ACM International Symposium on Code Generation and Optimization (CGO), February 2021. IEEE, 2--14. doi: 10.1109/CGO51591.2021.9370308, machine learning (ML) Jia, 2019Zhihao Jia, Oded Padon, James Thomas, Todd Warszawski, Matei Zaharia and Alex Aiken. 2019. TASO: optimizing deep learning computation with automatic generation of graph substitutions. In Proceedings of the 27th ACM Symposium on Operating Systems Principles, October 2019. ACM, 47--62. doi: 10.1145/3341301.3359630 Fang, 2020Jingzhi Fang, Yanyan Shen, Yue Wang and Lei Chen. 2020. Optimizing DNN computation graph using graph substitutions. Proceedings of the VLDB Endowment 13, 12 (August 2020, 2734--2746). doi: 10.14778/3407790.3407857 and quantum computing communities 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 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. In all these domains, graphs encode computations that are either expensive to execute or evaluated repeatedly over many iterations, making the optimisation of the execution cost of the computation a primary concern.

Domain-specific heuristics are the most common approach in compiler optimisations Paszke, 2019Adam Paszke, Sam Gross, Francisco Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kö pf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai and S. Chintala. 2019. PyTorch: An Imperative Style, High-Performance Deep Learning Library. In Neural Information Processing Systems. doi: 10.5555/3454287.3455008 Sivara., 2020Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington and Ross Duncan. 2020. t|ket⟩: a retargetable compiler for NISQ devices. Quantum Science and Technology 6, 1 (November 2020, 014003). doi: 10.1088/2058-9565/ab8e92​ – a more flexible alternative are optimisation engines based on declarative sets of graph transformations Bonchi, 2022Filippo Bonchi, Fabio Gadducci, Aleks Kissinger, Pawel Sobocinski and Fabio Zanasi. 2022. String Diagram Rewrite Theory I: Rewriting with Frobenius Structure. Journal of the ACM 69, 2 (March 2022, 1 - 58). doi: 10.1145/3502719 Bonchi, 2022Filippo Bonchi, Fabio Gadducci, Aleks Kissinger, Pawel Sobocinski and Fabio Zanasi. 2022. String diagram rewrite theory II: Rewriting with symmetric monoidal structure. Mathematical Structures in Computer Science 32, 4 (April 2022, 511--541). doi: 10.1017/s0960129522000317. In such systems, a graph transformation system (GTS) is used to find a sequence of allowed transformations that rewrite a computation graph given as input into a computation graph with minimal cost.

Transformation systems were first studied on strings Dersho., 1990Nachum Dershowitz and Jean-Pierre Jouannaud. 1990. Rewrite Systems, then generalised to trees and terms Bezem, 2003Marc Bezem, Jan Willem Klop and Roel Vrijer. 2003. Term Rewriting Systems (1. publ. ed.). Cambridge University Press, Cambridge, before being applied to graph domains Ehrig, 1973Hartmut Ehrig, Michael Pfender and Hans Jürgen Schneider. 1973. Graph-Grammars: An Algebraic Approach. In 14th Annual Symposium on Switching and Automata Theory, Iowa City, Iowa, USA, October 15-17, 1973. IEEE Computer Society, 167--180. doi: 10.1109/SWAT.1973.11 Rozenb., 1997Grzegorz Rozenberg. 1997. Handbook of Graph Grammars and Computing by Graph Transformations, Volume 1: Foundations. World Scientific König, 2018Barbara König, Dennis Nolte, Julia Padberg and Arend Rensink. 2018. A Tutorial on Graph Transformation. In Graph Transformation, Specifications, and Nets - In Memory of Hartmut Ehrig. Springer, 83--104. doi: 10.1007/978-3-319-75396-6_5. Their use in quantum computing is part of a long tradition of diagrammatic reasoning in physics Penrose, 1964Roger Penrose. 1964. Conformal treatment of infinity. General Relativity and Gravitation 43, 3 (901--922 (reprint)). doi: 10.1007/s10714-010-1110-5 Feynman, 1949R. P. Feynman. 1949. Space-Time Approach to Quantum Electrodynamics. Physical Review 76, 6 (Septempter 1949, 769--789). doi: 10.1103/physrev.76.769, and particularly in quantum mechanics with the advent of categorical quantum mechanics Abrams., 2008Samson Abramsky and Bob Coecke. 2008. Categorical quantum mechanics. arXiv: 0808.1023 [quant-ph] Coecke, 2012Bob Coecke, Ross Duncan, Aleks Kissinger and Quanlong Wang. 2012. Strong Complementarity and Non-locality in Categorical Quantum Mechanics. In 2012 27th Annual IEEE Symposium on Logic in Computer Science, June 2012. IEEE, 245--254. doi: 10.1109/lics.2012.35 Coecke, 2017Bob Coecke and Aleks Kissinger. 2017. Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning. Cambridge University Press. doi: 10.1017/9781316219317.