Universal resources for measurement-based quantum computation

0:00 In fact, I'm going to talk about measurement-based quantum computation because, in fact, I don't want to talk about one-way quantum computations, only industries of the causal state model where you can make notations clear. This MQC remediation will be used quickly in the talk, and this is just for measurement-based quantum computation. So, in our work, we're not just dealing with the specifics of the cluster state model, but rather with some questions which are conceptual. Mainly, if you have the cluster state model in mind, then you know that quantum computation is conceived in the following sense. First, you prepare a large resource state, which is the cluster state, and then the state is processed by doing a single fluid layer. And in this way you can do university research, whatever you can do in it. Now, one question which may be alive is, we discuss the state of such university research, right? And in the same line of thought, which other states would be all university researchers and why? And related to this question, when is efficient mathematical simulation of such data-based quantum computations of certain resources possible? So, which research states would be completely useless? This is a question which is kind of similar to what Richard Wilk was talking about, but now in the

2:30 model. So, we don't ask which surface can be physically similar to chemistry, but we ask which states rise to efficiency. And, of course, important for this whole issue is the role of entanglement. Inclusively, it might be clear that entanglement should play a large role because if you look at the procedure of quantum computation, you start with a state and in the computation the only thing you do is destroy it. Because every time one keeps operations and in every step you kind of lose one cubit. So the document consists of two parts. The first one will be with Yaron Sarpy, and the second one will be with Jessica Simich. The first part, I think, is going to be together with another. So here is just one slide to remind you what a lot of the content of this is all about. So, suppose one wants to simulate the process where a unitary unit acts upon several states and discovers an output state on the side. What one does then, in the one-way model, is first one prepares for two discussing states of a certain size, where the size depends on the unitary, depends on this side state. After this stage has been prepared, you perform a sequence of measurements, from cubic measurements on cluster, for instance, the top left one is measured in x, some in z, and some filtered measurements, and so on. So, a bunch of qubits are measured, and some of them are not measured, in these circle forms here, and these remaining qubits who are not measured end up up to some local linear operation. And this one says that by one-way quantum computation on a cluster state, you can simulate the action of a unitary on the cluster.

5:00 And since you can do this for any unitary or for any state of size, you say that the cluster state is a universal resource. Now, my question is, which other states are universal in this sense? So first we need some kind of definition of universality, and we propose the following. So first, note that universality is some kind of property which should be attributed not to just one single state. As it's not one cluster state for a fixed number of qubits which is universal, it's really a class or the family of all the cluster states going down the qubits which are the whole resource. We just consider a family of states. It's psi-1, psi-2, and so on, ongoing number of qubits, and a class as interpenal states. And then we say that this family of states is a universal resource. And when we do quantum quantification, basically any state can be prepared by doing local measurements of this value. So what would we need for any state pi to use? There must exist some number in this class, a large number of qubits, such that this transformation is possible by means of local measurements or generally local operations and classical computations. So if you can do this for any state on any number of qubits n, then you have a universal transformation. The universal state is the universal resource if and only if you can prepare all 3D clusters. Both directions are in fact trivial because if you have the universal resource then surely you must be able to prepare the clusters if you can make anything. And of course if you can prepare the cluster states then you have the universal set because the cluster states themselves are universal resources.

7:30 You want to get an insight in the question if I'm given some, can I have some way of deciding whether it's universal or not. And we propose a way to do this by looking at a diamond-thin family in the following graph. So suppose you have a functional E, which is defined on curve states, and it should be defined on all m-thin states for all m-thin. And we note by each star the supremal value that this measure can take when taken from all possibilities. Now, further, we assume that this function has two properties. First, it's not increasing under LOCC in the following sense. So, if you have two states, psi and psi prime, and you give the transformation from psi to psi prime and so on. If the measurement is possible by LCC, then the measure, when evaluated in size, must be larger than when evaluated in size. And second, suppose that if you evaluate this measure on a given class in size, and you look at the supremum value which is obtained on this class, then it's larger than the supremum value. Now, here whenever you have a situation, then your family can't be universal. From the very definition of universality, you must be able to be there at any state, and therefore you must be able to reach this freedom. So if this is not possible, then you can rule out such family as being non-universal. The 2D justice state has the property of universality. One really has the property that for any measure e which has this property, that the supreme is in fact the least of the thousands.

