### A graph representation for quantum programs

←Return to chapter

## 3.3. A graph representation for quantum programs

For the purposes of this thesis, we introduce a simplified graph-based IR for quantum computations that we will call minIR. It captures all the expressiveness that we require for hybrid programs whilst remaining sufficiently abstract to be applicable to a variety of IRs and, by extension, quantum programming languages and compiler frameworks.

MinIR can be thought of as being built from statements of the form

    x, y, ... := op(a, b, c, ...)

to be understood as an operation `op` applied on the SSA values `a, b, c, ...` and producing the output values `x, y, ...`.

Computation and dataflow graphs are commonly defined with operations as vertices and values as edges. To faithfully capture the function signature of `op`, this requires storing and preserving an ordering of the incoming and outgoing edges (also known as port graphs Ferná., 2018Maribel Fernández, Hélène Kirchner and Bruno Pinaud. 2018. Labelled Port Graph – A Formal Structure for Models and Computations. Electronic Notes in Theoretical Computer Science 338 (October 2018, 3--21). doi: 10.1016/j.entcs.2018.10.002).

Instead, we adopt the hypergraph formalisation of computation graphs, which is more common within category theory (see string diagrams Seling., 2010P. Selinger. 2010. A Survey of Graphical Languages for Monoidal Categories and their formalisation in the hypergraph category 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 Wilson, 2022Paul Wilson and Fabio Zanasi. 2022. The Cost of Compositionality: A High-Performance Implementation of String Diagram Composition. Electronic Proceedings in Theoretical Computer Science 372 (November 2022, 262--275). doi: 10.4204/eptcs.372.19). This definition is particularly well-suited for our purposes because it frames the graph transformations of interest to us in the well-studied language of rewriting within adhesive categories Lack, 2004Stephen Lack and Paweł Sobociński. 2004. Adhesive Categories. In Foundations of Software Science and Computation Structures, Berlin, Heidelberg. Springer Berlin Heidelberg, 273--288. doi: 10.1007/978-3-540-24727-2_20.

### Hypergraphs and minIR #

At a minimum, a directed hypergraph – for simplicity sometimes in the following referred to simply as graph – is defined by a set of vertices V\mathbf V V and a set of (hyper) edges E\mathbf EE. We will always consider hypergraphs where the edges e∈E e \in \mathbf Ee∈E are directed and the vertices attached to e ee are given by ordered lists. We formalise this incidence relation between vertices in V\mathbf V V and edges in E\mathbf EE by writing E\mathbf EE as the partition over the disjoint sets E s t\mathbf E_{st}E st​

E=⨆s, t∈N E s t\mathbf E = \bigsqcup_{s, t \in \mathbb{N}} \mathbf E_{st}E=s,t∈N⨆​E st​

and introducing s ss source and t tt target maps for each E s t\mathbf E_{st}E st​. Why we write sets in boldface will become clear in a moment.

Definition 3.1Directed hypergraph

A directed hypergraph is given by sets V\mathbf V V and E s t\mathbf E_{st}E st​ for s, t∈N s, t \in\mathbb{N}s, t∈N, along with maps

src s t, i: E s t→V for 1⩽i⩽s tgt s t, j: E s t→V for 1⩽j⩽t \begin{aligned} \textit{src}_{st,i}&: \mathbf E_{st} \to \mathbf V\quad&\textrm{for } 1 \leqslant i \leqslant s\\ \textit{tgt}_{st,j}&: \mathbf E_{st} \to \mathbf V&\textrm{for } 1 \leqslant j \leqslant t\\ \end{aligned} src st,i​tgt st, j​​:E st​→V: E st​→V​for 1⩽i⩽s for 1⩽j⩽t​

for all s, t∈N s, t \in \mathbb{N}s, t∈N.

Note that in this thesis, as in most common uses of hypergraphs, the sets V\mathbf V V and E=⨆E s t\mathbf E = \bigsqcup \mathbf E_{st}E=⨆E st​ will always be finite, and thus E s t≠∅\mathbf E_{st} \neq \varnothingE st​=∅ for a finite number of s, t∈N s, t \in \mathbb{N}s, t∈N only.

For simplicity, we can further omit the s t stst subscript of the source src s t, i\textit{src}_{st,i}src st,i​ and target tgt s t, j\textit{tgt}_{st,j}tgt st, j​ maps whenever it can be inferred from the domain of definition of the map. For e∈E s t e \in \mathbf{E}_{st}e∈E st​, we call src 1(e),…,src s(e)∈V\textit{src}_{1}(e), \dots, \textit{src}_{s}(e) \in \mathbf{V}src 1​(e),…,src s​(e)∈V the s ss source vertices of e ee and tgt 1(e),…,tgt t(e)∈V\textit{tgt}_{1}(e), \dots, \textit{tgt}_{t}(e) \in \mathbf{V}tgt 1​(e),…,tgt t​(e)∈V the t tt target vertices of e ee.

We introduce the notation u⇝v u \leadsto vu⇝v to signify that there is an edge from u uu to v v v, i.e. there is e∈E s t e \in \mathbf E_{st}e∈E st​ for some s, t∈N s, t \in \mathbb Ns, t∈N and 1⩽i⩽s, 1⩽j⩽t 1 \leqslant i \leqslant s, 1 \leqslant j \leqslant t1⩽i⩽s, 1⩽j⩽t such that u=s r c i(e)u = src_i(e)u=sr c i​(e) and v=t g t j(e)v = tgt_j(e)v=t g t j​(e). We define the equivalence relation ∼⊆V 2\sim \subseteq \mathbf V^2∼⊆V 2 of connected vertices, given by the transitive, symmetric and reflexive closure of ⇝\leadsto⇝. The equivalence classes of ∼\sim∼ are the connected components of the graph. We will write [v][v][v], resp. [e][e][e] for the connected component that contains the vertex v v v, resp. the edge e ee.

