Better Contraction Algorithms

[chaserileyroberts]

This has already been brought up in #120, but I'm bringing it up again because our contraction algorithms suck.

We need much better algorithms, as hand coding contraction orders, or worse, just using naive is a really bad practice.

As the first step, we need to implement a fast version of fully optimal contraction. It's ok if it's just in python for now, but we need it to exist. We could also possibly adapt opteinsum's code to our own, but I don't know how easily that will be.

[stavros11]

I think it is fairly easy to adapt opt_einsum's code, at least for their optimal DFS contraction. There is a function optimal that takes sets with input/output edges and a dictionary with the dimensions and returns a list with the optimal contraction order. We can just write a wrapper that creates the sets and dictionary and use this function as it is (I can PR this). I have only checked how the optimal works but it might be possible to "transfer" their other opt_einsum algorithms similarly (if the opt_einsum people are okay with using their code of course).

At least this is the quick solution. If we would like something more elegant perhaps we should implement the algorithm from scratch using our cost calculators (I can try that, too), because opt_einsum has its own way of calculating costs.

[chaserileyroberts]

if the opt_einsum people are okay with using their code of course.

It's MIT open sourced, so they literally have no say in the matter. :)

Making a shim to go from our TensorNetwork to their optimal might be a good first step. Would love a PR on this! Feel free to include opt_einsum as a dependency if need be.

[chaserileyroberts]

Actually, using opt_einsum library seems like exactly what we should be doing. We could use the signatures/ids of the edges instead of letters. This allows us to make a shim pretty easily.

Let me try writing a PR tonight. If I can't get it done by midnight then feel free to take charge on it.

[chaserileyroberts]

Stavors, if you want to add the other contraction algorithms from opt_einsum after this PR is in, go for it.

[stavros11]

Sure, I can look at this. It should be easy now that the first one is in.

[stavros11]

By the way, it might be useful to take advantage of opt_einsum's path reuse functionality so that we avoid recalculating paths when we want to contract the same network many times (for example during optimization). I am not sure how this could be done easily, for now I just mention it to keep it in mind.

[chaserileyroberts]

Good idea. Add it as a Github issue so we don't forget about it.