{'fraction_non_alphanumeric': 0.03452379136218706, 'fraction_numerical': 0.007627881432211017, 'mean_word_length': 4.252824745572562, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Twisted graph states for ancilla-driven quantum computation

We introduce a new paradigm for quantum computing called Ancilla-Driven Quantum Computation (ADQC) combines aspects of the quantum circuit and the one-way model to overcome challenging issues in building large-scale quantum computers. Instead of directly manipulating each qubit to perform universal quantum logic gates or measurements, ADQC uses a fixed two-qubit interaction to couple the memory register of a quantum computer to an ancilla qubit. By measuring the ancilla, the measurement-induced back-action on the system performs the desired logical operations. By demanding that the ancilla-system qubit interaction should lead to unitary and stepwise deterministic evolution, and that it should be possible to standardise the computation, that is, applying all global operations at the beginning, we are able to place conditions on the interactions that can be used for ADQC. We prove there are only two such classes of interactions characterised in terms of the non-local part of the interaction operator. This leads to the definition of a new entanglement resource called twisted graph states generated from non-commuting operators. The ADQC model is formalised in an algebraic framework similar to the Measurement Calculus. Furthermore, we present the notion of causal flow for twisted graph states, based on the stabiliser formalism, to characterise the determinism. Finally we demonstrate compositional embedding between ADQC and both the one-way and circuit models which will allow us to transfer recently developed theory and toolkits of measurement-based quantum computing directly into ADQC.


Introduction
There are two main paradigms which have driven both the theory and implementation of quantum computation; gate-based quantum computing (GBQC) [1], and measurement-based quantum computing (MBQC) [2]. Though these two models are computationally equivalent, in practice each has their own advantages and disadvantages which have major implications for the choice of physical system, design, and operation. We introduce a new paradigm called ancilladriven quantum computing which combines features of both models, in order to parallelise the architecture of quantum computers, to decrease decoherence effects, and simplify their physical implementation and operation.
GBQC requires, in general, arbitrary networks of dynamic operations which in turn complicates the design and characterisation of the entire computer. There are many scenarios where it would be desirable to physically separate preparation, measurement, and coherent interaction regions to reduce control complexity, circuitry congestion, and decoherence due to cross-talk. In contrast, MBQC performs computation purely through single-qubit measurement on a pre-existing static multi-partite entangled state, distilling and processing nonlocal correlation. However, the generation of the initial highly entangled state, incorporation of quantum error correction and fault-tolerance, and individual measurement of each qubit are issues in many candidate systems.
Our new model of ancilla-driven quantum computing (ADQC) is partly inspired by the previous works of Andersson and Oi in [4], and also Perdrix and Jorrand in [5]. Andersson and Oi introduced an efficient method to implement any generalised quantum measurement by coupling the system with an ancilla qubit. The method, however, assumes arbitrary dynamic coupling operations between ancilla and system. Perdrix and Jorrand, on the other hand, describe a probabilistic version of MBQC in terms of a Turing machine where one can view the read-write head as an ancillary qubit, though this is not the way the model is presented. Moreover their approach still requires direct manipulation of the memory register and dynamic global measurement operators.
ADQC attempts to overcome such issues by performing computation where the memory register (input data) can only be remotely manipulated through interaction with a supply of prepared ancillas. In other words, instead of directly manipulating data qubits to perform universal quantum logic gates or measurements, ADQC uses a fixed two-qubit unitary interaction to couple the memory register of a quantum computer to an ancilla qubit. By measuring the ancilla, the measurement-induced back-action on the system performs the desired logical operation. Practically, a single fixed unitary interaction coupling the data and ancilla qubits greatly simplifies design, construction, and operation of the computer since only one particular discrete operation needs to be generated and characterised. Furthermore, separating interaction and measurement leads to a parallel structure with possibly reduced decoherence [30]. A requisite interaction for ADQC already exists in a variety of physical systems ranging from ion micro-traps, neutral atoms, nuclear spin donors in semiconductors, SQUIDs and cavity QED which greatly increases the scope for implementation of the core ideas. ADQC also naturally benefits from optimisation of the qubit species employed for memory and ancilla. Memory qubits can be chosen for long coherence time at the expense of being static and difficult to manipulate directly, whilst ancilla qubits may be chosen for high mobility and rapid initialisation and measurement, e.g. donor nuclear spins in isotopically pure silicon as mem-ory and electron spins conveyed via charge transport by adiabatic passage as ancilla in solid state quantum computing.
So far we have mentioned only the practical advantages of our proposed architecture. The formalisation of the computational model underlying ADQC, which is the focus of the current paper, leads to the introduction of a new multipartite entanglement resource. Only recently has it been demonstrated that a very restricted class of multi-partite entangled states are useful for universal MBQC [6,7]. However a full characterisation of such states [8] remains an open problem which this paper aims to make progress upon.
The entangled graph states [10] have emerged as an elegant and powerful quantum resource, especially for measurement-based quantum computation (MBQC) [2]. Many important results on their entanglement properties [11], information flow [13,14], implementation [15], and novel applications in cryptography [16,17], are due to their simple description. The generating operator for graph states, called controlled-phase, is a symmetric and commuting operator which leads to a simple graphical notation and hence the name for these states. Additionally, the elegant result by van den Nest et al. [11,18] shows that any stabiliser state is equivalent to a graph state up to local Clifford operators. This greatly expands the scope of the results for graph states, and leads to a natural extension of the above constructions into stabiliser states, as well as allowing a convenient graphical notation for a very general class of states.
If we consider open graph states, graph states where some nodes (called input nodes) are given in arbitrary states (rather than being prepared in a particular fixed state which is the case for graph states) much of the theory still follows. However open stabiliser states with arbitrary input nodes no longer fulfil the pre-requisites of the theorem by van den Nest et. al., and in general they do not admit a trivial graphical notation.
Moreover, not all two-qubit interactions between system and ancillary qubits can be used for ADQC. To characterise interactions that will eventually enable universal ADQC we demand that the ancilla-system interaction leads to a unitary and stepwise deterministic evolution of the system qubit, and that it should be possible to standardise the computation, that is, applying all global operations at the beginning. By doing so we are able to place conditions on the possible interactions resulting in two classes of interactions that are necessary and sufficient for ADQC. This naturally leads to the definition of a particular class of open stabiliser states, called twisted graph states which, despite being generated by non-commuting operations, still admits a simple graph representation. They form the key ingredient for ADQC. We then show how this new class of states can be viewed as open graph states up to somelocal swap operations. We also develop an algebraic framework similar to the measurement calculus, which is the mathematical framework underlying MBQC computation. This makes it possible to derive the standardisation theory for the ADQC patterns of computation. As we will see, any ADQC computation requires a classical control structure to compensate for the probabilistic nature of the measurement. In order to characterise the determinism, we introduce the notion of causal flow for twisted graph states based on the stabiliser formalism. Compared to the open graph state, the stabiliser state has a more complicated and global structure. We construct, however, direct translations between ADQC and MBQC for a subclass of deterministic patterns with flow which preserve depth, in order to prove that ADQC is as parallel as MBQC. We also present the embedding between GBQC and ADQC and show how, as for MBQC, a separation in depth can be obtained.

Preliminaries
We briefly review the required concepts from quantum computing. A more detailed introduction can be found in [19]. Let H denote a 2-dimensional complex vector space, equipped with the standard inner product. We pick an orthonormal basis for this space, label the two basis vectors |0 and |1 , and identify them with the vectors (1, 0) T and (0, 1) T , respectively. A qubit is a unit length vector in this space, and so can be expressed as a linear combination of the basis states: Here α 0 , α 1 are complex amplitudes, and |α 0 | 2 + |α 1 | 2 = 1. An m-qubit state is a unit vector in the m-fold tensor space H ⊗ · · · ⊗ H. The 2 m basis states of this space are the m-fold tensor products of the states |0 and |1 . We abbreviate |1 ⊗ |0 to |1 |0 or |10 . With these basis states, an m-qubit state |φ is a 2 m -dimensional complex unit vector There exist quantum states that cannot be written as the tensor product of other quantum states. Such states are called entangled states, e.g. |00 + |11 .
We use φ| = |φ * to denote the conjugate transpose of the vector |φ , and φ | ψ = φ| · |ψ for the inner product between states |φ and |ψ . These two states are orthogonal if φ | ψ = 0. The norm of |φ is || φ ||= φ | φ . A quantum state can evolve by a unitary operation or by a measurement. A unitary transformation is a linear mapping that preserves the norm of the states. If we apply a unitary U to a state |φ , it evolves to U |φ . The Pauli operators are a well-known set of unitary transformations for quantum computing: and the Pauli group on n qubits is generated by Pauli operators. Several other unitary transformations that we will use in this paper are the identity 1, the phase gate P (α), of which P (π/4) and P (π/2) are a special cases, the Hadamard H, the controlled-Z (∧Z) and the SWAP operation: The Clifford group on n qubits is generated by the matrices Z, H, P (π/2) and ∧Z, and is the normaliser of the Pauli group. This set of matrices is not universal for quantum computation, but by adding any single-qubit gate not in the Clifford group (such as P (π/4)), we do get a set that is approximately universal for quantum computing [19]. The most general measurement allowed by quantum mechanics is specified by a family of positive semi-definite operators to the condition that i E i = 1. A projective measurement is defined in the special case where the operators E i are projections. Let |φ be an m-qubit state and B = {|b 1 , . . . , |b 2 m } an orthonormal basis of the m-qubit space. A projective measurement of the state |φ in the B basis means that we apply the projection operators An important class of projective measurements are Pauli measurements, i.e. projections onto eigenstates of Pauli operators. So far we have dealt with pure quantum states. A more general representation with density matrices also allows us to describe open physical systems, where one can prepare a classical stochastic mixture of pure quantum states, called mixed quantum states. For a system in a pure state |ψ , the density matrix is just the projection operator |ψ ψ|. Suppose that we only know that a system is one of several possible states |ψ 1 , . . . , |ψ k with probabilities p 1 , . . . , p k respectively. We define the density matrix for such a state to be The most general physical operator that acts over density matrices is a completely positive trace preserving map (CPTP) E : is the Banach space of bounded linear operators and we require that Any unitary operation U can be approximated with a circuit C, using gates from a fixed universal set of gates. The size of a circuit is the number of gates and its depth is the largest number of gates on any input-output path. Equivalently, the depth is the number of layers that are required for the parallel execution of the circuit, where a qubit can be involved in at most one interaction per layer. In this paper, we adopt the model according to which at any given time-step, a single qubit can be involved in at most one interaction. This differs from the concurrency viewpoint, according to which all interactions for commuting operations can be done simultaneously.

Measurement-based model
We give a brief introduction to measurement-based quantum computing (MBQC) [2,22,23]. A more detailed description is available in [3,24,25,26]. Our notation follows that of [3]. In MBQC, computations are represented as patterns, which are sequences of commands acting on the qubits in the pattern. These commands are of four types: 1. N i is a one-qubit preparation command which prepares the auxiliary qubit i in state |+ = 1 √ 2 (|0 + |1 ). The preparation commands can be implicit from the pattern: when not specified, all non-input qubits are prepared in the |+ state. 2. E ij is a two-qubit entanglement command which applies the controlled-Z operation, ∧Z, to qubits i and j. Note that the ∧Z operation is symmetric so that E ij = E ji . Also, E ij commutes with E jk and thus the ordering of the entanglement commands in not important. 3. M α i is a one-qubit measurement on qubit i which depends on parameter α ∈ [0, 2π) called the angle of measurement. M α i is the orthogonal projection onto the states followed by a trace-out operator, since measurements are destructive. We denote the classical outcome of a measurement performed at qubit i by m i ∈ Z 2 . We take the specific convention that m i = 0 if the measurement outcome is |+ α , and that m i = 1 if the measurement outcome is |− α . Outcomes can be summed together resulting in expressions of the form m = i∈I m i which are called signals, and where the summation is understood as being done modulo 2. The domain of a signal is the set of qubits on which it depends (in this example, the domain of m is I). 4. X i and Z i are one-qubit Pauli corrections which correspond to the application of the Pauli X and Z matrices, respectively, on qubit i.
In order to obtain universality, we have to add a classical control mechanism, called feed-forward, which allows measurement angles and corrections to be dependent on the results of previous measurements [2,3]. Let m and n be signals. Dependent corrections are written as X m i and Z n i and dependent measurements are written as n [M α i ] m . The meaning of dependencies for corrections is straightforward: The rewrite rules also contain the following free commutation rules which tell us that if we are dealing with disjoint sets of target qubits, then measurement, corrections and entanglement commands commute pairwise [3], so that where k represent the qubits acted upon by command A, and are distinct from i and j. Standardisation allows us to graphically present the global operation of a pattern. We define an open graph state (G, I, O) to consist of an undirected graph G together with two subsets of nodes I and O, called inputs and outputs. We write V for the set of vertices in G, E for the set of edges, I c , and O c for the complements of I and O in V and E G := {i,j}∈E E ij for the global entanglement operator associated with G. Trivially, any standard pattern has a unique underlying open graph state, obtained by neglecting measurements and correction commands.
We now give a condition on geometries under which it is possible to synthesize a set of dependent corrections such that the obtained pattern is uniformly and strongly deterministic, i.e. all the branches of the computation are equal, independently of the angles of the measurements. In what follows, x ∼ y denotes that x is adjacent to y in G and N I c denotes the sequence of preparation commands i∈I c N i .
The coarsest order for which (f, ) is a flow is called the dependency order induced by f and its depth is called flow depth.
where the product follows the dependency order of f , is uniformly and strongly deterministic, and realizes the unitary embedding If the underlying geometry of a pattern has a flow and its pattern command sequence is constructed as given by the flow theorem, we call this pattern a pattern with flow.

Ancilla-Driven Model
As mentioned in the introduction, in ancilla-driven quantum computing we are interested in two essential properties: • The only global operation is a fixed two-qubit interaction between any ancilla and system qubit.
• Only ancilla qubits will be measured.
We introduce the ADQC model within an algebraic framework similar to that of the measurement calculus recalled in the previous section. We have a set of fixed basic commands described below where the indices i, j, . . . represent the qubits on which each of these operations apply. A pattern is a sequence of commands defined over a set of qubits in the list V , called computation space, where the particular sub-list S represents the system qubits (we may refer to them as data or memory register) and the rest A = V \ S are the ancilla qubits. We define an arbitrary pure single qubit state by and denote its orthogonal state (the opposite point in the Bloch sphere) with where 0 ≤ θ ≤ π and 0 ≤ φ ≤ 2π.
• Preparation. N |ψ a (a ∈ A) prepares an ancilla qubit in the state |ψ .
• Interaction. E as (s ∈ S, a ∈ A) entangle a system qubit and an ancilla qubit with interaction operator ∧Z followed by Hadamard on each qubit: Note that a SWAP ∧Z interaction would be another possible choice. In section 4 we will prove that ∧Z and SWAP ∧Z are the only two possible interactions, up to local unitary equivalence, that allow for universal ADQC. Choosing one over the other will depend on the natural dynamics of the physical system used for an implementation.
with the convention that |+ θ,φ + θ,φ | a corresponds to the outcome m a = 0, while |− θ,φ − θ,φ | a corresponds to m a = 1. The propagation of dependent corrections (next command) defines dependent measurement: where m, n, . . . are module 2 summation of several measurements outcomes, also called signals. The domain of a signal is the set of qubits on which it depends. 1 • Corrections. X i and Z i (i ∈ V ), 1-qubit Pauli operators. As in MBQC, to control the non-determinism of the measurement outcomes certain local corrections will depend upon previous measurement outcomes. These will be written as C m i , with C 0 We write H V for the associated quantum state space ⊗ i∈V C 2 . To run a pattern, one prepares the system qubits in some given input state Ψ ∈ H S , while the ancilla qubits are all prepared according to the N commands in fixed |ψ states. The commands are then executed in sequence, and finally the result of the pattern computation is read back from the system qubits 2 . Similar to the one-way model we will consider only patterns satisfying definiteness conditions. The main differences between ADQC and MBQC are: (1) The interaction operator being ∧Z instead of ∧Z, which still belongs to the so-called Clifford group, the normaliser of the Pauli group; (2) Only ancilla qubits can be measured, that is to say in the terminology of MBQC any ADQC pattern has the same number of inputs and outputs which are overlapping (system qubits). Apart from universality, which we will prove later most of the theory of measurement calculus [3] which was developed for the one-way quantum computer can be easily adapted to ADQC. For completeness we briefly review this here.
The first way to combine patterns is by composing them. Two patterns P 1 and P 2 may be composed if S 1 = S 2 . Provided that P 1 has as many system qubits as P 2 , by renaming these qubits, one can always make them composable. However it is important to emphasise that since the E ij operators are noncommuting, their order of appearance in each pattern must be preserved under the renaming and composition. The other way of combining patterns is to tensor them. Two patterns P 1 and P 2 may be tensored if V 1 ∩ V 2 = ∅. Again one can always meet this condition by renaming qubits in a way that these sets are made disjoint.

The semantics of patterns
We present a formal operational semantics for ADQC patterns as a probabilistic labelled transition system, similar to [3]. Besides quantum states, one needs a classical state recording the outcomes of the successive measurements made in a pattern. If we let U stand for the finite set of qubits that are still active (i.e. not yet measured) and W stands for the set of qubits that have been measured (i.e. they are now just classical bits recording the measurement outcomes), it is natural to define the computation state space as In other words, the computation states form a U, W -indexed family of pairs q, Γ, where q is a quantum state from H U and Γ is a map from some W to the outcome space Z 2 . We call this classical component Γ an outcome map, and denote by ∅ the empty outcome map in Z ∅ 2 . We need further notation. For any signal m and classical state Γ ∈ Z W 2 , such that the domain of m is included in W , we take m Γ to be the value of m given by the outcome map Γ. That is to We may now view each of our commands as acting on the state space C: We introduce an additional command called signal shifting: It consists in shifting the measurement outcome at i by the amount m Γ . Note that the Z-action leaves measurements globally invariant, in the sense that Thus changing α to α + π amounts to exchanging the outcomes of the measurements, and one has Signal shifting allows us to dispose of the Z action of a measurement, sometimes resulting in convenient optimisations of standard forms. In the rest of the paper, for simplicity, we omit the superscript Γ on the measurement outcomes. The convention is that when one does a measurement the resulting state is renormalised and the probabilities are associated with the transition. We do not adhere to this convention here, but instead leave the states unnormalized. The reason for this choice is that in this way, the probability of reaching a given state can be read off its norm, and the overall treatment is simpler.

Denotational Semantics
We now present the denotational semantics of ADQC patterns. If n is the number of measurements then the run may follow 2 n different branches. Each branch is associated with a unique binary string n of length n, representing the classical outcomes of the measurements along that branch, and a unique branch map (Kraus operator) K n representing the linear transformation from H S to H S along that branch. This map is obtained from the (un-normalised) operational semantics via the sequence (q i , Γ i ) with 1 ≤ i ≤ m (where m is the total number of commands), such that and all measurement commands in the sequence {K i } have been replaced by appropriate projections corresponding to the outcome index n. Definition 2. A pattern P realizes a map on density matrices ρ given by ρ → ] for the map realised by P.
It is then easy to prove [3] that each pattern realizes a completely positive trace preserving (CPTP) map and if a pattern is strongly deterministic (see section 2), then it realizes a unitary embedding [3]. Hence the denotational semantics of a pattern is a CPTP-map. It is also compositional, as the following theorem shows.
Theorem 2. For two patterns P 1 and Proof. Recall that two patterns P 1 , P 2 may be combined by composition provided P 1 has as many system qubits as P 2 . Suppose this is the case, and suppose further that P 1 and P 2 respectively realise some CPTP-maps T 1 and T 2 . We need to show that the composite pattern P 2 P 1 realizes T 2 T 1 . Indeed, the two diagrams representing branches in P 1 and P 2 : can be pasted together, since S 1 = S 2 , and H S1 = H S2 . But then it is enough to notice 1) that preparation steps p 2 in P 2 commute with all actions in P 1 since they are appled on disjoint sets of qubits, and 2) that no action taken in P 2 depends on the measurements outcomes in P 1 . It follows that the pasted diagram describes the same branches as does the one associated to the composite P 2 P 1 . A similar argument applies to the case of a tensor combination, and one has that P 2 ⊗ P 1 realizes T 2 ⊗ T 1 .