To proceed, it is useful to frame the hypergraph definition in a categorical setting. We write [C, S e t][\mathbb{C}, \mathrm{Set}][C, Set] for the presheaf topos of the category C\mathbb{C}C, i.e. the category with functors C→S e t\mathbb{C} \to \mathrm{Set}C→Set as objects and natural transformations as morphisms. Definition 3.1 can be equivalently restated as:

> hypergraphs are objects in the presheaf topos H=[C, S e t]\mathbb H = [\mathbb{C}, \mathrm{Set}]H=[C, Set],

where the category C\mathbb{C}C has objects V V V and E s t E_{st}E st​ for s, t∈N s, t \in \mathbb{N}s, t∈N and arrows given by (1), now interpreted as morphisms in C\mathbb{C}C rather than as functions in S e t\mathrm{Set}Set. In this framing, a graph is a functor that defines a set for each object of C\mathbb{C}C and specifies functions between these sets – one for each arrow in C\mathbb{C}C.

This is where the distinction between bold and non-bold typeface comes from: we use bold letters to refer to images in S e t\mathrm{Set}Set of a hypergraph functor, whereas the non-bold typeface is refers to objects in the indexing category C\mathbb CC. The distinction between C\mathbb CC and S e t\mathrm{Set}Set is less important for morphisms – it will typically be clear from the context. We thus use the same symbols for both.

#### Linearity constraints #

The introduction of H\mathbb HH not only gives us a notion of hypergraph homomorphisms – maps between hypergraphs that preserve the structure of the graph. It also provides us with a way to express the linearity constraints that arise from our discussion in section 3.2, and which we must enforce on our computation graphs.

The definition that follows adds the coproduct E E E explicitly as an object of the category (which we did not need to do in Definition 3.1), as we need it as the codomain of the new morphisms use\textit{use}use and def\textit{def}def. The adhesitivity of the category does no longer comes for free – we will get back to this in section 3.4.

Definition 3.2Hypergraph with linearity constraints

The category lin-C\textrm{lin-}\mathbb{C}lin-C is the category given by objects {V, V src, V tgt}∪{E}∪{E s t ∣ s, t∈N}.\{V, V_\textit{src}, V_\textit{tgt}\} \cup \{ E \} \cup \{ E_{st}\, |\, s, t \in \mathbb{N}\}.{V, V src​,V tgt​}∪{E}∪{E st​∣s, t∈N}. Its arrows are the incidence morphisms given in (1), along with

u s e: V src→E d e f: V tgt→E λ s r c: V src↣V λ t g t: V tgt↣V \begin{aligned} \mathit{use}&: V_\textit{src} \to E\quad& \mathit{def}&: V_\textit{tgt} \to E\\ \lambda_\mathit{src}&: V_\textit{src} \rightarrowtail V& \lambda_\mathit{tgt}&: V_\textit{tgt} \rightarrowtail V\\ \end{aligned} use λ src​​:V src​→E: V src​↣V​def λ tgt​​:V tgt​→E: V tgt​↣V​

and ι s t: E s t↣E\iota_{st}: E_{st} \rightarrowtail Eι st​:E st​↣E for all s, t∈N s, t \in \mathbb{N}s, t∈N. The morphisms λ s r c, λ t g t, ι s t\lambda_\mathit{src}, \lambda_\mathit{tgt}, \iota_{st}λ src​,λ tgt​,ι st​ are split monomorphisms and the following diagrams commute for all s, t∈N s, t \in \mathbb{N}s, t∈N and 1⩽i⩽s, 1⩽j⩽t 1 \leqslant i \leqslant s, 1 \leqslant j \leqslant t1⩽i⩽s, 1⩽j⩽t:

Directed hypergraphs with linearity conditions are objects in the full subcategory lin-H\textrm{lin-}\mathbb Hlin-H given by objects H l i n∈[lin-C, S e t]H_\mathrm{lin} \in [\textrm{lin-}\mathbb{C}, \mathrm{Set}]H lin​∈[lin-C, Set] such that E=⨆E s t\mathbf E = \bigsqcup \mathbf E_{st}E=⨆E st​ is the coproduct in S e t\mathrm{Set}Set and H l i n(ι s t):H l i n(E s t)→H l i n(E)H_\mathrm{lin}(\iota_{st}): H_\mathrm{lin}(E_{st}) \to H_\mathrm{lin}(E)H lin​(ι st​):H lin​(E st​)→H lin​(E) are the injections into H l i n(E)H_\mathrm{lin}(E)H lin​(E).

We probably owe an explanation for this definition – at least for the sake of the few computer scientists that are still following us.

First of all, notice that every hypergraph with linearity constraint corresponds to a hypergraph in the sense of Definition 3.1: there is an obvious functor L: C→lin-C\mathcal{L}: \mathbb{C} \to \textrm{lin-}\mathbb{C}L: C→lin-C that maps each object and morphism in C\mathbb{C}C to the object or morphism with the same name in lin-C\textrm{lin-}\mathbb{C}lin-C. By contravariance, we can thus (functorially) map every hypergraph with linearity constraints H l i n∈lin-H H_\mathrm{lin} \in \textrm{lin-}\mathbb{H}H lin​∈lin-H to the hypergraph H=H l i n∘L∈H H = H_\mathrm{lin} \circ \mathcal{L} \in \mathbb{H}H=H lin​∘L∈H.

