{'fraction_non_alphanumeric': 0.03898473974719258, 'fraction_numerical': 0.009135998746039388, 'mean_word_length': 4.226301930953774, 'pattern_counts': {'":': 1, '<': 8, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 24, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Unitary-circuit semantics for measurement-based computations

One-way measurement based quantum computations (1WQC) may describe unitary transformations, via a composition of CPTP maps which are not all unitary themselves. This motivates the following decision problems: Is it possible to determine whether a ``quantum-to-quantum'' 1WQC procedure (having non-trivial input and output subsystems) performs a unitary transformation? Is it possible to describe precisely how such computations transform quantum states, by translation to a quantum circuit of comparable complexity? In this article, we present an efficient algorithm for transforming certain families of measurement-based computations into a reasonable unitary circuit model, in particular without employing the principle of deferred measurement.


Introduction
The one-way measurement model of quantum computation (1WQC), presented by [1] and subsequently elaborated in [2,3], allows descriptions of unitary transformations in terms of operations, such as measurements, which are not themselves unitary. This may be regarded as being due to an appropriate combination of the observables which are measured on the one hand, and the stabilizer group of the state-space (in the "quantumto-quantum" setting where we admit an input subsystem which may support an arbitrary input state) on the other hand. This intuition may be used in certain cases to prove that particular measurement-based computations perform unitary transformations [4], using a slight modification of the stabilizer formalism [5].
As we are often interested in describing computation in terms of unitary evolutions, measurement-based computing presents us with natural decision problems. Is it possible to efficiently determine whether a 1WQC procedure performs a unitary transformation? Is it possible to describe precisely how such computations transform quantum states, by translation to e.g. a unitary circuit of bounded complexity? If not, is it at least possible to efficiently verify whether it performs a given transformation?
These questions arise because simple unitary circuit models -such as uniform circuit families generated over the gate-set {H, T, ∧ Z} consisting of the Hadamard gate, the π /8 phase-gate, and controlled-Z gate respectively (with no classically controlled operations and measurement deferred to the end of a computation) -are the de facto standard models of quantum computation. Such circuits provide the (thus far) best-developed set of idioms for uniformly expressing algorithms independently of architecture. Other mathematical representations of quantum computation may be useful as abstractions of proposals for implementations of quantum computers, as in the case of the measurement-based models [6,1] and the adiabatic model [7]; and "purely physical" idioms seemingly divorced from uniform circuit families may suggest new quantum algorithms, as in the case of the O( √ N )-time algorithm for evaluating NANDtrees by quantum walks [8]. However, simple unitary circuit models are currently the preferred means for expressing quantum computations.
Because of the present uncertainty as to which implementation proposal will prove successful, the unitary circuit model represents a natural candidate for an intermediate language for representing algorithms independently of the target architecture, even if alternative models suggest new algorithms. Therefore, one may argue that how effectively one can translate from a given model of computation to unitary circuit models, and back, is an important measure of how well-understood the model is. Unless some one proposal for implementation comes to dominate over the others, or an unlikely breakthrough (e.g. the discovery of an efficient classical algorithm for simulating quantum circuits) is made, translation to a "simple" model of quantum computation such as the unitary circuit model is the best that can be reasonably hoped for as a uniform way of obtaining low-level semantics of a quantum computation.
We are generally not interested in arbitrary translations to and from unitary circuit models: we should require a translation scheme which does not substantially increase the complexity of the operation being translated. For instance, provided a 1WQC procedure P for performing a unitary transformation, we may decompose each classically controlled measurement into a classically controlled change-of-basis rotation followed by a standard basis measurement; applying the principle of delayed measurement, we may then replace the classically controlled rotations with coherently controlled ones. We may then decompose the gates of this circuit with respect to a desired gate-set, such as {H, T, ∧ Z}. However, in constructions for 1WQC procedures such as those defined in [2,3], each single-qubit transformation requires at least one additional qubit, one two-qubit entangling operation, and a classically controlled measurement which may depend on the results from several measurements. If one applies the principle of deferred measurement to such a 1WQC procedure P, which "represents" a unitary circuit C using one of these constructions, the result is a circuit C which requires many more qubits than C, and has at least one additional two-qubit operation for each single-qubit operation in C. This represents a constant factor inflation in both the number of operations of the circuit; and depending on the ratio of single-qubit to either the number of qubits or the number of two-qubit operations in the original circuit C, the asymptotic increase in the either the memory required or the number of two-qubit gates in C over C is in principle unbounded.
In contrast, we may consider translation procedures S from the 1WQC model, possibly with a restricted domain, which yield circuits of "reasonable" complexity. In this case, we may establish a reference for the complexity of the resulting circuits by considering (as in the previous paragraph) 1WQC procedures which arise from a translation routine R from unitary circuits to the 1WQC model. We may then require that img(R) ⊆ dom(S), and that S • R maps each circuit in dom(R) to one which is no more complex (and which performs the same unitary transformation). In particular, we will be interested in the case where dom(S) contains a wide range of operations. In this article, we require that dom(R) consists of the set of unitary bijections generated over {H, T, ∧ Z} (without measurements or classical control). Then dom(S) must be similarly general, as it must "recognize" different representations of arbitrary unitary bijections in the 1WQC model, and produce unitary circuits which are equivalent both in function and efficiency to the "original". We encapsulate these requirements as follows: a Definition 1.1. Let C B be a model of unitary circuits generated over a gate-set B. A semantic map for the 1WQC model in terms of unitary circuits is an efficiently computable partial function S from 1WQC procedures to C B , for which membership in dom(S) is efficiently decideable, and for which there exists a corresponding efficient translation routine R from C B back to the 1WQC model such that • dom(R) = C B and img(R) ⊆ dom(S); and • for any circuit C ∈ C B , C = (S • R)(C) performs the same transformation as C, and has complexity bounded above by that of C: in particular, -C acts on at most as many qubits as C; -C has at most the same depth as C; and the number of one-qubit and two-qubit gates in C are each at most the number of such gates in C.
We say that R is a representation map of C B in the 1WQC model, for which S provides the semantics.
A simple alternative notation for quantum circuits.
In order to facilitate descriptions of the construction of 1WQC procedures, as well as the task of determining when two circuits are congruent, we define in Section 2.1.3 a variant notation for unitary circuits (and products of linear operators generally) having convenient combinatorial properties.
An explicit account of two constructions of 1WQC procedures.
In order to explicitly describe a semantic map, we present in Section 2.3 the construction of [10] ("the DKP construction") and a simplified version of the construction of [2] ("the simplified RBB construction) for 1WQC procedures, including an explicit account of the time complexity of these constructions.
A succinct characterization of measurement dependencies in these constructions.
Using adjacency matrices of directed graphs, we characterize the classical measurement dependencies of the 1WQC procedures arising from the DKP construction and the simplified RBB construction in Section 3.1.
Circuit constructions from combinatorial decompositions. In Section 3.3, we illustrate how we may efficiently decompose the structures underlying a 1WQC procedure obtained from the DKP or simplified RBB constructions. Using these decompositions, we show in Section 3.4 how such a decomposition may be used to describe unitary circuits which may perform the same operation as the original 1WQC procedure.
These results allow us to define an efficient algorithm for computing a semantic map S which produces circuits for unitary bijections from an efficiently identifiable class of 1WQC procedures.

Related work.
A study into interpreting the effect of 1WQC procedures in terms of unitary circuits is performed by Childs, Leung, and Nielsen [11] via single-qubit "teleportation-based quantum computation". Their results may be described as providing alternative proofs of validity of the constructions of Raussendorf, Browne, and Briegel [2] of particular unitary operations in the 1WQC model, but do not present conditions for when such a reduction to the circuit model may be performed. The first algorithm to convert 1WQC procedures to unitary circuits was presented by Kashefi and Danos [12], who investigated conditions under which 1WQC procedures produced by the DKP construction perform unitary transformations. These conditions are formulated in terms of combinatorial structures, which were shown to be efficiently detectable in [13,14]. Using these structures, [12] outlines a procedure to generate a unitary circuit using those structures. Building on the results of [13,15,14], we extend those results to include procedures produced by the simplified RBB construction. We also characterize the measurement dependencies which arise in such 1WQC procedures when they are in a particular canonical form, in order to verify whether such a 1WQC procedure performs the unitary described by the constructed circuit; and demonstrate that the complexity of the circuits which are constructed are no more than the complexity of the original circuits.
The results here represent an extension of results in Chapter 3 of [9] concerning the DKP construction, by proving remarks made briefly there concerning the simplified RBB construction. In the few places where the terminology here differs from [9] (or from prior results), the differences are explicitly noted.

Preliminaries
We begin by presenting conventions and notational devices used throughout the article. Among these are a concise operational notation for procedures in the 1WQC model, and a transparent notation for unitary circuits which has convenient combinatorial properties. These will prove instrumental to simplify the description of the constructions for 1WQC procedures in the following section.
We take for granted a number of basic concepts in graph theory; the interested reader may refer to Diestel's text [16] for elementary definitions and proofs.

Unitary circuits
We will consider a particular model of quantum circuits: circuits without classical control, and with measurement (and trace-out operations) deferred to the end. We refer to such circuits as unitary circuits. As is common practise, we will ignore the terminal measurements and trace-out operations, and consider only the component involving unitary transformations and unitary embeddings.

Sets of approximately universal gates
As we noted in the introduction, we must consider a particular unitary circuit model with a fixed set of unitary gates. We consider a model closely related to most common gate sets: the set {H, T, ∧ Z} consisting of the Hadamard gate H, the π /8 gate T , and the controlled-Z gate ∧ Z. These are expressed in matrix form by are also approximately universal for quantum computation. b In unitary circuit models, one usually permits the introduction of fresh qubits into the circuit. In order to prevent the preparation of computationally expensive initial states, we will require that all fresh qubits be initially in some fixed pure state independent of the other qubits. Without loss of generality, to obtain a simpler correspondence to the operations of the 1WQC model, we will suppose that all fresh qubits are initially prepared in the |+ ∝ 1 √ 2 |0 + |1 state.

Parsimonious sets of gates
As well as being approximately universal for quantum computation, the gate sets described above have another useful property: Definition 2.1. A set S of unitary operations is parsimonious if every multi-qubit gate in S is diagonal, and if distinct gates in S acting on a common qubit commute if and only if they are diagonal. c Each of the gate-sets described above are parsimonious. For instance, it is immediately clear that {H, T, ∧ Z} is parsimonious; that B DKP and B RBB are parsimonious follows from the fact that J(α) † J(β) † J(α)J(β) = e iZα/2 H e iZβ/2 H 2 e −iZα/2 H e −iZβ/2 = e iZα/2 e iX(β−α)/2 e −iZβ/2 , (2.4) which is equal to 1 2 if and only if α = β.
The motivation for this terminology is that, for a "parsimonious" gate-set S and for any orthogonal basis {|φ 0 , |φ 1 } ∈ H 2 other than the standard basis, there is at most b The gates J(π/4) and J(−π/4) alone generate a dense subgroup of U(2) up to scalar factors: this is in fact shown by [17] (Section 4.5.2) in the proof that H and T are approximately universal for single-qubit operations. We include gates J(θ) for each θ an integer multiple of π/4 for both B DKP and B RBB in order to obtain a closer correspondence with circuits generated over {H, T, ∧ Z} in the construction of 1WQC procedures in later sections.
c The title of [3] predates this definition of "parsimonious" by four years, and does not refer to the concept we have defined here. However, the sets of unitary operations {J(θ), ∧ Z} θ∈R and {J(θ), ∧ Z} θ∈ π 4 Z described there are both parsimonious in this sense.
one gate in S for which the vectors |φ j are eigenvectors. Requiring that a get-set be parsimonious is a strong constraint: by definition, operations in a unitary circuit over such a set commute if and only if they are of the same "type" (they are either equal or inverse to each other), if they act on disjoint sets of qubits, or if they are both diagonal. This is evidently useful in determining when two quantum circuits are equivalent up to transposition of gates.

Stable-index tensor notation for unitary circuits
For a representation map R from unitary circuits to 1WQC procedures and a semantic map S, to show that S • R maps unitary circuits to equivalent circuits of the same (or lesser) complexity, we may attempt to show that S • R maps each circuit in dom(R) to one which is congruent d to the original (possibly up to a set of "trivial" simplifications). For this purpose, it will be useful to have a notation for unitary circuits which is easy to produce by an algorithm, in which irrelevant details such as the order of commuting gates are essentially absent. In general, this is a problematic task: however, we will be satisfied with a notation which solves this problem for parsimonious gate-sets, such as the sets of gates which we use in this article. One solution is to describe a notation whose meaning is invariant under permutation of any of the terms. An example of such a notation is Einstein summation notation ( [18], Section B5), in which (for unitary circuits on qubits) operations U are described as tensors, using their coefficients with respect to the standard basis on individual qubits involved in the circuit. We use superscripts for column-indices, and subscripts for rowindices: thus, we have (−1) ab e i(2b−1)θ/2 , (2.5b) ∧ Z r,s t,u = δ r,t δ s,u (−1) rs , (2.5c) and so on (where δ j,k is the Kronecker delta). In an expression involving multiple gates, two such tensors are identified as acting on a common qubit when the columnindex of one agrees with the row-index of another: the coefficients of the compound tensor are computed by summing over the range of the repeated index. The order of the multiplication of the tensors is then determined by the location of the index: an operation U strictly precedes another operation V if one of the row-indices of U matches a column-index of V . To represent tensor products of two operators, it suffices to juxtapose them with disjoint sets of indices. For example, given for a generic three-qubit operator U , two-qubit W , single-qubit operators V and T , and d For two unitary circuits, or two 1WQC computations, we will say that the computations are congruent if they differ only by transpositions of commuting operations (and by a possible relabelling of the qubits operated upon). state-vectors |φ , |ψ ∈ H 2 , we may equivalently write C a2,b3,c2 a0 = W b3,c2 b2,c1 V a2 a1 U a1,b2,c1 a0,b1,c0 T b1 b0 |φ b0 |ψ c0 .
(2.6b) Furthermore, the coefficients described on the right-hand side remain the same under an arbitrary permutation of the factors, and the equality remains true after an application of any (one-to-one) relabelling of the indices. However, while the order of the factors is not significant in Einstein notation, circuits which are equivalent up to rearrangements of commuting operations still give rise to tensor expressions which are not congruent via permutations of factors and index relabelling. This is because the tensor indices themselves fix an order of multiplication: for instance, although the operations ∧ Z a,b , ∧ Z a,c , and ∧ Z b,c commute (where the subscripts here indicate that the operations are performed on some pair chosen from three qubits named a, b, and c), the products b1,c1 ∧ Z a2,c1 a1,c0 ∧ Z a1,b1 a0,b0 , and (2.7a) give rise to expressions in Einstein notation which cannot be made the same by a relabeling of indices and re-ordering of terms.
In the case that two gates commute if and only if they are both diagonal, as in circuits generated from parsimonious sets of gates, we may resolve this problem as follows. We use a notation similar to Einstein notation, but in which in which an index can be repeated multiple times without summation, when the index represents a qubit in a part of a unitary circuit in which the standard basis is preserved for that qubit. e Stable index notation. Consider a unitary operator U on N qubits, whose eigenvectors are all of the form |s 1 ⊗ · · · ⊗ |s n ⊗ |Ψ for s 1 , . . . , s n ∈ {0, 1} and |Ψ ∈ H ⊗m 2 , where N = n + m. We may represent the non-zero matrix coefficients of U in the standard basis by U s 1 ,··· ,sn y n+1 ,··· ,y N x n+1 ,··· ,y N = s 1 , . . . , s n , y n+1 , . . . , y N | U |s 1 , . . . , s n , x n+1 , . . . , x N (2.8b) e If one interprets tensor indices as a random variables ranging over {0, 1}, whose value may be realized by a standard basis measurement, this corresponds to re-using indices when the value of that variable would be unchanged (or "stable") under some number of subsequent operations.
Terminology and composition conventions for stable-index notation. In an expression U s a d as defined by (2.8b), we call the indices s j stable, the indices d j deprecated, and the indices a j advanced. A product of such expressions is well-formed if each index is advanced at most once and deprecated at most once; there is no limit to the number of times an index may occur as a stable index. An index which is advanced in one term and deprecated in another is a bound index; otherwise it is free. We sum implicitly over all bound indices in a stable-index tensor expression, as in Einstein notation: we then form composite tensors V • U by matching advanced or stable indices of U to corresponding deprecated or stable indices of V . (If the indices of U and V are disjoint, this is a tensor product of U and V .) Example 1. The π /8 operation T is a single-qubit diagonal operator, and so has one stable index and no deprecated or advanced indices; the Hadamard operation H is a single-qubit non-diagonal operator, and so has no stable indices and one deprecated/advanced index each. We may then write their coefficients as The J( π /4 ) operation may be defined by composing these two operators, while the inverse of J( -π /4 ) is the other composition of these operators; we may write these compositions as Finally, the tensor product P = T ⊗ H has eigenvectors of the form |z ⊗ |ψ for z ∈ {0, 1} and |ψ ∈ H 2 an eigenvector of H: its coefficients may then be written as Identified systems. For operators U : acting on distinguishable qubits, we describe how U acts on these qubits by fixing an order of the qubits, where the advanced indices and deprecated indices of the qubits are presented in the same order.

Extension to general linear operators. For operators
where N and M may differ, a stable-index tensor expression for A will have advanced indices which do not have corresponding deprecated indices if M > N , or deprecated indices which do not have corresponding advanced indices if N > M . Then A describes an operation which either adds qubits to the input space, or discards qubits from the input space. (These may occur when A describes an isometric embedding, or a single-qubit measurement with a selected outcome, respectively.) We may represent a qubit which is added by an advanced index with no corresponding deprecated index (padding the sequence of deprecated indices by a space, dot, or similar placeholder), and similarly for deprecated indices representing qubits which are discarded.
Example 2. We may transcribe the operator expression given in (2.6b) as C a2,b3,c2 a0, · , · = W b3,c2 b2,c1 V a2 a1 U a1,b2,c1 a0,b1,c0 T b1 b0 |φ b0 |ψ c0 . (2.10) The order of the indices is purely conventional (in the same way that the order of the indices of C in (2.6b) is purely conventional); we could equally well define C above as C b3,a2,c2 · ,a0, · ; the change in the order of the qubits causes a corresponding change in the matrix representation of C. The adjoint of the tensor in (2.10) is given by C † a0, · , · a2,b3,c2 . A formal procedure for translating tensor notations such as in (2.6a), or involving operators U a,b,··· ,q labelled with the qubits that they act on, is easy to define: such a procedure is presented in Section A.2.1.
Example 3. Considering the same tensor C as in (2.10), in the special case that U has eigenvectors of the form |a |b |ψ for a, b ∈ {0, 1} and for some states |ψ ∈ H 2 , we may simplify the expression of C to The operators described by the expressions in (2.10) and (2.11) are identical in this case.
The following example illustrates the intuitive purpose of stable-index notation: by allowing stable indices to be repeated multiple times while remaining "free" variables, we also discard some redundant combinatorial information about the order of the product of operators.
Example 4. For generic unitary operators U ∈ U(2) ⊗n , we may define the operator (2.12a) Let V ∈ U(2) and W ∈ U(2) ⊗2 . For qubits a, b, c, and d, consider the circuits ∧ V a,d ∧ W a,b,c and ∧ W a,b,c ∧ V a,d (where the subscripts here denote the qubits on which the operators act). We may represent these two circuits with stable-index expressions respectively. Note that these are equivalent expressions, up to permutations of the factors: this may be regarded as being due to the fact that the operations ∧ V a,d and ∧ W a,b,c commute (i.e. the circuits are congruent).
In contrast to Einstein notation, while the numerical meaning of a stable-index tensor expression is invariant under permutations of the terms, information about the order of consecutive operations is not represented when these operations preserve the standard basis of qubits on which they both act. Circuits which are congruent up to the re-ordering of commuting gates may then give rise to "equivalent" stable-index tensor expressions in the following sense: 2. An isomorphism of stable-index tensor expressions S 1 and S 2 is a bijective relabelling λ of the index labels of one stable-index expression S 1 to those of S 2 , and a bijective mapping τ of terms of S 1 to those of S 2 , such that for any term U s1,...,sn a1,...,am d1,...,dm in S 1 (with n 0 stable indices, and m 0 each of deprecated and advanced indices including placeholders), there is a term in S 2 given by τ U s1, ...,sn a1, ...,am d1, ...,dm = U λ(s1), ...,λ(sn) λ(a1), ...,λ(am) λ(d1), ...,λ(dm) (2.13) (where placeholders on the left are mapped by λ to placeholders on the right). f Isomorphic stable-index expressions represent not only equivalent unitary operations (which follows from the implicit summation convention), but congruent circuit decompositions as well: Theorem 2.1. Let C 1 and C 2 be two sequences of unitary operators over a common gate set, and acting on the same number of qubits. If the stable-index tensor representations of C 1 and C 2 are isomorphic, then C 1 and C 2 are congruent via a re-ordering of commuting operators and relabelling of the qubits. Furthermore, if C 1 and C 2 are generated from a parsimonious set of gates, the converse also holds.
Thus, for unitary circuits constructed from a parsimonious set of gates, isomorphism of stable-index tensor expressions is equivalent to congruence up to rearrangements of commuting gates. This feature is the motivation both for this tensor notation, and for the interest in parsimonious sets of gates as in Definition 2.1. We only explicitly use advantage of this feature of this tensor notation in Section 3.5; however, other combinatorial properties of stable-index notation will frequently prove convenient in describing constructions of 1WQC procedures from the circuit model. The proof of Theorem 2.1 is provided in Section A.3.
While stable-index expressions lack any information about the order of operations which preserve the standard basis of the qubits that they act on in common, it is possible to retrieve information about the order of non-commuting gates, in order (for example) to determine how to actually perform such an operation as a physical transformation. As in Einstein notation, the order of non-commuting gates can still be determined from the indexing. Definition 2.3. For a stable-index tensor expression S, the index successor function f for S is the mapping defined on the indices δ of S which are deprecated but which have a corresponding advanced index α (corresponding conventionally to the same qubit), such f (δ) = α for each such δ and α.
Note that for a deprecated index v ∈ dom(f ), any term U which involves the index f (v) must be performed after any operation in the circuit acting on v (excepting U itself, if it is the unique term in which v and f (v) both occur). We may define: Definition 2.4. For a stable-index tensor expression S, the interaction hyper-graph for S is the hypergraph G on the set of indices in S, whose edges consist of those sets of indices which are acted on by some operation in C.
f Note that isomorphisms of stable-index representations may change the order of the terms as well as the index labels. That is, they are combinatorial homomorphisms, not just a relabelling of the indices in the terms of S 1 kept in the same sequence.
For any v ∈ dom(f ), the index f (v) is adjacent to v in this hypergraph. We may then use f and G to establish a partial order u v on the indices of S, which describes when an index u is deprecated before another index v, given an ordering of the terms which is consistent with an order in which the operations may be performed. We may define as follows. For two indices f (v), f (w) which occur in a common term, each must be deprecated strictly after the indices v and w in order for the term to describe a well-defined (acyclic) product of operators. If v ∼ w denotes the adjacency relation in and for any v ∈ dom(f ). We can then describe a pre-order g U V on the operations in S, where U V if U has an index u and V has an index v such that u v. We then have U V U if and only if either U and V are the same term, or different terms which act on common qubits but commute; if U V U , then U must occur strictly earlier than V . We may then obtain an order for the operations in S by finding a linear order which extends .
In the case of the gate-sets defined in Section 2.1.1, the operations all act on single qubits or pairs of qubits. The interaction hyper-graph G of (a stable-index expression for) a circuit over such a gate-set will then be a conventional graph. If we ignore singlequbit diagonal operations which add no information to the ordering of the indices, and note that the square of the two-qubit operations are in each case a product of local unitaries, we may even describe the circuit by a simple graph (without repeated edges or loops). This graph structure, and the ordering structures we have described above for circuits will prove convenient for analyzing constructions of 1WQC procedures.

The measurement calculus
The way in which computation is performed in the 1WQC model is very different from unitary circuits as we describe them in Section 2.1. In the latter case, computation is performed with interleaving non-commuting single and two-qubit unitaries without any classical control or intermediate measurement. In contrast, a 1WQC computation consists of an initial stage in which all of the (mutually commuting) two-qubit operations are performed, followed by a sequence of classically controlled measurements and (for procedures which produce a residual quantum state as output) classically controlled single-qubit unitaries. In this section, we briefly review the elementary operations in the 1WQC model and describe standard forms for procedures in the 1WQC model as a preliminary to describing 1WQC constructions for unitary transformations, essentially following the terminology and notation introduced by Danos, Kashefi, and Panangaden [10]. g A pre-order is a binary relation which is reflexive (x x for all x) and transitive (if x y and y z then x z), but with no further requirements. Partial orders and equivalence relations are both examples of pre-orders. An example of a pre-order which is neither an equivalence relation nor a partial order is the relation x y ⇐⇒ Re(x) Re(y) for complex numbers x and y.

Conventions for writing CPTP maps
In the 1WQC model, classical information is obtained via measurements which may in practise be destructive (e.g. as with photodetectors). Thus, it is usually preferable to describe 1WQC procedures by completely positive trace-preserving (CPTP) maps acting on density operators, where the input and output spaces of these operators may not be supported by the same set of qubits.
In order to better distinguish CPTP maps from linear operators on H ⊗N 2 , we will represent CPTP maps in either sans-serif (as in J ) or fraktur (as in J ) typeface. We also adopt the following additional notational devices: When a qubit v has been measured, we will represent the result by a bit s[v] ∈ {0, 1} whose value is only defined after the measurement.

Elementary operations of the 1WQC model
As in unitary circuit models, we define 1WQC computations as compositions of elementary operations. We define these following [10]. The initial stage of a 1WQC computation is the preparation of a large entangled state, which may be obtained by performing entangling operations on a collection of qubits prepared in the |+ state. Furthermore, the entangling operation which is performed may be described as a product of ∧ Z operations acting on distinct pairs of qubits. It will then be useful to define the operations for a state ρ S on a set of qubits S, where the subscripts on the right-hand sides indicate the qubits on which the operators act. For the map N v , we require that v / ∈ S, and obtain the system S ∪ {v} as output; for E vw , we require that v, w ∈ S, and obtain the same system S as output. We refer to N v as a preparation map, and E vw as an entangling map.
The single-qubit measurements we require will be with respect to orthonormal bases on "the XY plane" (of the Bloch sphere): that is, with respect to uniform superpositions of |0 and |1 which we denote by for angles −π < θ π. Using these states, we may define the measurement operators , (2.17) acting on a density operator ρ S on a set of qubits S. (Recall that s[v] is a classical bit storing the boolean measurement result. h ) We require that v ∈ S; the output consists of the system S {v}, ignoring the newly defined bit s[v].
We extend this notation in a simple way to describe how measurements are adapted according to previous measurements: we introduce the abbreviation for a classically controlled measurement performing either M α or M -α , depending on a boolean expression β = s[a] + s[b] + · · · representing the parity of some set of measurement results. i We refer to θ as the default (measurement) angle of the operation, and β a sign-dependency of v; we say that v has a sign-dependency on w when such an expression β depends non-trivially on s[w].
For 1WQC procedures which produce a residual quantum state as output (as we consider in this article), it is also necessary to adapt the final state depending on the outcomes of the measurements by using classically controlled single-qubit operations. For boolean expressions β describing the parities of some measurement outcomes, we may decompose these corrections into X and Z operations with the operators acting on a density operator ρ S on a set of qubits S which contains v. Finally, a purely classical operation which is useful in descriptions of 1WQC procedures is a classical bit-flip operation on a measurement result s[v]: 20) which acts on the bit s[v] which stores the result of a previous measurement. j This operation is also known as a signal shift operation, as it can be used to remove the h While we typically do not represent the classical bits used in operations in terms of density operators, we may do so when this is convenient for exposition.
i The calculus defined in [10] also admits the possibility of a measurement angle being modified by a possible addition of π, depending on a boolean expression (as with sign dependencies above). As this elaboration is not necessary for measurement-based simulation of unitary circuits, we omit it in order to present a streamlined description of how to construct a 1WQC procedure in "standard" form. j Such "shift" operators are usually not noted in accounts of measurement-based computation (with [10] being an exception), probably because they are simple operations on classical bits. However, in any implementation of quantum computers based on single-qubit measurements, shift operators may in practise be used to describe how parity expressions β are computed in the midst of computations. Thus, while much of the analysis of this article follows the convention of eliminating shift operations where possible, it seems productive to extend the sense of "standard forms" found in the literature to include shift operations between measurements. dependency on the result (or signal) of the measurement of some qubit a from the measurement of a later qubit v; the influence of the measurement on a is then accumulated into the classical bit s [v]. As a result, shift operators S β s [v] only occur after the measurement of the corresponding qubit v.

Elementary transformations of 1WQC procedures
A typical 1WQC procedure is a composition of many operations as described above.
In composing them, we may simplify them through simple transformations of the operations involved. At the same time, we wish to bring these expressions into a canonical form in which the entangling and measuring operations are separated into different phases of the computation (one of the motivations of the 1WQC model being to separate the tasks of creating entanglement, and maintaining control of the states of individual qubits). We now describe these transformations.
A well-formed 1WQC procedure prepares each qubit at most once, in which case that preparation is the first operation performed. We may then accumulate all preparation operations N v to the beginning of a measurement-based procedure. k Thus, for an operation Op S acting on a set of qubits S, we have (When v ∈ S, the expression on the left-hand side is not well-defined.) We may collect these preparation maps together and describe them as a single operation on many qubits: to this effect, we define the shorthand Similarly, because every operation aside from the preparation maps and entangling maps are either measurements (which are the last operation performed on any qubit), Pauli corrections (which we may easily transform by commutation with ∧ Z, a Clifford operation), or shift operations (which do not act on qubits), we may apply the following commutation operations to accumulate all of the entangling maps to the beginning of a 1WQC procedure (just after the preparation maps): and similarly for E vw Z β w .
(2.23d) (When p ∈ {v, w}, the expression on the left-hand side of (2.23a) is not well-defined, and the bit s[p] on the left-hand side of (2.23b) does not have a defined value.) As ∧ Z is a diagonal operation, we also have k Composition is performed from right to left, as with standard notations for unitary circuits; thus, the beginning of a 1WQC procedure is on the right-hand side of a sequence of operations.
As with preparation maps, we may collect these entangling maps together and describe them as a single operation on many qubits. Controlled-Z operators act symmetrically on pairs of qubits: in stable-index notation (Section 2.1.3), we have ∧ Z v,w = ∧ Z w,v . Then the order of the entangling operations and the order of the qubits acted on for any single entangling map is unimportant. As ∧ Z is self-inverse, we have E uv E uv = 1; then we may represent a product of entangling maps simply by an entanglement graph where the edge-set E(G) consists of all of the pairs of qubits on which entangling maps act.
We may also consider how to commute correction operations past other operations. First, note that commuting X β and Z γ operations on a state vector accrues at most a sign factor. Then, the corresponding CPTP maps commute: Similarly, X operations on any two qubits commute, as do Z operations. We may accumulate corrections of the same type on a common qubit: With respect to measurement operations, corrections on a qubit v may be interpreted as (classically controlled) changes of basis for the measurement on v; then, we can consider "absorbing" correction operations on qubits to be measured into the measurement operations. Consider a measurement in the |+ θ , |− θ basis for some −π < θ π. We have and similarly X |− θ ∝ − (-θ) . We may then incorporate X β v corrections into the basis of a subsequent measurement on v via the equation for a boolean expression β, using the notation defined in (2.18): more generally, we . We may describe the effect of Z corrections on measurements in a similar fashion: and similarly Z |− θ = |+ θ . For an arbitrary state ρ S on a set of qubits S including v, we then have Thus, Z corrections effectively exchange the roles of the states |± θ for measurements made in that basis. As this exchange is independent of any classically-controlled change of sign in θ, we then obtain There are some further simplifications to measurement operations which are possible when the measurement angle θ is a multiple of π /2 . We refer to these as Pauli simplifications, as such measurements are with respect to the eigenbases of the X or Y Pauli operators. For θ ∈ {0, π}, we have + (-θ) = |+ θ and Z |− θ ∝ − (-θ) ; thus, we have (2.32) so that we may ignore sign-dependencies in this case. For θ ∈ { -π /2 , π /2 }, we have X |+ θ ∝ Z |+ θ and similarly for |− θ , so that Thus, measurements in so-called Pauli bases may be performed without dependencies on previous measurements. In summary, we have the following relations which allow correction operations to be commuted past or absorbed into measurements: We will occasionally be interested in describing transformations of 1WQC procedures "without Pauli simplifications", in which case we do not use the relations given in (2.34f) and (2.34g). Finally, we consider the transformations which are possible by commuting shift operators. We may accumulate multiple signal shifts acting on a single measurement result: We may use this commutation relation to accumulate all shift operators at the right-hand side of a 1WQC procedure, after every operation acting on qubits: we refer to this as signal shifting. Conventionally, we may discard any classical measurement results when they are no longer required; thus, at the right-hand end of a 1WQC procedure, we may remove any signal shift operators which remain.

Standard forms for 1WQC procedures
Using the simplifications above, we may transform 1WQC procedures into "standard" orderings of the operations which are comparatively convenient for discussion, and are also of low operational depth: we now describe two different such forms.
As we have noted above, in any well-formed 1WQC procedure, it is possible to commute all preparation and entangling maps to the beginning of the procedure (on the right), and to propagate all correction operations to the end (on the left), possibly absorbing corrections into measurement operations while doing so. Some of the corrections will also induce shift operations just after the measurement into which they are absorbed; and we may do this in a uniform way without explicit knowledge (or despite uncertainties in) the values of the default measurement angles. This motivates the following: Definition 2.5. A 1WQC procedure P is said to be in standard form m if it can be decomposed as where N P is a product of preparation maps acting on some set of qubits P , E G is a product of entangling operations acting on pairs uv connected by an edge in the graph G, M consists entirely of measurement operations and shift operations (where any shift operation S * s [v] immediately follows the measurement M * v ), and C consists entirely of correction operations. The procedure of transforming a 1WQC procedure into such a form using equations (2.21), (2.23), and (2.34a)-(2.34e) is called standardization.
Note in particular that the process of "standardization" does not apply Pauli simplifications or signal shifting. For practical applications, it is probably preferable to perform Pauli simplifications, at least; but for the purposes of discussion it is useful to consider the case where such simplifications of expressions for 1WQC procedures are not applied.
By applying Pauli simplifications on measurements and signal shifting, it is possible to have equivalent 1WQC procedures which are each in standard form. Rather than attempt to characterize when such expressions are equal, it is useful to consider a form in which any variation of measurement dependencies has been removed. We may define such a form as follows: Definition 2.6. A 1WQC procedure P is said to be in normal form if it is in standard form, does not contain any shift operations, and any measurement operator with an angle θ ∈ π 2 Z has no measurement dependencies. We call the a procedure P in normal form the normalization of another P if we may obtain P from P by standardizing P , applying Pauli simplifications (2.34f)-(2.34g), and then performing signal shifting (2.36), removing the shift operators from the left after doing so.
While it may not be desirable to compute such expressions for the practical application of 1WQC procedures, obtaining the normalizations of 1WQC procedures will be useful for the analysis of this article.

Composability of 1WQC procedures
To perform universal computation, it is necessary to compose 1WQC computations: that is, to apply a second 1WQC procedure P 2 to the output system produced by another 1WQC procedure P 1 . Therefore, when composing 1WQC procedures P = P 2 • P 1 , we will be interested in restricting the qubits which are allocated in P 2 to be distinct from any qubits involved in P 1 , except those which P 1 produces as output.
It will be convenient at this point to introduce a combinatorial structure which partially describes a 1WQC procedure in order to define composability conditions (as well as to visually convey the structures which will be important in later sections). For a 1WQC procedure P, we may consider the information contained in P which is independent of ordering or of the particular measurement angles or outcomes: Definition 2.7. The geometry underlying a 1WQC procedure P is a triple (G, I, O), where G is the entanglement graph on the qubits of P specified by the entangling maps E vw in P, I ⊆ V (G) is the set of qubits which are not prepared by P, and O ⊆ V (G) is the set of qubits which are not measured by P. We refer to I and O as the input subsystem and output subsystem of P, respectively. (When a given graph G may be inferred from context, we may write I c = V (G) I and O c = V (G) O for the complements of these subsystems.) We will often illustrate geometries in the style shown in Figure 1. Such diagrams give a partial description of a 1WQC procedure, in which each qubit v ∈ I c is prepared, the entangling operations E vw implied by the edges vw ∈ E(G) are performed, and the qubits w ∈ O c are measured. However, the measurement order, measurement angles and dependencies, and any correction/shift operations are left unspecified.
Using geometries, we can express conditions for the composability of two 1WQC procedures in terms of a sense in which the geometries of these patterns may be "composed":   Figure 2: Illustration of the composition of two generic geometries for 1WQC procedures. Notice that composition in the diagrams is left-to-right, while the composition in written notation is right-to-left.

38b)
] is the symmetric difference of A and B. Two 1WQC procedures P 1 and P 2 are composable if their underlying geometries G 1 and G 2 are composable; the underlying geometry of the procedure P 2 • P 1 is then G 2 • G 1 . Figure 2 illustrates the composition of two geometries (and, by way of synecdoche, represents the composition of two 1WQC procedures).
In order to obtain a composition of two 1WQC procedures P 2 •P 1 , we may relabel the qubits involved in P 2 in order for the conditions of (2.38) to hold. From this point onwards, when we wish to compose two generic 1WQC procedures P 1 and P 2 , we will assume that they are composable in the sense above, eliding over the procedure of relabelling the qubits to be prepared which may be necessary.

