An invitation to tensor networks - Michael Walter

so much yes what's the way this this talk came about is that that I was attending this workshop last week in a--when physics and Confirmation and field theory and con gravity and so are we going to what my other life and he recruited meet it to talk about tensile networks so happy I'm happy to oblige so so I I guess I just want to do so I since this is sort of the computer science discrete mathematics seminars I understand I want to sort of try to explain things from this perspective so for those of you sort of for the physics or mathematical physics background it may be a bit boring or if not worrying with strange but but you know i hope you'll you'll bear with me and anyways please feel free to interrupt and we can make this more of a discussion than sort of a lecture so so I want to talk about this thing called tensile networks and so the goal of tensile networks is to define succinctly scription of high dimension tensors tensions in high dimensional space of tensors that are sort of well sort of rich enough to capture tensile of interest and and hopefully also amenable to sort of efficient computation in the sense of making extract we cannot only efficiently store these object but also extract expectation values and other quantities of interest so that's sort of the the goal and so that's we try to write this down descriptions tensors and a tensor from you will be all churned the an array of number or something in this space so I'll always use D for the local dimensions and n for the total number systems and so the reason that the prime reason historically why we care about transfer networks is that well the kind of or why we care about describing tensors that tensors arise naturally as describing states of quantum systems of quantum system with many particles and the trippity correspond to number of particles and so these you know in sort of a material of sort of a not too small size and it's really large and so we can't hope to represent this tensor by just listing its coefficients and so we are trying to look further other representations so that that was sort of the the goal so we would like to use to represent or describe for example a quantum states of many body systems among other things but you could also say okay maybe just want to represent a function you know that has sort of n inputs you know the I fin put ranging between 1 and di and it assigns a number to it's lots of function on a you know with many with many possible inputs and we want to characterize this in some way and so there are some multiple ways by which code one could go about characterizing such an object so maybe I'll put this here so these are sort of attempts that will not pursue so one way would be to just have a classical circuit and I soft tell you the index I 1 I 2 up to I N and the output will be the amplitude the component of the tensor ok so that would be one way of going about it so here some attempts so sorry so income some indices I want Y n so these are just discrete between the I 1 is between 1 and D 1 up to I n between 1 and T n so these are inputs to some black box maybe this could be a circuit or some programs an algorithm and the output will be some component this density so this is a perfectly fine way by which one could represent the tensor so all the so so this is why I write I said was discrete that's why I would basis a a scalar say a complex number but but it's not a very useful representation for all kinds of question that we may for some of the questions that we may care about for example suppose we want to compute something like the norm square of the tensor then it seems we have to we have to probe this black box about all possible inputs so for this kind of question it's not clear but that this is a good representation ok so another thing that we may want to do so may be also part of estimating or computing this seems to be a tricky another thing that we could do is we could try to may maybe produce a box that samples so it's imagine we have a tensor say the l2 norm is normalized to 1 then the component squared former probability distribution and we could ask for box that sort of samples from such strings I 1 to I n according to this amplitude square to these probabilities ok so that is that is something that one can do so maybe it's a classical maybe probabilistic circuit for sampling as well so like okay so um here I'm thinking we just have a box and it outputs a 1 2 iron with an according to the probability distribution which is given by you know ti1 I am squared over say the l2 norm okay so that if I write Norman will always be the l2 norm so that's something something one could do and for example one could survey it's a fashionable to use for example a neural network some generate if you are networked to this ultimate machinist on the actors and so that's one way by which one could represent amplitudes of a quantum state which people have done those that will not be the approach that you pursue but it's interesting problems so what we want to do is we want to consider our circuits where the or formulas where the wires correspond to extra vector spaces rather than to single scalars they're having multiple wires in parallel means the tensor product of vector spaces ok so I want to define what I mean sort of first pictorially and then maybe we can give a precise rigorous definition if if you like so today we're so these are not things that we are going to pursue but instead we wanna pursue tensor networks and the idea behind a tensor network is basically that we start with lower dimensional tensors in particular tensors that have few indices and then we are trying to build a big tensor by taking many of these small amounts of contracting so that will be sort of the the approach and depending of course what structure what sort of graph what network you choose you get a different family and so you get different families of quantum space of quantum states or tensors that from some some low dimensional subspace of this big tensor product and hopefully their form they characterize an interesting subspace or interesting sub sub sub sets up sub manifold of this of this vector space okay so here so the pictorially this goes as follows so suppose we're using they don't use pictures that look like this we never have such a bubble or a box this will correspond to a tensor that transfers as many tons of factors or indices as they are selects coming out of the bubble so for example this thing but correspond to a tensor with components TABC in you know and then there's some dimensions da DB DC maybe I'll label those for clarity this is the a the CP in this just acidic so that that's gonna be the the notation so far so good okay so so the only additional rule that we need is when we have two of these things and we hook them up and that's going to mean contraction oh yeah my talk will be totally on the level of pictures and there will be some theorems interspersed but will be mainly pictures so here is another picture so suppose we take one of these tensors and another one so maybe this is a p/e CDE may be prime know suppose we hook those up this will correspond by definition of this calculus of this graphical calculus to a contraction and so this will correspond to a tensor maybe we'll suppose if this is tensed tensor called T that's another tensor called s then this whole thing will correspond to now a tensor with one two or three four indices maybe I'll call this U and the police say ABCD and the components will be just governor will be given by the contraction that is the sum over you know all possible values for e ta be e s e C D or maybe CDE would be more natural right we always know which elect corresponds to which index because we have these nice labels okay so that's going to be in a tensor right and CDA up to see DDM so now we can build up you know tenses of normal indices in this fashion and as well as long as you know each of these we as long as we don't have too many of these tensors say if you're only a polynomial domain and in some scaling parameter and each of these things don't have too many lacks this will be an efficient way an efficient description of some tensor in this high dimensional space okay it's also going to be useful may be that we give meaning to just a single line so if you just have a single line this will correspond to I guess a tensor with two indices which is just the identity map in a way so this we can we can think of they yeah I guess the identity map or the unit tensor or say that tensor with indices Delta and so okay so I draw these pictures but but of course one can make them rigorous so one can use for example informative tensor categories to assign sort of an ambiguous meanings to these pictures I'll be a bit sloppy but please do interrupt me if something is just doesn't seem kosher okay so the point is that we have these these pictures so this is a simple example of a tensor network and any such picture defines a tensor sometimes these tenses also called tensile Network states because we think of quantum states so chance to network I'll abbreviate by TN and the saw was a freeway by DNS so that's the that's the that's the the approach so maybe we can practice with represent take some small tensors that we like let's look at some examples so for example suppose that we start with a tensor I'll omit the the names if they're not important but it's just a young attention so e i8 n zi8 and Zoe I icon from 1 to D so that's a 3 tensor people call it a unit tensor then you could ask okay what is does this thing correspond to ok so that is of course a una tensor that has now 1 2 up to N in disease okay because because by the way this contraction works we're going to match the AI from here with ie be high from there so this object is going to represent a tensor n so we can build you know large unit sensor from small ones so that that's one particular example maybe we will look at in another simple example so maybe I mean this is sort of a so far pretty homogeneous state maybe we can look at them another one where some or something that's known as the W tensor and in the literature so so here we take us out of our little tensor the following object so this is ABC so I want to say I want to define the ABC component of this tensor to be either 1 or 0 and I want to define it to be 1 if ABC is either say say these these dimensions are true that and these two-dimensional each so that's going to be a tensor in c2 1032 1032 and I want to I want to send set this thing to one for the following combinations either 5d of all of the indices are one if we have something like two one two actually maybe let me do it differently I made two zero zero zero one zero one and then I want to do 0 1 1 ok so there's three non non non zero entries in this tensor and then if I didn't make a mistake yesterday night I can look at a larger a tensor Network where I use this as a building block so I'll take many of these and then at the end I'll insert certain vectors so I'll start with the zero basis vector here which is a tensor with a single index and I'll end with the e 1 tensor over here so now if I if I look at what's going on right sort of so each of these indices this will be now B as some of you know certain basis states product basis states but sort of in in those two cases this and X will be 0 and we'll sort of you know we'll just copy so if this guy 0 will copy 0 over here so that will be this case and I will omit 0 here we can also use use use this mate at this tensor entry right route which will emit a 1 here and at this point this and X will be 1 but then somehow we are only we are left with Windows operating we have to we have to route 1 through and we'll get us all the way so this this is a tensor that looks at in the end as follows it's basically e 1 0 0 plus e 0 1 0 so it's a superposition of all these product basis States so I'm omitting the tensor products we have one index is 1 and all the other ones to 0 K this is something that but sometimes pops up sometimes it's called the W State okay so this was um some play examples maybe we can look at a more interesting one good so here's another one so suppose we have the following network let's say tensor a a tensor tensor a it cancer fee and a tensor C so a B and C up to tens of each so we can think of them as matrices if we like so then what is this object that's that's exactly matrix multiplication tensor if you think of a B and C as variables right because that because I mean so this is this thing is supposed to be number there's no dangling legs and you're contracting right say if there's a IJ a then maybe you call this Raj in K and this is exactly well actually doesn't maybe I won't write it down that's exactly trace ABC if you think of you know a B and C you already the emissive a B and C in the right way okay so that's interesting so so in particular we can sort of think of a B and C as variables so we can remove them from the network and so we basically just have a picture with three edges like this and we think of this these are standing edges d sustaining address and these are strangling edges so that's now that's now a tensor that lives in c d square tensor c d square to the c d squared and that is in that is the matrix multiplication tensor right this was a particular trace if i fill in the values if I don't fill them in then I get the matrix multiplication cancer and so one can okay so so explicitly right yep okay depending on what these dimensions are you know the rectangular matrices that we are multiplying so that's that we can also do yeah maybe I'll call this mmm matrix multiplication tensor for certain dimensions D 1 2 2 3 3 this is 1 this is 3 now we could also apply some linear map here also from d square to d squared may be alpha beta and gamma all right this will correspond to applying some triple of matrices in the right way to this matrix notification tensor so in particular if a beta and gamma are inverted we could think of there's something in the orbit of this of this matrix of abdication tensor that's like it's an object of interest to some to some people here okay and we can use this graphical calculus of era Phi certain rules for example it's clear that if I look at something like a four cycle that's where correspond to an iterated multiplication made from application tensor and I guess it is it is true that if you take a matrix multiplication tensor three matrices and another one and we glue them together right if we get those objects or this so you can play these these rules on the other level of pictures but of course it's clear what's going on maybe one last sort of thing in the this bestiary of ten says if you have a tensor and interested in its norm then of course you can just take two copies like so and maybe you take the complex conjugate here you just took us up doesn't say picture corresponding to the norm squared of the tensor right okay good so in general somehow so what's the point and in general that's just briefly collect what kind of data we need to define one of these sensor network States so we'll have some graph and sort of okay these pictures they had dangling edges the way I want to model is that I will have vertices and that correspond to you know the extroverts in the graph and then I will have sort of fake vertices for these terminals so my vertex I'll decompose into a set V and they said I'll call Delta like boundary then there will be set of edges and this will be just some graph so that's part of the input the next thing I need to specify is I need to specify the dimensionality of all of these addresses in my graph of each edge I want to have an an integer so these the integers I associate two edges now I could ask okay suppose I know you know this is two-dimensional this is five dimensions seven dementia I don't know okay what's the what's the dimension of what is the vector space in which these the tensor at this vertex a student I just of course have to multiply them or more generally I can define what is the vector space H X corresponding to your vertex that's going to be just a tensor product of all these edge hilbert spaces where edges everywhere in the edge this edge is incident to X okay so I hope this uh this uh notation makes sense so so let's tell the line I mean he's an edge that is incident to Wert exact sorry yeah that sort of yet that's right that's my that's my definition sort of that I'm using for the third part of the input thanks so input is this G this set of integers and then indeed it will be one tensor for each of these living in this HX for each X in this in this in in a vertex set yeah let's try it so will be a collection of tensors TX and HX all of these guys okay so that's sort of the input done looking inside the box and so this now defines a tensor in well the tensor product of all these filbert spaces for X and O's boundaries and set of boundary add vertices or terminals or dangling edges okay so that's that's that awesome and then we'll one last bit of abstract nonsense we'll use this notation TNS as in tensile Network States for a given graph and collective one dimensions this will be a family of of tensors the family of tensors that can be obtained by burying all these T X's but that's going to be my notation okay good and so that so that's the setup and so the rest any question you mean I could have also parallel lines yeah like you mean how I lay out this thing and spare no that's true but I mean it is important that there's a an edge between any pair of these spaces right like for example if this edge was going here and something that's what this input would be a three tensor and you wouldn't contract things but-but-but-but sort of comparing this picture with say this one that sorts just convention you know in some sense oh oh yeah do you mean like like that's correct yeah yeah yeah so so when I had these like like little dots around meant to indicate what I think of a sort of the elementary building blocks that's right so - so yeah Tony right so in a sense it's just like a tensor part of three identities which is regrouped in the correct way such that you know we think of - each of them of the of the right pairs as matrices yep yes yes so yeah maybe in another way yeah saying is sort of ya know I is that doesn't make sense oh okay yeah yes oh yeah when we make this identification indeed like you have to know if you take these matrices these variables ABC where do i plug them in in which of the two legs that that's sort of something that possibly was hidden when I removed these these guys that's correct yes sir so in these pictures I'm being somewhat sloppy about it I guess that's right sort of that's right so here somehow it would CBA yeah so I mean to make this to make us more correct one one should somehow identify the space of matrices with you know C D tensor CD I should pick some order and then zero so maybe add subscripts in the right way so there's some some so in a sense it's it's I mean in this notation everything will be fine by it because because these all these these vertices they have distinct identities and when I when I would write down that this graph and label things correctly everything would be good but but that's something that's being suppressed sort of like by convention in this in this picture so so I guess here if I try to make things precise in this notation say say for this tensor in some sense there would be one two three four five six vertices in this in this in this Delta there would be these three edges and then the the way I define the connectivity of these vertices as well as the so so this then would define a tensor and in a six tensor power of CD but then the way I identify this was three but the triple of matrices is sort of whether where indeed which will determine whether I drew a trace ABC or Tracy CBA that's right yes yeah so I mean that so what I mean I think there's just several ways of going about it one would be to more to be more specific about you know how sort of the the row and the column index of a mapped to these two lines another maybe mathematically more conceptual thing would be to use dual spaces so if whenever you have an etch maybe you have an oriented edge and you think of this as an action identity map from the duals but I mean from one space to the other or ten so in V start and so V and then some other zone you want there's only one natural way of associating a matrix then the object in be tense of a star and so that this would be one way of removing ambiguity in this particular case where we have one one V and one V duel for each for each input here in general though you you probably have to label things in some way to make to make it this thing so I if I agree that that somehow there's there's some convention that needs to be done so so that doesn't equality it's not very correct yeah some example I don't think doesn't make this alright good so the rest of today I kind of want to first I want to say some things about what are sort of the general properties of these sensor network States so how in a sense particular ways in which they deviate from being generic and will focus in particular on ranks simple matrix ranks not answering an entropy so this look is sort of an indication of you know what are the limits so these two the expressiveness or the richness of these classes and what is the significance actually of the graph that we chose what of the underlying graph so right for example here right we had this line this is something that we will talk about again it's called a matrix product state or a finitely correlated state here we have this this the cycle right but you could also have some two-dimensional picture so what is the meaning of this graph how does it constrain how does it constrain your tensor so that's what we I want to talk about next and then I want to talk a bit about sort of their how do we actually compute with these tensor networks and what is the computation exit of certain operations so is it simple to for example compute the norm squared of a tensor network or is it not good you may already know the answer so then we can be quick and then finally I want to talk about so that's sort of the the complexity of evaluation then I want to talk about social learning a tensor network state or how do we actually find a tensor network to approximate some tens of interest and so the first thing we have to talk about is of course is what is this source what is the origin of the chances that we care about so we'll talk about briefly about local hamiltonians ground states and and then I can sort of present what has known in what is known as mostly results in one dimension for one dimension contemn systems and I hope to sketch sort of give a give a sketch of the state of the art there and say what yeah so that's that's a plan for the rest of today then let's see how this goes so but maybe I'll start with was talking about some some basic properties let's say something something simple first of course the number of parameters is just is very simple right sort of we have we have to essentially so what I wanna Majan I won't imagine I fix G and at these dimensions and then I get this this manifold of tensile Network States or say the set of tensile Network States so I've fixed G and this these dimensions sometimes they're called bond dimensions so if you hear me saying pond dimension I mean that I mentioned associate whose edges so that's of course we have to provide one tensor for each of these vertices D and then the dimensionality of this H X here let's place tensors by a vector space of course you know just this product so that's the formula we get so so so very very roughly speaking right we have something like the number of vertices then we have something like the maximum of all these these dimensions these bond dimensions times the maximal degree of this graph right that's sort of a course upper bound so clearly if the degree is bounded if this dimension is you know sort of for normally large or sort of small in the corresponding context if there's not too many vertices then this is a very low dimensional set and it can be represented efficiently it is also completely not generic in this you know big big exponentially in a large large vector space of all tensors okay so I'm gonna next I wanna just show you - interesting families and they are sort of important both because they are what what what physicists use all the time but they're also sort of illustrative and the word comes so the first one are these matrix product sites or finitely curly the state which go back to a fun enough DeGale and Verna MPs so there's a lot of a lot of sort of abbreviations with drawing in this business so please interrupt me if I'm using it without defining it so here the idea is G is just a linear chain or maybe a cycle for simplicity I'll just look at the linear chain so it's a one-dimensional chain of some length say n and it looks exactly like the picture that we drew beforehand and one can look at versions where all the tensors are the same and maybe you have cyclic boundary conditions so we had look at a cycle or ones where the tensors are different okay so these are so and customly a customarily one one has some some dimension D here which is fixed by physics for example ufs you know some spin 1/2 system then this T is 2 and this cap will be as something you get to choose you try you're trying to minimize it if it's not too large then there's an efficient representation if it's too large well you can represent any quantum state but it's not not so interesting so these guys would curse but this dangling edges correspond to these vertices in in Delta this corresponds to vertices in B and we get to choose all these tensors okay so here we get some some set MPs parameterize know by the number of sides on these two dimensions that's a subspace of CD these are all yeah that's right these are all little deep so just for simplicity I'll choose them all to be the same yeah but for now I'll allow these tensors did you Beast inked at each side okay and so here sort of that dimensionality is of course you know and DD cube and so so this is parameterize right by n3 tensors or if you like you could also say n little D tuples of capital D by capital D matrices okay [Music] d tuples and I'll maybe use some notation like so where X labels the site and I label small in the index in this d tuple of D by D matrices and the reason I want to write it like so is because now I can write a particular coefficient so I can ask if I suppose this to represent some tensor T some some big tensor T in C D tensor and I can ask what are the components of this tensor so those would be such a component now what is this thing given by well it's it's basically given by okay I guess I was being slightly sloppy here because because sort of on the 4x equals 1 and x equals n and that that's not ID by D matrix but a 1 by D and a D by 1 matrix so maybe I should say 2 will have to equal to X 10 minus 1 and then for you know for I guess we could say we have a we have to to maybe we can say a 1 I and a n hi our set of well 1 by D respectively D by 1 matrices or just vectors Kove actress so the movies also say these are vectors so then we can write this as a I 1 1 and now a product I 2 up to I n minus 1 by 2 iron well that's too bad - one my hand and sorry there's nothing because slightly nicer sorry about that so we have these matrices in the middle maybe I'll call I'll call this lead just because they're vectors so we have a vector at the beginning where a B 1 D 2 + actors of the beginning and another T 2 + actors at the end sorry and these are vectors ok so now we can try can so for each index here we get a vector here this is a V 1 V FB n here for each index I and now this the whole the whole this whole component of the tensor is skinned by starting with this right-hand side vector which is labeled by n applying a sequence multiplying with all these matrices corresponding to our choice of I n minus 1 n minus 2 and so on and then at the end we choose a vector corresponding to it to the index I 1 and we compute this inner product ok so in the end in the end sort of what's happening is you have a a product of matrices right and that's why they are called a matrix product side if you had something like these cyclic boundary conditions then would just be trace which is what I was going to write on before yeah that's right so so yeah I think my notations a bit is a bit confusing so X labels these notes from 1 to N and then for each X I have a little D tuple of capital D by capital D matrices so that's so that's really a three tensor that's correct and I single out the dimension that corresponds to these dangling edges so that when I fix them to some particular value I so if I look at the corresponding slice I get to C by D matrix now have this nice well nice representation as just in terms of a product of matrices the only reason I wrote in this asymmetric way was that I could sort of relate to this named matrix product state and its really because because essentially the components of the tensor can buy traces of products of matrices here I guess they are rectangular at the end just some special case if this D is 1 then this is nothing happens here right that's just a tensor product of rank one thing so these are tensor rank one objects or I guess some secret variety if if if only two of these sides then what we're really dealing with so I suppose we only have two of them like this D D D and we're looking at a little D by little D matrix whose rank is bounded by capital D ok so these are sort of keys classical objects you can think of this as a generalization right it's generalizing tensor products to some some slightly higher rank and it's but the rank is enforced locally it's not like a global bound on the tensor rank or something like this naively okay so that's not good so these are these matrix products say it's what's your time then another thing that someone is now naturally that's so this is something that people later see is useful for describing physical systems in one dimension on the line okay and there's a one dimensional graph so naturally there will be a two dimensional object it has another name which I will not I I think I think we do not need this anymore but maybe I can just erase this done so we so this is was my sort of the attempts that we will not pursue today let me erase this this will neat and so now I'll add these I'll look at the 2d version of this thing so this is often called P EPS which is projected and tangled pair States I think for okay so this is a reason that's a name that's not so important right now but it looks exactly the same but in two dimensions so we have pictures right basically that look like like this so you have these if like a square lattice for example of tensors and then there's like these legs sticking out to the bottom so this say again the ones that sort of stick out to the bottom are little D dimensional and the ones in the plane I'll say capital D dimensional so that's exactly the same does that picture make sense oh it's exactly the same thing as here except in two spatial dimensions and so such a thing describes an element now of C D say tensile and X x and y if you've NX lattice sides in the X direction and y del slice in the Y direction okay and again you know you clearly these are few parameters as long as this capital T is not large enough and it's something people like to use for two-dimensional systems now let's let's let's try to see sort of more specifically I mean let's not let's let's look at certain ways by which these these particular families and also general tensile Network States deviate from being generic and so yeah that's correct you know you're totally right yeah get ready right so you could ask how large does this capital D have to be so that actually you kept to all tensors and then you'll see okay this one for this one G squared is enough now this one has already to be larger because the rank of you cannot be T squared so maybe this is I don't know that's correct that's right and so you'll find that of course this capital T has to be exponentially large if you want to capture all tensors in this in this exponentially large space but there's typically so in the situation of interest that'll be is just some fixed thing like like two or three and this capital B we hope grows only polynomially but the number of sites and then we'd be happy and you'll see later that the theorems exist the teller that this works and in certain situations good so let's let's look at sort of let's look some more into into ranks okay so so one sort of measure diagnostic by which you can see how how these states differ from generic States is by looking at ranks of flattening so flattening of a tensor is basically you have a tense of many indices you group the indices into two parts a and B you think of the whole thing you know as a big matrix from the a indices to the B indices and you look at the rank of this matrix so that sort of the pedestrian definition of of the rank of a flattening so let's let's do this maybe well okay this will involve some walking let's look at ranks so ranks or flat links so suppose we have some tensor say in our trade tensor and CT tense and um we will write the side one to end at some you know we will choose some subset or will write this as a you mean a compliment now corresponding to this we can consider a what's called a flattening which would be I guess conceptually speaking a well nevermind so first it will be a linear map from 8 to be front from a to a compliment again everything is in coordinates and I'll not write on tools we can ask what's a rank of this linear map okay and that's that's something that of course in general we can only bound by the smaller of the two dimensions okay so the rank of the straightening ta said most D to the say minimum of the cardinality of a and a complement okay and clearly generic tensors will saturate this so now suppose we look at the same quantity but for one of these sensor network states maybe for one of these matrix products say it's over here and so suppose we have some some some subset of these legs right of these n legs maybe this one maybe this is a and we also put some actual rank of this flattening so while I walk over there who okay so say in such a matrix part state if a is such a contiguous interval well the tents are sort of gifts I mean the stencil network gives you basically factorization of the chance all right and the factorization spacing mediated by these two legs right because if you if you cut them off then you just connect the tensor so whenever you fix these values you're good there's two of them and so the rank of this thing will be mostly squared so rank because basically the network that the graph itself gives you eight certainty composition of your tensor adapt it took to this thing okay so that's that's good similarly how about these PPS rate is pep States I do not have to be just contiguous this right so suppose I have um I have two intervals maybe this is also part of it well maybe no this this is also part of a then in this case I could still say let's cut some of the edges adjacent to this block let's cut the ones adjacent to this book and so on so in general what you would look at this you would sort of look at the boundary of a so the edges that leave a each component of a and then sort of each boundary Lac gives you know one one thing in the exponent so you look at the size of the boundary it's you get e to the size of boundary it's that's a sort of a more transparent in the studio Manship icture so suppose here we look at a a subset of these T's in this ace let me make it slightly larger so that Network continues maybe I care about these okay or some are some larger region then okay naively I get a bound on the rank which is little D to the number of sites but if I run the same argument I can instead cut off the network like so so along again this sort of along these edges that that leaf region a and I'll get a bound on the rank which is good if the reach was really large because only scales like the boundary of this region okay so find rank ta that's equal to D and maybe oh how did I call us maybe I'll call this gamma a and gamma a is this particular cut that I chose here maybe this thing I call gamma because all of these quantum ends I capital D I get I get the bound I wrote okay and that the general picture I guess is now clear so whenever I have a a general tensile network state based on some graph and I look at the I want to bound the rank corresponding to some flattening then what I should look as best basically at a minimal cut between a and a compliment and but I want to weigh this cut the weight I want to give us the product of the bond dimensions that I'm off of the dimension of all the edges that I'm cutting so in general so our usual setup right we have we have some graph some tensile work state TNS some graph G and so on GS this work these two word a sets these dangling legs on Delta so we're gonna split up Delta into a in a compliment disjoint Union and then what we can do is we can bound the rank of TA by the minimum of our cuts and then whenever we have a cut we look at all the edges that we are cutting you're multiplying the bond dimensions and we want this guy to be a cut between a and a compliment okay good so so that's that's that okay good so similarly to before under mild assumptions this is going to be tight for generic tensors that is something that has been dubbed the quantum max-flow min-cut theorem by bike we Friedman and others who looked at this so and the mild assumptions are for example that all these dimensions are powers of some base say two tooth or something then you can apply basic classical maximum cut so this is tight for a generic say 10 so STX assumptions we like Friedman and France course a touch strong and mean so so yeah I guess if you want to know more about other kinds of ranks non bipartite ranks you should ask good who told me yesterday that you thought about this so it's nice so but now if you about bound ranks we can also look at sort of more quantitative measures so ranks are very core some all right they're not very stable if you put up your tent so it will go up and so on so typically you know just the fact that this rank is not very large it not concern us so much we could also look at something that's a bit more continuous like an entropy and so entropies are also of interest otherwise typically entropy is a reasonable entropies will be bounded by the lock of the rank so the same upper bound will apply I should actually say so this thing that's this bound is an instance of what is called an area law area as opposed to volume the lock rank this basically bounded by the area by the size of minima cut by the boundary area instead of the number of sites in a so we could also ask the same question for entropy for example we could use big in here maybe I should briefly define what kind of entropy s we're looking at so because we've tensors and quantum states you want to look at quantum entropy s let's look at the family of rényi entropy is quantum brainy entropies which are permit rice button parameter alpha so the general definition of a of a of the Alpha or any entropy of some quantum state is as follows so how do we specify quantum states in general they are specified by PSD matrices let's trace one we'll see in a moment how row such a row arises from a tensor and a choice of a that is for my flattening so if you have such intensity operators that like a non commutative Robel distribution where the angle is formal probabilities first then the rainy alpha entropy is hopefully defined as follows 1 over 1 minus alpha log trays row to the alpha okay so this is monotonically decreasing as we increase alpha 4 Alpha equals zero we basic at the lock rank right because sort of that sort of the meaning of Row 2 to 0 for alpha equals 1 we get what's called the phenomenon entropy which is the Shannon entropy of the eigen values for alpha equals infinity we get something like minus log of the largest eigen value so that's the smallest of all these entropies that that's correct yes sir so also infinities men I guess offer zeroes max or yeah depending on the definition that's right yeah and so some all that's idea so how do we excuse me Rose yeah sorry you had better I mean PSD matrix so this will be some PSD matrix with trace 1 then we can define this entropy s now the question is how do we get a PSD matrix from our setup yeah but that's correct yeah so let's say there in this range for 1 if you take the limit you'll also get a good definition you get this far 5 to 1 you get this call to form what's called a phenomenon true P which is minus Rho at raise role or grow so they happens to be a good I got a good extension to one and as well as to 0 infinity that's right so these are exactly the classic already entropy is generalizing the Shannon entropy for the eigen values of Rho and the eigen values form of probabilities abusing by this assumption Thanks so now okay I want to construct such rows to which we can sort that we can measure this entropy so let's do this so if if a tensor T saying that in the end the general scenario s above and we have such a such a subset a and let's suppose the stencil normalized for good measure so normal norm square of T is 1 then we can define an operator Rho a basically precisely by taking ta star ta right so ta is a linear map from a to a complement to multiply it like so I'll get an a map from from CD 10 to a to CD tense for a so it's and the more first most positive semi-definite because it looks like so and it has trays one because this intensity is normalized to non one so that's a particular object to which we can apply this definition this is called the reduced density matrix of a quantum state described as tensor two region a okay that's the lingo so in physics it describes the state of a subsystem sometimes we also call it the marginal the quanta marginal because it's like marginalizing a probability probabilities of fusion and also of trevally because because any of these alpha entropies is bounded by a 0 by the lock rank we get a similar bound so that's something that's more maybe more commonly known as so usually we state these area loss for entropies but it's just a trivial consequence of what you said above so by what we said here we can bound s alpha of rho a right by lock rank rho a i know i guess i just have to take the lock in the right way we do the same minimization but now we're summing e and gamma hey i'm gonna take a lot of the fun dimension and so that's maybe a slightly so same minimization of what cuts between a and a compliment that's very slightly more pleasant because if you imagine that these bond time it's all the same right you get something that's proportional to the number of elements and that you're cutting so that maybe it's so that's linear so in this in the size of this area volume of this area okay so now you could again ask is the saturated for generic tensors maybe that's a more quantitative statement no no that's right this was a weaker statement on this bound but of course if you sure that that's approximate cetera it's going to be stronger statement they're showing the same for the ranks and one way but you can do this you can sort of so this is going to be true if you choose your tensors at random for example how random and you look in the limit of large quantum engines but in order so that this geometric picture is the same you should scale all these one dimensions and appropriately so you so maybe you take them all right sort of basically the the lock you imagine that the bond dimension is something like I guess Sadie should be maybe something like D to some C I guess and then you let D become large that would be sort of a legitimate thing that would be a good limit to take because then you would sort of preserve the ratios of these of these longer rounds but you know I I think an expectation these things would be true but if you want sort of some fluctuations like if you want some hype with I probably statement and the time and Trust to be a bit larger this would be probably I think this may be true like if you just yeah I think that probably right here I mean the so we were interested somewhere in the strongest I mean if you choose them at random from particular ensemble because then like some of in some applications we we would need this for many A's at the same time and you want to choose you need balance and the concentrate thanks so let me very say the the the stronger statement so if if you choose them at random from size the harm ensemble then this is true up to some of one Corrections for in this limit of large bunch of bond dimensions for for random if you choose it randomly that's something we we did to it with was Patrick Hayden and friends in in some specific context which relates to last week's conference but it's maybe maybe not important here but it's it's basically a way of constructing it's like an interesting random ensemble it gives you some geometric meaning right because you still have this graph to play with so it's a way of constructing certain quantum error correcting codes that have some interesting locality properties because because you can play with us graph so that was sort of our motivation but this may be a bit of an aside so maybe okay just to summarize so we only looked at those we looked at sort of these two measures right the rank and the entropy one maybe being a bit more stable than the other and so if the key point is basically and okay though is that you know you pick your graph you get a set of ten so Network States and they satisfy such an area law so roughly speaking you can only hope to approximate a quantum state by such a tensile Network state if you choose the graph in such a way and the Bandhu did I mention in such a way that you know you have the capacity of reproducing this entropy that's a sort of a priori and maybe not an imprecise statement but that's not the intuition that people have right and but but there but there are some converses actually so in one dimensions we know that a converse in one dimension we know that sort of on the line if the area law is satisfied say for some Rainey entropy with alpha strictly smaller than one then there will be a you will be able to approximate your tensor by matrix product states of sort of only polynomially large quantum engine say so there are such converses so so maybe I can so roughly speaking need area law if want to approximate some given tensor T by some tensor network state and in 1d it sort of an if and all here so that's very weak but but so if I think that maybe I will I will come back to this yeah and more precision so that that's it that's right that's correct that's kind of what we what we discussed the other but that's right and I will not go into the proof of this but I will say in more precision what what is being proved there in the corresponding setup but sort of historically so I mean we'll talk about this locomote owning business later on and then people were trying to prove that the ground state of these models could be approximated by medics part state and the root but the first group I which the sort of worked out was by Hastings sort of celebrated proof of the area law and then it implies somewhat straightforwardly as was some few easily explained by think first rottens Iraq that you can actually approximate by matrix product says I think a similar yeah so that that's right and and but it's sort of using those monuments the structure you have a left and a right you can do some recursive inductive construction of your type of a matrix proud state but that sort of yeah maybe I'll come back to this in a second yes yes yes for this statement for the statement that satisfying the area law Allah that's correct that's correct it that's correct that that's what I'm in with one yeah you're right yeah I think so all right good good good good good so this is this oh yeah maybe I should say yeah we okay this is extremely rough and superficial so I mean people know more some structure properties I guess of tensile Network states and I guess there's a lot of intuition in the physics community about which networks may match which states so what we'll come back to this but but what is known as gapped lok Hamiltonians I believe to be well approximated by such networks who asked for four critical systems or systems at a phase transition you believe that these ponta might just have to become larger and or you should use different kinds of networks so for example you could so here it was sort of a maybe natural but but it was a coincidence that the dimensionality of the graph right the intuitive dimension of the graph was the same as the dimension of the the state's everyone approximate right here we had a two-dimensional lattice which our hilbert space was built and then we put a graph on top but no one tells us that we should that that's the only way of doing it we could have like a three dimensional structure describing a two dimensional object and and that's well of course I mean in general increase the expressiveness of those and that's for the if you use the same bond dimensions and so on so that's something when we do so for example there's something called a mirror which is again an acronym inspired by what's called the renormalization group so it's it's it's basically described systems where you have correlations all scales and so it makes sense even for a one dimension so seem to have sort of a decomposition of your state into a sort of you know correlations at a certain scale then it's sort of twice a scale or four times the scale so it's sort of a self-similar Network similar to say these convolutional layers and in neural networks for some of you work in this right so it's basically like a fine or coarse graining procedure so that that's something one can do and and and those of course they would satisfy different kind of area law it would not be this this one dimension air I know they just get a constant for each connected component but maybe some logarithmic growth of entropy which is known that that is to be satisfied by the system so maybe I'll say some some more word of this okay so now we have this zoology of tensor networks maybe we can talk a bit about sort of operations that we would like to perform on tensor networks what the audience like to take a break I mean it might be a good person a good time now so so basic plan for the rest is I want to talk a bit more about what are the operations that we want to do with these networks so mainly to contract them so we should talk about when is it easy - it's hard to contract a tensor network so we'll see in one dimension it's easy in general it's a sharpie hard for you know even for tensors that is the earth and once we'll talk about this and then we'll come back to these sort of physic inspired ground state problems and I'll briefly say what is known there so maybe maybe we'll reconvene in five minutes camping on the the door okay yeah maybe I'll just continue for a little longer so next part we want to talk a bit about about the complexity of doing certain tense operations so I guess I hope I only erase the right thing so these were two sort of instructional families of tensile networks this mixed fog states in these pepp states that was the general setup I guess here is this this area off on entropy set will reappear later so let's let's briefly return to the general situation maybe that's called computational complexity so here suppose now you know someone hands you a tensor network which you know is internally composed of contracting many small networks so it's it's somehow more efficient you represent or write to this all these like tensors here and some contractions and whatnot but in the end this is just some box right you all put them in a box an outcome a certain number of wires which are these indices I I 1 to I n corresponding to this silhouette space let's vector space and so now you can also hear what are the kind of operations that we care about that we want to do so I've also press write this internal structure this is just my cartoon in the inside this black box is a tensor network so so you know that you can represent the thing efficiently right you say it's not very large so so now it turns out that Mouse tensor network most things that we want to compute about these tensor network states are actually basic boiling down to computing norms norms or norm Squared's that is basic basically evaluating 1/10 so if you have a such a box attention network that does not have any dangling edges this correspond to a scalar as we discussed before like for this matrix multiplication triangle when you plug in specific matrix a B and C so here they are dangling at just but what sort of I claim that the most interesting examples boil down to situations we don't have them so maybe I'll write this down the most tensor networks sort of questions that we asked the most computations that we care about reduced to what is called contracting it tends to network that does not have these dang it legs contracting a cancer Network I don't know state is maybe a misnomer with Delta equals zero Delta equals empty set so so so this corresponds to a scaler just computing the scalar computing a scalar so that the prime example of course this is norm or norm squared which you may for example try to compute in order to determine whether this thing is zero at at all nonzero at all so pictorially okay what do we have to do well we take our tensor network and then so this is sort of a vector now we need the corresponding cofactor we can just obtain this by conjugating all these tensors which maybe I will suppress or maybe I maybe I'll write this tensor network state maybe this is the complex conjugate I just hooked them up right and that's an inner product between the vector and the corresponding cofactor and this is a tensor network without any dangling edges so that's exactly the situation so that's a particular contraction I'm just expressing so I'm only certificate trying to explain this production in a way that's right and then we will see how to solve how to solve such a problem or why it's hard you could also ask right I mean sort of the thing that we said before is maybe not so interesting general but we could also ask for four specific components of the sensor right for example say the t I 1 to I n component well clearly just is just obtained by taking this same tensor Network state from above and you know here we're sort of contracting with a you know the the first basis vector e AI 1 AI 2 right this I guess it's a sort of a trivial way of doing it but but it's so I'm just saying this can be done what's most of interest in physics is well Spacey does non-square because in general these things will not be normalized and then expectation values expectation values of so I'll say what this means must not be exact expectation value of of local observable which means operators that only act non-trivial on a few of these legs so maybe I'll first write this down pictorially so pictorially what I want to do is the following so I want to take my tensor network state it's a bit wider and then I want to maybe so if all these embassies here all these tons of factors now I want to apply a linear operator to one or a few in general a few of these these these legs maybe just one for simplicity may be an operator hey this is gonna be matrix so I get another leg back and I want to contract this again with a with a corresponding cool vector okay so I want to look at a picture like this this is Venus I'll often omit these complex conjugates but you'll you'll catch me if I do so what does computes mathematically is basically following so we take this tensor corresponding to the tensor network state be applying basically something that's intensive work of many identity operators identities and all of these other indices accepted sort of at one of the self the location X corresponding towards operate ax so something like many identities a more identities on the right on these other things so I draw a draw this on a one-dimensional line but of course it does make sense in general maybe I'll call this guy a X there's an operator so and suppose supposing that this is sort of the X of location this could be an integer or it could be a particular vertex and Delta okay in general so we're interest in these things more generally we're interested in such expressions where we insert not only one but what a few of these operators so foreign to boot be something that that's called a correlation function two-point function which is pictorially internetwork state let's network state and then maybe here we apply an a and then somewhere else we apply a B and that's a bit like sort of a you know something like when you compute the covariance a right you have this expectation value of x times y for two random variables that space is the quantum version of sort of a mixed well I guess it's not a moment but yeah but sort of the mixed the part wait don't in the covariance where you don't extract that means the product of the means right this is this is like roughly something like an expectation of a acting on side X P acting on side so that's so these are things that we like to compute but you see sort of even from pictures or these are all contractions of tensile networks without bound relax okay so how do we do with this done how do we how do we solve how if you can do this how do we do it so how would you compute that's correct that's that's correct so the that's right so say the the input is really so you could imagine maybe you know maybe there exists a universal contractor that gets this input maybe well either we fix some family of transcendental a be just entire description say this is a polynomial our description can i compute this contraction okay and so now I want to restrict my family indeed say two matrix products diets and then we will see that you can do it and then we'll talk about how and generally it's really hard to do and so so for me so in the case of matrix product so it's say the input would indeed just be that say the tensor T t1 to TN and so remember from here that those looks and things we could just write as follows at the input would be a classical description of a description of these these tensors and so well how do we compute this norm squared here I'll just draw exactly the picture that we drew here okay this will be the contraction of this network now what I should not do of course is I should not cut this like this computer problems in a speaker bed space and then you know take the computers inner product what I should do instead is sort of doing inner product in this in this direction so what I should what I should do is I should think about well this thing as a vector in a you know d square time and should have a vector space then they fix up the picture a little bit this thing I could then think as an operator different color this thing I could think of an operator and these are the inputs and those are the outputs I simply apply this operator n minus 2 times and then I get a vector and C D tensor C D and I take the inner product with us thing that's boundary vector on the left hand side so that's going to be the approach okay and it's exactly just iterators matrix multiplication by basically the tents are corresponding to this thing in sometimes it's called a transfer operator and the lingo so maybe I'll just say this pictorially so really what we're doing is we're sort of taking the inner product between this vector and C D tensor CD then we're taking the a power of this operator at the N minus second power I guess and we apply this to to this vector right yeah sorry yeah utterly right yeah so I guess I was too quick here yes yes yes oh I should I should say this to separately Thanks so all of these things I can think as operators so these are all you know so of c d squared to c d squared operators and i just multiply them so i guess i need T to the 2 times Omega to do so but but certainly can do some point on my time at and I get the answer so this we can do and and often there some interesting I mean so that's an interesting object on its own right first for several questions so I guess we can just say this is sort of something like order an T squared by G squared matrix multiplications so that's often quite doable in this particular case it will be fine indeed yeah you would you would sort of just calculate the product you have and the closing it up will correspond to the trace that that's right in two dimensions of course all these things are much less clear and things are hard as we will see momentarily but in one dimension good in both situations Thanks so it's okay so I guess it's clear that now we can solve that we can of course use the same strategy for say you know these these expectation values and so on we treat those things all the same and here we just have to insert this one operator but if you don't have too many of these operators floating around I mean well I guess even a fifth one everywhere that's even simpler you have enough time to do everything yep that's right so that's all simple so that's great yeah so now maybe I can briefly say say what we said before so this'll be somewhat heuristic and sloppy so suppose that this is yeah no I think you could still you could still built you could still feel this object I think as a building block as an operator and then you it yeah that's correct yeah I think you're right I mean I think that's fine yeah it would only be an issue if you really acted on a lot of sites but then I guess also input is pretty large depending how you specify let's briefly look at a situation but all these tenses are the same yeah well yeah we're all these tensors are the same sometimes that's called a translation invariant matrix part set in particular in this cyclic situation then you really have a shift symmetry are same so then then there's this interpretation of just taking a power of then I've sort of a unique such a single such operator right which is the same for all sides except the boundary sites or the sites where inserts an operator a OB so it's sort of interesting to look at this object I'll just insert these arrows to indicate directionality so what I'll have to do is I have to do things like this right so so some power of this the so-called transfer operator and so suppose the strands operator is diagonalizable and it even has say some spectral gap then it's sort of clear what happens if we take hi tensor powers right sort of this will sort of quickly we'll get something that that's roughly projection on the largest on the eigenvalue correspond to the larger on the eigenvector correspond to the large dying value or as well on this left right eigenvector pair but we would not know on the eigenvector in fact sorry and and and so what it means is that if we have if you have a correlation function which you I'll just draw again here which kind of looks like this so there's some a so then we have many of these things maybe maybe say the separation so this a site X then maybe you have a be on side Y and we continue over here say the separation here is K sites then we would be led to computing such an operator here in the middle but if this is so but if these this gap assumption satisfied you essentially decoupling the left and the right hand side of your chain right because sort of because because because sort of so maybe I hope you somewhat sloppy so if diagonalizable right we can sort of think about this as some you know I don't know whatever GDP inverse to the K right which is more GED to the K minus one so if we have something like a maybe I'll just say spectral gap and I make I normalize the largest dying body to path to be unit C or something like this then basically this is right something like GeV maybe maybe the first I noticed a large is one right then have something Kewanee one star G inverse and so this is really some of our vector times the cove Ector right so that's a pictorially this corresponds to something like you know some state here times some other state here so so what I'm saying is sort of the I mean you're sort of rank one and the f K becomes large the left of the right decouples so what follows is that this does this expectation of this correlation between a and B is roughly the product of the expectation value of a times expectation value of B in other words if you look at something like the covariance just will go to zero very quickly or the correlation will go to zero very quickly and we're gonna expand entry quickly basically if you have two spectra gap assumption so so this is maybe let me let me write down what I mean mathematically then we'll come back to the picture I guess there should be some approximate and this approximate will be true if we have a spectral gap in K is large enough so we'll find something like this but let's remember the notations before I wrote a X for the operator that acted non traveling on the on side number X and by a dentist's otherwise so that's such a correlation function I can write as ax times B Y that's the expectation value of x DX times B Y so this is the thing that's calculated by this picture and now I want to compare this with the expectation value of a alone times the expectation value of B alone and turf those interpretations expectation values maybe I want to normalize my Kuantan my tensor to be just to avoid trouble otherwise I could do quite appropriately so the statement will be that some of this difference will vanish exponentially something and there will be something of the form something like this I guess one - what was today our say spectral gap Delta - the ex - why I think so it's something I guess maybe there's some constant somewhere so maybe I'll be a bit careful and maybe I'll add some constants here but roughly speaking I mean I think these no maybe I'll not write this roughly speaking something like this should be true so there's sort of an exponential decay in this correlation functions as you use separate X&Y if if these conditions satisfied right if you have the spectra gap diagnosed and so on and and so that that's sort of I mean something yes something that is called involved form or another so maybe don't-don't-don't told my you know self accountable for factors that are missing here we call this exponential decay of correlations and so in a sense you know it's a consequence of this matrix product standards provided you have this gap and you could again ask for the converse suppose you you know that exponential decay of correlation holds can you then find a matrix product state approximation and if one in you know sorry in a one a system so yeah that's right yeah it's this crucial say in a 1d system which is sort of also where this notion of distance comes from suppose you have such a property can you then prove that there exists a nearby a go to matrix product state approximation and this was belief not to be true for for a while sort of because for example there's quantum states that are very entangled but they have small correlations but to know if you if you demand this property sort of in a somewhat stronger way sort of not only for these single points for say a fixed single point but sort of arbitrary ones and also for larger regions and so on so maybe I should not go into details you can actually prove that it's enough there's something it was thrown by brandão of an underground oh and Makaha or that's key so there's sort of a converse and in 1d I guess everything on this board was in 1d so exponential okay of correlations yeah I'll just say again in 1d it implies out of the existence of MPs approximation yes so suppose I have a one-dimensional graph maybe on a cycle and I have a particular quantum state and it's true that whenever I have you know and and I put two regions ok maybe I should have let me add more these things suppose I have one region a and another region B and I'll suppose that the the generalization of the expressions are sort of covariance for any operator support in here and operate a support in here it's exponentially small in this distance between these two regions so that's a bit more general I don't don't look only at single points then let's call this exponential decay of correlations and they exponent would be this design we look at the minimum distance if you have this for all pairs a and B of regions then it implies that that the existing matrix product state of of small say in second how large bond dimension that is a good approximation to the state you started with so you don't need a Hamiltonian for this but but you need a state that satisfies this kinematic property so if T is an arbitrary tensor that has this generalization of this property you find it tensor T prime that's an M matrix forex idea which is nearby yeah yeah that's right and so some other the way that these scales is it's somehow exponentially in this in this correlation length I think sort of that's that's what Brando and friends proof so I guess something like I mean this is I think this is true up to some log factors and stuff so I guess in this case it's something like one oh what the gap but I mean this is of course derived from the sensor network but but suppose you had something like this of this form so that's ok yeah so but yeah so the the correct technique way of interpreting is this is it's it's a it's a stronger statement on this one right you have it for all these regions what what what replaces the distance you look at the minimum distance but sort of you know sort of either this or this a on the circle and if you have this exponentially decay for some sign in all these regions you get a good matrix peroxide approximation but this the spawn dimension that you that is not the physical ones of the fundament the bond dimension here this was D is that large I think that's roughly that rundown I guess I didn't write on people's names which I should have so front our or a Tatsuki okay so that so far is so some reason I mentioned this is now we sort of have two of these converse statements one is an area law implies nearby a good matrix parse it approximations and exponentially decay of croatians applied one so historically this converse statement was I think discovered after Hastings had well both I think established exponentially decay of Croatians in certain gap one-dimensional systems based on sort of IDs mathematical physics the de provence and bounds and so on and but then some of this was not clear so here here first to prove this area law to get a good matrix part state approximate to prove that the existing got made that approximation and I think it was only later discovered that there was also this alternative fluid so that sort of to two criteria in a way for forgetting forget for proving the existence not for finding for proving the existence of a good metaphoric state approximation well that's what was to be shown I mean if you know it comes from a matrix part yeah yeah yeah yeah that's right okay yeah so now this looks great in one dimension so how about higher dimensions of course Derek generically things are hard and so basically contracting an arbitrary so I guess I they are quite a number of works that's of explore the the richness or the computational hardness of contracting cancer Network yeah you know maybe maybe believe this one actually perhaps people Oh my guess excellent got some space yep so in general yes so I think not not sort of to complete satisfaction so I don't I don't so I so the the ultimate sort of serum that I'll talk about in the end will be one that shows that we can actually find in polynomial time these matrix part state approximations for certain one-dimensional systems and I think such a theorem is not known for trees it's only known for line yeah I think not I'm not sure but I think also I think it's not I think like of course if you have a tree you can derive lots of structural properties that are very similar to what we discussed but I think these converse that ones I don't know they are known so here was the trans operator and what I write here but Bill when I say when I said gapped lok hamiltonian all the time i was referring to meltonian so that's very confusing sorry so here sort of for the purpose of this bound this was more to establish that's of generic him you would expect from matrix product states to have an exponential decay of correlations so again you could only hope you know if you have a physical system that's a very physical assumption or physical property so for physical system where this is not true maybe those are bad patterns arts so I mean there's some caveats because of course generically you don't have to have to expect to look up okay but but we will come back later and sort of discuss actual Hamiltonians which also have a spectacled gap and that's something more physical and this for this class Hamiltonians basically both exponential decay of correlations when one can establish as well as an area law and so we can use either of these two converses to to see that they must exist automated approximation that question would be how to find it we'll talk about this I think maybe I'll be very short on the sort of complexity side of thing here so in general sort of you could look at these two problems given you know its input a chance a network either restricted to a family such as peps or you know just an arbitrary graph on dimensions and these tensors TX it's this thing zero or not zero or not or or you could ask you know actually what's the norm squared let's compute the norm squared and maybe we could restrict to a sort of the case where these tensors are only Anderson's dollars you're on one right and this is an integer we can think of it as a you can try to put in some counting class for example or prove some hardness so suppose all these T X's our entries have entries in 0 & 1 but we don't know the earth metric more to with your northmet arithmetic but I'm just restricting to integers and this non squared will also be an integer and we could ask you know what's happening here and so here I guess this thing is say yeah maybe we'll assume both of these properties actually for now one can do very some things one can look at it more to when people have done this but that's not the scenario I know best so this will be np-hard and this will be sharpie heart and general and basically the I think that I mean simple proof for example you you want to suppose you want to reduce circuit satisfiable the counting number satisfying solutions to a set or to a circuit set you can basically easily construct it tensile Network corresponding to a boolean circuit and you can choose certain so this would be right like you have your circuit is in output so your tends to network as in and outputs but then you can sort of contract it with certain states such that you exactly count the number solution and so basically it's it's so simple I think so that we can we can try to do it so suppose we have some boolean circuit so say some gate okay so maybe it has two inputs and one output maybe this X 1 X 2 and Y so these are bits why do these wires from this we can construct it turns on a tensor with where all these dimensions are 2 so these 1 dimensions are all - right so again it has two inputs into outputs maybe I'll make make this sort of a fat line to distinguish it from the gate we started with and this tensor will just be you know sum over X 1 X 2 they both either 0 1 DX 1 tensor ex2 so these and basis vectors e f of X 1 X 2 right so that's a perfectly good tensor and now of course if I have a circuit I can directly and efficiently translate those into a tensor Network and so that lets do this so if I have one circuit that's what give me a tensor network or network state if you like and so now suppose we I want to know the number of satisfiable inputs for which I get 1 okay so then let's let's do this it's a number of satisfying inputs how do i compute this well i take this this big tensor network state right so this is going to be something it says you know if my formula is well my formulas one output but in general there's many inputs x1 x2 xn sorry my my circuit so here the inside is now the tensor network is corresponding to my circuit so how do I get a number out of this well what I could do is the following let's plug in certain vectors here I'll call these vectors + + is a the vector that's just 0 plus u1 that's a nice vector right no one base is summing about all these two to the N options and here for y I guess I'm just maybe projecting on the one by one basis vector and then this would if I didn't make a mistake just give me the number of satisfying I know input assignments or inputs to the circuit and so that that would be a one way of seeing where this repeat tricky I think even even if restrict to something like peps it will be a hard problem because you can for example you can encode classical partition functions basically an arbitrary classical partition function of some local classical Hamiltonian you can based encode in this fashion understand this by bike by constructing corresponding tensile Network so you can put any growth yeah that's right yeah so you know you could say these are like very very unphysical circuits right circuits ever done physical objects but even if you look at a regular grid and you take some hard partition function yes yes yes yes yeah that's right yes right so that so even sort of sort of EPs that sort of tricky on the other hand does pep formalism is something people do use in practice party successfully so I think there's still sort of work to be done to prove why why this is the case you know why things work well so the way they usually deal with them I think numerically is I mean there's various heuristic answers something else you can do is you can you can try to do the same transfer operator business we did here but now we do it for for like the one-dimensional lines that so if you know slice up here to them and regret so you're a trans operator actually so many indices so that seems of course problematic so you can only do something like a narrower strip that's very wide and so on but that's my I think things that people do I guess so that I don't know the so well but that's this Holland Holland framework and I guess these which is very similar to tensor networks in some sense and people study this dichotomy theorems sort of saying which I think in this language basically means can we prove interesting statements when we restrict our certain subclasses I think I think yeah yeah that's right yeah but I yeah that was my my impression I mean so I think people some some question that people ask there that maybe has only partially explored in this context is what if you say okay let's not allow arbitrary tensors but only certain ones so for example there are certain subclass of quantum states that we know how to reason about efficiently for example Gaussian States or what's called stabilizer States so that sort of a states that you know you can you can reason it's like it's another sort of subset of this big here bit space which is not so modifying this geometric fashion that still can be represented efficiently so I one could ask you know are the other classes natural restrictions on these tensors that won't get something something that's more tractable anyways there was something I wanted to I wanted to mention so I guess the summary is that if you have some family of tensor Network States you get some I don't know maybe you could call it a computational model I'm not sure and you could relate this to sort of the ordinary you know computation months you could ask how hard is it to do this contraction problems in general it's hard sometimes it's not so hard it certainly just depend on the graph that you start with on the allowed tensors maybe one brief comment that may be interesting you could also ask about the quantum complexity of these objects on the butt but also on like the tenses done locally okay okay all right yeah maybe let me make one brief comment about sort of quantum complexes so you could ask I mean yeah we're I mean we're trying to to reason about quantum states using classical complexity theory right ideas and class competition you could also ask can you so if if you hand me an classical description of such a peps or a tensor network state can I prepare a quantum state efficiently right so using a quantum computer so it's a lot something that's more natural question for fathers but you could ask this question and basically what it amounts to so suppose you had a maybe I'll just put this somewhere here because it's offered cite remark and we'll come back to the rest so suppose you had a header machine you give this machine a classical description of a say ed peps or some other tensor Network State classical description of Chancellor network state maybe even of a peps just restricted to the student family and out comes a quantum state that is the rest of this perhaps okay so this is the quantum state that is this tensor okay and so you have this you have this magic this magic Oracle is a magic black box that achieves this furnace so now you could look at a computational model right where you allowed to do some classical pre-computation that you know so you have some computation problem that you want to solve so you get some problem instance you get some input now you you you you maybe you do some some classical pre-computation you somehow convert this into a tensor Network description so you do some classical pre-computation maybe and I don't know if you peepee or something or maybe just in pee because you can do the randomness maybe likely here and now well here you get a quantum state so it's natural to do something like bqp is to do some you know polynomial time bound confrontation and now at the end you get yes or no you could ask how rich is this what's the power of this model and that turns out to be equivalent to what's called post bqp so that was I mean maybe that's only a short remark for the extra bit so so that's basically the power of a quantum computer way allow a post selection so what it means is you're allowed to do measurement right and then if you get measurement outcomes zero you're saying okay no that that's great but but if that's one you just try again and but it doesn't cost you time or in other words you can always assume that your measurement gave you a certain result and the intuitive reason is that I guess there's something I didn't say before sort of in quantum computing that that it's very similar like a quantum circuits very similar to tensor Network right it's also multi linear on all these gates but the gates are unitary matrices in these sensor networks we didn't demand that the tensors were unit area isometries or anything like those and so does non unitarity is is what you have to pay for by doing post selection you so you can emulate any linear algebraic operation or any linear map if by a quantum computer if you love to post select but in general of course the probabilities will be in or tiny that you get the right result but here you don't pay for it so I think this is I think the same as P P I think which is crazy yep and so that's I mean that's sort of in other words it's also crazy and we wouldn't buy that yeah but that's sort of the thing I think is by eschew from a silicon and friends okay I guess ten minutes so let me briefly actually talk about these more about these one-dimensional systems maybe that's a nice way of wrapping things up so I can erase two dimensions and I can hide the quantum part all right so here we want to find tensile Network descriptions in particular one matrix product state of approximations let me briefly sketch it's the general scenario and then restrict you one dimensions so that this is about algorithms for finding tensile Network State its descriptions I should say that I guess the whole talk was a bit more focused on approximating ground state so something that has both a numerical flavor and then there's these rigorous results or this rigorous algorithms to start to be somewhat competitive this whole formalism of tension oculars has also been quite a success and sort of related to kind of what one could call exactly solvable models so sort of toy models or certain physical features such as topological order so there's there a certain sort of it's like it's like model model systems that one wants to understand very well and for example there well I guess is something else about that was of interest versus a klt Hamiltonian but but then so from top of shoo order there's a story coat and the string net models and all of them have a very compact Cancer Network description so those one was one of the I mean maybe these address words but I'm what I want to say is that apart from doing numerix and proving that numerics can work there's also some theoretical insight that people have gained but this those maybe these four maybe more for physics flavors I didn't want to emphasize them too much but one can kind of like almost you sort of proof by pictures of some interesting physical properties in this way so that that is something that I'm sort of ignoring in this talk I'm also ignoring things like like symmetries how to incorporate symmetries instance I know even though I may have announced as in the abstract ok so how do these tensors arise in nature so suppose gamma is some graph some interaction graph of a physical system and fast it will always be some regular you know letters like a line or square or something but that's just for for two minutes say this is some graph and you just have in mind a wonderful line so that that's not yet a tensor network anything that's a graph on which we want to define that that's underlying our physical system now how's this physical system then described so this will correspond to a one dimensional system quantum system now a consistent would be described by a Hamiltonian and usually we assume that the same atonia is either local meaning it each okay what is the Hamiltonian Hamiltonian has a hermitian operator on some underlying Hilbert space may be associated with us okay I guess I'm jumping ahead so so here's a physical system I think of each vertices on this interaction graph as the physical sites at each site I have a Hilbert space you have some dimension C little D if I have n sides then my Hilbert space would be no cd tensor and in general it would be the number of vertices in this in this graph gamma so now what's the Hamiltonian Hamiltonian transformation operator in the space is somewhat describes physics on the system and a local Hamiltonian is a hermitian operator that I can write as a sum of terms each of which is again a hermitian operator but a hermitian operator only acts non-trivial on a few of the tensor factors and actually the the meaning of the graph of the edges in the graph is that I only want this the terms the Hamiltonian to act non trivial pawns of sites that are neighboring according to this graph okay I could also look at some you know stuff edges that include more this is hypeeee I had to say include more and two but that's sort of without loss of generality so a local Hamiltonian is a hermitian operator eight we are sort of summing over say all okay now I'm so abusing in this notation maybe let's say X Y our edges on this graph you know each Amma I know there's some term H little X Y and this is some permeation operator that acts as the identity on all tensor factors except for the X&Y tons of vectors okay so and that X a non trivial only on X and y tons of factors so in this it's it like in this in this correlation function right I had sort of two operator this was a tensor product acting on two sides to think of something like this so that's and we would usually normalize these terms right because I will talk about things like a gap so it's good to normalize so maybe I'll say all of these terms have operating on bound if I want or something this and there I guess I said this but yeah so they hermitian so this thing has eigenvalues on on a finite system and one thing of interest is the subspace corresponding to the smallest eigenvalue or let's just assume this is a that's only one and let's call this the ground state otherwise looking in space of ground states so goal is we want to understand we want to find you want to approximate what's called the ground state so T sorry I guess I didn't give the server space in name the specter spacer names icd-10 sir so this is the eigenvector an eigenvector with eigenvalue domain of H so that's that's what is by definition what is a ground state we want to approximate this aha by watch by for example a tensor network state and in particular by matrix product state if gamma is just this line okay so that's a bit like right you have some constraint satisfaction problem you want to find a solution but but of course in a class constraint satisfaction in the end you have some assignment of all these n variables here this is this a general this tensor is not a product of you know rank want answers but it's some entangled state and we have some physical intuition about when is the state very entangled and when should it be well approximable bye-bye for example matrix parts to it and so one measure that has turned out to be useful is again a gap a spectral gap now it's a gap of this operator H naught of thermtron so operator doesn't exist anymore doesn't exist at this point which is basically you know the difference between the lowest two values and so what what is sort of the idea is roughly speaking because you only have these local interactions most of the correlations are entanglement between sites I mean the integrant should be local so if I look at say in a two dimensional system if I look at some region a we would believe that most of the correlations come from nearby sides so the amiss so on the one hand side we would think of this meaning that the entropy should scale like the boundary of this area or not like the volume and also that correlations will decay because they are so mediated by these local interactions okay but of course those things that these are statements that have to be proved but but that sort of why one would believe that sort of having a gap look I'm atonium sort of on physical grounds implies say in area law and justice exponentially decay of correlations okay and so this in one dimension such things have been proved by these results by by the Hastings which I understand self-reliant that's sort of a large body of work and techniques from from mathematical physics sort of that vector that go go back for example these new Robinson bounds that are something like and it's something like a maximum speed of information transmission in these physical systems so that seems like something that's useful to consider here but that's kind of things that go in so in 1d by which I mean this graph is just a chain like so there's rigorous results so first questions right does the access to match for our state approximation second questions how to find it so for the first question we had two criteria one was in the area on the other was exponential decay of correlations and so both of them so this is safe things have been established one is sort of the exponential decay of correlations in the ground sites or yeah these are all properties of the ground state assuming this gap and say assuming for now yeah it will enter the bound in a in a bad way and in fact that's us right here so so the for this curve so this sigh here does correlation length will scale like the inverse cat I think roughly speaking so so what you can call the correlation length so I'm not sure this Oh it's roughly roughly speaking like this I think and then he also proved an area law because at the time this was not yet good enough to establish to take this matrix products eight approximations Harry our law kind of saying that you know if you look at this entropy of a subsystem then I think it should be something like this some exponential and then I guess here there's a D is this physical bond dimension just D and then again there's an inverse gap I think something like this is is probably right yes and so either of these two things right imply the existence of matrix power state approximations and I guess one one could say that things like this exponentially characterize I understand we're established in relativistic systems and mathematical physics like like like decades ago and I guess here that that sort of in a nonrelativistic system of the Hamiltonian and so on and yeah I guess similar it special cases such things and so on but that's a very nice general result basically relying only on these two assumptions and so when people say having a gap like usually what people have in mind is that you let the size of the system become large that's your parameter and s n becomes large this gap should not close I should stay constant or maybe go to zero very slowly say so that that's that's what what hasn't mind so now the question is how to find it so we have one minute to find the grants you have to find the ground state so I think that there's kind of two answers the one is sort of the non-rigorous answers so there's an algorithm called DM RG transformation normalization group that people like to run in a numerix community and I think what it does so roughly speaking as it's like an alternating minimization scheme a you fix all tensors in your matrix product set except to one and you're trying to minimize the energy like keeping all fixed except for one and that seems to work out your own practice but I no one has yet proof that this should be the case but there by now they are rigorous algorithms that are somewhat closing in flavor I would say and so the the best results I think are due to well Arad Londo was Iranian and Vedic and so maybe I'll just state what what they what they what they would prove so you'll say how to find so maybe I'll just say in practice justice grg algorithm which is this alternating minimization scheme but now we have these also these these rigorous results all right Londo which was Ronnie and Tomas Vedic saying roughly that you can find a one over poly n approximation so this is sort of the distance a and a trace distance or hilbert space vector distance mps approximation with aha in in time something like one over the spectral gaps into the spectra kept square so this is fully time of the gap doesn't close okay so I think that that's basically what they have okay so so that's I think roughly speaking the state of the art in this scenario now you could ask yeah are there any questions about what I'm saying here so I guess I didn't explain how this is goes about I think sort of their latest algorithms there some local procedure they have what they call kind of approximate ground state projection so they have they sort of prepared sort of for small sort of subsystems they prepare things that are close to the concept of that system then they have two of these and they try to merge them together and some hierarchical scheme doesn't yeah it looks looks not too dissimilar from these Mara Network sorties yeah that I mentioned before but anyways so you're trying to merge them together and then you value the dimension of your space multiplication that in is rich enough to capture the state and so in this merging process the damage multiplies they have to truncate it again and so they do some clever and careful analysis to to establish the serum which is kind of making making this existence statement effective in one dimension so one could ask what happens if this gap is some does not satisfy it say it goes to zero when the system size becomes large yes right that's correct yeah yeah yeah yes yes suppose suppose does suppose this gap is not constant though suppose it it it goes to zero then you sort of sorry so it supposes this assumption that you know this is sort of large and zero and states are zeros violated there could be a sort of roughly speaking there two reasons one could be that you know simply the ground state is degenerate there's more than one vector with this with this exact eigen value lambda min but there's still a gap to the next eigen value right so the spacing is kept but the there's just a degeneracy another thing could be that you have some window of energies lambda min and lambda min plus you know some little Delta and inside here you have a you have some you have more than one eigenvalue but only say polynomial number of them so a small number out of the whole bit space so so I guess we call this a density of states and this in this regime is not so large in this case roughly speaking this test result generalizes I I think I think yes and but but everything here is on this line rough like it's yeah it's almost 1:00 no mattress situation like as soon as you deviate and even if yet like like some branching thing at the end a priori there's no result yeah so it's all all on the line graph yeah no I'm trying to I think there's strengths remember if there's some translation variance that is being imposed I think I think I think not yeah but okay but don't don't yeah yes okay so but yeah so I think that's that's my skirt so sorry yeah the only calmed I want to me so I think that's the right normalization but but maybe we should check if you could consider the situation to where this gamma goes down faster and I guess in this normalization I think you know I think it's good to normalize like this right because you want you want this this energy to scale like the system like like the number of sites roughly speaking so I think it's good to normalize things like this so then you have this gap if it goes to zero there's there in if it if the gap closes well if sort of the number of states in some constant energy window that is it may be large and one but it's not to large as the number of sites in your chain increases then that's still okay if the ground state is degenerate that's also still okay I guess one you could think of a special case of the other so that that sort of also also done by those guys there's some results if in in more dramatic situations but but maybe that's more I mean that's more using terms of the physics community there's there's something known as conformal field theories which describe systems where the skepticism is not at all true there are some rigorous constructions of matrix product sites by by Cooney controls also constructing matrix products at approximations and we have done some work on on a different kind of network not this one-dimensional train matrix provides a network that we drew here but some our network the test is hierarchical selves in our structure proving that for certain simple systems we're also the gap zero one gate gets good approximations so these are sort of sort of works whether in some sense one studies explicitly given systems which one in some sense can solve by hand ish but it's it's still highly non-trivial to find this tensile network approximations so usually would so you could think of it a bit out like you know some of these systems you can solve by Fourier transform but a Fourier transform is very non-local in space so you're trying to solve some sense a simple problem by you know but but you want to bring it into a certain answer so there are some results only along these lines so the connections result I mentioned some some work I've been doing this for some collaborators including Brian who is spending some time here which I guess is the first rigorous result for this for for something that is not the matrix product say but this other kind of family of tensor networks yeah maybe it may be that's all I have to say thanks [Applause]

Channel: Institute for Advanced Study

Views: 3,207

Rating: 4.8888888 out of 5

Keywords:

Id: ivfuJ1JIET4

Length: 121min 35sec (7295 seconds)

Published: Tue Dec 11 2018