10:00 The justice state and all universal resources, in a sense, must have a maximum entanglement. Sorry, I just realized I didn't... So we get something from me from the last slide about a universal resource. You have this sort of criterion with M and N that didn't say anything about the relative size of M and N. It doesn't so far. So when you say universal, you can sort of imagine a family of states. What if you need a sort of exponentially large state to do a small computation? Would you still call that universal? Well, in the first approximation, yes. But one shouldn't. Of course, we should take into account the efficiency there. And I won't do it in this talk because here I'm mainly concerned with the no-go results. So I don't care when even this is not possible. But in the end, that's up to you. Having this kind of strategy in mind, the question is, of course, which measures E are good ones? Which measures can you use to really decide that a certain class is universal? In our next paper, we have proposed two such measurements. The first is the localizing entanglement, and in fact I won't use this script because I have no time. I will focus here on a measure which we have introduced for this purpose, which we call entanglement width. And this is a measure which will prove particularly useful to assessing the results of graphs. I'll spend some time now defining it. Please first forget about this formula. So the entanglement width is defined as the minimal Schmitt plan in a system where the minimum is taken not over all bipartitions but over a specific class of bipartitions and which bipartitions you consider is in fact determined by some kind of combinatorial construction.

12:30 So, to compute the entanglement, we have to see it as follows. First, one draws an object, which is called, this is a graph, a tree graph, and it's a subcubic. A subcubic is meant that every edge here, sorry, every black vertex has exactly three edges coming out of it, and of course you have the leaves of the tree which have exactly one. The red edges, sorry, the red vertices in this tree, so the leaves, are to be associated with the qubits in a system. So every qubit is associated to one vertex, to one leaf in a tree. Once this is done, you single out some kind of edge, and so this is the other one, and you delete it from the tree. And then you end up with two subtrees, this one. Therefore, you end up with a bipartition of the leaves of the tree. Since we have identified the leaves of the tree with the qubits in the system, you end up with a bipartition of the system. And you compute the Schmidt rank of this bipartition. We will call the bipartition AEP and BEP. You compute this Schmidt rank. Having these three sticks, you do this for all edges. So in the second step, you put this edge back and you remove another one. And then again, if you touch a thing, and you take the maximum for all edges in the tree. And then you repeat this for all possible trees which you can draw where the leaves are attached to the cubits. And you take the minimum value. It's normal if you are thinking this is strange. And this is then the entanglement piece. And then one can show, by using the properties of this Schmitt rank, that also the entanglement width is really an entanglement of its own. It's even decreasing under the stochastic globalization.

15:00 And moreover, if you look at this entanglement width for the cluster states, then you can have this kind of bound, which means if you take the limit for infinite many qubits, then this thing actually diverges. So this is a quantity E star, this quantity E star here is just equal to infinity. So how does this measure respect the underlying structure of the graph? It doesn't care about the graph? It doesn't care about that. So this tree has nothing to do with the graph. So it means that different graphs will get the same amount of time? Okay. So this construction here is nothing but a way of partitioning your system in certain ways, that's all. So now because this thing is diverging from the justice state, this E star quantity is infinity. So this means if you're given some kind of state, resource, where this measure is bounded, then this thing cannot be a universal resource. Maybe you're doing what? There are some motivations for this measure, which I will deal with later in the talk, but now I just want to convince you that it's useful by going through results. So, it turns out that you can compute this entanglement width for graph states, for a bunch of graph states, and we in fact show that this measure is actually bounded for many class numbers. For instance, for the 1D cluster states, the linear chain is equal to 1, so it's bound, so these states cannot be universal. Neither can the GZ state, or tree graphs, or graphs locally equivalent to tree graphs, cycle graphs, and in fact there is a whole list of such graphs for which one can show that this measure is bound and therefore by this criteria they cannot be universal.