Another way of looking at this is to realise that by requiring that λ s r c, λ t g t\lambda_\mathit{src}, \lambda_\mathit{tgt}λ src​,λ tgt​ be split monomorphisms, we obtain that the resulting functions in S e t\mathrm{Set}Set are injective. Up to isomorphism, we can consider that V src, V tgt⊆V\mathbf{V}_\textit{src}, \mathbf{V}_\textit{tgt} \subseteq \mathbf{V}V src​,V tgt​⊆V are subsets of vertices in H l i n H_\mathrm{lin}H lin​. A hypergraph with linearity constraints is thus a directed hypergraph with two selected subsets of vertices V src\mathbf{V}_\textit{src}V src​ and V tgt\mathbf{V}_\textit{tgt}V tgt​.

Vertices within these subsets are special. For every v∈V src v \in \mathbf{V}_\textit{src}v∈V src​, there exist unique indices s, t∈N s, t \in \mathbb{N}s, t∈N, 1≤i≤s 1 \leq i \leq s1≤i≤s and edge u s e(v)=e∈E s t use(v) = e \in \mathbf{E}_{st}use(v)=e∈E st​ such that src i(e)=v\textit{src}_i(e) = vsrc i​(e)=v. In words, for every v∈V src v\in \mathbf{V}_\textit{src}v∈V src​ there is a unique edge in the hypergraph that has v v v as one of its sources. We then say that e ee is the unique use of vertex v v v. Similarly, vertices in V tgt\mathbf{V}_\textit{tgt}V tgt​ have a unique edge e ee in the hypergraph with v v v as one of its targets – it is the unique definition of v v v.

#### Typed graphs #

MinIR graphs are strongly typed. We introduce typed graphs for this purpose, a concept for which graph transformation was first formalised in Ehrig, 2004Hartmut Ehrig, Ulrike Prange and Gabriele Taentzer. 2004. Fundamental Theory for Typed Attributed Graph Transformation. In Graph Transformations, Berlin, Heidelberg. Springer Berlin Heidelberg, 161--177. doi: 10.1007/978-3-540-30203-2_13. A type system for directed hypergraphs is just another object Σ∈H\Sigma \in \mathbb HΣ∈H. A typed graph is then an object of the slice category H↘Σ\mathbb H \searrow \SigmaH↘Σ, that is to say, typed graphs are morphisms H→Σ H \to \Sigma H→Σ of H\mathbb{H}H and morphisms between typed graphs are given by the subset of morphisms H 1→H 2 H_1 \rightarrow H_2 H 1​→H 2​ of H\mathbb HH that make the triangle diagram formed by H 1 H_1 H 1​, H 2 H_2 H 2​ and Σ\SigmaΣ commute.

To type hypergraphs with linearity constraints, we do not pick the type system Σ\SigmaΣ in lin-H\textrm{lin-}\mathbb Hlin-H, as the existence of u s e useuse and d e f defde f morphisms impose restrictions that are too strict. We consider instead the category lin-C type\textrm{lin-}\mathbb C_\textrm{type}lin-C type​ given by the same objects as lin-C\textrm{lin-}\mathbb Clin-C, as well as the same morphisms, with the omission of u s e useuse and d e f defde f. There is an obvious functor lin-C type→lin-C\textrm{lin-}\mathbb C_\textrm{type} \to \textrm{lin-}\mathbb Clin-C type​→lin-C and thus, by contravariance, every hypergraph with linearity constraints H lin∈lin-H H_\textrm{lin} \in \textrm{lin-}\mathbb H H lin​∈lin-H can be mapped to a hypergraph in lin-H type\textrm{lin-}\mathbb H_\textrm{type}lin-H type​. We say that a hypergraph with linearity constraints H lin∈lin-H H_\textrm{lin} \in \textrm{lin-}\mathbb H H lin​∈lin-H is Σ\SigmaΣ-typed for a type system Σ∈lin-H type\Sigma \in \textrm{lin-}\mathbb H_\textrm{type}Σ∈lin-H type​ if there is a morphism Σ→H lin\Sigma \to H_\textrm{lin}Σ→H lin​, when interpreting H lin H_\textrm{lin}H lin​ is as an object of lin-H type\textrm{lin-}\mathbb H_\textrm{type}lin-H type​.

Two example hypergraphs. Vertices (labelled with capital letters) are circles and hyperedges (labelled with small letters) span between them. Vertices that are attached to an edge in the black half of the circle correspond to source vertices of the edge; those in the white half correspond to target vertices. The functions s r c i src_i sr c i​ and t g t j tgt_jt g t j​ map edges to the incident vertices, defining the directed hypergraph. On the left, there are further functions use\textit{use}use and def\textit{def}def that map vertices to the unique edge that uses or defines them. This defines a hypergraph with linearity constraints, with V tgt={A 1, A 2}V_\textit{tgt} = \{A_1, A_2\}V tgt​={A 1​,A 2​} and V src={A 3}V_\textit{src} = \{A_3\}V src​={A 3​}. These cannot be defined on the graph on the right. On the other hand, the edges `b` and `c` are in F 11 F_{11}F 11​, and are in the domain of functions i n 11 in_{11}in 11​ and o u t 11 out_{11}out 11​, thus defining a child region of a hierarchical graph. Note that it would be invalid to have any edge connecting i 1 i_1i 1​ or o 1 o_1o 1​ to i 2 i_2i 2​ or o 2 o_2o 2​. The i ii and o oo vertices also have incidence morphisms, not displayed here.

