Question about density matrix algorithm for MPO-MPS contraction

[ultimatile]

I have a question about the sentence below on the page MPO-MPS Multiplication: Density Matrix Algorithm.

https://github.com/TensorNetwork/tensornetwork.org/blob/32c3234f819d1d0b07a884003c2cc37ef1d03ba1/src/mps/algorithms/denmat_mpo_mps/index.md?plain=1#L59-L61

Consider the contraction of the overlap tensor $Lj$, MPO $W{j+1}$, MPS $A{j+1}$, and their conjugates $W^\dagger{j+1}$ and $A^\dagger{j+1}$. Does the sentence mean that the tensor $R{j+1} = W{j+1}A{j+1}$ is retained and conjugated to avoid computation for the contraction of $A{j+1}^\dagger W{j+1}^\dagger$?

[emstoudenmire]

Thanks for the question. Basically the steps are to prepare $W^\dagger{j+1}$ and $A^\dagger{j+1}$ first, by copying $A{j+1}$ and $W{j+1}$ and conjugating the elements of these copies, then you have these four tensors and contract them onto $Lj$ one at a time, trying to choose the most efficient sequence of contraction. I think (doing this in my head) that a good sequence would be to contract on $A{j+1}$, then $A^\dagger{j+1}$, then $W{j+1}$, then $W^\dagger_{j+1}$.

[ultimatile]

Thank you for your reply. I have understood the meaning of the sentence. I am currently trying to check the optimal contraction order and will report back when it is done.

[ultimatile]

If my estimate is correct, a "top-down" order (↗︎→↘︎↗︎ in the figure below) is more efficient than the suggested order (↗︎↗︎↘︎↘︎). The "top-down" order requires $O(2dk^2M^3+2d^2k^3M^2)$ operations, whereas the suggested order requires $O((d^2+d)k^2M^3+(d^3+d^2)k^3M^2)$ operations, where $d$ is the bond dimension of the vertical bond. Therefore, the suggested order requires $O((d-1)(dk^2M^3+d^2k^3M^2))$ more operations compared to the "top-down" order.