17:30 Sorry, so I'm confused. If the measure recognizes the difference between a glycograph and a 1-D cluster state, but you just said that this entanglement measure doesn't make any difference between the underlying graph structures. No, it may be the same. It can be the same. So, for instance, the entanglement with a 1-D cluster state is one, and for a geotephthate it's also one. But I think it's, for instance, too far. So it can coincide on certain graphs, but it doesn't have to. I think they can only do that at constant time. Yes. I didn't ask you a basic question. Yes, yes. So how does one prove these things? Well, the point is here that, in fact, there is something very special happening when you evaluate this entanglement, what we've measured in graph states. Namely, you can interpret this measure not as a measure of states, but as a measure of graphs, and this thing then corresponds to a graph parameter which has, in fact, already been defined for, namely, the so-called rank-width parameter. And this measure has been computed for all these graphs, and we just have the worst field results. Okay, so now I have one slide about this connection between these two things. So, I will more or less define what this rank is, and say what the relation is. So, suppose we have a graph in G, and this is the start. And then, what happens if we do this operation? So, this is the graph. This is the adjacency matrix. In this state, with respect to some bipartition. So, for instance, if you look here, you take a bipartition between these two qubits and the rest, and then you want to compute the Schmitt rank in this state with respect to this bipartition. Through the Schmitt rank, you will look at the latency matrix.

20:00 And you look at those rows in the latency matrix which are indexed by these vertices, and then you look at these rows, and within these rows you look at this kind of off-diagonal block in the middle. Here is A, and here is A, and this is kind of the complement of A. So this is a matrix that we call gamma-A. And using some very standard graph state techniques, you can show that this Schmitt rank is equal to just the rank of this gamma-A matrix. And using this identity example and this expression, we have a very similar expression now, but for here there is no mentioning of the state, but only of the graph. And this is the exact definition of this rank-width parameter. And, in fact, the way we defined this entanglement width measure was, we knew about this measure of rank width, and we knew that this thing could be interpreted as a Schmitt rank, and then you can look at the definition and just define this entanglement width for any space. If you have a family state, then it can only be a universal resource if this entanglement width is unbounded, and if you look at graph states, then the entanglement width is equal to the tank width, and this has been calculated for a bunch of graphs, so you can really have this result. And just a few words about this rank width. For people who are interested in graphing, the right width is a parameter similar to the tree width of a graph. It's a so-called width parameter, which is introduced for a common reason. So, like we all know, there are many graph problems which are very difficult to solve. And techniques have been developed.

22:30 All of these have the property to make such difficult problems solvable on certain subclasses of graphs. So one has introduced, for instance, this notion of tree width, which has the property that if you look at graphs, classes of graphs where this tree width is bounded, then NP-hard problems can become efficiently solved. So the question is there, if you have classes of graphs, does this class have a bounded tree width or an unbounded tree width? And the rank-width was defined later by William Seymour, but in fact it's the same region, and in fact it's a more powerful universe with parameters, but there are plenty of ways to have rank-width, gradient-width, peak-width, path-width... So this gives us some idea how to assess the results of these statistics. But there are several questions which remain. The first and the most obvious one is, is there any physical evolution behind this measure? We can use this starting from the graph-tree connection, but it may not be sufficient for physicists, so are we just lucky with this connection or is there something more here? There might be many states which are not universal, but which are still very useful to do a specific quantification. So the question here is, does this boundlessness of entanglement really imply, or does it not imply, that classical simulation is a specific question? And this goes down together with what I'll do. So just to repeat, now we're not really talking about universality, but we care about if we have a resource state or a family of resource states, when is simulation of such measurement-based quantum computation efficiently possible, and what is the role of entanglement here.

25:00 So here we have to remark that, in fact, this question or questions which are very similar in spirit have been addressed by many people. Namely, the global question of when can one have an efficient description of the quantum state and quantum system, and when can one, moreover, have an efficient simulation of dynamics. And this work has been done by several people. All the people in this list and many more. And this also has much to do with these matrix product states and these tensile networks, which are just mentioned in this talk. So the idea is to find descriptions of states which are efficient, so which don't need too many parameters, and then also kind of hope that also the processing of such systems can be done efficiently. And we'll see that these tensor networks, in particular, three tensor networks, will play quite an important role in our problem. With this one slide, I hope to make more or less clear what a three tensor network is. So, consider an expression of this form. This is a sum, and there are a bunch of tensors, A1, 2, and 6, with a certain number of integers. And some of these integers are summed over, they are contracted, so this is the i here and the i there, or the j here and the j there, and there are certain sums of integers, and other integers which are not summed over, like a, b, and h, and this we call open integers. Now, if, for instance, this expression has eight open integers, one can naturally associate such an expression All of these things can look very complicated and one has quite an elegant