#### Hierarchical hypergraphs #

A final bit of structure that minIR graphs require is a notion of hierarchy between regions of the graph. This will be useful to define functions, control flow blocks such as `if-else`, or any subroutine that can itself be viewed as an operation in the computation.

Hierarchical hypergraphs were first proposed in Drewes, 2002Frank Drewes, Berthold Hoffmann and Detlef Plump. 2002. Hierarchical Graph Transformation. Journal of Computer and System Sciences 64, 2 (March 2002, 249--283). doi: 10.1006/jcss.2001.1790 and further generalised in Busatto, 2005Giorgio Busatto, Hans-Jörg Kreowski and Sabine Kuske. 2005. Abstract hierarchical graph transformation. Mathematical Structures in Computer Science 15, 4 (July 2005, 773--819). doi: 10.1017/s0960129505004846 Palacz, 2004Wojciech Palacz. 2004. Algebraic hierarchical graph transformation. Journal of Computer and System Sciences 68, 3 (May 2004, 497--520). doi: 10.1016/s0022-0000(03)00064-3. However, we opt to use a more restrictive definition, closer to the notion of flattened hypergraphs of Drewes, 2002Frank Drewes, Berthold Hoffmann and Detlef Plump. 2002. Hierarchical Graph Transformation. Journal of Computer and System Sciences 64, 2 (March 2002, 249--283). doi: 10.1006/jcss.2001.1790. The reason for this is twofold. Firstly, hierarchical (hyper)graphs are typically defined recursively. It is not obvious under which conditions (and if) such definitions form adhesive categories, although progess in this direction was made in Padberg, 2017Julia Padberg. 2017. Hierarchical Graph Transformation Revisited: Transformations of Coalgebraic Graphs. In Graph Transformation, Cham. Springer International Publishing, 20--35. doi: 10.1007/978-3-319-61470-0_2 with the introduction of coalgebraic graphs. As a result, to the extent that graph transformation results can be applied to such structures, it must be done so carefully.

The second, more practical, reason is that the notion of typed graph introduced above cannot be directly lifted to the hierarchical graph setting: while some subset of the hierarchical relation in minIR should be enforced by the type system, the type graph of a nested graph should be identical to the parent’s (as opposed to being itself nested within the type graph of the parent).

It is therefore more convenient for us to encode hierarchy in directed hypergraphs as follows. Note that it is not clear that our definition is adhesive either1 – but at least it is framed as a subcategory of a base category that is.

Definition 3.3Hierarchical hypergraph

The category hier-C\textrm{hier-}\mathbb Chier-C is the category with objects and arrows of C\mathbb CC along with additional objects F s t F_{st}F st​ for s, t∈N s, t \in \mathbb{N}s, t∈N and arrows:

- F s t↣E s t F_{st} \rightarrowtail E_{st}F st​↣E st​ that are split monomorphisms,
- input arrows F s t→i n s t E 0 s F_{st} \xrightarrow{in_{st}} E_{0s}F st​in st​
  ​E 0s​, and output arrows F s t→o u t s t E t 0 F_{st} \xrightarrow{out_{st}} E_{t0}F st​out st​
  ​E t0​.

Hierarchical hypergraph are the objects in the full subcategory hier-H\textrm{hier-}\mathbb Hhier-H given by objects H hier∈[hier-C, S e t]H_\textrm{hier} \in [\textrm{hier-}\mathbb{C}, \mathrm{Set}]H hier​∈[hier-C, Set] such that

- for any edge e∈E e \in \mathbf{E}e∈E of H hier H_\textrm{hier}H hier​, the set P([e])=i n‾−1([e])∪o u t‾−1([e])P([e]) = \overline{in}^{-1}([e]) \cup \overline{out}^{-1}([e])P([e])=in−1([e])∪out−1([e]) has at most one element.
- the transitive and reflexive closure of [e]≼[P([e])][e] \preccurlyeq [P([e])][e]≼[P([e])] for e∈E e \in \mathbf Ee∈E is a partial order on the connected components of H hier H_\textrm{hier}H hier​.

Here i n‾\overline{in}in and o u t‾\overline{out}out are the functions with domain E\mathbf EE defined piecewise as i n s t in_{st}in st​ and o u t s t out_{st}out st​ for all s, t s, ts, t on their respective (disjoint) domains of definition.

The same definition can also be applied to lin-H\textrm{lin-}\mathbb Hlin-H to obtain the category of hierarchical directed hypergraphs with linearity constraints hier-lin-H\textrm{hier-lin-}\mathbb Hhier-lin-H. Similarly, we define the associated category for type systems; however, we do not impose any of the two conditions related to P(⋅)P(\cdot)P(⋅) for the type category, i.e. hier-lin-H type=[hier-lin-C type, S e t]\textrm{hier-lin-}\mathbb H_\textrm{type} = [\textrm{hier-lin-}\mathbb C_\textrm{type}, \mathrm{Set}]hier-lin-H type​=[hier-lin-C type​,Set] is the full presheaf category, rather than a subcategory of it.

As with the incidence morphisms src\textit{src}src and tgt\textit{tgt}tgt, we will drop the s t stst subscript for the IO arrows in\textit{in}in and out\textit{out}out when it can be inferred from the domain of definition.