The DKP and simplified RBB constructions
Having established stable-index tensor notation (Section 2.1.3) and a calculus of the operations used in a 1WQC procedure (Section 2.2), we may describe two constructions for approximately universal quantum computation in the 1WQC model. n The first construction we will refer to as the DKP construction, and is based on the work of Danos, Kashefi, and Panangaden [10] for the construction of 1WQC procedures in the absence of topological constraints on the interactions of qubits. The second construction is derived from the elementary constructions among those presented by Raussendorf, Browne, and Briegel [2] for producing 1WQC procedures, under the topological constraint that the entanglement graph be an induced subgraph of a suitably large rectangular grid; we call this the simplified RBB construction. By definition, the CPTP entangling map E vw performs controlled-Z operations on pairs of qubits: for a system S including qubits v, w, we have (2.39) We may implement zz and J(θ) operations in the 1WQC model with somewhat more elaborate procedures: where the subscript w/v in the latter denotes that it discards v from the input system and introduces a new qubit w. It is possible to show that the effects of these two 1WQC procedures are given by n The presentation of such construction presented here differs from the approach of [10]: while the latter proceeds by defining the composition of formal denotational semantics; we will adopt a somewhat more informal approach involving stable-index tensor notation. o The simplification implied in this title is twofold. Firstly, we use the zz operation given in (2.2b) to describe the construction of arbitrary operations, rather than the CNOT operation as in [2], page 5. While this will lead in practise to a constant-factor reduction in the complexity of some 1WQC procedures, this construction is clearly implicit in [2], and so we may attribute this construction to that work. Secondly, the "simplified" RBB construction omits the special-purpose constructions exhibited in Sections IV.A-F of [2], such as compact patterns for reversing an block of consecutive qubits, non-nearest neighbor CNOT operations, the quantum Fourier transform over Z 2 k for k 0, and addition circuits for Z 2 k . for arbitrary operators ρ S acting on a system including v and w, and Thus, the procedures E vw , Zz v,w , and J θ w/v given in (2.39), (2.40), and (2.41) respectively may be used to represent each of the operations in B DKP and B RBB . The geometries underlying these three 1WQC procedures are illustrated in Figure 3.