27:30 This is a graphical way of representing which indices here are contracted with which others, and this is such and such graph. So, to go from this kind of expression to this picture, one simply draws a white vertex for every tensor. We have six of them. Two sensors are contracted. For instance, here we have I here and I there. We draw an edge between the corresponding vertices. I do this for all the white vertices. And I find that all the open inches here, for instance, are attached by the blue vertices. And you attach them to their corresponding vertices. So this is a graphical way of representing this, and this is just called the Penrose tensor graph. So any type of expression gives rise to a graph. So these graphs don't have to be treated like this. Now one can easily verify, like in the case of these matrix-border states, if these tensors are not too large, then one obtains an efficient description. The important point to keep is here, the maximum range of the integers in the network, right, so every index goes from one to a certain number, you take the largest of those numbers, and if, so you call this dimension, b, and if this b scales modically, then you have a state which can only depend on modically many parameters, right, so this gives you an efficient description. All these things have been shown by Xi, Yuan, and Li, that if this B is 1, then you can even simulate measurement-based quantum computation efficiently based on these types of descriptions. Moreover, this efficient classical simulation is possible exactly when

30:00 These graphs are for when you have tree graphs. If this thing corresponds to a tree graph, then you talk about a three tensor network, and these guides show that if this dimension D scales as O , then measurement-based quantum computation on such three tensor networks will be similar. Moreover, in these treatment semantics, it's sufficient to consider graphs which are exactly these trees which we optimized over in our entanglement measure. So these sub-qubit trees where every vertex has exactly three edges. So it's sufficient to consider only those in the sense that if you have some kind of state with an efficient treatment semantics description, So these kind of unnatural specific trees are all you have to consider. And this already hints at some connection with this. Now, these results of Shih, Yuan, and Lidl, they tell you that if you have, if you have a state and you know the tree tensor net description, However, if you are given a state, several of those three tensor descriptions might exist, and some of those might be efficient, and some of those might be not efficient. But the question is, if you are given a state, what is really the optimal one? What is the best one? Which three tensor networks have the smallest speed? So, results should be following. If you have a state side and a treat B, then you will always find the treat as a description of the side with underlying treat B, and the dimension of this treat as a network, so this largest...

32:30 The range of an index is given by exactly this construction by looking at Schmitt ranks of bipartitions, and the bipartitions are given in the exact same way as in this entangled equation. So you take out pages in the tree, and then you end up with two entangled trees, and you take the maximum value of the Schmitt rank. This is more or less similar to the results of Where you can show that every state has a matrix from its description. Okay, now this line here immediately gives us the desired interpretation of cantangles. Because if you now minimize this expression over all sub-territorial trees, then you find dots, no more. And you find the three-tensor matrix description of a state with the smallest dimension. Okay, so this is kind of now a more physical interpretation of the entanglement width. The entanglement width is a measure which gives you the smallest dimension, d, of any three-phase network, which represents this thing. And now we can immediately use these results by a sheet we want to build. At point n, then an efficient simulation of measurement-based quantum computation is possible. Of course, one has to know the optimal pre-test method. This is a problem. Moreover, if you have an entanglement which is bounded on a random state, so constantly bounded, then you have now an answer to the question we have, namely, you can really efficiently simulate any measurement-based quantum computation on this state. So this means every family which was ruled out as being non-universal, by the criterion of having bounded triangles with, do not prove that also the efficient simulation of any measurement-based quantum computation is in fact true.

35:00 So all the graph states with bounded triangles, they are also in the simulation process. And here we kind of recover all the results which were previously shown on simulation of omnipotent computational graph states. So Nielsen showed that you can simulate on one decluster state. He then showed that you can simulate on trees, also on graphs with small fields. And using this entanglement with bacteria, we all recover all these results. Very quickly here. Now, of course, in theory you know that if this entanglement width is multiply growing, and the optimal and the three-tester networks are available, then you can do the simulation. Of course, if you are given a state, you still have to calculate all these quantities. You have to calculate the entanglement width, you have to calculate the optimal tree, and then when you have the optimal tree, you have to calculate the three-tester network, which is corresponding to this. So the results work there. And the question is then, can you do this efficiently or not? And we showed that for graph dates, you can affect. So this rank width measure can be shown to be efficiently calculated. This is not a result, this is some room show. And then the optimal fitness and network can be contributed to zero. So for some interesting dates, one can really go through all the steps and go from this date to the official answer. So I have now a preliminary conclusion. So what have we done? We introduced this measure at Langman-Witt. In fact, we have introduced it from the relation with the graph here, the notion of Rank-Witt. And then later we realized that this measure has, in fact, already implicitly been considered by all these people working in the simulation of quantum physics.