Generating patterns
In order to prove the universality we present two simple generic patterns where only measurements in the (X, Y ) plane (M α ), Pauli Z measurements (M Z ) and preparations of the ancilla in the state |+ (N ) are sufficient. Note that a Pauli Z measurement can be considered as a special case of a measurement in the (X, Z) or (Y, Z) plane, with α = 0.
The following one-parameter family J(α) generates all single-qubit unitary operators [27]: as any unitary operator U on C 2 can be written: for some α, β, γ and δ in R. Recall that the MBQC implementation of the J generator is the following pattern: where s is the system qubit input, a is the ancilla and E sa is ∧Z operator [27].
On the other hand, the following pattern also implements the J gate, but now the ancilla qubit a will instead be measured: where H s represents the application of a Hadamard gate on the system qubit.
We can now manipulate the new pattern to derive a generating pattern for the operator J in our model. We want to use E sa as the interaction command: In addition to this, we only need a generator for a two-qubit unitary such as ∧Z to obtain the full universality. The MBQC pattern for controlled-Z ij (E ij with i, j ∈ S) is, however, not desirable, as it is an operator between two qubits of the system rather than an interaction between system and ancilla qubits. Therefore the natural choice instead is to consider the interaction E as E as . It is easy to check that this, combined with Pauli Z measurement of the ancilla, will give us a simple generating pattern for the two qubit operator ∧Z: Any unitary can then be simulated by sequential and parallel compositions of the above generating patterns, where the composition simply glues given patterns over the common system qubits, while preserving the initial orders of the commands. We will return to the important issue of how to represent the composed pattern graphically, but in order to do so, we first have to address the important feature of standardization in the ADQC model. That is, the standardisation procedure which permits us to rewrite any well defined patterns, e.g. obtained from composition, in a standard form where all the preparation commands are applied first, followed by the entangling, measurement, and finally correction commands.
For simplicity, in the remainder of this paper we will restrict ourselves to a special class of patterns, namely, those using only ancillas of degree 1 with arbitrary (X, Y ) plane measurement and of degree 2 with Pauli Z measurement. However, the whole theory developed in this paper can easily be extended to the more general setting.

