### Preliminaries and simplifying assumptions

←Return to chapter

## 4.2. Preliminaries and simplifying assumptions

For simplicity, we will throughout consider minIR graphs that admit a type system Σ\SigmaΣ, though most of the results can also be adapted to other graph domains. We will write T T T for the types of Σ\SigmaΣ (i.e. its values) and Γ\GammaΓ for the operation types (i.e. its edges).

#### Linear paths and operation splitting #

An operation type ν∈Γ\nu \in \Gamma ν∈Γ in the type system Σ\SigmaΣ is a hyperedge. Its endpoints

src(ν)=src 1(ν)⋯src s(ν) and tgt(ν)=tgt 1(ν)⋯tgt t(ν) \textit{src}(\nu) = \textit{src}_1(\nu) \cdots \textit{src}_s(\nu) \textrm{ and } \textit{tgt}(\nu) = \textit{tgt}_1(\nu) \cdots \textit{tgt}_t(\nu) src(ν)=src 1​(ν)⋯src s​(ν) and tgt(ν)=tgt 1​(ν)⋯tgt t​(ν)

are strings of data types that define the input and output signature of the operation ν\nu ν. We can refer to the set of all hyperedge endpoints of ν\nu ν using the string indices I d x(⋅)\mathrm{Idx}(\cdot)Idx(⋅) (⊔\sqcup⊔ denotes the disjoint set union):

P ν=I d x(src(ν))⊔I d x(tgt(ν))={1,…,s}⊔{1,…,t}.P_\nu = \mathrm{Idx}(\textit{src}(\nu)) \sqcup \mathrm{Idx}(\textit{tgt}(\nu)) = \{1, \dots, s\} \sqcup \{1, \dots, t\}.P ν​=Idx(src(ν))⊔Idx(tgt(ν))={1,…,s}⊔{1,…,t}.

Fix a partition of P ν P_\nu P ν​ into disjoint pairs

P ν={p 1, p 1′} ⊔ {p 2, p 2′} ⊔ ⋯ ,P_\nu = \{p_1, p_1'\} \,\sqcup\, \{p_2, p_2'\} \,\sqcup\, \cdots, P ν​={p 1​,p 1′​}⊔{p 2​,p 2′​}⊔⋯,

where the last set of the partition may be a singleton if ∣P ν∣|P_\nu|∣P ν​∣ is odd. For every ν∈Γ\nu \in \Gamma ν∈Γ, we then define f=⌈∣P o∣/2⌉f = \lceil |P_o| / 2 \rceil f=⌈∣P o​∣/2⌉ new split operation types ν 1,…,ν f\nu_1, \dots, \nu_f ν 1​,…,ν f​, each with two endpoints: the i ii-th operation type ν i\nu_i ν i​ has endpoints p i p_ip i​ and p i′p_i'p i′​ in P ν P_\nu P ν​. For every operation o∈E o \in Eo∈E of type ν\nu ν, we can then split o oo into f f f operations o 1,…,o f, o_1, \dots, o_f,o 1​,…,o f​, each of arity 1 or 2 and of types ν 1,…,ν f\nu_1, \dots, \nu_f ν 1​,…,ν f​ respectively. We will refer to the graph transformation that replaces an operation o oo in a minIR graph with the operations o i o_io i​ for 1⩽i⩽f 1 \leqslant i \leqslant f1⩽i⩽f as operation splitting.

It is important to note that the splitting of an operation o oo is unique and given by the type of o oo, and thus invariant under (typed) morphisms: there is a morphism P→G P \to G P→G of a pattern into a graph if and only if there is a morphism P′→G′P' \to G'P′→G′ from the split pattern P′P'P′ into the split graph G′G'G′.

A transformation rule splitting an operation with 3 sources and 2 targets. The choice of endpoint partition made here, obtained by pairing the i ii-th use with the i ii-th define, is arbitrary but convenient for quantum gates as they correspond to the input and output values of a same qubit.