37:30 And we noticed that these things are exactly the same and have been introduced or have been considered in the penalty in completely different contexts. Moreover, we found that if this entanglement measure is bounded on some family of states, then it is non-universal and, moreover, one can practically simulate any measurement with quantum computation, which is performed on these states. And for the out-of-state, this is the central concept of this. So this is kind of an addendum where I will say something about measurement-based quantum computation on graph states and some connection to logic which we need. So to remind you, this whole work is about understanding which kind of resources are necessary to do interesting quantum computation. Then, as Dan explained in his talk, the graph is in fact the complete encoding of the state. So once you know the graph, you know the whole graph. And then the question would be, instead of what states are necessary, what do these graphs have to look like? These graphs are treated as purely classical alternatives. So we already know if you look at this language measure of graphs, then it has to be in numbers. So this is some kind of requirement perspective and time limits. But now we will see that, in fact, this criterion implies another criterion, which is completely different in its labor, and which has to do with the notion of decidability, which we find in a very scary slide. So, this slide is here to more convince people who are not familiar with logical graphs.

40:00 To convince you that there is a whole community interested in expressing and investigating graph properties in a very formal language and looking at formulas which are looking like these ones. So this expression in fact says that a graph is two-coloured. Two subsets of vertices such that no two vertices in the same subset have edges. So just to give you a flavor of what kind of things can be in such formulas, for instance, this thing, HZt', denotes that there is an edge between the vertex Z and the vertex Z'. So this relation is equal to 1 when there is an edge, and it's equal to 0 when there is no edge. So you can express the J2D operations. Second, you have these z and z behind, which are variables. These are called first order variables and they denote positions. You also have large x, large y. These are set variables and they denote subsets. You also have quantifiers here for these set variables and for these first order variables. In this way, one can write many graphical properties in such formulas and one ends up with a logic defined on graphs with which you can express product properties. And if you use these kinds of elements in your formulas... Then you end up with something which is called counting module 2 monadic second-order logic, or C2MSL. And this monadic second-order logic is something which appears to be quite standard, although it has an adult name.

42:30 So never mind the actual form of the formulas. So one important issue here is the issue of decidability of logic, which is defined as follows. So, suppose you have some class, some family of state, sorry, some family of class, infinite domain, then you say that this family G has a decidable P2MF degree in the following issue. If for every formula compiled expressible in this logic, so for any formula of this kind, It is possible to decide whether there is a graph in this family, or which is the lowest. And this, what is here, is true for every formula 5, then you say that this family has the decidable. And if it's not true, so if there exists certain formulas for which you cannot decide this property here, then you say that the family G has an undecidable. So decidability or untidability of a family of graphs is some kind of notion of complexity of the family. But not complexity in the usual sense, but complexity in terms of the logic which is defined on this. Last slide. So the graph theory result which we are interested in here is If a family G has a decidable Ciklomath theory, then the family must have a bounded rank, which can also be proved by Ohm and Kohl. This may not mean much as it is, but if we interpret this by going from rank-width to entanglement-width across it, then we can immediately interpret this as follows. Whenever a family G has a decidable Ciklomath theory, or whenever the terminology is decidable, Then, the corresponding set of graph states cannot be used. In a sense, it cannot be universal, because it has a bounding triangle, and any measurement-based quantum computation can be simulated efficiently in practice, because it has a bounding triangle. So this seems to be, for us, an intriguing connection between measurement-based quantum computation of graph states, which are a physical quantum kind of thing,

45:00 I'd like to be sure that you're defining How do you connect to the notion that Richard was defining this morning in a sense of the line which goes over the partition? Isn't he also looking at the Schmitt line and trying to see how many times you cross it over this partition? We are not completely sure about it yet, but there seems to be... If you have a space, you can compute this measure, and if you have a space, you can also compute a different measure, namely something like, you look at all the circuits making this measure, and you look at, for instance, the minimal tree width of these circuits, or the minimal d of such circuits, and then there seems to be, well, we think there is an insurance, in the sense that if this field has only, then also this d should still exist. Yeah, I don't know, I mean, I heard a similar talk some months ago now. I think that's before this work came out. So I think this might be a generalised version, might be, might be a special case. This is a possible remark in answer to this question of Elham's about partitioning your entanglement resource with not very many lines crossing it. So it is known that if you have graphs of bounded tree width, then you can decompose it into pieces with only about log n connections across the pieces.