Corresponding stable-tensor indices to qubits in the 1WQC model
By the analysis of Section 2.3.1, we have a simple correspondence between unitary circuit operations described in terms of stable-index tensor expressions, and simple 1WQC procedures for effecting them: we have We may extend this correspondence also to account for the preparation of fresh qubits: as a preparation map N v simply prepares a qubit v in the |+ state, we may also write These parallels between operations on indices in stable-index expressions, and CPTP maps operations on qubits in the 1WQC model, also extend to syntactical considerations: • If we order terms in a stable-index expression from right to left according to an order in which the operations may actually be performed, by construction there cannot be any terms acting on an index v to the right of an operation such as J(θ) w v which deprecates v; nor operations to the left of v before an operation such as J(θ) v u in which v is advanced. Similarly, in a 1WQC procedure, operations acting on a qubit v are not permitted after it has been measured, nor before it has been prepared.
• In a stable-index expression for unitary circuits, stable indices (which are neither advanced nor deprecated) are those indices representing the a qubit whose configuration over the standard basis are unchanged by the operator acting on it.
Similarly, in a 1WQC procedure, a qubit which is neither added to the system nor discarded is in both the input and output subsystems of the procedure, and so is only acted on by diagonal operations (setting aside possible X operations), which similarly do not affect the diagonal terms of their reduced density operators.
Thus, the role of tensor indices (in a stable-index expression) in describing quantum states as distributions over the standard basis is analogous to the role of qubits in a 1WQC procedure which actually support quantum states. We may then obtain 1WQC procedures for unitary embeddings U by simply applying the correspondences in (2.44) to a stable-index expression of a unitary circuit. While the the constructions of [10] or [2] are not presented in precisely such terms, the DKP construction and simplified RBB constructions may be described as transliterating a sequence of gates in a unitary circuit into 1WQC procedures of the form J θ , E , and Zz, yielding a 1WQC procedure for the circuit as a whole. We present an explicit algorithm to do so in Section 2.3.
In the case of the DKP construction, in which the qubits of the resulting procedures are not subject to any topological constraints, application of the correspondence in (2.44) is an essentially complete summary of the construction. The case of the simplified RBB construction is similar, but is subject to topological constraints which we describe below.

Topological constraints in the simplified RBB construction
The simplified RBB construction is subject to the constraint that the entangled states which are used must be obtained from a cluster state: that is, a state in which qubits involved are arranged in a two-dimensional grid, and two qubits v, w are acted on with an entangling map E vw if and only if v and w are nearest neighbors in the grid. We will describe circuit constructions in which the indices of the stable-index representation satisfies the same constraints as required for the qubits in the cluster-state-based variant of the 1WQC model, which will allow us to employ the correspondence of (2.44) directly.
In the cluster-state-based (and original) variant of the 1WQC model, the only tool provided for obtaining graphs other than a rectangular grid is the removal of qubits from such a grid, via measurement in the |0 , |1 basis. Temporarily extending the set of operations defined in Section 2.2.2, we may define a M z v operation which performs a destructive single-qubit measurement of a qubit v in the standard basis, and produces a bit s[v] storing the result in the obvious manner. We may then show We may use this to remove all of the entangling maps E vw incident to a qubit v, propagating the measurement to the right until it is performed immediately after the preparation of v. If we remove the redundant preparation and measurement of v (and the corrections Figure 4: Illustration of the effect of removing vertices from a two-dimensional grid. This corresponds to the effect of performing measurement of select qubits in a cluster state, in the standard basis. Vertices correspond to qubits, with vertices in grey corresponding to qubits which have been measured; edges (or absence of edges) correspond to the presence (resp. absence) of entangling maps on adjacent qubits. induced by that measurement), this procedure has the effect of removing the vertex v from the grid. This is illustrated in Figure 4.
We may instead suppose (equivalently) that we may prepare any subset of the qubits in a two-dimensional lattice (omitting those qubits which we would subsequently remove as described above), and that two qubits are subject to an entangling map if and only if they are nearest neighbors in the grid. That is: we will merely require that the entanglement graph G is an induced subgraph of a rectangular lattice. Given this restriction on 1WQC procedures, we impose the corresponding restriction that the circuits which are accepted as input must have a linear nearest-neighbor topology.
To represent products of single-qubit gates as a 1WQC procedure, in the DKP construction as well as in the simplified RBB construction, we may compose patterns of the form J α w/v as in We may refer to such a procedure as a chain pattern. Note that in such a procedure, we require that the qubits v j for 0 < j < N to have degree 2 in the corresponding entanglement graph, having no neighbors aside from v j−1 and v j+1 . In the simplified RBB construction, the degrees of these qubits must be "enforced" by a representation in the grid, where every neighbor of these qubits v j in the grid (for 0 < j < N ) are removed except for the neighbors v j−1 and v j+1 . An illustration of such an embedding of a chain in the grid is illustrated in Figure 5. (Typically, such chain patterns would be embedded as a horizontal path through the grid, but as Figure 5 also shows, we may also employ more general paths in the grid.) Two logical qubits in a circuit which do not interact must be represented by (chains of) qubits in the grid which are separated by at least two edges; otherwise there will be entangling relations between them. Thus, we will represent products of single-qubit operations on independent qubits as non-adjacent horizontal rows of the grid. We may then use a vertical column of three qubits (as illustrated in Figure 3) to implement a zz operation between these non-adjacent rows, using a single qubit between the two rows to mediate the interaction. However, there are two technicalities which must be addressed: Adjusting for uneven chain lengths. Consider a decomposition of single-qubit operators U and V on distinct qubits, as products of J(θ) operators. If the number of terms in the two products differ, the ends of the corresponding chain patterns may lie in different columns. To operate on two chains with a zz operation as described above, we require that the ends of the chains representing each qubit lie in the same column. To achieve this, we may extend each chain by two or more vertices, as necessary, representing a decomposition of 1 as a product of J(θ) gates. We may define 1WQC procedures the geometries underlying these procedures are illustrated in Figure 6. In terms of the correspondence between stable-index expressions and 1WQC procedures described in Section 2.3.2, we have One can verify the stable-index products given on the right evaluate to 1 v2 v0 and 1 v3 v0 respectively; then both 1WQC procedures above simply transmit the state presented as input to its respective output system, using a chain of length either 2 or 3. By composing these procedures repeatedly, we can then implement a path of any length 2 in the grid, representing a sequence of operations which performs the identity 1 2 on a given qubit. Thus, whenever required, we may suppose that the paths in the grid corresponding to any two qubits are of the same length, regardless of the number of (non-trivial) unitary transformations performed on them.
"Forbidden" qubits adjacent to the mediating qubit in zz. Just as we require a distance of 2 between qubits in a 1WQC procedure representing non-interacting qubits in a unitary circuit, we require that the qubit a which mediates a zz vw operation is adjacent only to v and w; that is, we require that the qubits immediately to the left and right in the grid are not in the entanglement graph. Then we require a distance of two edges between any two instances of Zz performed on the same pair of rows. For vi zz vi,wi on a pair of logical qubits v and w, in which two zz operations are separated only by a layer of single-qubit operations of depth 1, we may perform the substitution (2.49) Mapping each J(θ) a d term to a procedure J θ a/d and each zz s,t term to a procedure Zz s,t , the distance between the qubits v i and v f resulting in the right-hand side is then at least 2 (and similarly for w i and w f ), as required.
These observations describe ways in which a 1WQC procedure for performing transformations must be "padded" by operations which perform the identity, in order to simulate a unitary circuit in the 1WQC model. We illustrate these observations in Figure 7 as sample constructions of 1WQC procedures. However, in order to obtain a uniform description of both the DKP and simplified RBB constructions, we may instead pad the stable-index representations for circuits with the corresponding products of single-qubit unitaries as a pre-processing stage. By construction, the indices of the resulting stable-index expressions will then satisfy the same constraints which are required for the qubits in a cluster-based 1WQC computation. We may perform such padding as part of an alternative procedure for constructing stable-index expressions for circuits: such a procedure is described in Section A.2.2.

Unified description of the DKP and simplified RBB constructions
Using the above techniques for the simplified RBB construction, we may obtain a unified procedure describing both the DKP and simplified RBB constructions, as follows.
Procedure for both constructions. Suppose we are given a unitary circuit C over the gate-set {H, T, ∧ Z} : as described in the previous section, we further require that C have a linear nearest-neighbor topology in the case of the simplified RBB construction.

Obtain a circuit in normal form.
Given a unitary circuit C generated over the gate-set {H, T, ∧ Z}, we obtain an equivalent circuit as follows. We cancel pairs of ∧ Z gates which act on common pairs of wires, and which are separated only by gates with which they commute (i.e. T operations and operations acting on other wires). In the case of the simplified RBB construction, we convert the circuit to the (essentially equivalent) gate-set {H, T, zz} by applying the substitution to all ∧ Z gates; no such translation is required for the DKP construction. We then commute all T and T † operations to the left (simplifying them using the identity T 8 = 1), collecting them in each case either at the end of the circuit, or immediately preceding a Hadamard operation the same qubit.
We call the resulting circuit C the normal form of C; this circuit consists of a product of operations ∧ Z and HT r (for various r ∈ Z) for the DKP construction, and zz and HT r for the simplified RBB construction.

Convert the circuit to a stable-index expression in the gate
Having obtained C , we apply the substitutions for each consecutive block of T operations, applying the right-hand equality for blocks of T operations at the end of the circuit. These substitutions yield an equivalent representation of the same operation using the gate-set B DKP or B RBB , depending on whether the circuit makes use of ∧ Z or zz gates. As we do so, we a0 a3 Figure 7: Illustration of the constraints on composition of the pattern Zz in the setting of an induced subgraph of the grid. Grey dots represent vertices which have been removed from the grid. Composition is illustrated with overlapping tiles, whose shapes represent spatial constraints imposed by the operations.
(a) The geometry itself, together with the "forbidden" neighbors of the mediating qubit a.
(Broken lines between the dots represent the edges removed as a result of removing these vertices.) (b) A composition of Zz procedures with J θ procedures, corresponding to a circuit in which two zz gates are separated by two J(θ) operations. The bottom row of the corresponding 1WQC procedure is padded with a Id 2 procedure to synchronize the lengths of the rows. In this case, a single vertex is a common forbidden neighbor of each mediating qubit.
(c) A composition of Zz procedures with J θ procedures, corresponding to a circuit in which two zz gates are separated by one J(θ) operation on either wire. The forbidden neighbors of the mediating qubits force both rows to be padded with identity operations.
convert the resulting circuit into stable-index notation: we use an algorithm such as that of Section A.2.1 to do so for the DKP construction; for the simplified RBB construction, we may use instead the procedure of Section A.2.2 to impose additional topological constraints on the resulting circuit. We call the resulting stable-index expression for the circuit C .

Translate individual operations into the 1WQC model.
In C , note that each single-qubit J(θ) operation deprecates one index and advances another, and that all of the two-qubit ∧ Z or zz operations act "stably" on their indices. We may then define a mapping Φ from stable-index expressions of operations in the gate-set B DKP ∪ B RBB (and introduction of fresh qubits in the |+ state) to 1WQC procedures involving J θ , E , and Zz operations as follows: where we identify the labels of indices of the stable-index tensor expression with labels for qubits in the 1WQC procedure. We then extend this map Φ homomorphically to products of such terms.
4. Obtain a normal form for the resulting 1WQC procedure. We standardize (Definition 2.5) the 1WQC procedure Φ(C ), and then apply Pauli simplifications and signal shifting to obtain a procedure in normal form (Definition 2.6).
By construction of C in the above procedure, each index is advanced at most once and deprecated at most once; thus, each qubit in Φ(C ) is produced in the output of an operation (or "allocated") at most once, and removed from the input of an operation (or "discarded") at most once. Furthermore, by order of the terms in C , the operation which allocates a qubit v is the first which acts on v, and the operation which discards v is the last acting on v. The resulting 1WQC procedure is therefore well-formed. By the analysis of Section 2.3.1, we may easily show in either case that Φ(C ) is a CPTP map which performs the same unitary transformation as described by C , modulo an identification of each input qubit with a corresponding output qubit. Then the final procedure produced performs the same transformation as the circuit C. We refer to this procedure as the simplified RBB construction for 1WQC procedures when we require that C be linear nearest-neighbor and when we perform the substitution of (2.50), and the DKP construction for 1WQC procedures when we do not impose the added constraint or perform the substitution. (For the sake of brevity, we will often refer to this construction simply as "the RBB construction", as we do not consider any constructions using the special-purpose 1WQC procedures in Section IV of [2].) Run-time complexity. Both the DKP construction and the (simplified) RBB construction can be performed efficiently in the size of the input circuit. In both cases, let k be the number of qubits which C acts upon, N be the number of one-qubit gates, and M be the number of two-qubit gates: if we consider only those circuits which act non-trivially on each qubit, we may assume that k N + M for simplicity. We may then show that the run-time complexity of the DKP construction is O((N + k)M ), and of the RBB construction is O(N M (N + M )), in each case bounded by the complexity of obtaining a 1WQC procedure in normal form. (The difference in complexity between the two constructions may be traced to the difference in the procedures to obtain the stable-index expression C for each, and hence to the single-qubit gates which are added in the RBB construction in order to impose the desired topological constraints on the indices of the stable-index expression.) An explicit analysis of the complexity of these constructions is presented in Section B.2.

Partial constructions
As a final remark on constructions of 1WQC procedures, it will be useful to describe partial versions of the DKP and (simplified) RBB constructions. We define the DKP construction without normalization p and the RBB construction without normalization to be, simply, the 1WQC procedure constructions which result from omitting the Pauli simplifications and signal shifting stages from the phase of obtaining a 1WQC procedure in normal form. A procedure produced by such a partial procedure may then indicate sign dependencies for a measurements whose default angle is an integral multiple of π /2 , and they may have signal-shift operators immediately following measurements.
In a practical setting, provided sufficiently fast control of the classical memory storing the measurement results s[v] for all qubits v in a 1WQC procedure, it is likely that a more useful procedure would be an intermediate construction to the constructions with or without normalization, in which one performs Pauli simplifications but leaves the shift operations in place. The purpose of identifying the partial constructions without normalization above is to obtain a simplified analysis of measurement dependencies, which may be used as a starting point for the analysis of the "complete" constructions.

Semantic maps
We may now consider the roles of the DKP and (simplified) RBB constructions as defining representations of unitary circuits in the 1WQC model. Both constructions make use of a simple process of translating unitary circuits from a gate set including J(θ) gates and a single two-qubit diagonal operation into corresponding 1WQC procedures: this will induce a graph structure which is dominated by vertex-disjoint paths, with supplemental vertices and edges linking pairs of paths. After standardizing the 1WQC procedures in the course of these constructions, the additional structure which might arise from measurement dependencies or the grouping of operations is lost or obfuscated; preparation maps and entangling operations become dissociated from individual measurement operations, and corrections will in some cases be absent entirely after absorbing them into measurements and performing Pauli simplifications.
Given a 1WQC procedure, in which no additional information is encoded e.g. in the labels for the qubits, we may ask whether we can efficiently identify whether a 1WQC procedure is one that may be produced by the DKP or the RBB constructions. In the case where the input and output subsystems of the procedure are of the same size, we answer this question in the affirmative. We do so by considering the combinatorial structures which are present in the geometries (Definition 2.7) of the 1WQC procedures which result from these constructions. We then define a map S from 1WQC procedures to circuits in the {H, T, ∧ Z} model which serves as a semantic map (in the sense of Definition 1.1), for the representation maps R DKP and R RBB corresponding to both the DKP and simplified RBB constructions restricted to input circuits which are unitary bijections.

