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.

tensornetwork.org/src/mps/algorithms/denmat_mpo_mps/index.md

Lines 59 to 61 in 32c3234

	To compute these overlap tensors efficiently, one contracts the previous
	$L_j$ with the next MPS, MPO, then conjugate MPO and MPS tensors one
	at a time (not shown).

Consider the contraction of the overlap tensor $L_j$, 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 $L_j$ 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.