47:30 Any tree decomposed? You can break it up into pieces of smaller size with few connections, basically. In fact, we did results like this in the old days when I was doing parallel computing. We wanted to distribute a data structure across many machines with few connections across partitions. It's also true that bounded tree-width graphs are generated by graph grammars. Okay, so let's start the final session for today. And our first speaker is Ellen Sheffy from Oxford, and she's going to be talking about information flow in applications. Okay, so yes, I have a few questions. Thanks for inviting me to be here. So if you think that like Peter who was at the end of the QPL, I'm also happy to be at the end of the conference today. So hopefully you all heard about most of the introduction and all the definitions and all the stuff, so I think we'll stick to that. So maybe the motivation for this work is that measurement method is a new way of quantum computing. That's, we've kind of seen already, but you're differently thinking about computation. So our approach is based on some direct analysis, as I always say, it's like... Going over the circuit picture, which is behind me, I'm trying to focus on the measurement-based background directly, and the qualities directly, with the two ideas in mind that I'm actually reaching to this classification, that hopefully, to get a new method for algorithmic design, I'll talk about it a little bit, and mainly on the recent work on parallelizing quantum circuits, which we gained terms already in Richard's talk. So these are the main motivations behind the work. What I'm intending to cover is to talk about these tools that we define, we call this Information Flow for Graphics Day, which is a joint work with Ransom Mellos.

50:00 After covering that, I want to show you the application of that tool which we constructed for the one-way model particularly. The application is to a heuristic method for direct composition of literature to the one-way model. So the idea of like new way of looking at quantum algorithms. And the other thing is more on the, and this is the joint work with Neil from IPC Waterloo, Sam Danos. And the last part is the work and the depth complexity. And some new parallel circuits, which is a joint work with Anne Budman from Montreal University. And they are, apart from the last one, which is still needed to be submitted somehow, they are all on the archive. So, as I said, you already heard an introduction, so I'm going to go very quickly on that, just to cover the notation that I'm going to give you, which is mainly on the dimensions, more of this algebraic representation of the whole story. What we have been seeing so far about how do we define measurement-based models, or let's say that I need to talk on concept with the one-way model, with the all-model, this one-way model, solicitation model, all of them can be nicely mapped to each other, so everything that stays here can be also extended to the other faces. So we have these four commands and for the new qubits that you initialize in a particular state. Then you have entanglement, which is creating this whole huge quantum channel across the state of the light. Then you have the measurement, which is propagate and manipulate, and that's interesting. The main gate is the measurement. And you have correction to, as the name suggests, to collect at the end the drift, which is created by the measurement. The way I like to think about measurement model is the quantum pragmatism, so as you can see here, we have a graph state, some part of it is the input, the particle state, some part of it is the output, then we have the single cubic measurement, this is my notation that I want to obligate in the community, that hasn't been... I don't know if you can make it now completely, but basically you are doing a single cubic measurement, and then you do the correction.

52:30 So this is more or less the way I want you to think about the measurement model. And that's what I mean by direct analysis, that you start from the geometry and you plan by manipulating the geometry to reach the moon. Well, if you want to be a boring person thinking you can do it, basically, you have one of these inputs, these are inputs, these are algebraic qubits, which I've prepared in six slides, and you have these ones, which this part is creating your graph state, then you have your single qubit measurement, this one is yellow, and then, based on the result of that one, you have this adaptive structure, which is a classical communication. Or if you like, in terminology of classical control over your quantum operator. And finally, the object of the lecture. Okay. So, then we have this formal language. I'm just boring you because this is what I will use to define this information flow and it just becomes... It is convenient to play with these algebraic representations. So Ni is for to bring a particular cubism plus measurement, which is a normal xy measurement to a sort of another state. The classical outcome is 0 or 1, which is the signal Si. Eij is the entanglement control depth. And local corrections. We know that this is not enough for universality. We need to have the forward structure of classical control, that means measurement correction should be dependent on some previous measurement result. And that's an important part to divide it precisely so that it works. So you take a bunch of signals into some previous measurement result that you have computed, and you sum them into two. Then you have your correction dependency. The signal after evaluation becomes zero means you don't do any correction. If it's one, you just apply your local value. And then there are two other types of measurement, dependencies. Again, exactly the same as I was explaining it. So you have either x-action, or I would refer to it as x-dependency, which means you're flipping the sign of the measurement angle. Or you have the z-dependency, which is the other one, and it's just adding a pi to that one. So that's the dependency, and more or less, this is the language that we will use to... The main question that we are considering, and it leads to this notion of information choice, is our images.