Measurement dependencies arising in the constructions
The DKP and RBB constructions produce 1WQC procedures from circuits by transforming gates such as J(θ), ∧ Z, and zz into simple 1WQC subroutines, via the mapping Φ defined in (2.52). It is instructive to consider the structures described by the sign-and bit-dependencies which arise from composing such 1WQC subroutines, using the partial constructions without normalization described in Section 2.3.5.

Measurement dependencies and index successor functions
For a unitary circuit C consisting of gates from the set B DKP = {J(θ), ∧ Z} θ∈ π 4 Z , consider the last gate J(θ) performed in the circuit. (If there is more than one such gate which may be performed in parallel, we may choose an arbitrary one.) We may decompose C into circuits C C , where C consists of this final J(θ) gate acting on some qubit u, and any controlled-Z operations acting on u which follow it;C consists of the remaining operations of C. We may refer to C as a star circuit q Consider the translation of a star circuit C into the 1WQC model via the map Φ defined in (2.52), and standardizing the resulting procedure (Definition 2.5). Writing C in stable-index tensor notation (Section 2.1.3), and letting W be the set of qubits w = u on which C acts, we have q These star circuits are similar to, but have a different orientation to, the circuits described in Section III B of [12]. This different choice of construction will facilitate the analysis of combinatorial structures later in the article: these are used in much the same way as the circuits arising from "star patterns" do in [12].
where on the last line we commute the entangling operations to the right. In the final 1WQC procedure, the qubit u is distinguished as the only qubit measured, and v is the only qubit prepared; v is also the only qubit subject to an X s[u] v operation, with every other qubit (aside from u) being subject to a Z s[w] w operation. The fact that u and v are measured and prepared qubits (respectively) in Φ(C ) above is a direct result of the fact that they are deprecated and advanced indices (respectively) in the stable-index expression given for C . In particular we have v = f (u), where f is the index successor function (Definition 2.3) of C ; thus, the corrections may be described in terms of the index successor function of the original circuit, and the entangling operations.
We may make similar observations for the (simplified) RBB construction as we have for the DKP construction above. Motivated by the realization of the operator where we define the operator P = + π/2 | , and for a constant proportionality factor (as illustrated in (B.4) in Section B.1.1). In the stable-index expression on the right, the index successor function f remains the same (as the indices a are advanced without corresponding to any deprecated index, and vice versa), but the interaction graph G is transformed essentially by subdividing every edge arising from a zz gate by introducing a new vertex in the middle (representing the mediating qubit with the index a).
Then, consider the translation of zz v,w to a 1WQC procedure via Φ, if we extend the successor function f to a functionf for which we definef (a) = a, while we have noX s[a] w operations, we have aZ s[a] w for every qubit w adjacent to a =f (a) in the entanglement graph.
In each case, either the index successor function (or a modest extension of it) for a stable-index description of a simple unitary circuit can be used to characterize the corrections performed in a corresponding 1WQC procedure. We may then consider the result of translating a composition of such simple circuits, where each C (j) is a star circuit as above, extending the definition to also include individual zz operations as described in (3.2). Commuting all of the preparation and entangling operations to the right, we obtain the same dependency of the corrections on the successor function (extended for each zz gate as described above): we obtain Z s[u] w corrections for each qubit in the interaction graph which is adjacent tof (u), either due to the commutation of entangling maps past X s w operations arising from Zz procedures.

Efficiently verifying consistency of measurement dependencies
Based on the descriptions of the dependencies arising in the DKP and RBB constructions without normalization, we may characterize the dependencies of operations which arise in the two constructions with normalization, and show that verifying that such dependencies hold in a 1WQC procedure P can be used as a subroutine to certify that P performs a unitary transformation. Following the remarks of the preceding sections about the constructions without normalization, we characterize the dependencies arising from the DKP and RBB constructions as follows.
whose domain is the set of indices ofC which are deprecated.
Then (1 − T ) is invertible modulo 2, and the dependencies inP between qubits v, w ∈ V (G) may be characterized in terms of F and T as follows: • w has a sign-dependency on v if and only if v operations commute with entangling maps, we obtain no further corrections depending on u if we commute the entangling maps of P 0 to the right. Similarly, P 0 contains an X s [u] v operation if and only if v = f (u) = u, which must arise from a J θ v/u procedure. Any operation on v in P 0 which is not a part of the J θ v/u procedure must come after it, every entangling map acting on v must occur after the X s[u] v operation except for the E uv map occurring as a part of J θ v/u . Commuting all of the entangling maps in P 0 to the right, we then induce Z s [u] w operations for all w ∼ v such that w = u, as described in (2.23c). Thus, commuting all preparation and entangling maps in P 0 to the right yields an equivalent procedure P 1 , in which for there is an X s for some linear order satisfying the conditions of (2.14) for the extended successor function f . Commuting correction operations in P 1 to the left, we obtain another procedure P 2 , in which the same corrections hold as above for w ∈ O. For w ∈ O c , there is instead a sign-dependency on v if and only if w = f (v) = v, and a bit-dependency on v if and only if w = v and w ∼ f (v). Note that the procedure of producing P 2 from P 0 is precisely that of standardizing P 0 : thenP may be obtained by normalizing P 2 .
Consider how the process of normalization effects dependencies of qubits w on a particular qubit v.
(i) The effect of Pauli simplifications are to remove sign-dependencies from qubits in A X according to (2.34f), and to change them to bit-dependencies for qubits in A Y according to (2.34g). As signal shifting does not introduce sign-dependencies for measurements where none previously exist, the measurement of a qubit in A X ∪ A Y will not have any dependencies on previous measurements in a procedure in normal form.
Applying Pauli simplifications to P 2 will yield a 1WQC procedure P 3 : then P 3 will have no sign-dependencies for qubits v ∈ A X ∪ A Y , and will have signal shift operators S s[u] s [v] for any qubits v = f (u) ∈ A Y , in addition to the shift operators in P 2 . We may describe the sign dependencies which remain in P 3 by a square matrix over V (G), with a 1 in the row v and column w for v, w ∈ V (G) when w has a sign-dependency on v. Accounting for the removals of sign dependencies of P 2 for qubits w ∈ A X ∪ A Y , the procedure P 3 then has a sign-dependency of w on v when w = f (v) / ∈ A X ∪ A Y . The matrix described in this manner is then the matrix F in (3.6a).
For the sake of simplicity of discussion, we will assume that the shift operators are not accumulated with any pre-existing shift operators using the relation of (2.35). However, it is important to note that the shift operators arising from Pauli simplifications will not cancel any operators existing originally in ; in turn, the resulting operation may be transformed into one depending also on qubits u for which D has arcs v → u, ranging over the qubits v of the previous step; and so on. The effect is then of transforming bit-dependencies corresponding to arcs in this digraph D (arising from signal shifts) into measurement and correction dependencies corresponding to directed walks in D.
We may represent this digraph as an adjacency matrix over V (G), with a 1 in the row v and column w for v, w ∈ V (G) when P 3 contains a shift operator S s [v] s [w] , and 0 if not. Considering the shift operations in P 3 which are also present in P 2 , there will be such a shift operator whenever w = v and w ∼ f (v); and as a result of Pauli simplifications, there will be such a shift operator when w = f (v) and w ∈ A Y . As there are no other sources of shift operators, these are the only positions in which the adjacency matrix will be non-zero. The adjacency matrix described is then the matrix T in (3.6b).
As the ordering (used in (3.7) to fix the order of operations) is a linear order, the digraph D described by the shift operations is acyclic: for any standard basis vectorê w ∈ Z V (G) 2 , the column-vector Tê w is supported only on indices v w. Then we have T r = 0 for some r |V (G)|, so that T is nilpotent (and in particular has no +1 eigenvectors). Consequently, the operator 1 − T is invertible.
We may then express the cumulation of dependencies for each operation in P 3 due signal shifting as follows. For two qubits v and w, the number of walks in D from w to v of a fixed length 0 is given byê v T ê w : the total number of walks of any length from w to v in D is then If we represent the dependencies of operations in terms of boolean column vectors, we may then represent the effect of signal shifting by multiplying a vector of dependencies by (1 − T ) −1 computed modulo 2.
To determine the classical dependencies of each operation inP, it suffices then to identify the dependencies of the same operations in P 3 , represent these as a vector , and compute (1−T ) −1 d. We may characterize the classically controllable operations and their dependencies in P 3 as follows: • As we have noted above, the sign-dependencies for qubits w ∈ O c are represented by the coefficients of the matrix F , where F vw = 1 if and only if w has a sign dependency on v in P 3 . Then w has a sign dependency on v inP if and • For w ∈ O, there is no measurement into which corrections on w may be absorbed, and so the corrections in P 3 are the same as in w operation in P 3 if and only if F vw = 1, and a Z s [v] w operation if and only if T vw = 1. It follows that after signal shifting, the resulting  Algorithm 1 describes an algorithm which, provided a 1WQC measurement pattern P in normal form and a candidate for the extended successor function f for an originating circuit, tests if the dependencies of P are consistent with the dependency conditions described in Theorem 3.1.
If we are presented with a 1WQC procedure P in normal form which is not known to be a result of the DKP or RBB constructions, we may only verify whether these conditions hold relative to some "candidate" successor function f . How such a function f may be constructed for a 1WQC procedure P is the subject of Section 3.2.
Run-time analysis of Algorithm 1. We bound the run-time of Algorithm 1 as follows. In the following, we let N be the number of operations in P, and for the geometry (G, I, O) underlying P, we let n = |V (G)|, k = |O|, and m = |E(G)|. We assume that f can be evaluated in constant time, using an array structure. We assume that the dependencies of operations  Let F be a matrix depending on f as in (3.6b). 3 LetT ← (1 n − T ). 4 For each measurement or correction operation Op in P, do: be the indicator vector for β. 7 IfT d = Fê w , then return false.

Conditions on candidate successor functions
In the preceding section, we characterized the dependencies in the DKP and RBB constructions in terms of an extended index successor function, from a stable-index representation of the original circuits. This leaves open the question of how such a successor function may be obtained. We examine this problem using the observations made above about the dependencies arising from circuit decompositions without normalization. We show that these dependencies can be captured in each case by a modification of the flow conditions formulated by Danos and Kashefi [12]. This modification will provide the "candidate successor functions" which we require for the verification procedure of Algorithm 1, and which lead to important structural constraints on the geometries (G, I, O) arising from the DKP and RBB constructions.

Measurement ordering from index successor functions
As we described in Section 2.3.2, there is a correspondence between the "deprecation order" of indices as described in (2.14), for a stable-index expression for a circuit C over B DKP ∪ B RBB , and the order of operations in a well-formed 1WQC procedure Φ(C). This correspondence may be attributed to a sense in which measuring qubits in a 1WQC procedure simulates the summation over indices in a tensor expression, and thus to evaluating a unitary circuit applied to a state as a sum over computational paths. When applied to a completely specified pure state, every deprecated index in a stable-index expression becomes bound, in which one evaluates the result by summing over all deprecated indices. When these indices are represented by qubits in a 1WQC procedure, one may simulate this summation by measurement of qubits v with respect to the |+ θ , |− θ basis.
• Consider a measurement arising from a J θ procedure, corresponding to summing over the deprecated index of a J(θ) operation. If the |+ θ state is measured (i.e. if s[u] = 0), the resulting transformation corresponds to summing over the |0 and |1 components, weighted with the with the relative amplitudes phases as those associated with the J(θ) operation which deprecates the corresponding index.
• For measurements arising from a Zz v,w procedure, we measure a mediating qubit a in a fixed basis |± π/2 . Again, a measurement result of |+ π/2 corresponds to summing over an auxiliary index a in a stable-index expression: the relative phases of the |0 and |1 components correspond to those of the projection operator P .
In either case, if the measurement yields the |− θ result instead, the corrections and measurement adaptations are chosen precisely to effect the same transformation which would have occurred for the |+ θ result, by influences on the measurement angles due to sign-dependencies or the measurement results due to bit-dependencies on v. s Thus, we may interpret the sign-and bit-dependencies in such 1WQC computations as potential "influences" in evaluating the summation of deprecated indices. By construction, the measurements are chosen in such a way that the tensor which is produced at the output is related to the tensor at the input by a unitary circuit: the amplitudes arising from each measurement are a function of at most two boolean indices, where the two-index dependencies are signs encoded by the entanglement graph, and whose single-index dependencies are given by the choice of measurement basis. This may be regarded as indicating that a 1WQC procedure where such an ordering is possible has a "circuit-like structure".
A measurement order which corresponds to a "deprecation order" for indices in a circuit C as in (2.14) is governed by the index successor function of C. An extended index successor function as defined in Definition 3.1 has the effect of imposing constraints on the deprecation of the mediating indices a arising from the substitution of s Bit-dependencies, as represented by shift operators S * s [v] immediately after measurements, may be informally interpreted as flipping the bit s[v] to produce "the result which would have been measured if an appropriate Z correction had been performed prior to measurement". As the measurement results are often maximally random whether or not such corrections are performed, this is a somewhat counterfactual interpretation, but one which could perhaps be given an ontological foundation in terms of hidden variables. (3.2) for zz gates, which may be interpreted as creating a well-defined notion of when the zz operation is performed. By construction, 1WQC procedures arising from the DKP and RBB constructions do admit extended successor functions: this can be used to define the domain of a semantic map for these constructions.

Flow conditions
The ordering in (2.14) was first formulated by Danos and Kashefi [12], for qubits in the 1WQC model rather than tensor indices, to describe dependencies arising in the DKP construction without normalization. We may formulate these properties in terms of the geometry of a 1WQC procedure without reference to the DKP construction as follows: Examples of geometries with and without flows are illustrated in Figure 8 and Figure 9, respectively. The function f and the partial order capture the essential structure of the dependencies in the DKP construction without normalization: f represents the mapping of qubits to their successors (corresponding to an index successor function for a circuit), and the partial order represents a suggested order in which the qubits may be measured (or the tensor indices deprecated).
Danos and Kashefi show that any geometry which has a flow underlies some 1WQC measurement pattern which can be obtained by the DKP construction, t and which therefore performs a unitary transformation: performs a unitary transformation.
The proof presented in [12] is essentially by showing that applying the map Φ defined in (2.52) to a suitably constructed circuit yields the 1WQC procedure above. If we can construct a flow for a geometry (G, I, O), we may then use the same circuit construction as in [12] to construct a candidate circuit whose representation as a 1WQC procedure (via the DKP construction) has the same geometry. We may then verify whether the dependencies of a 1WQC procedure are consistent with one arising from the DKP construction, using Algorithm 1.

Extending to modified flows
By considering the dependencies described in the proof of Theorem 3.1 following (3.7), we may formulate a similar combinatorial condition which generalizes flows, and also captures the dependencies arising in the (simplified) RBB construction without normalization: u .
The function f again corresponds essentially to an (extended) successor function for stable-index expression of a unitary circuit, and again represents an order of measurement corresponding to an order in which the indices of stable-index expression are deprecated. The set M represents qubits whose measurement angles are π /2 : these are qubits which might be mediating qubits a in the Zz v,w procedures. We may recover the definition for flows in Definition 3.2 if we either set M = ∅, or simply require that v = f (v) for all v.
The following generalization of Theorem 1 of [12] to modified flows provides the basis for the approach we will take to define semantic maps for the DKP and RBB constructions: performs a unitary transformation, provided θ u = π /2 for every u ∈ M . Furthermore, for 1WQC procedures P arising from the DKP or (simplified) RBB constructions, the geometry (G, I, O) underlying P (together with the set M of qubits with measurement angle π /2 ) has a modified flow.
Proof. We may obtain a procedure as above using a mapΦ extending Φ, as follows.
where we define the d qubit operator We may define the 1WQC procedure Zzz d analogously to Zz, as follows: (3.14) by an analysis deferred to Section B.1.1 (see also Section 3.8 of [19]), we may show for a system S including the qubits v j , but excluding a. For a stable-index expression for gates in B, we may then define: extending this to unitary circuits overB in the usual manner. For a star circuit C = ∧ Z v,w1 · · · ∧ Z v,w k J(θ u ) v u as in (3.1), we then havē after commuting the entangling maps to the right, where G is a star graph with center v and edges from v to each w j and to u; we may define a similar star graph for the entangling maps of Zzz d v1,...,v d so that we may writē for such a star-graph. Given a tuple (G, I, O, M ) with a modified flow (f, ), define the circuits C u for u ∈ O c via the following stable-index expressions: We also define a circuit CĨ by we may describe the ∧ Z operations in this circuit by the induced subgraph G[Ĩ], wherẽ I = V (G) img(f ). Consider the circuit C described by the stable-index expression consisting of the concatenation of these circuits. Placing the circuit CĨ at the beginning, and ordering the the remaining circuits C u in a linear order extending , we obtain an expression in which operators with index u = f (u) occur no later than any operator involving f (u) or w ∼ f (u), and any operator with index u = f (u) occurs before the indices w ∼ u are deprecated. Thus, applying the homomorphismΦ to each sub-circuit C u in C yields a well-formed 1WQC procedure where G u is the star graph for each qubit u as described above, and the congruence arises from commutation of preparation maps and entangling maps to the right of each term in the ordered product. Note that for every edge vw ∈ E(G), we have either v, w / ∈ img(f ), or one of the vertices (without loss of generality, v) is of the form f (u) for some u ∈ O c . In the former case, vw corresponds to a ∧ Z operation in CĨ , and thus to an entangling operation inΦ(CĨ ); in the latter case, we have w ∼ f (u), in which case vw corresponds to an entangling operation in the star-graph G u and thus to an entangling operation in Φ(C u ). Conversely, every entangling operation in P above corresponds to some edge in G, by construction; the geometry underlying P is then (G, I, O). Note also that the individual operations in P and the procedure described in (3.12) are identical, except that corrections of the form Z s [u] f 2 (u) do not occur in P; commuting all the preparation and entangling maps to the right of the expression, these are induced by commuting op- f (u) . Thus, (3.12) is the result of performing this commutation to P; the 1WQC procedure in (3.12) thus performs the same unitary transformation as C.
Finally, we may show that every geometry underlying a 1WQC procedure obtained from the DKP or (simplified) RBB constructions has a modified flow. Consider a stable-index expression C for a circuit over the gate-set B DKP ∪ B RBB , whose terms of C are ordered according to the order of performance in the circuit. Let f be the extended successor function of C, and be the order in which the indices are deprecated in C. Then f will be a mapping from the deprecated indices to the advanced indices, and (f, ) satisfies (2.14) by construction. If (G, I, O) is the geometry underlying the procedure Φ(C), and M is the set of qubits with measurement angle π /2 , by construction (f, ) will be a modified flow for (G, I, O, M ); as the DKP and RBB constructions both involve producing such a stable-index expression C, and the process of normalizing a 1WQC procedure leaves the geometry invariant, the result holds.
The foregoing proof not only demonstrates that a 1WQC procedure as in (3.12) performs a unitary transformation, but gives a description of a unitary circuit performing the same transformation. This will form the basis of a similar construction in Section 3.4 for constructing circuits without reference to corrections or measurement dependencies.
The proof above also describes a construction of 1WQC procedures based on a gate-set which subsumes B DKP ∪ B RBB , containing operations acting on arbitrarily many qubits. The extension to this gate-setB from B DKP and B RBB corresponds to the way in which modified flows extend the pattern of dependencies found in either the DKP or RBB constructions without normalization; the inclusion of the operators zzz d for d > 2 is essentially a byproduct of the lack of further constraints on the definition of modified flows.