Just as in the discussion of Definition 3.2, we interpret the split monomorphisms as equivalent to requiring F s t⊆E s t\mathbf{F}_{st} \subseteq \mathbf{E}_{st}F st​⊆E st​. Taking over terminology from Drewes, 2002Frank Drewes, Berthold Hoffmann and Detlef Plump. 2002. Hierarchical Graph Transformation. Journal of Computer and System Sciences 64, 2 (March 2002, 249--283). doi: 10.1006/jcss.2001.1790, we call elements f∈F s t f \in \mathbf{F}_{st}f∈F st​ the frames of H hier∈hier-H H_\textrm{hier} \in \textrm{hier-}\mathbb H H hier​∈hier-H. For each frame f f f, there is thus a unique input edge i n(f)in(f)in(f) and a unique output edge o u t(f)out(f)out(f) in H hier H_\textrm{hier}H hier​ that have respectively s ss targets and zero sources, and t tt sources and zero targets.

By the first condition we imposed on P(⋅)P(\cdot)P(⋅), the partial function p a r e n t parentparent mapping connected components to their parent edge:

p a r e n t([e])={p if there exists p∈P(e)⊥ otherwise. parent([e]) = \begin{cases} p\quad&\textrm{ if there exists } p \in P(e)\\ \bot&\textrm{ otherwise.} \end{cases} parent([e])={p⊥​ if there exists p∈P(e) otherwise.​

is well-defined. We call the subgraphs of H hier H_\textrm{hier}H hier​ that share a same parent a region of H hier H_\textrm{hier}H hier​2. The subgraph of vertices and edges without parent is the root region of H hier H_\textrm{hier}H hier​.

#### The minIR computation graph #

In minIR, the vertices are the values of the computation, while the hyperedges define the operations. This imposes some constraints for a hypergraph to be a valid minIR graph:

- all values in minIR must have a unique operation that defines them;
- values that are linear must also have a unique operation that uses them;
- the graph must be acyclic, meaning that no value can be defined in terms of itself.

This can be expressed as a hypergraph with linearity constraints by choosing V tgt=V\mathbf V_\textit{tgt} = \mathbf V V tgt​=V and V src=V L\mathbf V_\textit{src} = \mathbf V_L V src​=V L​, where V L⊆V\mathbf V_L \subseteq \mathbf V V L​⊆V is the subset of linear values.

The following definition then comes as no surprise:

Definition 3.4MinIR graph

Let Σ∈hier-lin-H type\Sigma \in \textrm{hier-lin-}\mathbb H_\textrm{type}Σ∈hier-lin-H type​ be a type system. A minIR graph H H H typed in Σ\SigmaΣ is an object of hier-lin-H\textrm{hier-lin-}\mathbb Hhier-lin-H that is Σ\SigmaΣ-typed and such that the adjacency relation ⇝\leadsto⇝ is acyclic. We call V src=V L\mathbf V_\textit{src} = \mathbf V_L V src​=V L​, the linear values of H H H.

In the context of minIR, ⇝\leadsto⇝ relations encode the data flow of values across the computation. The lack of explicit operation ordering differentiates minIR (and HUGR) from most classical IRs, which, unless specified otherwise, typically assume that instructions may have side effects and thus cannot be reordered. All quantum operations (and the classical operations we are interested in) are side-effect free, which significantly simplifies our IR.

#### Input and output values #

Notice that in Definition 3.4, it is not enforced that every value has a definition, i.e. there might be v∈V∖V tgt v \in \mathbf V \setminus \mathbf V_\textrm{tgt}v∈V∖V tgt​; nor that every value with a linear type is in V L\mathbf V_L V L​, i.e. if τ: H→Σ\tau: H \to \Sigma τ: H→Σ is the typing morphism and T L\mathbf T_LT L​ are the linear types in the type system, there might be v∈τ−1(T L)∖V L v \in \tau^{-1}(\mathbf T_L) \setminus \mathbf V_L v∈τ−1(T L​)∖V L​.

This would be easy to fix: we could on the one hand enforce the equality V tgt=V\mathbf V_\textrm{tgt} = \mathbf V V tgt​=V, thus guaranteeing that every value has a unique definition in the graph. On the other hand, we could define V\mathbf V V as the coproduct V=V L⊔V NL\mathbf V = \mathbf V_L \sqcup \mathbf V_\textit{NL}V=V L​⊔V NL​, where V NL V_\textit{NL}V NL​ is a new object introduced to explicitly capture the set of non-linear values. Morphisms in this category would guarantee that the linearity of values is always preserved, and thus in particular the type morphism would map a value to a linear type if and only if it is linear.

Instead, we opt to allow undefined values and unused linear values to be able to express rewrite rules that match sugraphs of minIR graphs within the same category.

Definition 3.5Inputs and outputs of minIR graphs

For a minIR graph H H H with typing morphism τ: H→Σ\tau: H \to \Sigma τ: H→Σ, we call the set I=V∖V tgt I = \mathbf V \setminus \mathbf V_\textit{tgt}I=V∖V tgt​ the input values of H H H and O=τ−1(T L)∖V L O = \tau^{-1}(\mathbf T_L) \setminus \mathbf V_L O=τ−1(T L​)∖V L​ its output values, where T L\mathbf T_LT L​ are the linear values in Σ\SigmaΣ.

If I=O=∅I = O = \varnothing I=O=∅, we say that H H H is IO-free.

Note that by this definition, an output value in O O O always has a linear type! This is because non-linear values do not need to be treated specially when they are outputs: unlike linear values that must always be used in a non-output position, non-linear values may have no outgoing edge, in which case they are simply discarded in the computation.

### Structured control flow #

The operations and values of a minIR graph define the data flow of a program. However, a program must also be able to control and change the data flow at run time in order to express loops, conditionals, function calls etc. This is the program control flow, which minIR expresses using regions and so-called structured control flow.

Using regions, any non-trivial control flow (function calls, conditionals, loops etc.) is captured by a frame, a “black box” operation within the data flow of the program. Its implementation is then defined in the nested region of the frame. This can be used for function calls, but also for branches of control flow. A simple function call, that unconditionally redirects the control flow to the operations within a nested region, could for example be represented as follows:

In this figure and below, circles are SSA values (the vertices of the hypergraph), while the edges spanning between them are the operations. Edges attached to the white half of circles are value definitions, while hyperedges attached to the black half of circles are value uses. The `call` and `+` operation can be read left to right: for instance, the two values `x` and `y` on the left of `call` are inputs (the operation uses those values, and is thus attached to the black half of the circles), whereas the `x + y` value on the right is the output of the `call` operation (the operation defines this value, which is thus attached to the white half of the circle).

Dashed arrows indicate hierarchical dependencies that map the frame edge to the two input and output edges in the child region; dashed rectangles mark the non-root regions of the graph.

Importantly, the frame edge representing the `call` operation must intuitively “forward” all its input values to the `in` operation of the child region, and similarly passes on the value at the `out` operation to the output value of the `call` output in the parent graph. Passing function arguments and retrieving returned values in this fashion will be very familiar to any computer scientist. Unlike most programming languages, this is also how in minIR values are passed to and from any control flow constructs we would wish to model.

In terms of graph structure, this relation between values in parent and child regions means that the arity and types of the inputs and outpus of `call` fix the signatures of the child `in` and `out` operations. Definition 3.3 already ensures that the input and output arities of `in` and `out` are correct. The correct typing of these input and output values will be ensured by the type system, which we discuss in a separate section below.

To handle constructs that require more than one child region, such as an `if-else` statement, we can use frames that have zero input and one output:

The output of the `ifblock` is intuitively a higher-order type representing an operation that takes two inputs and ouputs the sum.

An if-else statement might then look as follows:

The `if` and `else` blocks must expect the same input and output values. This is key to respecting any linearity constraints that values passed to `ifelse` might be subject to. By definition, all operations that use or define a value v v v will be in the same region – in other words, values are only available within their defining region. This in effect implements “variable scoping”. With some imagination, this construction can easily be adapted to model loops, complex control flow graphs, or any other control flow structures.

#### Why not plain branch statements? #

There is a simpler – and at least as popular – way of expressing control flow in IRs without requiring regions and operation hierarchies, using branch statements3. For instance, LLVM IR provides a conditional branch statement

    br i1 %cond, label %iftrue, label %iffalse

that will jump to the operations under the `iftrue` label if `%cond` is true and to the `iffalse` label otherwise.

This is a simple and versatile approach to control flow that can be used to express any higher-level language constructs. Unfortunately, conditional branching does not mix well with linear values.

Linearity, as defined in Definition 3.4, is a simple constraint to impose on minIR graphs. In the presence of conditional branching, however, the constraint would have to be relaxed to allow for single use in each mutually exclusive branch of control flow. For instance, the following two uses of `b` should be allowed (in pseudo-IR):

    b := h(a)
    <if cond> c := x(b)
    <else>    d := h(b)

This is a much harder invariant to check on the IR: linearity would no longer be enforceable as a syntactic constraint on the minIR graph as in Definition 3.4, but would instead depend on the semantics of the operations to establish mutual exclusivity of control flow4. Forbidding arbitrary branching in minIR and resorting instead to structured control flow as described above to express control flow is just as expressive and gives the linearity constraint a much simpler form.

### Type graph #

We have seen how minIR graphs impose some structure on the types of computations that can be expressed: a linear value cannot be used by two (or zero) operations, frames will always have a unique `in` and `out` operation in their child region with correct arities, etc.

However, without a “good” type system and associated semantics, it is still possible to express nonsensical programs: we have mentioned for instance earlier that it is up to the type system to enforce that the types of the `in` and `out` operations match the types of the frame. Similarly, it is possible to construct programs that break linearity: take the `ifelse` operation discussed in the previous section, but now replace its semantics to be `do-in-parallel`, i.e. it will execute both the `if-block` and `else-block` in parallel on the inputs that it is given. This would violate the linearity of its inputs, but would nonetheless be a syntactically valid minIR graph!

To resolve this we present here some typed operations, along with their semantics, that can be used to construct well-behaved type systems: programs typed in this system model the kind of quantum programs that we are interested in expressing and are guaranteed to be valid computations. Categorising all valid constructions or an exhaustive enumeration of conditions that type systems must satisfy to guarantee the validity of programs is beyond the scope of this thesis. It is in practice often straightforward to combine and extend the elements presented here to support further custom syntactic constructs and types.

#### Basic types and operations #

The most elementary types in our computations are `Bit`s and `Qubit`s. The former is typically known as a Boolean and represents the purely classical values `0` and `1`. The latter is the canonical quantum example of a linear type. Indeed, just like values in minIR graphs, the type system in hier-lin-H type\textrm{hier-lin-}\mathbb H_\textrm{type}hier-lin-H type​ distinguishes between linear and non-linear types.

Other typical classical types such as integers, floats, strings, custom algebraic data types (ADT) etc could also be introduced as required. In the figure below, we for instance introduce the `Angle` type to represent rotation angles that parametrise quantum gates. Further examples of linear types, on the other hand, include higher-dimensional qudits, but also any ADT that contains a linear type within it.

As we saw in section 2.1, the number of input qubits in pure quantum operations will match the number of output qubits: the single-qubit `h` (hadamard gate) and two-qubit `cx` (controlled NOT) operations thus have one or two `Qubit`s as both inputs and outputs `rz` (Z rotation) is also a single-qubit operation, but it takes an additional input of type `Angle` to specify the rotation angle.

On the pure classical side, we are free to add any side-effect free operations on our types; in our example we model addition `+` on `Angle`s and negation `not` on `Bit`s. In the type system Σ∈hier-lin-H type\Sigma \in \textrm{hier-lin-}\mathbb H_\textrm{type}Σ∈hier-lin-H type​, each type is represented by a single vertex.

In our example, we thus have three vertices:

We introduce a different colour for each type. Operations such as `cx` are represented by a hyperedge with two sources on `Qubit` and two targets on `Qubit`. As in the previous diagrams, we can distinguish operation inputs from outputs by whether they are attached to the dark or light half of the type vertex: the `rz` operation thus has one `Qubit` input, one `Angle` input and one `Qubit` output.

As you can tell from the diagram, whilst `Qubit` is a linear type in the type system, it is not a linear value in the sense of a minIR graph: the `Qubit` type has multiple uses and defines in the `cx` operation alone. This is the key difference between lin-H type\textrm{lin-}\mathbb H_\textrm{type}lin-H type​ and lin-H\textrm{lin-}\mathbb Hlin-H.

#### Qubit allocation and measurement #

We also introduce non-pure quantum operations `qalloc` and `measure` which respectively “create” a qubit (so no input, one `Qubit` output) and “destroy” it (one `Qubit` input, one `Bit` output – depending on whether the qubit was projected onto the ∣0⟩\ket{0}∣0⟩ or ∣1⟩\ket{1}∣1⟩ state). Remember that the reason these operations seem to “break” the laws of pure quantum physics is because they result from interactions with the classical environment.

`measure` is fundamental, as it connects quantum values with classical ones!

#### Region definition and structured control flow #

Our type system is so far missing a crucial aspect of minIR: the hierarchical structures. For this we need frame types, i.e. frames in the type graph. We must introduce a distinct type for each possible type signature of a frame. To keep this as simple as possible, we will introduce exactly one type for each signature.

If we write T T T for the set of types in our type system (i.e. `Bit`, `Qubit` and `Angle` in our example), then a type signature of an edge is given by a pair (I, O)(I, O)(I, O) of ordered lists of types I, O∈T∗I, O \in T^\ast I, O∈T∗. For each such (I, O)(I, O)(I, O) pair, we introduce

- the frame type `regiondef<I, O>`,
- the in and out types `in<I,O>` and `out<I,O>`,
- along with a new non-linear type `Region<I, O>`, the higher-order type representing a region with inputs I I I and outputs O O O.

The `regiondef<I, O>` op takes zero inputs and returns one output `Region<I, O>`, whereas `in<I,O>` takes zero inputs and returns values of type I I I and `out<I,O>` takes inputs of type O O O and returns nothing. For instance, for I=(I = (I=(`Qubit`, `Qubit`))) and O=(O = (O=(`Qubit`, `Bit`))), we have the following type graph.

Note that there is an important distinction in hier-lin-H type\textrm{hier-lin-}\mathbb H_\textrm{type}hier-lin-H type​ in comparison to hier-lin-H\textrm{hier-lin-}\mathbb Hhier-lin-H: there is no notion of regions in the type system: the `Qubit` and `Bit` types in the above diagram would be in the child region of `regiondef<I, O>` if it were a graph in hier-H\textrm{hier-}\mathbb Hhier-H, but in the type system, they might also be used by other operations in other regions (such as `cx`, `rz`, `h` etc. defined earlier).

Using the `Region<I,O>` types, it is then easy to define typed operations for any structured control flow of interest, such as the `if-else` example above. The following figure gives an overview of the entire type system of our example. For display purposes, we have included multiple copies of each type vertex; we remind the reader that in the actual type graph, all circles of the same type (colour) are one and the same.

A complete minIR type graph, following the example in this section. Value vertices with the same label (and same colour) form a single vertex in the type graph. They have been split into multiple vertices in this representation for better readability. The data types and op types with the `<I,O>` suffix are parametrised on the signature type (I, O)(I,O)(I, O) for I, O∈T∗I,O \in T^\ast I, O∈T∗.

### An example minIR program #

Taking a step back, let us make the introduced ideas more concrete through an example. We demonstrate how a simple program written in textual form can be translated and expressed as a minIR graph. All statements are of the form

    x, y, ... := op(a, b, c, ...)

where `a`, `b`, `c` etc are the SSA values passed to `op` (or used by `op`), and `x`, `y` etc are the SSA values returned by `op` (or defined by `op`). We use curly bracket to define the child region of a `regiondef` operation. A valid minIR program might then look as follows:

     1main := regiondef<(Qubit, Qubit), (Qubit, Bit)> {
     2    q0, q1 := in()
     3
     4    q0_1 := h(q0)
     5    q0_2, q1_1 := cx(q0_1, q1)
     6
     7    m0 := measure(q0_2)
     8
     9    ifregion := regiondef<(Qubit,), (Qubit,)> {
    10        q1 := in()
    11        out(q1)
    12    }
    13    elseregion := regiondef<(Qubit,), (Qubit,)> {
    14        q1 = in()
    15        q1_1 := h(q1)
    16        out(q1_1)
    17    }
    18    q1_2 := ifelse(m0, q1_1, ifregion, elseregion)
    19
    20    out(q1_2, m0)
    21}

Note that the `in()` and `out(..)` operations are only allowed within nested regions (as required by the type system). We have omitted the type parameters on these operations, as it mirrors exactly the paremeter of the `regiondef`.

It corresponds to the two minIR graphs on the following page. We use “wiggly hyperedges” that stretch between values, as in the first figure. They may look unusual if you are used to computation graphs. One can opt to draw the same graph with boxes for hyperedges and wires for values, yielding the second figure. The two representations are equivalent, but the rewriting semantics are most explicit when viewing values as vertices.

An example of an IO-free minIR graph. The vertex colours indicate their types in the type system presented in the previous figure. The `main`, `ifregion` and `elseregion` ops are all of op type `regiondef` (with type parameters omitted), labelled here with custom names for clarity. The type parameters of the `ifelse`, `in` and `out` op type have similarly been omitted. All other operation types are given as labels on the edges.

An equivalent representation of the computation above, now representing operations as boxes and values as wires. The arrow direction indicates the flow from value definition to value use(s). Dashed arrows have been changed to point to regions instead of individual operations.

### Differences to the quantum circuit model #

We conclude this presentation of minIR by highlighting the differences between this IR-based representation and the quantum circuit model that most quantum computing and quantum information scientists are familiar with5.

When restricted to purely quantum operations and no nested regions, the string diagram representation of a minIR graph (i.e. operations as boxes and values as wires) looks very similar to a quantum circuit. There is, however, a fundamental shift under the hood from reference to value semantics – to borrow terminology from C++.

In the reference semantics of quantum circuits, operations are typically thought of as “placed” on a qubit (the “lines” in the circuit representation), for instance, by referring to a qubit index. This qubit reference exists for the entire computation duration, and the quantum data it refers to will change over time as operations are applied to that qubit.

In the value semantics of computation graphs and SSA, on the other hand, qubits only exist in the form of the data they encode. When applying an operation, the (quantum) data is consumed by the operation and new data is returned. Given that the input data no longer exists, linearity conditions are required to ensure that no other operation can be fed the same value.

To make the difference clear, compare the program representations of the following computation:

Quantum circuit (pytket)6

    import pytket as tk
    circ = tk.Circuit(2)
    circ.H(0)
    circ.CX(0, 1)
    circ.X(1)

SSA (minIR)

    q0_0, q1_0 := in()
    q0_1       := h(q0_0)
    q0_2, q1_1 := cx(q0_1, q1_0)
    q1_2       := x(q1_1)
    out(q0_2, q1_2)

In value semantics, it becomes much harder to track physical qubits across their lifespan. This has very practical implications: without the convenient naming scheme, it would, for example, be non-trivial to count how many qubits are required in the SSA representation of the computation above. However, it is a drastically simpler picture from the point of view of the compiler and the optimiser – hence its popularity in classical compilers. When operations are defined based on qubit references, the compiler must carefully track the ordering of these operations: operations on the same qubit must always be applied in order. Through multi-qubit gates, this also imposes a partial ordering on operations across different qubits that must be respected.

SSA values remove this dependency tracking altogether: the notion of physical qubit disappears, and the ordering of statements becomes irrelevant. All that matters is connecting each use of a value (i.e. an input to an operation) with its unique definition, the output of a previous operation. In other words, the global ordering imposed by reference semantics is replaced by a causal order on the diagram Kissin., 2019Aleks Kissinger and Sander Uijlen. 2019. A categorical semantics for causal structure. Logical Methods in Computer Science Volume 15, Issue 3 (August 2019). doi: 10.23638/lmcs-15(3:15)2019.

All the concepts of minIR embed themselves very easily within the MLIR-based quantum IRs and the HUGR IR 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. In this sense, our toy IR serves as the minimum denominator across IRs and compiler technologies so that proposals and contributions we are about to make can be applied regardless of the underlying technical details.

By waiving goodbye to the circuit model, we have been able to integrate much of the theory of traditional compiler design, bringing us in the process much closer to traditional compiler research and the large-scale software infrastructure that is already available. This gives us access to all the classical optimisation and program transformation techniques developed over decades. Using structured control flow, we were also able to model linear resources such as qubits well – by using value semantics and SSA, checking that no-cloning is not violated is as simple as checking that each linear value is used exactly once.

Finally, this new design is also extremely extensible. Not only does it support arbitrary operations, but the type system is also very flexible. There is dedicated support for linear types, but this does not have to be restricted to qubits: lists of qubits could be added or even, depending on the target hardware, higher dimensional qudits, continuous variable quantum data, etc.

1. And in fact, we will see in section 3.4 that it is not. ↩︎

2. Note that a region may not be a connected subgraph. Albeit, it is a simple exercice to convince yourself that any non-root region contains either one or two connected components. ↩︎

3. You may know this from prehistoric times as the `goto` statement, in languages such as Fortran, C, and, yes, even Go. ↩︎

4. You might be thinking “oh, but all that is required here are phi nodes!”, if you are familiar with those. No – you’d also need a sort of “phi inverse”. Besides, see this discussion for more arguments on why no phi nodes. ↩︎

5. Note that these comments apply specifically to characteristics of quantum circuits. Other diagrammatic representations of quantum processes in use, such as string diagrams, quantum combs etc may not share the same properties. ↩︎

6. This is python code: `pip install pytket`. ↩︎

←Return to chapter