Standardisation
Similar to the one-way model [3] we present a simple calculus of local equations by which any general pattern can be put into a standard form where entanglement is done first, then measurements, then corrections. The consequences of the existence of such a procedure (called standardisation) are far-reaching and is explained in details in [3]. We just recall that since entangling comes first, one never has to do "on the fly" entanglements and the rewriting of a pattern to standard form reveals parallelism in the pattern computation. In a general pattern, one is forced to compute sequentially and to strictly obey the command sequence, whereas, after standardization, the dependency structure is relaxed, resulting in lower computational depth complexity. It is known that any MBQC model can admit a standardisation procedure if and only if the entangling command belongs to the normaliser group of the group generated by the correction commands [14]. This is the case for our ADQC model. The required rewrite rules are The rules for propagation of the correction through measurement are the same as for MBQC, but with additional rules for the M Z measurement: We also have the same free commutation rewrite rules: where k represent the qubits acted upon by command A, and are distinct from i and j.
Recall that the effect of a Z correction on a qubit a simply flips the outcome of a measurement to be made on that qubit. Hence we can replace the dependencies induced by the Z correction by appropriate operations over the measurement outcomes as described below. In what follows, m[n/m i ] denotes the substitution of m i with n in m, where m, n are modulo 2 summations of several measurement outcomes: One can then use the exact same method as for MBQC in order to prove that this rewrite system has the desired properties of confluence and termination. We emphasise again that a key difference between ADQC and MBQC is the interaction command E ij versus E ij . The explicit inclusion of the additional local Hadamard operations, E ij = H i H j E ij , is necessary for universality. This is due to the fact that no system qubit can be directly measured but instead any operation has to be implemented via the ancilla. It is apparent that while rotations in the z-basis can be performed with only E ij = ∧Z ij , no basis change at the system can be implemented via the ancilla.
As shown in section 2, for any standard pattern in MBQC we can write its underlying open graph state with qubits representing the nodes and E ij the edges of the graph. Then, remarkably, only from the geometry of this graph we can obtain the dependency structures to guarantee a deterministic computation in MBQC. In other words, the simple graph representation for the global operation defining pattern allows one to determine dynamic properties directly from the static structure. Can we still obtain similar properties for our new model? Despite the non-commutativity of E ij the answer is yes. In section 5 we define the twisted graph state which is the underlying geometry of a given ancilla-driven pattern obtained from standardisation and we present how one can directly construct the dependency structure from their geometry.