The endpoint partitions P ν P_\nu P ν​ also define linear paths. Two values v, v′v, v'v, v′ in a minIR graph are on the same linear path if there are values u 1,…,u k u_1, \dots, u_ku 1​,…,u k​ with v=u 1 v = u_1 v=u 1​ and v′=u k v' = u_k v′=u k​ such that u i u_iu i​ is connected to u i+1 u_{i+1}u i+1​ through an operation o oo and they correspond to the same pair of endpoints in the endpoints partition (i.e. the indices of P t y p e(o)P_{type(o)}P t y pe(o)​ correspond to values u i u_iu i​ and u i+1 u_{i+1}u i+1​ in src(o)⊔tgt(o)\textit{src}(o) \sqcup \textit{tgt}(o)src(o)⊔tgt(o)).

#### Linearity assumption and rigidity #

Recall that in Definition 3.2, V src V_\textit{src}V src​ and V tgt V_\textit{tgt}V tgt​ refer to the subset of values that are within the domain of definition of src\textit{src}src and tgt\textit{tgt}tgt respectively. For this chapter, we will assume V src=V tgt=V V_\textit{src} = V_\textit{tgt} = V V src​=V tgt​=V; in other words, minIR graphs are IO-free (this is w.l.o.g., see discussion after Proposition .) and all values are linear1 (this is definitely not w.l.o.g.!).

As a result of this assumption, the subcategory of minIR graphs that we consider forms a rigid category, as introduced by Danos et al. Danos, 2014Vincent Danos, Reiko Heckel and Pawel Sobocinski. 2014. Transformation and Refinement of Rigid Structures. The definition, which we reproduce here, is given in terms of morphisms that intersect all components of the codomain. We refer to Danos, 2014Vincent Danos, Reiko Heckel and Pawel Sobocinski. 2014. Transformation and Refinement of Rigid Structures for the precise definition of that notion: in the context of linear-valued minIR graphs, this is equivalent to requiring that the image of the graph homomorphism intersects every connected component of the codomain.

Definition 4.1Rigid Category

A category C\mathbb CC is rigid if for all morphisms A→h B A \xrightarrow{h} BA h
​B in C\mathbb CC that intersects all components of B B B and for all A→g C A \xrightarrow{g} CA g
​C that factorises as g=f∘h g = f \circ h g=f∘h, then B→f C B \xrightarrow{f} C B f
​C is unique.

In other words, there is a unique way to extend a morphism A→g C A \xrightarrow{g} CA g
​C to a morphism B→f C B \xrightarrow{f} C B f
​C, if it exists. If we interpret A AA and B B B as graph patterns that we are interested in matching with A⊆B A \subseteq BA⊆B, then rigidity guarantees that there is (at most) a unique way to extend a match morphism A→G A \to GA→G into a match morphism on the larger pattern B→G B \to G B→G.

The linearity assumption also has other useful consequences. Every linear value has exactly one use and one definition. As a result, all linear paths are disjoint and form a partition of the values of the graph. They correspond to the paths that form the connected components of the fully split graph, i.e. the graph obtained by splitting every operation. We call the number of linear paths (and hence the number of connected components in the fully split graph) the circuit width, written w i d t h(G)width(G)w idth(G). We also use the linear path decomposition to define circuit depth, written d e p t h(G)depth(G)depth(G), as the longest linear path in G GG.

As discussed in section 3.4, minIR rewrites are instantiated from transformation rules by minIR match morphisms m: P→G m: P \to Gm: P→G. Restricting our considerations to linear-valued minIR graphs has the further implication that all such match morphsisms m mm will be injective. We call m mm an embedding and write it using greek letters and a hooked arrow

m=φ: P↪G. m = \varphi: P \hookrightarrow G.m=φ: P↪G.

Finding such embeddings P↪G P \hookrightarrow G P↪G is the pattern matching problem that we are solving. This problem is equivalent to finding minIR subgraphs H⊆G H \subseteq G H⊆G of G GG such that H H H is isomorphic to the pattern P≃H P \simeq H P≃H.

#### Convexity #

According to Proposition ., a necessary condition for a subgraph H H H to define a valid minIR rewrite is convexity. In this chapter we weaken this requirement and propose a condition based on circuit width:

Proposition 4.1Necessary condition for convexity

