I am learning the very basics of tensor network theory and I am trying to understand why some ways to contract tensors are better than others in terms of computational complexity. Knowing in which order we should contract the tensor is known as "bubbling".
As a reference, I am following this paper, bubbling is described on page 7 (my background is quantum information, I need to understand how tensor networks are used to represent entangled quantum states).
I am following the examples on page 7 of this paper and for that I consider a ladder-shaped network. I put some notations first (don't pay attention to the dotted circle on this first image).
As a reminder, what this graph means is basically the number:
$$N=\sum_{ijklmno} A_{ni} B_{ijo} C_{jk} D_{kl} E_{lmo} F_{mn}$$
Where, $A$, $B$,... are tensors of rank given by the number of indices they have. The principle of "bubbling" is to try a way to compute it in the most "efficient" manner from a computational perspective. To do it, we can either contract the tensor network through the first manner (below):
Or the second one:
For the first approach, what we will have are the following steps in the computation:
$$\text{Step 0: }X^0_{njo}=\sum_{i} A_{ni} B_{ijo} $$ $$\text{Step 1: }X^1_{nok}=\sum_j X^0_{njo} C_{jk} $$ $$\text{Step 2: }X^2_{nol}=\sum_k X^1_{nok} D_{kl} $$ $$\text{Step 3: }X^3_{nm}=\sum_{lo} X^2_{nol} E_{lmo} $$ $$\text{Step 4: }X^4=N=\sum_{nm} X^3_{nm} F_{nm}$$
For the second approach, we will have the following:
$$\text{Step 0: }Y^0_{im}=\sum_{n} A_{ni} F_{mn} $$ $$\text{Step 1: }Y^1_{mjo}=\sum_{i} Y^0_{im} B_{ijo} $$ $$\text{Step 2: }Y^2_{jl}=\sum_{mo} Y^1_{mjo} E_{lmo} $$ $$\text{Step 3: }Y^3_{lk}=\sum_{j} Y^2_{jl} C_{jk} $$ $$\text{Step 4: }Y^4=N=\sum_{lk} Y^3_{lk} D_{lk}$$
My current understanding
Those explanations are what I understood from the paper linked.
It is not completely apparent because we fixed $w=3$ in this example, but in the first approach, for a ladder of width $w$ (and height $2$), during the computation, we will have $w$ links in memory. This is apparent for instance at step $2$ of the first approach, we see that $X^2_{nol}$ (it depends on three indices here and for the general case it will depend on $w$ indices). Because of that, if each link has a dimension $d$, we will have $d^w$ elements to keep in memory.
In the second approach, we will never have more than $3$ links in memory. Hence, we say that it is less memory expensive. This is because of the way we contract the tensor network, we always make sure to never have more than $3$ links that are not summed.
As here $w=3$ the difference is probably not so clear with this specific value of $w$ (but this is the example taken in the paper, I hope it will be clear enough for the readers)
What disturbs me - my questions.
First question:
I am not sure to fully understand the logic. Even though the "actual" computation we are doing requires $d^w$ terms in memory for the first approach but a number that doesn't grow with $w$ in the second one, we need "anyway" to keep in memory the tensors that we are not summing. For instance at a given step $n_0$ of the calculation, maybe some tensors haven't played any role yet (they will be summed in the future), but I have to have them in memory somewhere. If we take this into account, wouldn't it imply that both approach are actually similar in terms of memory consumption?
Second question:
Here, I mainly talked about the memory consumption of the two approaches. What about the number of calculations to be done? Could I have an explanation telling me why the second approach is "better"?
Third question:
This question is simply to check that a "ladder-shaped" network is a network in which the width grows with some parameter $w$ while the height is constant. In the paper they actually don't give a precise definition of what it is.