Characterisation of Interaction
A central question in the theory of measurement-based quantum computing is the characterisation of the universal resources [8,9,11,12]. Unlike these studies that analyse the computational power of a uniform class of multi-partite entangled states, we take a "bottom up" approach and identify basic building blocks that can be composed to perform universal ADQC. This requires the characterisation of all two-qubit interactions which couple any two ancilla and system qubits, while satisfying certain desirable conditions such as stepwise determinism, unitarity and standardisation that will lead to universality, in the 'universal state preparation' sense [11,12]. We obtain a full characterisation of universal resources for ADQC for these conditions, while in contrast, such a general result is not available for MBQC.
In this paper we will focus on stepwise determinism, that is a pattern which is deterministic after performing each single measurement together with all the Pauli corrections depending on the result of that measurement. Other computation strategies could be considered that are not stepwise deterministic, such as the (finitely) repeated application of the same operation in the scheme [8,9]. Generalising ADQC to adapt to these less restricted strategies remains an open problem.
We introduce the canonical decomposition of two-qubit unitaries [28], where W a , W s and V a , V s are single qubit unitaries and the diagonal global operation is D as (α x , α y , α z ) = e −i(αxXa⊗Xs+αyYa⊗Ys+αzZa⊗Zs) .
The vector α = {α x , α y , α z } characterizes all non-local properties of E as . It is sufficient to restrict the α's to 0 ≤ α x,y,z ≤ π/4, and the set of distinct α, up to symmetries, make up the so-called Weyl chamber. The complete characterisation of two-qubit interactions that allow for universal ADQC is summarised in the following theorem: Theorem 3. The global interactions, E as , between any two system and ancilla qubits which enable stepwise deterministic and unitary evolution that also admits standardisation procedure for universal ADQC are locally equivalent to (i.e. D as is of the form) ∧Z and SWAP ∧Z.
Note that, both ∧Z and SWAP ∧Z are among the so called "maximally entangling" operators, hence the importance of the above theorem is in the only if part which proves for the first time the necessity of this particular type of building blocks.
The proof of Theorem 3 is lengthy and we have broken the characterisation of the non-local operation D as into several lemmas on unitarity, determinism, standardisation and universality. Figure 1: The qubit s belonging to the system in state ρ and the ancilla qubit, a, are coupled via the two-qubit unitary e Eas. For suitably chosen local unitaries V a and W a , the initial ancilla state V a |+ a = |+ γ,δ a and the measurement basis {W † a |+ a, W † a |− a} = {|+ θ,φ a, |− θ,φ a} are such, that the final state of the system ρ ± is related to the initial state by a single qubit unitary on s, ρ ± = U ± s ρ U ± † s , conditional on the measurement outcome of the ancilla.