Let φ: P↪G\varphi: P \hookrightarrow Gφ: P↪G be an embedding of a pattern P P P into a linear-valued minIR graph G GG such that φ(P)\varphi(P)φ(P) is a convex subgraph of G GG. Then for every subgraph H⊆G H \subseteq G H⊆G such that φ(P)⊆H\varphi(P) \subseteq Hφ(P)⊆H, it holds that w i d t h(P)≤w i d t h(H).width(P) \leq width(H).w idth(P)≤w idth(H).

Up to isomorphism, we can assume P⊆G P \subseteq G P⊆G. Suppose there is H⊆G H \subseteq G H⊆G such that P⊆H P \subseteq H P⊆H and w i d t h(P)>w i d t h(H)width(P) > width(H)w idth(P)>w idth(H). Let L P, L H⊆P(V)\mathcal{L}_P, \mathcal{L}_H \subseteq \mathcal{P}(V)L P​,L H​⊆P(V) be partitions of V P V_P V P​ and V H V_H V H​ into sets of values that are on the same linear path of P P P and H H H respectively. It must hold that for all ℓ∈L P\ell \in \mathcal{L}_Pℓ∈L P​ there is ℓ′∈L H\ell' \in \mathcal{L}_Hℓ′∈L H​ such that ℓ⊆ℓ′\ell \subseteq \ell'ℓ⊆ℓ′, because P⊆H P \subseteq H P⊆H and operation splitting is preserved under embeddings. As the map from L P\mathcal{L}_PL P​ to L H\mathcal{L}_HL H​ cannot be injective, there must be ℓ 1, ℓ 2∈L P\ell_1, \ell_2 \in \mathcal{L}_Pℓ 1​,ℓ 2​∈L P​ and ℓ′∈L H\ell' \in \mathcal{L}_Hℓ′∈L H​, such that ℓ 1≠ℓ 2\ell_1 \neq \ell_2ℓ 1​=ℓ 2​ and ℓ 1, ℓ 2⊆ℓ′\ell_1, \ell_2 \subseteq \ell'ℓ 1​,ℓ 2​⊆ℓ′. We conclude that there must be a path in the fully split graph of H H H between a value of ℓ 1\ell_1ℓ 1​ and a value of ℓ 2\ell_2ℓ 2​ that is not in the fully split graph of P P P. Given that P P P is convex, this path must be in P P P, which contradicts the preservation of operation splitting under embeddings.

In this chapter, whenever we define a subgraph H⊆G H \subseteq G H⊆G of a graph G GG, we will assume that H H H satisfies the above weakened convexity condition.

The converse of Proposition ., however, is not true. The pattern-matching technique presented below will find a strict superset of convex embeddings. To restrict considerations to convex embeddings, it suffices to filter out the non-convex ones in a post-processing step.

#### Ignoring minIR Hierarchy #

So far, we have omitted discussing one part of the minIR structure: the nested hierarchy of operations. Syntactically, the hierarchy formed by p a r e n t parentparent relations between minIR operations can be viewed as just another value type that operations are incident to: parent operations define an additional output that children operations consume as additional input. Because of the bijectivity requirement of minIR morphisms on parent-child relations of Definition ., these parent-child relations behave, in fact, like linear values – and hence do not violate the linearity assumption we have imposed.

However, by treating them as such, we have further weakened the constraints on pattern embeddings. We do not enforce that boundary values must be in the same regions or that parent-child relations cannot be boundary values. Similarly to convexity, we defer checking these properties to a post-processing step.

#### Further assumptions (harmless) #

We will further simplify the problem by making presentation choices that do not imply any loss of generality. First of all, we assume that all patterns have the same width w w w and depth d dd, are connected graphs and have at least 2 operations. These conditions can always be fulfilled by adding “dummy” operations if necessary. Embeddings of disconnected patterns can be computed one connected component at a time.

We will further assume that all operations are on at most two linear paths (and thus in particular, have at most 4 endpoints). Operations on Δ>2\Delta > 2Δ>2 linear paths can always be broken up into a composition of Δ−1\Delta-1Δ−1 operations, each on two linear paths as follows:

Expressing an operation on Δ=3\Delta = 3Δ=3 linear paths as a composition of two operations on 2 linear paths.

This transformation leaves circuit width unchanged but may multiply the graph depth by up to a factor Δ\DeltaΔ.

We furthermore define the set of all port labels

P a l l=⋃ν∈Γ P ν P_{all} = \bigcup_{\nu \in \Gamma} P_\nu P a ll​=ν∈Γ⋃​P ν​

so that we can associate every operation endpoint in a minIR graph G GG with a port label from the set P a l l P_{all}P a ll​. We further endow the labels P a l l P_{all}P a ll​ with a total order (for instance, based on the string index values). The total order on P a l l P_{all}P a ll​ then induces a total order on the paths v 1⋯v k∈V∗v_1\cdots v_k \in V^\ast v 1​⋯v k​∈V∗ in G GG that start in the same value v 1 v_1 v 1​: the paths are equivalently described by the sequence of port labels of the operations traversed. These form strings in P a l l∗P_{all}^\ast P a ll∗​, which we order lexicographically. Given a root value r r r, for every value v v v in G GG there is thus a unique smallest path from r r r to v v v in G GG2. This path is invariant under isomorphism of the underlying graph (i.e. relabelling of the values and operations but preserving the port labels). With this we conclude the discussions of the specificities of minIR graphs related to typing, linearity and hierarchy, and the related assumptions that we are making.

To summarise, minIR graphs as they are considered in this chapter are hypergraphs (Definition 3.1) that satisfy the following properties

- every vertex (value) is incident to exactly two hyperedges (operations). It is the target of one hyperedge (its definition) and the source of another one (its use),
- every hyperedge is incident to at most four vertices,
- every hyperedge can be split in a unique way (and invariant under isomorphism) into at most two split operations, with each at most two endpoints.

When modelling subgraphs of IO-free minIR graphs (typically patterns for pattern matching), some hyperedge connections at the boundary of the subgraph will be missing. We say a value is open if a use or define operation is missing (i.e. it is a boundary value in a minIR subgraph).

We will simplify refer to hypergraphs that satisfy the above assumptions as graphs. In the unique instance of this chapter where a graph that does not satisfy this construction is referred to, we will specifically call it a simple graph.

We conclude with the following notable bound on circuit width.

Proposition 4.2Bound on circuit width

Let G GG be a graph with n odd n_\textrm{odd}n odd​ operations of odd arity (i.e. ∣d e f(o)+u s e(o)∣|def(o) + use(o)|∣de f(o)+use(o)∣ is odd) and n ω n_\omegan ω​ open values. Then, the circuit width of G GG is

w i d t h(G)=⌊(n odd+n ω)/2⌋.width(G) = \lfloor(n_\textrm{odd} + n_\omega) / 2\rfloor. w idth(G)=⌊(n odd​+n ω​)/2⌋.

For any linear path P⊆V∗P \subseteq V^\ast P⊆V∗ in G GG consider its two ends v 1 v_1 v 1​ and v 2 v_2 v 2​, i.e. the two values in P P P with only one neighbouring value in P P P (by definition linear paths cannot be empty). In the fully split graph of G GG, these values are either open or must be connected to two operations. In the latter case, at least one of the operations must have a single endpoint (otherwise by acyclicity, the operation would have two neighbours).

In a fully split graph, operations with a single endpoint result from a split operation with an odd number of endpoints. We conclude that for every linear path, there are either two operations with an odd number of endpoints in G GG, or one such operation and one open value, or two open values. The result follows.

1. This restriction is necessary for our results: copyable values may admit an arbitrary number of adjacent hyperedges. As a result, minIR graph pattern matching with copyable values is a generalisation of the subgraph isomorphism problem, a well-known NP-complete problem 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. The approach generalises to non-linear types, but the complexity analysis no longer holds (we pay a computational price for every non-linear value matched). ↩︎

2. Remark that the ordering of the operations thus defined is a particular case of a depth-first search (DFS) ordering of the graph: given an operation o oo that has been visited, all its descendants will be visited before proceeding to any other operation. ↩︎

←Return to chapter