The natural pre-order, and uniqueness in the case |I| = |O|
Following [13], for any geometry (with or without a modified flow) and for any function f : O c −→ I c , we may consider an ordering satisfying the conditions of (3.9) or (3.11) as follows: for all v ∈ O c and w ∈ V (G).
Note that the conditions of (3.22) are exactly the conditions (3.11c) and (3.11d) for modified flows. The definition of the natural pre-order then relaxes the condition that be a partial order, i.e. that is antisymmetric. If the natural pre-order happens also to be a partial order, then (f, ) is a modified flow. By the definition of the transitive closure, any pre-order satisfying the conditions of (3.22) must also contain the relations of the natural pre-order ; then if is not antisymmetric, there can be no antisymmetric relation satisfying the modified flow conditions with f .
Because of the distinguished nature of the natural pre-order, we may prove a useful uniqueness result for modified flows: Then the only function f for which (f, ) may be a modified flow is the identity function on O c .
Otherwise, suppose that I = O, and consider two functions f, g : O c −→ I c such that f (v) = v only for v ∈ M , and similarly for g. Note that the natural pre-order of f can only be anti-symmetric if there are no cycles of the form v ≺ f (v) ≺ · · · ≺ f k (v) = v; thus, we require that f have no such cycles for k > 1, and again similarly for g.
Suppose f and g differ, and let u 0 ∈ O c be some vertex for which f (u 0 ) = g(u 0 ). Letg : I c −→ O c be the inverse function of g: we may recursively construct an unbounded sequence of vertices u j for j ∈ N by defining u 1 = f (v j ), and for j 1. Note that dom(g) = I c = img(f ) and dom(f ) = O c = img(g); then this sequence is well defined for all j 0. We may also show that u j+1 = u j−1 for each j 1 by induction, as follows. Suppose that u j+1 = u j−1 for some particular j 1: in which case we have u j+2 =g(u j+1 ) =g(u j−1 ) = u j , by the injectivity of g.
• Suppose that u j+1 = f (u j ) =g(u j ). Because f is injective, we have u j+1 = f (u j ) = u j if u j = u j−1 ; and as u j+1 = u j−1 , at least one of the inequalities u j+1 = u j or u j = u j−1 must hold. Thus, we have u j+1 =g(u j ) = u j in any case; by the injectivity ofg, we then have u j+2 =g(u j+1 ) =g(g(u j )) = u j by the acyclic property of g.
As V (G) is finite, there must be integers N, N such that N < N and u σ(N ) = u σ(N ) : then we have u σ(N ) u σ(N +1) · · · u σ(N ) = u σ(N ) , where u σ(N ) = u σ(N +1) as noted above. Then is not antisymmetric. If on the contrary (f, ) is a modified flow, and (g, ) is also a modified flow for some partial order , it follows that f = g. Thus (G, I, O) and M have at most one modified flow (f, ), for the natural pre-order of f .
The uniqueness of a modified flow (f, ), when we require that be the natural pre-order of f , will play an important role in describing a semantic map for the DKP and RBB constructions. Different "flow-functions" f correspond to different sets of dependencies in a 1WQC procedure: provided a procedure P in which some of the dependencies have been obfuscated or eliminated altogether by Pauli simplifications and signal shifting, it may be difficult to determine whether there exists a successor function which describes the actual dependencies which are present. This problem is simplified if we are promised that there is at most one successor function f yielding a modified flow (f, ): we may simply attempt to construct f , and determine whether the dependendices in P are consistent with those described by f .

Decompositions of geometries
The proof of Lemma 3.3 suggests an approach to determining when a tuple (G, I, O, M ) has a modified flow, by means of a decomposition of the geometry (G, I, O) into subgeometries. Examining such decompositions will lead to an efficient algorithm for obtaining the candidate successor function f associated with a modified flow, which we may use to implement a semantic map for the DKP and RBB constructions.

Star geometries and star decompositions
We then define the star geometry rooted at v (or centered at f (v)) is the geometry Star geometries correspond to star circuits (as described in Section 3.1.1) and zz operations, via their representations as 1WQC procedures. Consider the 1WQC procedure P = Φ(C u1,...,un w v ) obtained from a stable-index expression for star circuit C as in (3.1). Then P has a geometry (G, I, O) consisting of a star graph G with center w ∈ O I, and where v ∈ I O. If f is the index successor function of the stable-index expression, we may then show that (G, I, O) is the star geometry with root v and center w as in Definition 3.5. We may similarly show that Φ(zz) also gives rise to a star geometry, where the mediating qubit a = f (a) is both the center and the root of the star geometry. (The same also holds forΦ(zzz d ), for the mappingΦ and unitary zzz d defined in the proof of Lemma 3.3.) Star geometries (G u , I u , O u ) are thus precisely those geometries which underlie the 1WQC procedures Φ(C ), where C are the featured circuits in decompositions described in Section 3.1.1. Extending the results of [12], we may consider how such structures for a geometry (G, I, O) may be used to describe "candidate" circuits C for 1WQC procedures P, where C may correspond to P via the DKP or RBB constructions: we consider how to construct such circuits in Section 3.4. Motivated by the connection with circuit constructions, we may consider a decomposition of geometries similar to the compositions of simple circuits in Section 3.1.1: (3.28a) In particular, if the restriction of the natural pre-order to G is such that (f , ) is a modified flow, then (f, ) is also a modified flow. Thus, the existence of a star decomposition for (G, I, O) implies that it has a modified flow, by induction.
Thus, we may decompose a circuit with a modified flow into star geometries. Figure 10 illustrates a decomposition of a geometry with a flow into star geometries in the manner described above; Figure 11 illustrates a more general case for a modified flow. Also illustrated in these figures are "candidate circuit" constructions for unitary circuits, which we describe in Section 3.4.

Structural characterization of star decompositions
In order to define a semantic map S for the DKP and RBB constructions, it will be necessary to attempt to obtain a star decomposition of a geometry which is initially not known to have a modified flow. We may facilitate this by showing that we may characterize star decompositions independently of modified flows, as follows: Let f : O c −→ I c be defined so that f (v j ) = v j for any v j as in the first case above, and f (v j ) = w j for any v j , w j as in the second case; and let be the natural pre-order for f . Then Proof. Let f be defined as above, and let be its natural pre-order. By construction, each geometry G j is then a star geometry with respect to f in the sense of Definition 3.5, whether or not (f, ) is a modified flow. We may show by induction on = |V (G)| |O| that is a partial order.
Then the natural pre-order is the equality relation, which is antisymmetric and therefore a partial order. O for every w ∼ v . Then the only relations that contains that does not are u v for qubits such that f (u) ∈ O, and v w for w ∈ O; that is, u v w for some w maximal and u bounded above in only by maximal elements.
Then the only relations that contains that does not are u w for qubits such that f (u) = w such that w ∼ w , and v w for qubits w ∼ w . In either case, we have w ∈ O ; thus we only add additional (maximal) upper bounds for u bounded only bounded by maximal elements, and new upper bounds for v which are also maximal.
In either case, is a partial order; thus (f, ) is a modified flow.
We will call a decomposition as in Lemma 3.6 a star decomposition of a geometry (G, I, O), and the associated geometries G j in the decomposition star geometries, whether or not they are defined with respect to a corresponding modified flow (f, ). More generally, we will call a geometry (G , I , O ) a star geometry when the input and output subsystems satisfies either property (i) or property (ii) in the statement of Lemma 3.6 above. In the case that I = O , we say that unique vertex v ∈ V (G ) O is both the root and the center of (G , I , O ); otherwise, we say that the unique vertex v ∈ I O is the root of (G , I , O ), and the unique vertex w ∈ O I is the center.
The proof of Lemma 3.6 suggests a recursive decomposition of a geometry (G, I, O) into star geometries using "maximal" star geometries, in the following sense: We may characterize a maximal star geometry as follows: Lemma 3.7. Let (G , I , O ) be a maximal star geometry, with root v and center w, for some geometry (G, I, O). Then one of the following two properties hold: Conversely, for a geometry (G, I, O) and vertices v, w ∈ V (G) for which either of the above hold, the geometry for W consisting of w and its neighbors in G, with input and output subsystems is also a star geometry. The Lemma then holds.
By definition, any geometry with a star decomposition has a maximal star geometry; we may then attempt to obtain a star decomposition by recursively constructing maximal star geometries for successive residual geometries. In the next section, we show how this leads to an efficient algorithm for obtaining a star decomposition (and a modified flow) for an arbitrary geometry (G, I, O) and subset M ⊆ O c , when one exists.

Efficiently decomposing geometries
In order to be able to test the consistency of measurement dependencies of a 1WQC procedure P with those arising in the DKP or (simplified) RBB construction, we may attempt to determine whether the tuple (G, I, O, M ) associated to P has a modified flow. As a special case, we may efficiently determine when a geometry (G, I, O) has a flow, and construct one if one exists. The most efficient known algorithm to do this is that of Mhalla and Perdrix [14]. We show how their algorithm may be adapted to produce modified flows when they are present, using an analysis in terms of maximal star geometries.
Maximally delayed flows. We may summarize the algorithm of [14] as follows. To find a flow (f, ) or a geometry (G, I, O), we consider the length of the longest chains of each qubit from the output set, and construct "layer sets" consisting of vertices of similar depth: A maximally delayed flow is also a flow of minimum depth, i.e. that the order of such a flow has the same depth as the natural pre-order for the given flow-function f . For a maximally delayed flow (f, ), let : V (G) −→ N be the function mapping each vertex v ∈ V (G) to the integer j such that v ∈ V ≺ j . Then, the partial order characterized by v w ⇐⇒ [v = w or (v) > (w)] also yields a minimum-depth flow by construction.
Mhalla and Perdrix show for a maximally delayed flow (f, ) for (G, I, O) that V ≺ 0 = O, and V ≺ 1 is the set of elements of W ≺ 0 such that, for some w ∈ O, v is the only neighbor of w which is contained in W ≺ 0 . By induction, augmenting the set O to include successive "layers" V ≺ j , one may show that where N G (w) is the set of vertices adjacent to w in G. By a depth-first search from O, we may find in a finite number of iterations of j those qubits w ∈ V (G) W ≺ j which have such a neighbor v, and accumulate them into new layers V ≺ j+1 .
Relation to maximal star geometries. This decomposition of the geometry (G, I, O) into layers V ≺ j corresponds strongly to the star decomposition of a geometry (G, I, O).
The maximal elements of V (G) in the natural pre-order are exactly the elements of O (as z f (z) for any z ∈ O c ): thus, the root v of a maximal star geometry in (G, I, O) is one such that all neighbors z ∼ f (v) are elements of O or equal to v itself. The set V ≺ 1 as described above is the set of precisely those vertices which are the root of a maximal geometry. Thus, the algorithm of [14] may be described as finding flows by performing a star decomposition of (G, I, O) when it has a flow.
We may easily extend the maximal delay principle of [14] for flows to one which identifies a maximal star geometry for (G, I, O) in the more general case where this geometry (together with a set M ) has a modified flow. For such a triple (G, I, O, M ) with a modified flow (f, ), we may define the sets V ≺ j and W ≺ j as in Definition 3.7. Then for each j ∈ N, V ≺ j+1 consists of those vertices v ∈ W ≺ j such that, for any ∈ M , this implies that (as in the analysis of [14]) the only neighbor of f (v) which lies in W ≺ j is v itself; for v ∈ M , it may also be possible that v has no neighbors in W ≺ j . The flow-finding algorithm of [14] can then be easily extended to test for the latter condition, yielding a procedure to produce a star decomposition of (G, I, O) when one exists, as we describe below.
Bounding the search for roots of maximal star geometries. The flow-finding algorithm of Mhalla and Perdrix ([14], Algorithm 1) operates on the basis of maintaining a set of "correcting vertices" w which, for each new layer V ≺ j+1 , may potentially be the successor of some vertex v ∈ V ≺ j+1 . These correcting vertices are precisely the centers of maximal geometries, in which case the corresponding v is a root. We thus take a similar approach to obtain a star decomposition by "removing" layers of maximal star geometries, identified with their centers.
For modified flows, we must accommodate vertices v ∈ M which may be simultaneously the root and the center of a geometry. To ensure that we do not fruitlessly examine vertices of M at each layer, we maintain a digraph whose arcs point in either direction along each edge of G, and from which we delete any arc ending at a vertex which has already been indicated as the root of a star geometry. Then, if a potential center w has a single neighbor v which has not been matched to a star geometry, v is the root and w the center of a maximal star geometry; and if a vertex w has not yet been identified as the center of a star geometry only neighbors vertices which have already been identified as centers, w is both the center and the root of a maximal star geometry. As a result, we may easily determine whether a potential center w has a single neighbor v which has not been matched to a star geometry (in which case v is the root and w the center of a maximal star geometry), or whether a vertex which has not yet been identified as the center of a star geometry only neighbors vertices which have already been identified as centers (in which case w is both the center and the root of a maximal star geometry).
Algorithm 2 defines a subroutine RemoveStarGeom to perform the necessary arc deletions for the digraph described above whenever we define the layer of a vertex, as well as several other operations useful to an iterative procedure for discovering the maximal star geometries of a star decomposition.
Data : M , a subset of specially designated vertices W , the set of vertices not yet marked as roots of star geometries emptyLayer, a flag indicating if the present layer is empty D, a digraph in which vertices v ∈ V (G) W have in-degree 0 f : V (G) − V (G) a mapping from "roots" to "centers" S , a set of possible centers of star geometries for the next layer v ∈ V (G), a vertex to mark as the root of a star geometry w ∈ V (G), a vertex to mark as the center associated to v Effect: Assigns f (v) ← w, adds v to the set of potential centers for the next layer and to the ordered list of qubits with identified star geometries, removes all of the inbound-arcs to v in the digraph D, and checks the neighbors of v in D for vertices in M with out-degree 0 to mark as a center for the next layer.

2
Remove v from the set W , and set f (v) ← w. 3 Insert v to the beginning of L. 4 For every neighbor z with an outbound arc to v in D , do: 5 Remove the outbound arc z → v from D. 6 If z ∈ M ∩ W and z has no more outbound arcs, then add z into S . 7 endfor 8 ALGORITHM 2. A subroutine to attribute a vertex to the current layer, for use in an iterative procedure for finding the roots of maximal sub-geometries with a modified flow. In particular, this subroutine maintains the arcs of a digraph D (a "sub-digraph" of the graph G of a geometry, interpreted as a symmetric digraph) from which we remove any arc inbound to a vertex with a well-defined layer.
Accumulating roots of star geometries. Using RemoveStarGeom as a subroutine, we may easily define a procedure similar to Algorithm 1 of [14] which either (a) determines that a star decomposition of the geometry does not exist, implying the non-existence of a modified flow, or (b) constructs a modified flow, represented as a tuple (f, L) consisting of a partial function f : V (G) − V (G) mapping the root of each star geometry to the corresponding center, and a list L of the roots corresponding to a composition order for the star geometries. v Algorithm 3 presents such a procedure, which we describe below. We begin by creating the digraph D which governs the search for roots: we copy all of the neighborhood relations of G, omitting those arcs ending in O, as these cannot be roots of star geometries. Similarly, as no w ∈ O is a root, it must lie outside the v The list L constructed by Algorithm 3 is a linear order, i.e. a partial order of maximum depth. To find one of minimum depth as in Algorithm 1 of [14], it suffices to maintain a layer counter and to record the layer for which each vertex v ∈ O c is the root of a maximal star geometry. However, as we are ultimately interested in producing a (linearly ordered) circuit expression, it is not necessary to obtain a partial order of smaller depth.   Let L be a sequence of vertices (initially empty). 3 Let W ← ∅ be a set of potential roots of star geometries. 4 Let S ← ∅ be a set of potential centers of maximal star geometries. 5 Let D be the completely disconnected digraph on V (G). 6 For all v ∈ V (G), do: Set f (v) ← nil. 10 If v / ∈ I , then add v into S. Add v into W . Let emptyLayer be a flag indicating failure to find any new roots. 16 Repeat: 17 Set emptyLayer ← true, initially.

18
Let S ← ∅ be the set of potential centers for the next iteration. 19 For each w ∈ S , do: 20 If w ∈ W , then 21 Call RemoveStarGeom(w, w). Call RemoveStarGeom(v, w).

24
If v / ∈ I , then add v into S .  If W = ∅, then return (f, L); else return nil.

