Tensor network contraction "bubbling": why are some approaches more computationally efficient than others (question from a beginner)

Question

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.

Answer 1

1. It's safe to assume the input was given to you, so whatever input you started with, you automatically needed that much memory anyway. Note that, if each wire in the ladder is $d$-dimensional, then each 3-tensor (node that isn't an endpoint of the ladder) only needs $d^3$ numbers to describe it, so the total input size for a $2 \times w$ grid (aka ladder of width $w$) would only be $2(w-2)d^3 + 4d^2 \leq 2wd^3$, which grows linearly with $w$, compared to the $d^w$ memory needed in the computation with the first strategy.

2. Each individual contraction you do is essentially a matrix multiplication (where the tensors themselves are suitably flattened). If you are contracting over $k$ indices simultaneously (and, again, assuming each wire correspond to a $d$-dimensional space), then you are multiplying matrices whose size is ~$d^k$. In practice, memory and communication requirements are the bottleneck for multiplying matrices. In theory, one can count arithmetic operations. Your matrices will likely be rectangular, e.g. here are the sizes for the matrices that would appear in the steps of method 2:

Step 0 $d \times d$ (for A) times $d \times d$ (for F)

Step 1 $d \times d$ (for $Y^0$) times $d \times d^2$ (for B, where the $d^2$ arises b/c the two indices of $B$ not being contracted over are flattened in this view)

Step 2 $d \times d^2$ by $d^2 \times d$ etc.

For multiplying square $d \times d$ matrices, the naive algorithm uses $O(d^3)$ arithmetic operations, but the exponent of matrix multiplication is known to be quite a bit smaller (albeit by theoretical algorithms that, at the moment, are not practical at exponents below ~2.7). For multiplying non-square matrices, sometimes better can be done, e.g. https://people.csail.mit.edu/virgi/6.890/papers/legallurrutia.pdf implies you can multiply a $d^2 \times d$ by a $d \times d^2$ matrix in times $O(d^{2.04...})$.

3. I think they are using the phrase "ladder-shaped" informally to mean, in your terminology, a ladder of height 2.