55:00 So, in the usual circuit model, when you do unitary operators, everything is remained deterministic when you exclude computations again, but each time that you do measurement in the measurement pattern, you're creating two branches, okay? Okay, so that's a simple picture. If I'm measuring a qubit, I have two branches, which is one is a block, the other one is a minus one. Then here, you're creating. So if I have n measurements, I would have two string branches. Okay? So, but somehow I want the denominator of a vector to be deterministic. So let's define the qubit size and see how we can do this directly. So each branch in this measurement computation is just a linear map. So if you read it the way that you were doing it, so you do some unitary, which is more or less the preparation part and the entangling, then you have projection, okay, projection along that particular branch, and then you have correction. So these are the branch maps. And in general, you can say that what your pattern is computing is a completely positive trace preserving map. So, if I don't make any assumptions, just basically make a random measurement or random correction, the most general way to define it, naturally, is a city map. That's a city map which is realized by a pattern. So, let's define determinism in terms of this city map. So, we say that the pattern is deterministic if it realizes a city map which sends pure state to pure state. So, which means what? It means that the branch marks are proportional, or another term is that they are of some other. Okay, so this is the first approach. Then we define strongly deterministic, as you can imagine, stronger. And this is just saying that the benchmarks are equal. So the benchmarks, no matter in which branches the computation will go, then you get exactly the same thing. And then not surprisingly, to ensure that the pattern is strongly deterministic, then you should realize the unitary embedding.

57:30 In the case that the size of your output is exactly equal to the size of your output, you're implementing a unitary vector. But the case that you have more output, you're implementing a unitary embedding. So in the quantum algorithm, in all the things that we are doing, we are always dealing with strongly determinism, but it's good to remember that deterministic is also there. So, what is the next definition? It is even stronger, and that's because it's uniformly deterministic. It means that the angle of measurement is not important. So somehow there is an instructive character of determinism in the pattern, that no matter which angle you pick, you still get the stronger determinism. Okay, so just a quick example to make sure that you got the whole thing. So it's not the case that whenever I write a deterministic pattern, as I already said, it will be uniformly or strongly. Okay, so this is a very simple example. So this is notation. So you prepare a qubit, and I say plus, and you entangle it with your input qubit, so it's just like two qubit A. If you do the computation, you see that you have two branch maps. These are the linear maps along the two branches that you have, or they are theoretical, as you can see, and so hence this pattern is only deterministic, because they are proportional, and this is not just the speaking map which implements the projection. But it's not uniformly deterministic, because the only angle that will let you draw deterministic is the angle zero, and of course, it's not also a unitary embedding, it's just projection. But for the rest of the stuff, I'm just considering about the case that you have the same cycle and you have unitary conversation. Coming back to the fact that, like, okay, so somebody gives me this graph today, okay, and then we want to find the proper strategy of our Pac-Man. I mean that the angle of the mouth of the fragment and where do I need to put the correction such that at the end I'm trying to have a strong lead determinism. Okay, so that's the goal. Of course I can always start from circuit and translate one by one and hence I'm getting determinism, but we want to do it directly.

1:00:00 So, remember, the main part that we had before, or this classical control, is to control our deterministic structure, but you need to find the right strategy to do that. Okay, that term is defined by this notion of information flow. Information flow is defined differently, like a very simple function, and as you can imagine, first there was a proof and then there was a definition. So a flow for a geometry is a function from complement of O to I complement, from the measured qubit to non-input qubit. So basically you want to see that each time that you're measuring, If you want to think of it, how the information will flow to the rest and you reach it to the output. I'll give an example and it becomes more clear, but let's talk for a little bit about the definition. So apart from these functions, you need to have the main part of the partial order. This partial order is kind of the Time that defines the causality or whatever time structure in this pattern, because you have a time in your, a notion of causality in your pattern that which measurement defines which other measurement should come next. So you have this question. What do you need to satisfy this condition? V is the set of the vectors. Yes. Thank you. So the first condition is that the two, the place that I'm putting my F, or the information of where I'm sending, should be connected to me. There should be an H between them. The other thing is the future notion, so F of X should be the future of X, okay? That's how I can send the information. And the slightly weird one is that anything which is connected...