Conditions for unitarity
In order to guarantee a stepwise deterministic computation we require that the application of a two-qubit interaction E as , followed by measurement of the ancilla shall result in an effective unitary evolution of a single system qubit, this is called unitary condition. In what follows, we absorb the local unitaries W a and V a in Equation (32) into the preparation and measurement of the ancilla, by choosing appropriate initial state and the measurement basis for ancilla (see For α x , α y = 0 it is necessary and sufficient that both, the initial state and the measurement basis of the ancilla lie in the X −Y plane, i.e. γ = θ = π/2. When one α is non-zero, w.l.o.g. α x = 0 and α y = 0, then the ancilla parameters must obey the following relation: sin θ cos γ sin φ = cos θ sin γ sin δ .
Proof. Depending on the measurement outcome, denoted by + or −, the system qubit is transformed according to where the Kraus operatorsK ± s are given bỹ These Kraus operators shall be proportional to unitaries. The local unitaries on the system qubit, W s and V s , do not affect whether or not the interaction E as generates a unitary transformation on the system qubit.
We will thus focus on the non-local portion D as of E as for now and reintroduce the local unitaries when discussing the standardisation procedure in Lemmas 4 and 6. The Kraus operator corresponding to D as alone are and D as can be diagonalized in the Bell basis [28], with The completely positive, trace preserving map on ρ in Equation (34) shall have only two possible outcomes, i.e.
The right hand side of the above equation for a general D as and initial ancilla state |+ γ,δ a is equal to where t = sin 2α x sin 2α y cos γ (40) r = sin γ sin 2α z (sin 2α y cos δ − i sin 2α x sin δ).
Since t = r = 0 must hold, at least one of the α j 's must vanish. Let us without loss of generality choose α z = 0 and hence r = 0. If only one α is non-zero then t = 0 is already true. However, if both α x , α y = 0, then the initial ancilla state must lie in the X − Y plane, i.e. γ = π 2 . These two types of interaction are much studied in physics due to their significance for coupled spin systems. The case with only one non-zero α is referred to as an Ising interaction, and the case with two non-zero α's as a Heisenberg interaction [29]. Both cases must have individual Kraus operators that are themselves proportional to unitaries, with probabilities p + + p − = 1. This puts requirements on the initial state and measurement basis of the ancilla as we discussed next. For the Heisenberg interaction with α z = 0, α x = 0, α y = 0, the initial state of the ancilla is in the X − Y plane (γ = π/2) and Equation (42) makes it necessary that the measurement basis of the ancilla must lie in the same plane, i.e. θ = π/2. The Kraus operators can then be written as, up to insignificant phase factors, with The probabilities for obtaining the measurement results + and − are independent of the system ρ and are given by (1 ± cos 2α x sin δ sin φ ± cos 2α y cos δ cos φ) .
For the Ising interaction with α z = α y = 0, α x = 0 since only one of the α j 's is non-zero, then any initial state of the ancilla, |+ γ,δ a , will lead to unitary Kraus operators for the system qubit provided the measurement basis for the ancilla, {|+ θ,φ a , |− θ,φ a }, is chosen such that sin θ cos γ sin φ = cos θ sin γ sin δ.
This can be satisfied, for instance, by θ = γ and φ = δ for arbitrary initial state |+ γ,δ a . The Kraus operators for the Ising interaction are given by where n ± are arbitrary integer numbers and the real coefficients A ± , B ± are where the angle θ and the phase φ of the measurement basis has to satisfy Equation (45). The probabilities for the two measurement outcomes are p ± = 1 2 (1 ± sin θ sin γ cos δ cos φ ± cos 2α x (cos θ cos γ + sin θ sin γ sin δ sin φ)) .
This concludes the proof of lemma.

Conditions for correctable branching
As the measurement results are random, the unitary operation that is applied to the state is either U + s or U − s where U ± s = K ± s / √ p ± are the normalised Kraus operators. To generate a deterministic evolution, for example with U + s , we require that the other unitary, U − s , can be corrected with an additional Pauli correction P s (up to an unimportant relative phase ∆), General Pauli corrections are of the form P s (a, b, c) = aX s + bY s + cZ s with a, b, c ∈ R and a 2 + b 2 + c 2 = 1 and have the properties Pauli corrections are the standard choice in measurement-based computation. Their structure is well understood and essential in ensuring an overall deterministic computation. Reuniting the branches with a Pauli correction after the measurement places no direct constraint on the interaction, D as . Instead this can be achieved by choosing the initial state and the measurement basis of the ancilla appropriately, as specified below.
In the Heisenberg case the correctable Kraus operators (43) must fulfil the relation a * + a − + b + b * − = 0, i.e. the two non-zero α's must relate to each other as cos 2α x tan δ = tan φ cos 2α y .
It can be seen that all values of α x and α y can be covered independently by choosing the phases δ and φ for the ancilla appropriately. However, if one of the interaction parameters is chosen as α y = π/4 the above relation implies δ = 0 and the probability for each branch becomes p ± = 1 2 . It will be discussed in Lemma 4 that this requirement is indeed necessary to allow for the standardisation of a computational pattern. The Kraus operators Equation (43) then have the coefficients It can be seen that these parameters imply that the Pauli correction between the two Kraus operators is Y (up to a phase), K + s = i Y s K − s . In the Ising case, the Kraus operators are a sum of identity and Pauli-X only, see Equation (46) and the only non-trivial correction available is X. To fulfil one has to choose the ancilla's initial state and measurement basis such that It can be seen that one n has to be even and the other one odd in oder to satisfy this condition. The probabilities for the two measurement outcomes need not be balanced and are given as p ± = A 2 ± + B 2 ± . The interaction strength α x can then be manipulated by choosing the ancilla parameters,

Conditions for standardisation
A computation can be standardised, see 3.4, when a general Pauli correction transforms, under the interaction D as , into a tensor product between ancilla and system qubit, where the new correction on the system qubit is again a general Pauli operation. By symmetry of D as the same must be true for the ancilla, i.e. we require where T a and Q s are either general Pauli operations or the identity operation. If this relation is valid the correction P s can be commuted through future interactions and shifted to the very end of the computation.  P (a, b, c), up to relabeling of the α's, that obey the standardisation relation Equation (52) 1. Fixed Heisenberg interaction: α y = π/4 and α x = π/4. Here Pauli corrections P (a, b, 0) and P (0, 0, 1) transform according to 2. General Heisenberg interaction: α y = π/4 and α x = π/4. Pauli corrections P (1, 0, 0) transform according to Proof. For D as (α x , α y , 0) the general Pauli correction P (a, b, c) transforms according to D as 1 a ⊗ P s D † as = 1 a ⊗ (a cos 2α y X s + b cos 2α x Y s + c cos 2α x cos 2α y Z s ) To determine which interactions fulfil Equation (52) we take the partial traces of either the ancilla or the system. Reading from the right hand side of Equation (52) the traces must be, up to global phases, Figure 2: Composition of gates on a single qubit s. In this example, each line represents the same effective computation. Attempting to implement K + (ϕ 1 ) results, with probability p − , in the actual operation K − (ϕ 1 ) = P K + (ϕ 1 ) where a correction P appears (first line). The correction can be shifted past local unitaries W and V (second line) and past subsequent ancilla-driven operations K + (ϕ 2 ) (third line), see the text for details.
The partial trace over the ancilla in the Heisenberg case, Equation (53), is Tr a [D as 1 a ⊗P s D † as ] = 2·(a cos 2α y X s +b cos 2α x Y s +c cos 2α x cos 2α y Z s ). (56) For α x , α y = 0 this expression can never be equal to 2Q s where Q s is a general Pauli or the identity for the system qubit. However, the right hand side can vanish (and T a must hence be a general Pauli) when a = 0 and α x = π/4 or b = 0 and α y = π/4 or α x = α y = π/4. Thus, for the Heisenberg interaction one of the parameters has to be fixed to π/4 to enable full standardisation of the computation and we choose, without loss of generality, α y = π/4. In the case that b = 0, i.e. for corrections P (a, 0, c), the right hand side of Equation (53) becomes which implies either c = 0 to match condition Equation (54). When both α = π/4 then the right hand side of Equation (53) becomes (−bX a + aY a ) ⊗ Z s + cZ a ⊗ 1, (58) and the correction must thus be either P (a, b, 0) or P (0, 0, 1).
An example for Case 1 is the SWAP ∧Z interaction whereas Case 2 allows a range of parameters 0 < α x < π/4; however, only one type of correction, X, obeys the standardisation condition. This becomes an issue when composing several ancilla-driven operations after one another.

Lemma 5. Case 2 in Lemma 4 is not compositional.
Proof. In order to implement arbitrarily complex computations it is necessary to repeatedly apply ancilla-driven unitary transformations to a single system qubit, see Figure 2.
The full ancilla-system interaction E as plus measurement of the ancilla generates the effective operator sequence ±| a E as |+ a = W s K ± s (ϕ) V s on the system qubit, where W s and V s see Equation (32) are the local unitaries on the system qubit and ϕ denotes all ancilla parameters. Due to the probabilistic nature of the measurement, when attempting to implement the operation K + (ϕ 1 ), the actual outcome could be K − (ϕ 1 ) ∝ P K + (ϕ 1 ) with a correction P , pictured in the first line, Figure 2. The branching behaviour discussed in the previous subsection requires that P = Y for the Heisenberg interaction and P = X for the Ising interaction. The local unitaries affect this original correction and transform it into a possibly different general Pauli P , as shown in the second line, Figure 2.
Constructing an arbitrary computation requires composition of subsequent ancilla-driven operations, K + (ϕ 2 ) etc. When commuting the correction P with the K + (ϕ 2 ) the result must be a new Kraus operation K ± (ϕ 2 ), implemented by a (possibly) different set of ancilla parameters ϕ 2 , and a new general Pauli correction P after the new Kraus operation, as depicted in the third line of Figure 2. In the two cases of interest here, cases 2 and 4, Pauli X is the only allowed correction, i.e. P = X. Moreover, in order for the new correction P to be shifted further, it has to be identical to the branching relation P , or 1.
The pictorial shifting conditions imply the following mathematical relations where ∆, ∆ , ∆ are arbitrary global phases. In Case 2 of Lemma 4 this set of equations cannot be fulfilled, as there is no pair of ancilla parameters ϕ 2 and ϕ 2 for which the Kraus operators Equation (43) with coefficients Equation (49) obey K + (ϕ 2 ) Y = e i∆ X K ± (ϕ 2 ) or K + (ϕ 2 ) Y = e i∆ K ± (ϕ 2 ). This implies that the possible ancilla-driven computations using a general Heisenberg interaction are extremely limited -only one ancilla interaction per system qubit can be tolerated. To enable composition with the Heisenberg interaction forces the interaction parameter to take the special value α x = π/4. Similarly, we characterise the Ising interaction cases.
Case 4 again allows only one type of correction, an X correction. We prove next that this requirement restricts any obtained ancilla-driven unitaries on a single system qubit to be on a fixed plane and thus fails universality.

Universality
The general Ising interaction, Case 4, fulfils the set of equations 59 as the Pauli X correction commutes with the actual Kraus operators (46), where the product of the local unitaries has to obey V W X = e i∆ XV W , i.e. V W is either of the form (up to global phases) V W = a1 + ibX or of the form V W = aY + bZ with some coefficients a, b ∈ R and a 2 + b 2 = 1. However, this leads to the following lemma.
Lemma 7. Case 4 in Lemma 6 is not universal.
The coefficient functions a(ϕ 1 , ϕ 2 , . . . ) and b(ϕ 1 , ϕ 2 , . . . ) with a 2 + b 2 = 1 will depend on the choice of all ancilla parameters ϕ 1 , ϕ 2 , . . . in the sequence. It is easy to show that both classes of operations, for arbitrary parameters, can move a given input state only in one plane of the Bloch sphere, parallel to the Y − Z plane. Finally, we note that the additional first and last local unitary operation, V and W , which individually can take arbitrary form as long as their product V W (anti-)commutes with X, are fixed. That means that once W an V are given, the plane whereŨ operates is tilted into an arbitrary, yet fixed direction in which the state can evolve. Since it is impossible to move out of that plane it is implied that the U (ϕ 1 , ϕ 2 , . . . ) for general Ising interaction, Case 4, does not allow universal single qubit preparation.
The final step for the proof of Theorem 3 is given below. Proof. It suffices to identify suitable local operations that ensure universality. The ∧Z interaction is an example for Case 3 and choosing the local unitaries V s and W s appropriately, for instance: = H a P (π/2) a H a ⊗ H s P (π/2) s H s D as (π/4, 0, 0) H a ⊗ H s makes this model universal as we proved in Subsection 3.3. The SWAP ∧Z interaction is an example for Case 1 and it is easy to verify that ADQC model with SWAP ∧Z is indeed the same as the one-way model, as the position of ancilla and system qubits are swapped, and hence universal.
Note that the local unitaries on the ancilla are irrelevant as they just redefine initial state and measurement basis of the ancilla. Moreover, as said before, for the Case 3 the local unitaries on the system have to enable a "change of basis", this would rule out the class of diagonal unitaries. However, the full characterisation of local unitaries that makes each cases 1 and 3 universal remains an interesting open problem. For the rest of this paper we will focus on the E as = H a ⊗ H s ∧Z as interaction which defines a new class of entangled states.

Twisted Graph States
The main issue with the E ij operators is the fact that they are non-commuting, therefore after standardisation their order will be important. Another important property of an ancilla-driven pattern is that system qubits interact only with ancilla qubits. Therefore we introduce a multipartite entangled state as a graph over ancilla and system qubits and E ij edges with extra condition to address the above mentioned requirements. In Section 6.2 we show how this new class of states can be viewed as open graph states up to some local swap operators. This is the reason behind the chosen name.

Definition 9.
An open twisted graph state (G, S, A, C) consists of a bipartite graph G over disjoint sets of qubits S and A, called systems and ancillas, such that the maximum degree of any ancilla node is 2, together with an edge labelling C. The labels define a partial ordering over edges where the order is total and strict on any edges that share a common vertex, i.e. it defines an edge colouring.
The corresponding quantum state, denoted as | E G , is obtained by preparing qubits in S in given arbitrary states and all the qubits in A in the |+ state, and then applying E ij over corresponding qubits according to the partial order of C (see Figure 4).
One may think of an open twisted graph state as the beginning of the definition of an ancilla-driven pattern, where one has already decided how many qubits will be used (V = S ∪ A) and how they will be entangled: To complete the definition of the pattern it remains to decide which angles will be used to measure ancilla qubits and, most importantly if one is interested in determinism, which dependent corrections will be applied. Conversely, any ancilla-driven pattern has a unique underlying open twisted graph state obtained by forgetting measurements and corrections where the colour of the edges is given by the most partial order of the E ij commands which respects the noncommuting order. Recall that two E ij commands commute if and only if they act on disjoint set of qubits. Note that the depth of this partial order is the true depth of the preparation of the state.
Different ordered colourings over the same graph structure might lead to different twisted graph states and consequently different patterns of computation. We leave as an open question whether one can find a more relaxed definition that can still uniquely define the entangled state corresponding to an ancilladriven pattern. On the other hand our restrained definition will allow us to derive the dependency structure of the measurements directly from the order of the colouring, this is the topic of the next subsection.

Dependency structure
We will use the graph stabiliser formalism [10,19] to construct a deterministic pattern. Recall that for any open graph state |E G defined over a graph G with vertices V , we have the following set of equations for all the non-input qubits: where G(i) is the set of neighbour vertices of i in G. The above Pauli operators are called the stabiliser operators of |ψ . Similarly we define the stabiliser operators of a given twisted graph state | E G defined over a graph G with vertices V = S ∪ A. We will use the following notation as well. Define S(a) for a ∈ A to be the attached system qubit s ∈ S with the smallest edge label and S (a) to be the other one if it exists; N (s) for s ∈ S to be the set of ancilla qubits connected to the system qubit s; and finally G S(a) to be the sub-graph with edges between S(a) and N S(a) .
Consider first a simple case where E G = E aS(a) N |+ a . Then the stabiliser has the form The above equation is due to and for another simple case of again due to In order to generalise the above cases the following rewrite rules for Pauli commutations will be used: transforms the X operation on the system qubit to the next immediate ancilla qubit, introducing a Z operation at the system qubit.
replaces the Z operation on the system qubit with an X operation.
Unlike the stabiliser of the graph state which has a local structure, in the case of a twisted graph state the stabiliser of a may affect the whole of the graph. This action is, however, recursive and can be defined using the collection of several local actions. Define the label of an ancilla node to be the same as the label of the edge E aS(a) . Consider an ancilla qubit a and those qubits in N (S(a)) with label greater than label of a (see Figure 5). We can assume, without loss of generality, that all edges connected to S(a) have labels 1 to n with 1 being the label of a. This is due to the fact that the stabiliser of a has an effect only on those qubits in N (S(a)) where their edge interaction are after the edge interaction of a and S(a) hence having a greater edge label. Definition 10. Given a twisted graph state (G, S, A, C), a local stabiliser on the ancilla qubit a is defined as following: • Consider vertices in G S(a) with labels greater than label of a and relabel them from 1 to n according to C ordering, with 1 being the label of a.
• Add X on vertices in N (S(a)) with even label and degree 1.
• Add Z on vertices in N (S(a)) with even label and degree 2.
• Add X on the system qubit if n is odd otherwise add Z.
We denote the above set of Pauli operators with P l (S(a)) which acts on a subset of qubits in N (S(a)).
Define I(a) to be the set of degree-two ancilla qubits in N (S(a)) with even label that get a Z Pauli operator in the definition of the local stabiliser of a. The stabiliser of a will have the same local effect as defined above over S(a ) for all the a ∈ I(a) and the same structure repeats for vertices in I(a ). Therefore we define recursively such qubits I * (a) = {a |∃n : a ∈ I n (a)} where I 1 (a) = I(a) and I n+1 (a) = a ∈I n (a) I(a ). We can now present a recursive definition for the stabiliser of a twisted graph state as the product of a collection of local stabilisers.
Definition 11. Given a twisted graph state (G, S, A, C), the stabiliser on the ancilla qubit a is defined as follows: P (a) = Z a a ∈I * (a) P l (S(a )) if a has degree one P (a) = X a a ∈I * (a) P l (S(a )) otherwise It is a straightforward but cumbersome computation to show the correctness of the above definition and we omit the details of the proof.
We can now adapt the notion of flow and generalised flow of graph states [13,14] for twisted graph states to derive a sufficient condition for determinism. The key idea is exactly the same as in the MBQC case based on the following simple observation. We could make a measurement M (X,Y ),α i "deterministic" (corrected) if it could be pre-composed by an anachronical Z si i correction (i.e. conditioned on the outcome of a measurement which hasn't happened yet). This unphysical scenario is a useful starting point for our proof.
The flow construction guarantees that a deterministic pattern with anachronical can be transformed into a runnable pattern, where all dependencies will respect the proper causal ordering. The key observation which allows us to transform this into a runnable pattern is that the flow construction defines a stabiliser P f (a) which when composed with the anachronical correction, forms an operator which commutes with the measurement, and thus the pattern can be brought into runnable order. For simplicity in the rest of the paper we consider only patterns where degreetwo vertices are measured with Pauli Z and degree-one vertices are measured in the (X, Y ) plane, we use the generic term M λa,αa a for both cases. This class of patterns are large enough to introduce a universal ADQC model as they include the generating pattern introduced in Section 3.3. However the definition of flow and determinism can be extended to the more general case as well.

Definition 12.
An open twisted graph state (G, S, A, C) has causal flow if there exists a partial order > over V such that for all a ∈ A and all vertices a ∈ P (a) we have a < a except for those a that will be measured with Pauli Z. where the product follows the dependency order >, is runnable, uniformly and strongly deterministic.
Proof. The proof is based on the following equations first consider the (X, Y ) measurement case for degree-one ancillas: Similarly for the Z measurement over degree-two ancillas we have: Hence we can write: The left hand side is clearly a uniformly and strongly deterministic pattern. The right hand side pattern is runnable as the introduced corrections follow the partial order > except for the Z correction introduced over degree-two ancillas.
However one can ignore them since these qubits will be measured with Pauli Z and we have M Z a Z m a = M Z a . This finishes the proof. It is interesting to note that the flow definition for a graph state was based on the geometry of the underlying graph, whereas in a twisted graph state it is based on the edge colouring order. Indeed, as mentioned before, different edge colourings lead to different twisted graph states and hence different flow constructions. Roughly speaking, the edge colouring plays the role of geometry for the twisted graph states.

Compositional Embedding
One of the main foci in constructing direct translations between models is to study parallelism as the more parallel the computation, the more robust it is against decoherence. Recently the advantage of MBQC over GBQC in terms of depth complexity has been demonstrated where a logarithmic separation was shown [30]. We will prove a similar result for ADQC and we present a transformation between ADQC and MBQC that preserves depth.

GBQC and ADQC
The question of translating GBQC circuits into MBQC patterns and vice versa has been addressed before in [30] and it can be directly adapted for ADQC as well. In fact the universality proof of ADQC already presents a method of translation of a circuit into ADQC: (I) Rewrite the given circuit in terms of the universal gates set of J(α) and ∧Z; (II) Replace each gate with its corresponding ADQC pattern (equations 16 and 17); (III) Perform the standardisation procedure.
The above construction cannot be used in reverse as the edge colouring order might lead to a circuit with an acausal loop. However it is possible to keep all the auxiliary qubits to avoid creating loops in the resulting circuit. The scheme is simply based on the well-known method of coherently implementing a measurement [30]. It is also easy to prove, in a similar way as in [30], that the translation from a GBQC circuit into an ADQC pattern will never increase the depth as the edge colouring number of the obtained twisted graph state will be upper-bounded by the depth of the original circuit. More importantly, we present an example where the depth decreases exponentially. Consider the ladder structure of the circuit in Figure 6 which has depth n. This circuit, through the introduced construction, will be translated into a pattern with the twisted graph state shown in Figure 6 which has constant depth 4. This is due to the fact that the preparation depth for any ADQC pattern by definition, is upper bounded by the edge colouring of the graph, which in this case is equal to 4. On the other hand the Pauli X measurements on the right most qubits, break the dependency chain between measurement i.e. an α i measurement depends only on the result of some Pauli measurements. Hence one can find a flow for this twisted graph state where all the Pauli measurements are in the first layer of the corresponding partial order and all the non-Pauli measurements are in the final layer and computation depth which is equal to the flow depth is 2. It is easy to verify that the same logarithmic depth separation result between GBQC and MBQC obtained for the parity function [30] is also valid for the case of GBQC and ADQC.

MBQC and ADQC
As mentioned before there exists a compositional embedding from MBQC patterns with flow into GBQC and vice versa, and together with the construction of the last subsection one can obtain an embedding between ADQC and MBQC for patterns with flow. However in view of parallelism, it is interesting to find such an embedding directly by presenting the correspondence between twisted open graph states and open graph states.
The following equation relates the two resources but it is only valid for degree-one ancilla qubits This equation and the next one are in fact the reason behind the chosen name for this class of states as one can recover a graph state from them by applying the appropriate sequence of twist (SWAP) operators. In order to handle the degree-two ancilla qubits we will use the following pattern equations In the new pattern for ∧Z both instances of E as can be replaced using Equation 62.
It is a straightforward but cumbersome computation to show that the above translation from MBQC into ADQC is depth preserving so we omit the details of the proof. We leave as an open question whether a general depth preserving translation between MBQC and ADQC can be constructed.

Discussion
ADQC presents significant advantages over GBQC for particular physical implementations. By isolating the system memory from measurement and state preparation, the physical layout of a quantum computer can be optimised. Potentially decoherent read-out mechanisms can be located away from the memory. Since only a fixed two-qubit unitary gate has to be implemented between memory and ancilla qubits, this simplifies considerably the construction, characterisation, control and operation of the computer. Control line clutter can be reduced, due to relaxing the need to implement single qubit rotations and measurement on the memory, simplifying the architecture of the computer as well as minimising the possibility of cross-talk. The choice of physical qubits for memory and ancilla can also be optimised. Memory qubits can be chosen for long coherence times at the expense of being static, whilst ancilla qubit can be chosen for mobility, and ease of initialisation and measurement.
Natural candidate systems consist of an array of static qubits addressed by flying qubits or a "read/write" head. For example, an optical lattice of neutral atoms can be addressed by a separately controlled atom [31,32]. Since it is difficult to individually address with lasers a single site of a fully filled optical lattice, the read-write head would interact with selected sites and can be used as the ancilla. A similar idea can be applied to neutral atoms trapped in dipole trap arrays [33] controlled by an atom in an optical tweezer [34]. Similarly in [35], ions in an array of micro traps would be manipulated by a single ion read-write head. Alternatively in [36], the role of the memory is played by the quantised electromagnetic field in an array of cavities whilst Rydberg atoms traversing the cavities act as ancillas (similar ideas are contained in [37]). All of the above schemes possess a natural ∧Z (dispersive) interaction between the ancilla and system qubits. For universality, either an additional Hadamard operation on the system should be incorporated into this interaction (e.g. through the pushing laser in [35]), or an effective SWAP operation be found in conjunction with the Controlled-Z. The latter could be achieved through cold collisions between ancilla and system [38,39].
A system which may prove particularly amenable to our model is discussed in [40]. Here, the nuclear spin of a single dopant atom in isotopically pure silicon plays the role of a memory qubit which can be controllably coupled via the hyperfine interaction to an electron spin which acts as an ancilla qubit. Nuclear spins can be very well isolated from the environment, as well as the state preparation and measurement areas. Electrons can be rapidly transported around the computer using charge transport via adiabatic passage (CTAP), this avoids the issue of swapping nuclear spin states, as in the original Kane proposal [41], which can lead to a reduction in fault tolerance. An issue here is making sure that the interaction between electron and nuclear spins is of the correct form as to allow conditional unitary dynamics. An interaction of the form ∧Z followed by SWAP gate can be achieved by using the method presented in [42] with only the Heisenberg interaction between ancilla and system and local operations on the ancilla itself.
A natural interaction which is also suitable for ADQC is the XY-Hamiltonian which be easily turned into the SWAP ∧Z gate [43] (equivalent to the ISWAP in the aforementioned reference). In [44], a natural XY-interaction between nuclear spins, as in the Kane proposal, is mediated by a 2D electron gas in the Quantum Hall regime. The XY-interaction also naturally occurs between quantum dots coupled by a cavity [45] or superconducting qubits [46,47]. Here, the memory and ancilla qubits are of the same species.