32
ALGORITHM 3. An iterative algorithm to discover a star decomposition inspired by the analysis of [14], using the subroutine RemoveStarGeom of Algorithm 2.
domain of f , so we set f (w) ← nil; but if w ∈ O is not an element of I, it will be the center of some star geometry, so we insert it to a set S of candidates for centers of maximal star geometries. Any vertex w / ∈ O is the root of some star geometry in a star decomposition of (G, I, O), provided such a decomposition exists; we then insert such w into a set W of candidates for roots of maximal star geometries.
We then search for layers of new roots, corresponding to the layer-sets in the analysis of [14]. For each layer, we iterate through the set of potential centers for maximal star geometries, which initially includes no elements of W . We maintain the invariant that D contains all (directed) adjacency relations of G, except that it contains no arcs ending at vertices w / ∈ W . We also maintain the invariant that v ∈ W becomes an element of S only if it is an element of M and has out-degree zero in D, in which case it is both the root and the center of a maximal star geometry. We indicate the removal of vertices (as a result of decomposing the geometry into star geometries and an as-yet decomposed "residue") by absence from both the sets S and W ; thus S represents at each stage the output subsystem of the residual geometry.
In any iteration, for the center w of any maximal star geometry, either w has a unique neighbor v / ∈ W in G (in which case w → v is the only outbound arc from w in D), or w ∈ M and has no neighbors in W (in which case it has out-degree 0 in D).
• In the latter case, unless w is isolated in G, there was some final neighbor u which was removed from W in an earlier iteration; immediately after the removal of u from W , we may then identify that w is the root (and center) of a maximal star geometry. In the call to RemoveStarGeom(u, u ), we thus examine each of the neighbors w ∈ M ∩ W (restricting our search to qubits in M which have not yet been assigned as the root to a previously removed star geometry) which have an outbound arc w → u, to see if that arc is the last outbound arc from w. If this is the case for some w, we add w into the set of potential centers S for the next iteration.
In Algorithm 3, this is the only condition under which an element of W may be inserted into S ; the only other condition under which S accumulates elements is for a vertex v which has already been removed from W . Thus, in the subsequent iteration, any element of S ∩ W is necessarily the root (and center) of a maximal star geometry, which we may then decompose from the parent geometry. This decomposition is represented by the removal of w from W , and the omission of w from S .
• In the case where w has a unique outbound arc w → v in D, the vertex v is necessarily the root of a maximal star geometry for which w is the center. We may then decompose this star geometry from the parent geometry, which we represent by the removal of v from W (and the insertion of v into S ), and the omission of w from S . In the next iteration, as an element of the output subsystem of the residual geometry, v is then a potential center of a maximal star geometry.
For any w ∈ S which is not the center of a maximal geometry as above, we carry w forward for the next layer by including w in S . We assign the list of new candidate successors to S before the end of the iteration; and we repeat until we cannot find any more roots for some layer.
If we cannot assign any vertices to new layers, this is either because we have exhausted the possible roots (in which case W = ∅), or because there are no vertices which are reachable from the existing layers which have viable successors. In the latter case, there is no modified flow; and in the former, we return the tuple (f, L).
Run-time analysis of Algorithm 3. The run-time of Algorithm 3 is similar to that of Algorithm 1 of [14], which we may show as follows. In the following, we let n = |V (G)|, k = |O|, and m = |E(G)|. We assume that the graph G and digraph D are represented with adjacency lists for each vertex, in the latter case using lists of neighbors from inbound and outbound arcs separately. The partial function f is represented with an array structure taking the value nil (indicating a vertex not in the domain) or vertices in V (G). We may represent the sets M and W as arrays of pointers to nodes of a linked-list structure, enabling constant-time membership checking and element insertion, as well as linear-time traversal of the elements of the set. The sets S and S we represent simply as linked lists, which also provides us with constant-time initialization to the empty set.
In the subroutine RemoveStarGeom(v, w), the run-time is dominated by the loop over the neighbors z of v , which requires time at most O(deg G (v)) . As this subroutine is called at most once for each vertex v, the total run-time of Initially, S has k elements, none of which are elements of W ; and in each iteration, as every element w ∈ S W gives rise to the removal of some vertex v from W and the potential insertion of v into S , there always remain at most k elements of S W at each iteration of the loop on lines 17 -31. The comparisons on lines 21 and 23 can both be performed in constant time, as can the set-inclusions on lines 25 and 27. The assignment on line 30 can be performed simply by re-attributing the element list of S to S. There are at most n iterations of the loop on lines 17 -31, as it only repeats as long as at least one vertex has been assigned to a new layer. Then, setting aside the work performed for vertices w ∈ S ∩ W in the loop on lines 17 -31 and the work performed by RemoveStarGeom, the work performed by that loop is O(kn).
As elements of W are only included into S when they are guaranteed to be attributed to the next layer, the total work performed by that loop (again aside from work performed by RemoveStarGeom) for elements of M is then O(n). The run-time of

Extremal analysis of geometries with modified flows
The run-time of O(kn+m) for Algorithm 3 is precisely the complexity of Algorithm 1 of [14]. However, Mhalla and Perdrix also use an extremal result presented in [15] which bounds the number of edges m in a geometry with a flow by kn − k+1 2 . This allows any geometry with edges in excess of this to be rejected at the outset, so that the run-time for geometries satisfying this bound may be simplified to O(kn). By observing the correspondence drawn in Section 3.1.1 between successor functions and the ordering described in (2.14) for indices of stable-index expressions, we may extend this extremal result as follows: In either case, we have |O | = |O| = k.
By induction, each star geometry in a decomposition of (G, I, O) contributes at most k edges, and has an output subsystem of size k. Then the output subsystem I = V (G) img(f ) of the initial geometry (G[Ĩ], I,Ĩ) in the star decomposition also contains k vertices; this geometry then has at most k 2 = 1 2 k(k − 1) edges. Furthermore, as (G[Ĩ], I,Ĩ) does not contain the center of any star geometry, and as each star geometry has a center distinct from the others, there are at most n − k star geometries in the decomposition, each with a distinct center. The number of edges in (G, I, O) is then bounded by (3.32) as required; this bound is saturated by the extremal construction of [15].
As a result, we may simplify the run-time of Algorithm 3 by O(kn) in this case as well, again by a pre-processing stage which returns nil for geometries with more than kn − k+1 n edges.

Candidate circuit constructions
Following the approach in the proof of Lemma 3.3, we may consider how to construct "candidate" circuits C for 1WQC procedures P, by decomposing of the underlying geometry into star geometries and mapping each star geometry to a corresponding unitary circuit. This will give rise to a circuit C over the gate set B DKP or B RBB , such that Φ(C) is another 1WQC procedure with the same underlying geometry. If we can prove that the circuit C performs the same operation as P, then C describes the semantics of P in the unitary circuit model. We may use this as the final step towards defining a semantic map S for the DKP and (simplified) RBB constructions.

Star circuits corresponding to star geometries
For a star geometry, we may consider a corresponding star circuit, possibly parameterized (in the case of a star geometry with root v and center w = f (v) = v) by an angle related to the measurement angle θ v of v: (3.33) For star geometries whose center and root are the same (in the case that f (v) = v), corresponding to the mediating qubits of a zzz d operation for some d 2 as in (3.13), the corresponding star circuit is just the operator zzz d u1,...,u d acting on the input/output subsystems: this corresponds to the decomposition of zzz d as generalizing (3.2). We may also correspond the geometry (G[Ĩ], I,Ĩ) to a circuit consisting solely of ∧ Z gates, as described with (3.20): as described in Section 3.1.1, such a circuit arises in star decompositions of circuits as well. We may then construct a candidate circuit C as in the preceding section by re-composing the circuits corresponding to the geometries in the star decomposition of (G, I, O). Such re-composed circuits are illustrated in the bottom panels of Figure 10 and Figure 11. For instance, in Figure 10, we may recover the geometry in the upper left-hand panel by composing and similarly, the larger circuit C in Figure 10 is obtained by composing where the circuits C u are those corresponding to each star geometry, and CĨ corresponds to the geometry G Ĩ , I,Ĩ .

The gate model for candidate circuit constructions
Neither of the circuits described in Figure 10 or Figure 11 are generated over the gate set {H, T, ∧ Z}; and the latter is not defined over either B DKP or B RBB , but instead over the more general gate-setB described in the proof of Lemma 3.3. (As we suggested just after the proof of that Lemma 3.3, this gate-set corresponds naturally to the structure of tuples (G, I, O, M ) with modified flows; we may refine this statement and describe this set of gates as that which naturally corresponds to star geometries. In order to use star decompositions to describe a semantic map corresponding to representations of circuits over {H, T, ∧ Z}, we must first translate the circuits from the gate-setB. There is one apparent problem: the circuits arising from such a decomposition are more general than those in the domain of Φ. This may conceivably complicate the task of comparing the circuits arising from a semantic map S based on star decompositions, and the circuits which lie in the domain of either R DKP or R RBB . We may show that this more general sort of construction will not arise in practise for 1WQC procedures resulting from either the DKP construction or the RBB construction when |I| = |O|. In this case, a geometry has at most one star decomposition up to commuting terms, by the uniqueness of the modified flow (f, ) shown in Theorem 3.4 for this case. In particular: • for (G, I, O) which underly procedures P produced by the DKP construction, there will be no qubits v ∈ O c such that f (v) = v, because (f, ) will be a flow; • for (G, I, O) which underly procedures P produced by the RBB construction, the only edges vw in (G, where one of the qubits is a mediator qubit for a zz operation between two logical qubits.
Thus, while the candidate circuits for arbitrary geometries with modified flows may be more general, the candidate circuits for 1WQC procedures P arising from a circuit C over B DKP or B RBB will be restricted to the same gate-set as C itself when |I| = |O|. For a semantic map defined relative to a particular construction, we may also ensure that we obtain candidate circuits over the appropriate gate-set by imposing restrictions on the type of star geometries which we permit in the decomposition of a particular geometry. However, as we considering only the special case |I| = |O|, this will not be necessary for our analysis.

Relationships between 1WQC procedures and candidate circuits
Properly speaking, a candidate circuit is a construction from a 1WQC procedure P rather than from a star decomposition of a geometry (G, I, O), as the angular parameters of the J(θ) gates in a candidate circuit are determined by the measurement angles in P. In order to use candidate circuits as a means of defining a semantic map S, we must consider the relationship between 1WQC procedures and their candidate circuits.
By Theorem 3.1, we may characterize the dependencies of operations in procedures P obtained from either the DKP or RBB constructions, relative to a candidate for the extended successor function for a corresponding circuit. If the geometry (G, I, O) underlying P (together with the set M of mediating qubits) has a modified flow (f, ), this defines a candidate circuit C, in which the gates J(α u ) arising from star-circuits C u (for a qubit u = f (u) at the root of a star geometry) have their angles fixed by α u = −θ u , where θ u is the default measurement angle of u in P.
By the observations made above, the circuit C will be defined over the gate set B DKP or B RBB , depending on whether P arises from the DKP or RBB construction: we may then consider the 1WQC procedureP =Φ(C), which will coincide with Φ(C). The procedureP will have the same geometry as P, and the same default measurement angles: if it also has the same correction and measurement dependencies, this implies that P performs the same transformation as the circuit C.
For procedures P arising from the DKP or RBB constructions in the case that |I| = |O|, there is only one modified flow for (G, I, O), which must then be the extended successor function for the circuit over the B DKP or B RBB gate sets produced in the course of constructing P. It follows then that C is also precisely the circuit arising in the construction of P, in which case the normal form of Φ(C) will be congruent to P. Thus, to obtain a semantic map for the DKP construction when |I| = |O|, it suffices to translate C into the gate-set {H, T, ∧ Z} . For the RBB construction, to obtain a circuit with complexity no greater than the original circuit from which P was produced, we must also simplify C by removing products of the form J(0)J(0) and J( π /2 )J( π /2 )J( π /2 ) introduced by the construction of Section A.2.2.
In the case that |I| = |O|, even conditioned on P arising from the DKP or RBB constructions, it may be difficult to obtain the modified flow function f corresponding to the circuit arising in the construction of P, and therefore to produce a suitable candidate circuit. Without an algorithm that can construct such candidate circuits in the case that |I| = |O|, for instance by finding the modified flow (f, ) for which P satisfies Theorem 3.1, we must therefore restrict ourselves to the DKP and RBB constructions in the case where no fresh qubits are introduced, i.e. which perform unitary bijections.

Efficient construction of candidate circuits over {H, T, ∧ Z}
For the sake of completeness, we present a procedure BuildCircuit (extending the remarks made in Section III B of [12]) for constructing a stable-index representation for a candidate circuit for P, represented in the gate set {H, T, ∧ Z} (rather than the sets B DKP or B RBB ). The procedure BuildCircuit takes as input a representation of a star decomposition of a geometry (G, I, O): we may represent this in terms of the graph G of the geometry, the successor function f from the modified flow which defines the star decomposition, and a sequence L of the roots of the component star geometries. This procedure is presented in Algorithm 4.
For each root u in the list L, BuildCircuit determines whether it is the root of a geometry whose root and center are both u (corresponding to a zzz d gate acting on the neighbors of u in G), or where the center v = f (u) differs from u (corresponding to a star circuit as in (3.33). It then appends to a circuit expression C the appropriate sequence of operations: • By expanding Z = 1 − 2 |1 1| in the tensor product Z ⊗ · · · ⊗ Z, and considering the expansion of zzz d = e −iπZ ⊗d /4 in terms of multi-qubit operations (3.38) We may construct such a gate for w j ranging over all neighbors of a qubit u = f (u) by obtaining the set N of these neighbors, and for each w ∈ N , adding Input : G, the a graph for the geometry G of a 1WQC procedure f : V (G) − V (G), a modified flow function for G L, a list of roots of star geometries in a decomposition of G t : V (G) − Z an array denoting multiples of π /4 Output: A candidate circuit generated over {H, T, ∧ Z}, corresponding to the star decomposition described by G, f , and L, with powers of T gates given by the parameters stored in t(u).
procedure BuildCircuit(G, f, L, t) : 1 Let C a stable-index representation of a circuit, initially empty.

2
For each u ∈ L, do: For each w ∈ N , do: 6 For each w ∈ N : add ∧ Z w,w to C. 7 Add T w T w to C. 8 Remove w from N . Let For each w ∈ N : add ∧ Z v,w to C.
14 Add H v u to C. T operations on w to C, as well as controlled-Z operations between w and the other elements of N . Removing w from N after doing so will then prevent controlled-Z operations from being added twice for each pair of neighbors.
• For each qubit u such that u = f (u), we may obtain the set of N neighbors of v = f (u) belonging to the output subsystem O u of the star geometry (G u , I u , O u ). N will then consist of the neighbors of v excluding u and (if it is defined) f (v) = f (f (u)). We may then add the star circuit C u to C by adding ∧ Z operations between each w ∈ N and v, followed by the components of the gate J(θ) for the appropriate angle θ. For angles θ constrained to integer multiples of π /4 , this will consist of H v u T t(u) u for some integer array t given as input: if t(u) is negative, we may add products of T † u to C.
After having added the star circuits for each star geometry, we then add the circuit corresponding to the geometry (G[Ĩ], I,Ĩ) forĨ = V (G) img(f ). After constructing the setĨ, we iterate through the qubits u ∈Ĩ, adding to C the ∧ Z operations acting on u and (if necessary) representing the fact that u / ∈ I by adding a preparation of a fresh qubit |+ in order to advance u as a fresh index in the circuit C. w Subsequently removing u fromĨ prevents duplicate ∧ Z operations from being added to C.
Run-time analysis of Algorithm 4. We may bound the run-time of BuildCircuit as follows. Let n = |V (G)|, m = |E(G)|, and k = |O|. We assume a list-like structure for the stable-index expression C and for the sets N G (u), and an array-structure for f , where f (v) = nil denotes that v / ∈ dom(f ).
(i) For each qubit u = f (u), the number of gates to add corresponding to the expression for zzz deg G (u) above is O(deg G (u) 2 ). As the output subsystem of each star geometry in a star decomposition has the same size input and output subsystem, we have deg G (u) |O| = k for each such u; then the total work number of gates arising from these qubits is O(k 2 n).
(ii) For each qubit u = f (u), the number of gates to add corresponding to the circuit C u is O(deg G (f (u)); summing over all such u, we have a total of O(m) gates arising from these qubits.
(iii) For each qubit u ∈Ĩ = V (G) img(f ), we have deg G (u) gates to add, plus possibly an initial state |+ u . Summed over all u ∈Ĩ, we again have at most O(m) operations arising in this case.
As each operation requires time O(1) to add, the run-time of Algorithm 4 is then O(k 2 n + m).

Complete algorithm for the semantic map when |I| = |O|
We may now describe a single, complete procedure Semantic (presented in Algorithm 5) to perform a semantic map S with respect to the representations R DKP and R RBB represented by the constructions of Section 2.3. We may describe the operations Input : P, a 1WQC procedure in normal form.
Output: Either nil, if P is not (congruent to) the normal form of a procedure as in Lemma 3.3, or a stable-index representation of a circuit C generated over the gate-set {H, T, ∧ Z, zzz d } d 2 which performs the same transformation as P.

17
ALGORITHM 5. A complete algorithm for a semantic map with respect to either the DKP or simplified RBB constructions, using the procedures defined in Algorithm 1, Algorithm 4, and Algorithm 3, as well as a procedure RemoveIdops which performs trivial simplifications of products of single-qubit gates. performed by Semantic in three different phases, which we may describe as follows.
Obtain the underlying structure of P. We first obtain the geometry (G, I, O) underlying P, as well as the set M of qubits measured with default angles π /2 , in order to obtain a star decomposition. We also obtain the cardinalities n = |V (G)|, m = |E(G)|, and k = |O|. For each qubit u measured, we record the integers t(u) ← −4θ/π which corresponds to the power of T for which HT t(u) = J(−θ u ); if the measurement at u corresponds to the execution of a J(θ) gate in the candidate circuit, we may use t(u) to determine the expansion of this gate in the gate-set {H, T, ∧ Z}.
Rather than perform these operations literally as presented in Algorithm 5, we may obtain this data with a single pass of the operations of P, constructing G, I c , and O c by inserting qubits and edges as each qubit is acted on by preparation maps, entangling operations, and measurements; we may obtain n, m, and k similarly. Using arrays of pointers to linked list nodes to represent I c and O c , we may then construct a similar representation of both I and O with a single traversal of V (G). As we do so, we also assign values to the array t and insert qubits into the set M . As P has at most O(n) preparation, measurement, and correction operations, and O(m) entangling operations, it has size O(m + n): this is then the time required for this phase of the procedure.
Examine the geometry and the measurement dependencies of P. As we noted in Section 3.3.4, a 1WQC procedure cannot have a modified flow if it has more than nk − k+1 2 edges, in which case it lies outside the range of both the DKP and RBB constructions by Lemma 3.3; we then return nil. We then attempt to obtain a star decomposition for (G, I, O) with the set M of potential mediating qubits: if this fails, we also return nil.
By Theorem 3.1, we may characterize the dependencies of operations in procedures obtained from either the DKP or RBB constructions, relative to a candidate for the successor function for a corresponding circuit. For the star decomposition described by the ordered pair (f, L) returned in the previous step, there is a corresponding candidate circuit C for which f is an extended index successor function, as described in Section 3.4. In the case that |I| = |O|, there is no other candidate successor function for (G, I, O, M ), by Theorem 3.4. Then the candidate circuit C described by (f, L) is the only one which describes a unitary transformation which may be performed by P.
The 1WQC procedure Φ(C) has underlying geometry (G, I, O) by construction; if P has the same operations (with the same dependencies) as the normalization of Φ(C), they then perform the same transformation, and thus P is a representation of C. Again by construction, the normalization of Φ(C) satisfies the conditions of Theorem 3.1 with respect to f . Then if TestDependencies(P, f ) returns true, we may provide the semantics for P in terms of unitary circuits by constructing C; otherwise, we have no such guarantee, and so we return nil.
We may compare m to nk − k+1 Constructing a circuit for P. Provided that the procedure does not return nil in the previous phase, the procedure P performs a unitary transformation, and in particular is a representation of the "candidate" circuit C obtained from the star decomposition of (G, I, O). We therefore construct the circuit C, using the star decomposition described by (f, L). We produce a stable-index representation for C, representing it in the gateset {H, T, ∧ Z} rather than the setB used in Lemma 3.3: this takes time O(k 2 n+m) = O(k 2 n), as m kn − k+1 2 by hypothesis. In the case of procedures P obtained by applying the RBB construction to some original circuitC, we must perform some final simplifications. We call a final subroutine RemoveIdops(C) in order to remove superfluous powers of T which may arise from the conversion of operations zz = (T 2 ⊗ T 2 ) ∧ Z, and which also removes products of the form H 2 = J(0)J(0) and HT 2 HT 2 HT 2 = J( π /2 )J( π /2 )J( π /2 ) on individual qubits such as those introduced in the stable-index construction presented in Section A.2.2. As the dependencies of P satisfies the constaints of Theorem 3.1 relative to the successor function f , this circuit provides the semantics for P as a unitary circuit, by the analysis of page 61.
The list L produced by FindModStarDecomp contains roots of star-geometries in a non-increasing order (in terms of the natural pre-order for the successor function f it produces), and the operations of C are in a similar order from the construction of BuildCircuit(G, f, L, t). We may therefore perform this simplification of C in a single pass from right to left, using buffers for each logical qubit of the circuit to maintain accumulated sequences of single-qubit operations performed between pairs of two-qubit operations. We may then cancel products of single-qubit unitaries that occur at the end of the buffer, as appropriate. The amount of time required to do so is then a constant factor time the size of the circuit, which by the analysis of page 62 is also O(k 2 n + m) = O(k 2 n).
Remarks on circuit congruence and total run-time. In order to consider the correctness of Algorithm 5, we may consider without loss of generality circuitsC represented in the gate-sets B DKP or B RBB which do not contain redundant operations J(0)J(0) or J( π /2 )J( π /2 )J( π /2 ), and which do not introduce fresh qubits. We may proceed as follows.
If we apply the DKP construction to such a circuitC over the gate-set B DKP , we obtain a procedure P for which the qubits of O c are labelled by deprecated indices iñ C, and I c by advanced indices; where the entanglement graph is the same as the interaction graph ofC; and where the default measurement angles are the additive inverses of the angles of the J(θ) gates. Furthermore, the geometry (G, I, O) has a modified flow (f, ), in which f is the index successor function ofC. Correspondingly, the candidate circuit C for P has an interaction graph given by the entanglement graph of P, and a successor function which agrees with f . The single-qubit gates corresponding to the edges uf (u) in the interaction graph correspond to operations J(−θ u ), where θ u is the default measurement angle of u; and all other edges correspond to ∧ Z operations. We may then define a bijective mapping between the terms ofC and the terms of C, via the structures induced in and recreated from P.
For the RBB construction, the analysis is similar: the only changes are the fact that the edges of the interaction graph ofC which correspond to operations zz must be subdivided by a single vertex to yield the entanglement graph of P, and paths of the form J(0)J(0) or J( π /2 )J( π /2 )J( π /2 ) may be inserted to achieve the topological constraint of being an induced subgraph of a two-dimensional grid. In constructing the candidate circuit C, the subdivided edges corresponding to zz operations are remerged, and the superfluous products of single-qubit unitaries are once more removed.
In this case, we may then also define a bijective mapping between the terms ofC and the terms of C, via the structures induced in and recreated from P.

Extensions and limitations
The analysis of 1WQC procedures presented in Section 3, in terms of modified flows and star decompositions, may be extended in a natural way to more general formulations of the 1WQC model. At the same time, this approach has limitations in its ability to describe even some of the earliest known constructions for 1WQC computation. In this section, we will describe in brief some of these extensions and limitations.

Extending beyond measurement in the XY plane
The model of measurement-based computation which we have focused on in this article (following the treatments in [1] and [2]) is one in which all single-qubit measurements are performed in the XY plane, i.e. with respect to uniform superpositions of the eigenstates of the Pauli Z operator. A natural extension of this is to allow measurements in any basis in a "Pauli plane", i.e. for any uniform superposition of the eigenstates of X and Y as well. We may define the notation |±xy θ = |± θ (denoting the fact that these states lie in the XY plane), and then define We may then consider extensions of the analysis of Section 3, in measurement-based models which include operations of the form above. • If θ = π /2 , we perform an X operation on some specially designated qubit v = u (which we denote f (u) for each u), and a Z operation on each of the neighbors of v except for u itself, if the state of u is projected onto |−xy θ .
• If θ = π /2 , either we perform the operation described above, or we perform a Z operation on each neighbor of u, if the state of u is projected onto |−xy θ .
In either case, the operation which is performed after each measurement may be described by an operator up to an operation acting on u itself (which we describe as being destroyed by the measurement and which thus cannot be carried out). This unitary operation is the Pauli group on V (G), and in particular stabilizes the state |Ψ G,I defined by for any |ψ ∈ H ⊗I 2 . In particular, as the preparation maps N v adjoin qubits prepared in the +1 eigenstate of the X operator, and theE vw maps perform two-qubit ∧ Z operations (which lie in the Clifford group) on pairs of qubits, the state of the system just prior to any measurements is a stabilizer code [5] S G,I generated by the operators (4.5) The modified flow conditions may then be considered as a certificate that there exists an order in which the qubits of O c may be measured so that one may use the stabilizer formalism [5] to simulate the post-selection of the state |+xy θ for each measurement (by applying suitable corrections should the measurement yield |−xy θ instead).
We may observe that the analysis of measurements by a single-qubit observable O v in the stabilizer formalism requires only that O v either commutes or anticommutes with every generator of the subgroup of the Pauli group which stabilizes the state of the system. We may observe that XY-plane measurements such as those above can be described by measurements with respect to observables O XY,θ = |+xy θ +xy θ | − |−xy θ −xy θ | = cos(θ)X + sin(θ)Y ; . The constraints on the partial order ensure that, for any linear measurement order extending , the generators which stabilize the state just prior to the measurement of u consist of K f (u) , and operators which all commute with u. Then, the evolution of the state-space system under these measurements may be efficiently described via the stabilizer formalism as a transformation of stabilizer codes (although how individual states within these codes transform may be difficult to simulate). As the modified flow conditions ensure that each measurement observable has a corresponding generator with which it anticommutes, the overall transformation will then be unitary.
A straightforward extension of modified flows. The fact that qubits u ∈ M may have either u ∼ f (u) or u = f (u) stems from the fact that O XY,θu = Y in this case: that is, the measurement basis for such qubits lies in the intersection of the XY and YZ planes. The condition u ∼ f (u) in this case is common to all other measurement angles, as this condition suffices for treatment via the stabilizer formalism for observables which anticommute with Z. We may then extend the notion of modified flows as follows to also include other measurement observables which, like Y , anticommute with X: hold for all v ∈ O c and w ∈ V (G).
In the above definition, the sets M XY and M YZ correspond to qubits whose default measurement basis lies in the XY-plane or the YZ-plane, respectively; the intersection are those qubits whose measurement basis is the eigenbasis of the Y operator, which is common to both. Modified flows then correspond to the special case where M YZ ⊆ M XY .
As with modified flows, an extended flow (f, ) for a tuple (G, I, O, M XY , M YZ ) certifies that any procedure on the geometry (G, I, O) which performs the appropriate types of measurement will perform a unitary transformation, provided also that it performs the appropriate corrections (or measurement adaptations) in response to the measurements. To this effect, we may prove an extension of Lemma 3.3, as follows:  Figure 12: Illustration of the geometry for the procedure Zzz θ d defined in (4.10), together with the "default state" |+yz θ to be measured for the qubit a in that procedure. (In the case that the measurement of a yields |−yz θ instead, each element of I = O is to be acted on with a Z operation.) and λ(u) = P for u ∈ M P otherwise. Then for any linear order extending , the measurement procedure performs a unitary transformation.
Again, as we described above for modified flows, this may be proven for extended flows by simulating the evolution of the state-space via the stabilizer formalism, steering the state after each measurement to the one which would arise upon selection of the |+xy θ or |+yz θ result as appropriate.
Generalization of zzz d operations using extended flows. An alternative proof would be to extend the analysis of the proof of Lemma 3.3 by considering the operation generalizing the operation zzz d defined in (4.9). We may define a 1WQC procedure the geometry for this procedure is illustrated in Figure 12. Following the analysis of Section 3.8 of [19], we then have The procedure of (4.10) is a straightforward generalization of the procedure Zzz d = Zzz d, π / 2 . In the same way that we map qubits u such that u = f (u) to a circuit C u = zzz d acting on the neighbors of u for a modified flow as a part of a circuit construction, we may map qubits such that u = f (u) to a circuitC u = zzz θu d , where |±yz θu is the default basis for the measurement of u.

Generalized certificates of unitarity based on stabilizers
In the preceding section we observed one sense in which modified flows may be generalized, by observing that they essentially provide sufficient information to certify via the stabilizer formalism that a 1WQC procedure performs a unitary transformation. This is done by attributing some generator K v to each qubit u ∈ O c to be measured, where the measurement on u may be described by some observable O u which anticommutes with K v , but commutes with K w for all w u. Similar, but more general, criteria that extended flows were defined in [4] in generalized flows and Pauli flows, which extend further to arbitrary generators of the initial stabilizer group K w w∈I c (and thus to non-trivial products of the operators K w ) when XY, YZ, and XZ-plane measurements are all allowed. We may paraphrase the definition of Pauli flows as follows:  u ∈ XY ∩ YZ, or u ∈ XY ∩ XZ and λ(u) = XZ =⇒ θ u ∈ { -π /2 , π /2 } , (4.14b) and for any linear order extending , the measurement procedure performs a unitary transformation.
This represents a further extension of the possible range of 1WQC procedures which may be identified as performing unitary transformations; the proof of the above y We may recover the definition of Pauli flows found in [4] by defining a function λ from O c to {X, Y, Z, XY, YZ, XZ}, such that  Figure 13: Illustration of the geometry for a qubit-reversal procedure of Section IV.B of [2], and a partial decomposition into star geometries. Each qubit in V (G) O is to be measured in the XY plane with default angle 0: when this yields the measurement result s[u] = 0 for each u ∈ V (G) O, the result is to perform a reversal of the vertical ordering of the logical qubits: input states |ψ a,b,c,d of the input subsystem (with a-d ordered from top to bottom) are mapped to |ψ w,v,u,t of the output subsystem (with tw ordered from top to bottom). Notice that the residual geometry in the decomposition on the right has no maximal star geometries, as every element of O is adjacent to more than one element of V (G) O , and every element of V (G) O is adjacent to at least one other element of V (G) O . Thus, this geometry has no star decomposition, and therefore no modified flow.
Lemma may again be obtained by considering how each measurement may be certified to transform the state-space unitarily conditioned on a preferred measurement result, where the transformation of the state-space and the corrections to apply are described by the stabilizer formalism.
In order to use this to provide semantics for such 1WQC procedures in terms of unitary circuits, we may consider how the concept of star geometries generalize from extended flows to Pauli flows. The natural approach, rather than attempt to retain the star-graph structure, would be to consider geometries with a single root u, multiple "centers" v ∈ g(u), and whose output subsystem consists of the qubits [g(u) ∪ odd(g(u))] {u}. However, it is not as clear what the circuit corresponding to such a geometry would be, nor what results may be shown for the decomposition of a geometry (G, I, O) into such geometries, as these lack the simple local structure of star geometries. How a Pauli flow structure may be exploited to produce more general semantic maps for 1WQC procedures in unitary circuit models is an open question.

A simple 1WQC construction lacking a star decomposition
Lemma 4.2 above presents a 1WQC procedure which performs a unitary embedding, but for which the techniques of Section 3 do not apply. Another example is the procedure for performing reversals of a linear array of logical qubits presented in Section IV.A of [2]. Figure 13 illustrates the geometry underlying this 1WQC procedure: the entire procedure may be obtained from the specification that each qubit in O c is to be measured in the XY plane with the default angle 0, and noting that as this represents selection of the +1 eigenstate of the observables X u for u ∈ O c , from which suitable correction operations may be obtained by the stabilizer formalism. However, as Figure 13 also illustrates, this procedure has no star decomposition, and so cannot be mapped to its meaning as a reversal of a linear array of qubits using the techniques of Section 3.
Despite this, we may gain some information about the qubit-reversal pattern using modified flows by an appropriate extension of the input and output systems, as exhibited in [11]. It is easy to see that if we include the left-most element of each row into I, and the right-most into O, the resulting altered geometry has a flow with a successor function which maps each vertex to the one immediately to the right. Chains in the natural pre-order have monotonically increasing column numbers: and therefore is antisymmetric. Given that the default measurement angle for each qubit is zero, we may obtain a candidate circuit for this procedure, as illustrated in Figure 14. The final circuit illustrated there can easily be described as a reversible classical computation: for seven input bits (v 0 , . . . , v 6 ), the computation performed by that circuit is If we apply this circuit instead to qubits, with the odd-indexed qubits initialized to the |+ state (i.e. a uniform superposition of the bit-values described above), those qubits remain in the |+ state, and the even-indexed qubits are reversed, as required.
We may then understand the qubit-reversal pattern in [2] as corresponding to a circuit which prepares auxiliary qubits in the |+ state, and subsequently removes them by an X observable measurement. The fact that we are able to obtain the circuit in this case is possible because the highly structured geometry makes it easier to guess which qubit measurements correspond to terminal measurements in a unitary circuit. Without exploiting this structure, however, there are no known approaches to algorithmically provide semantics for such a measurement pattern in terms of unitary circuits.

Review and open problems
In this article, we have presented an algorithm for obtaining the "meaning" of 1WQC procedures P in terms of unitary circuit models, using a combinatorial analysis of the structures underlying procedure P arising from standard constructions of 1WQC procedures. In doing so, we have identified a correspondence between elementary combinatorial structures (star geometries) and elementary circuits (star circuits) which, given a 1WQC procedure whose geometry which may be decomposed into these elementary structures, allows the construction of a corresponding circuit. Together with a characterization of the dependencies of operations on classical measurement outcomes, this enables us to efficiently construct a circuit C for a 1WQC procedure P, and to determine whether C and P perform the same operation, when P has input and output subsystems of the same size.
We There are three natural open problems: how this analysis may be extended to the case of unitary embeddings in general, how this may be extended to admit an analysis for quantum circuits with ancillas (qubits which are prepared, operated on, and subsequently removed without creating mixtures of states in the other qubits), and how we may extend this analysis to include stabilizer certificates such as Pauli flows.
General unitary embeddings. The problem presented by the case of a unitary embedding with |I| < |O| is that a star decomposition of the geometry may not be unique. Consequently, there may be many modified flow functions against which the dependencies of a 1WQC procedure must in principle be tested. We may relieve the situation if we can use the dependencies themselves to narrow the search space for a single modified flow; this seems a likely approach to extending the analysis of this article to a semantic map for the DKP and (simplified) RBB constructions, without further constraints.
Quantum circuits with ancillas. The qubit-reversal procedure described in Section 4.2 presents a situation where the introduction and removal of ancillas can be used to obtain a unitary circuit which corresponds to a 1WQC procedure. Combinatorial tools for the "detection" of instances in which a qubit may represent the state of an ancilla qubit would yield more general tools for presenting the semantics of 1WQC procedures in terms of unitary circuits, possibly permitting a semantic map to be defined for a construction employing all of the sub-procedures described in Section IV of [2], and for 1WQC procedures in general arising from circuits involving partial trace operations on qubits which are disentangled from the rest of the system.
Extension to more general stabilizer certificates. As noted in Section 4.1.1 and Section 4.1.2, modified flows essentially represent a means via the stabilizer formalism to certify that, for a given geometry (G, I, O), there is an efficiently describable 1WQC procedure having that geometry (G, I, O) and which performs a unitary transformation. We can then consider how to compare an arbitrary procedure with geometry (G, I, O) to this canonical geometry. In Section 4.1.1, we showed how such certificates may be extended to more general gate-sets: how we might exploit the definition of Pauli flows in Definition 4.2 to obtain more general semantic maps is an open problem.
DTO-ARO. The extension of the results to the simplified RBB construction was written during the author's current affiliation with the Unitersität Potsdam, and was funded in part by EPSRC. Finally, the author would to thank Ashwin Nayak, Andrew Childs, Michele Mosca, Debbie Leung, John Watrous, and Dan Browne for remarks on the presentation of [9]. qubit will then remain unchanged, even if one measures this state in the standard basis at the beginning of the wire-segment.
As with tensors in Einstein notation, we may describe a "path" as a mapping of each index (whether bound or free) to some fixed value; the amplitude associated with a path is the product of the corresponding coefficient of each factor involved in the expression. The convention of summing over bound indices (whose possible values may be thought to represent intermediate configurations which were not observed, and therefore not distinguished from one another) then represents a summation over indistinguishable paths. The simplification introduced by stable-index expressions corresponds to explicit recognition when operations leave some of the the "dynamical variables" associated to a path (represented by tensor indices) unaffected.

A.2 Constructing stable-index representations
We may automatically generate a stable-index representation S for a unitary circuit from a representation as a composition of operators C on specified qubits in an efficient manner. We consider two distinct methods: one which is appropriate for a network without any topological constraints on the operators, and one which is motivated by the constraints described in Section 2.3.3.

A.2.1 Construction for topologically unconstrained circuits
Let L be the set of qubit labels in C. We may then transliterate the terms in C, defining a set of tensor indices incrementally as we do so, as follows: 1. For each qubit v ∈ C, we define the tensor index v 0 . We designate v 0 as the current tensor index for v. (Throughout the transliteration of the circuit, the index designated as "current" for a qubit will be updated.) We also start with an expression S consisting of the null sequence of operators: this may be regarded as representing a stable-index representation for the the empty product (the identity operator).
2. We translate each operator U a,b,... in C taken in sequence, as follows. For each qubit v ∈ {a, b, . . .} on which U acts (again, in sequence), let v j be the current index for v, and perform the following: (i) If U a,b,... introduces v as a "fresh" qubit (or a new qubit which is possibly entangled with the others), then v 0 is still the current index for v. We then use v 0 as the advanced index corresponding to v, without a corresponding deprecated index.
(ii) If U a,b,... not preserve each of the standard basis states on v (that is, if U a,b,... |s s| v U † a,b,... = |s s| v for some s ∈ {0, 1}), then we define a new tensor index v j+1 for v. We then use v j as the deprecated index corresponding to v, and v j+1 as the corresponding advanced index. We update the current index for v to v j+1 .
(iii) If U a,b,... preserves each of the standard basis states on v (that is, for each s ∈ {0, 1} we have U a,b,... |s s| v U † a,b,... = |s s| v ), then we use v j as a stable index corresponding to v, without defining any new indices. z (iv) If U a,b,... removes a qubit v (e.g. describing an operation conditioned on a a particular measurement outcome), then we use v j as a deprecated index corresponding to v, without a corresponding advanced index.
This produces sequences of stable indices s and sequences of matched advanced and deprecated indices a and d (possibly with placeholders); we then translate U a,b,... as U s a d , and append it to S. 3. Having translated each of the terms in C, the sequence S is a stable-index tensor expression corresponding to C.
Note that in particular, every new index which is advanced by a gate U s a d must be distinct from any other index being advanced, as well as from all of the indices which have occurred to that point. This ensures that the resulting product is acyclic if the original network C was acyclic.
Note that the index successor function f (Definition 2.3) can be easily described from this construction: f has as a domain all those indices v j such that v j+1 is welldefined, and v j+1 = f (v j ) for all such indices.
1. For each qubit v acted on by C, we set the current index to v 0 . We also initialize the graph G to the totally disconnected graph whose vertices are the indices v 0 . We start with an expression S consisting of the null sequence of operators: this may be regarded as representing a stable-index representation for the the empty product (the identity operator).
2. We translate each operator J(θ) a or zz ab in C taken in sequence, as follows.
For each qubit v on which the gate acts, let v j be the current index for v. For a gate J(θ), we append J(θ) vj+1 vj to S, add the index v j+1 and the edge v j v j+1 to G, and set the current index to v j+1 . Otherwise, for a gate zz vw , we perform the following operations: (i) We ensure that the constraints on successive applications of two-qubit gates is satisfied as follows. If the current indices for v and w are v j and w j for a common value of j, and there is an edge of the form v j−1 w j−1 in G, we append the expression to S, and add the edges v j v j+1 , v j+1 v j+2 , w j w j+1 , and w j+1 w j+1 (along with the indicated indices) to G. We then set the current indices of v and w to v j+2 and w j+2 respectively.
(ii) We then recursively perform the following, letting v j and w k stand for the current indices of v and w at each iteration: • If |k − j| 3 or |k − j| = 2, we append either to S, according to whether k > j or j > k respectively, adding the appropriate indices and edges to G. We set the current index either of v or w to v j+2 or w k+2 accordingly, and repeat for the new current indices. • If |k − j| = 3 or |k − j| = 1, we append either to S, according to whether k > j or j > k respectively, adding the appropriate indices and edges to G. We set the current index either of v or w to v j+3 or w k+3 accordingly, and repeat for the new current indices.
• If j = k, we append zz[v j , w j ] to S, add the edge v j w j to G, and stop.
3. Having translated each of the terms in C, the sequence S is a stable-index tensor expression corresponding to C, and G its interaction graph.
In the above construction, note that the final index v for each qubit v may not have the same value of ; and that such stable-index expressions may both begin and end with operations zz vj ,wj . These degrees of freedom may complicate the procedure of composing two such circuits. These issues may both be mitigated by appending appropriate products of J(θ) operators which evaluate to the identity, of differing lengths for each qubit; this can be done to both uniformize the value of the final indices v , and also ensure that any zz operation is a distance of at lest 2 from the end of the circuit. However, for the purposes of this article, such operations will not be necessary, as we do not consider the composition of two such expressions.

A.3 Congruence of circuits and isomorphic stable-index expressions
In this section, we prove Theorem 2.1 (page 11), and expand on the role of parsimonious sets of gates in this result.
Lemma A.1. Let C 1 and C 2 be two sequences of unitary operators on a common set of qubits, composed from a common set of unitaries. If the stable[index tensor representations of C 1 and C 2 are isomorphic, then C 1 and C 2 are congruent up to re-ordering of commuting operators.
Proof. Consider the coarsest equivalence relation ∼ = on circuits which consist of permutations of the gates of C 1 , such that C ∼ = C if C differs from C by a transposition of commuting gates. By definition, the equivalence classes of ∼ = are sets of circuits which are congruent up to re-ordering of commuting operators. Consider stable-index tensor expressions S and S arising from two unitary circuits C and C , where S acts on the same index set as S , and S differs from S only by a transposition of two terms U 1 s1 a1 d1 and U 2 s2 a2 d2 , where without loss of generality the former precedes the latter in C, and vice-versa in C . Then, the corresponding gates U 1 and U 2 in C occur with U 1 preceding U 2 , and occur in C in the opposite order. Consider the index sets for these two operations in the stable-index tensor expression: • If the sequences of indices (s 1 ; a 1 ; d 1 ) and (s 2 ; a 2 ; d 2 ) do not overlap, the operations U 1 and U 2 act on disjoint sets of qubits, and so they commute.
• Suppose the sequences of indices (s 1 ; a 1 ; d 1 ) and (s 2 ; a 2 ; d 2 ) overlap, and let v be an index occurring in both sequences. In the construction of S, because v occurs in U 2 s2 a2 d2 , it cannot be a deprecated index in U 1 s1 a1 d1 ; and because it occurs in U 1 s1 a1 d1 , it cannot be an advanced index in U 2 s2 a2 d2 . By the construction of S , we similarly have that v cannot be a deprecated index in U 2 s2 a2 d2 or an advanced index in U 1 s1 a1 d1 . Then, v is a stable index of both terms.
Therefore, the only qubits v on which U 1 and U 2 both act are those whose standard basis states are preserved by both U 1 and U 2 . Then, U 1 and U 2 commute, in which case C ∼ = C .
Let S 1 and S 2 be the stable-index tensor representations of C 1 and C 2 , where the isomorphism is given by an index relabelling map λ and mapping of the terms τ . Let S 2 be the representation obtained by applying λ to all of the indices in S 2 : then S 1 and S 2 consist of a product of the same terms in different orders. Without loss of generality, we will then suppose that S 2 and S 1 differ only by a reordering of terms. Because the terms of S 1 differ from those of S 2 by a permutation, by induction on the decomposition of this permutation into transpositions, we therefore have C 1 ∼ = C 2 .
Whatever set of gates is used in a stable-index tensor expressions, rearranging the terms in the expression not only preserves the meaning (by summation over indices which are both advanced and deprecated) as a unitary operator, but also preserves the relevant structural information about the circuit -preserving the necessary order information in the way described following Definition 2.3, while discarding such information for each pair of commuting operators. As a consequence, we may regard permuting terms of such an expression as a way of exploring the elements of the congruence class of a circuit.
However, in the case where two gates commute without preserving the standard basis states of their common operands, we may obtain congruent circuits which do not have isomorphic tensor index expansions: Example 5. Let U ∈ U(2) be a non-diagonal operator, and define the operation ∧ U as in (2.12a). Consider the two circuits ∧ U c,b ∧ U a,b H a and ∧ U a,b ∧ U c,b H a on three qubits a, b, c (where the subscripts here denote the linear order of the qubits as operands of ∧ U and H): these have the respective stable-index expressions These two expressions are non-isomorphic: in the first expression, the leftmost factor contains the indices c (which is neither advanced nor deprecated in the entire expression) and b 3 (which is not deprecated in the entire expression); the second expression does not contain any factor with these properties.
In the example above, the inequivalence of the two stable-index expressions is due to the fact that the two operations ∧ U a,b and ∧ U b,c preserve the eigenbasis of U on b, rather than the basis |0 , |1 . The restrictions imposed on parsimonious sets of unitary operations prevent precisely this problem from arising, which allows us to prove the following: Lemma A.2. Let C 1 and C 2 be two unitary circuits composed from a common parsimonious set of unitaries. If C 1 is congruent to C 2 up to re-ordering of commuting operators, then the stable-index representations of C 1 and C 2 will be isomorphic.
Proof. Let K 0 ∼ = K 1 ∼ = · · · ∼ = K be a sequence of circuits which differ only by a transposition of two commuting gates, where C 1 = K 0 and C 2 = K . We may show by induction on that the stable-index tensor expressions for C 1 and C 2 are isomorphic; it suffices in this case to prove the case = 1.
Let S 0 and S 1 be the stable-index representations of K 0 and K 1 . Up to a relabeling, we may assume that the indices of S 0 and S 1 are all of the form v 0 , v 1 , . . . for different qubits v acted on by K 0 and K 1 : we set v 0 to be the first index corresponding to a given qubit in either S 0 or S 1 , and v j+1 to be an advanced index corresponding to each deprecated index v j for j ∈ N. Let U 1 and U 2 be the pair of gates whose order differs between the two circuits; and consider the truncation S 0 of S 0 just prior to the terms corresponding to U 1 and U 2 , and similarly for S 1 . Because K 0 and K 1 differ only by a transposition of commuting gates U 1 and U 2 , S 0 = S 1 . Let S 0 and S 1 be the truncations of S 0 and S 1 just after the terms corresponding to U 1 and U 2 : • If U 1 and U 2 act on disjoint sets of qubits, the terms corresponding to U 1 and U 2 in S 0 may differ from those in S 1 only by the indices which are advanced in each; and as the indexing scheme we have fixed is the same for each, and the indices which will be advanced for U 1 and U 2 are independent of each other in both expressions, S 0 differs from S 1 only by a transposition of those two terms.
• If U 1 and U 2 both have the standard basis as their eigenbases, their corresponding terms in S 0 and S 1 only have stable indices, and therefore do not advance any new indices. Then the term in S 0 and in S 1 corresponding to U 1 are the same, and similarly for U 2 ; the difference between S 0 and S 1 is a transposition of those two terms, and so they are isomorphic.
• If U 1 and U 2 perform the same single-qubit operation, there will be some common tensor index u j which is current for that qubit prior to the application of U 1 and U 2 in both S 0 and S 1 . Then, the terms corresponding to U 1 and U 2 in S 0 will be U 2 uj+2 uj+1 U 1 uj+1 uj , and the corresponding terms in S 1 will be U 1 uj+2 uj+1 U 2 uj+1 uj for some indices v and w . Given that U 1 and U 2 perform the same operation, we then have S 0 = S 1 .
Because the operations of K 0 and K 1 are identical after U 1 and U 2 , the differences between S 0 and S 1 after the terms corresponding to U 1 and U 2 can only arise from the indices advanced by each term; because we have fixed the indexing scheme, the only difference between S 0 and S 1 is then the (possibly trivial) transposition of those two terms. Thus, S 0 and S 1 are isomorphic. Theorem 2.1 then follows from Lemma A.1 and A.2. Using this, we may identify congruent circuits simply by relabelling their indices in a uniform way (e.g. as in the construction for stable-index expressions in Section A.2), and determining whether there is a perfect matching between the two expressions defined by equality of terms.
B Details for constructions of 1WQC procedures B.1 Construction of the gate-sets B DKP and B RBB In this section, we provide details on the construction of the 1WQC procedures J θ and Zz, as well as a generalization of the latter operation to a many-qubit diagonal operation.

B.1.1 Two-qubit operations
As described in (2.40), we may implement zz in the 1WQC model with the procedure For the analysis of Section 3, it will be convenient to generalize this to a procedure Zzz d v1,...,v d acting symmetrically on many qubits: where we define the non-negative scalars σ ± by σ + = + π/2 | Z x1+···+x d |+ +| Z x 1 +···+x d |+ π/2 , (B.3b) We may consider the terms of (B.3a) as outer products of standard-basis vectors: we may verify that In the case |Ψ v,w = ∧ Z v,w |ψ v |+ w , the terms in this equation may again be expressed as outer products of state vectors: where by J(−ϕ) w/v we denote the linear operator H v → H w which maps state-vectors |ψ v −→ J(−ϕ) |ψ w . By linearity, we may extend this to arbitrary entangled states |ψ v ⊗ |φ S with a system S which does not include v. Then, for a system S which includes v and excludes w, we have

B.2 Efficiency of the DKP and simplified RBB constructions
Both the DKP construction and the (simplified) RBB construction, as described in Section 2.3.4, can be performed efficiently in the size of the input circuit. We may illustrate this for both procedures, as follows. In both cases, let k be the number of qubits which C acts upon, N be the number of one-qubit gates, and M be the number of two-qubit gates: we may assume that k N + M if we suppose that C acts nontrivially on each qubit.

B.2.1 Obtaining a circuit in normal form
We may easily construct a normal form in each case in a single pass of the expression of the circuit C. For each qubit v acted on by C, we may maintain a buffer B v of single-qubit operations which are performed. These are initially empty for each qubit; we accumulate T and T † operations (cancelling them as appropriate) of each qubit as we encounter them; and upon encountering a Hadamard operation on a qubit v, we insert the contents of the buffer immediately before the Hadamard, resetting the buffer to zero after the Hadamard operation has been traversed. In both cases, we may also cancel ∧ Z operations by storing in the buffers B v indications of which qubits w the qubit v has interacted with via a ∧ Z: initially this is set to zero, and we toggle the presence of each qubit in the set with each ∧ Z operation between the two qubits.
When we empty a buffer for a qubit v, we also produce the corresponding ∧ Z gates between v and other qubits w. When we clear a buffer B v prior to a Hadamard, we may count the number of ∧ Z gates between v and each qubit w, and produce a ∧ Z operation when the total is odd. For each ∧ Z gate between v and some other qubit w, we also remove a ∧ Z gate in the buffer B w between w and v to avoid doublecounting the ∧ Z gates. For the RBB construction, we may elaborate this further by converting ∧ Z operations to zz operations by performing the substitution ∧ Z −→ zz(T † ⊗ T † ) 2 when we encounter such an operation, accumulating the resulting T † gates in the buffers B v and B w when we do so.
The total amount of work performed by this routine per operation in C (counting both insertions and removals of terms corresponding to these operations, to or from the buffers) is O(1). Using list-structures to implement the buffers B v and adjacency-list representations for the ∧ Z operations, we may initialize the buffers in time O(k). The amount of work required by this phase is then O(k + N + M ).

B.2.2 Conversion to stable-index representation
This phase may be performed simultaneously with the previous phase: with each gate produced, we may produce a stable-index representation of the gate, and we produce J(θ) gates rather than H, T , and T † gates when we clear the buffers. In the case of the RBB construction, an additional amount of work may be required for the insertion of J(θ) gates to achieve uniform wire lengths: the amount of additional work per zz gate is bounded to within a constant by the number of single-qubit operations performed on either wire, which is at most N . The amount of work required to do this is then O(k + N + M ) for the DKP construction, and O(k + N M ) for the RBB construction.

B.2.3 Translation of individual operations to the 1WQC model
This phase can also be performed simultaneously with the previous phases: rather than produce a stable-index expression C , we may produce the 1WQC procedure Φ U ··· for each term U ··· produced for the stable-index expansion. As each such 1WQC procedure is of constant length, this requires no additional overhead asymptotically.

B.2.4 Obtaining a 1WQC procedure in normal form
Let P 0 be the resulting 1WQC procedure from the previous phase. Let n be the number of qubits acted on by P 0 , and and let m be the number of operations J θ , E , or Zz in P 0 . (We may easily show that n = k + N for the DKP construction and n = k +N +M ∈ O(N +M ) for the RBB construction; we have m = N +M for the DKP construction and m N + N M ∈ O(N M ) for the RBB construction, essentially by the arguments given for the run-time for the production of the stable-index expression C .) As each operation J θ , E , and Zz consists of a constant number of elementary operations and contains only one or two entangling operations, the procedure P 0 also has O(m) elementary operations and O(m) entangling operations.
Standardizing P 0 . Let G be the entanglement graph associated to P 0 . In the process of standardizing P 0 , for each qubit v which is part of a J v/u operation for some u, we must commute a single operation X s [u] v past entangling operations E vw for all w adjacent 3. After we have read all of the measurements, we append the corrections for each unmeasured qubit (computed in the previous step) to to the end of P 1 .
The resulting procedure P 1 is then the same that would result from standardizing P 0 , and can be obtained in time O(m).
Normalizing P 1 . Obtaining a normal formP from P 1 can be done by checking for Pauli simplifications for each measurement, and then performing signal shifting by accumulating shift operators to the left (without commuting shift operators past each other). We may check for and apply Pauli simplifications as a part of the standardization process above, with no additional overhead asymptotically. We may also perform signal shifting simultaneously with the standardization process, by immediately commuting the shift operation S γ s [u] past any corrections X s[u] v and Z s[u] w which might have been introduced by the measurement on a given qubit u: if v ∼ w denotes the adjacency relation in G, we have (B.12) After performing this commutation, there are no classically controlled operations to be inserted to the left of the shift operator which will depend on s[u]; we may then commute it past all additional operations and remove it from the expression. Then, rather than inserting shift operations and the corrections described, we may accumulate the corrections described on the right-hand side after the measurement on u. The amount of work required for each measurement in this alternative procedure is then dominated by the work required to update the corrections, which is O(n deg[f (u)]); summed over all vertices u, obtaining a normal form may then be done in time O(nm).

B.2.5 Total run-time complexity
Comparing the complexity of the phases above (and recalling the relationship between n and m with N , M , and k at the beginning of Section B.2.4, the run-time of both the