I have a question about the implementation of the zip-up algorithm in iTensor. To give some context to my question, please consider the following. I am performing calculations that require evaluating the Hadamard Product of two MPS (element-by-element multiplication).
The naive implementation of the Hadamard has pretty bad scaling and will be the main limitation of the algorithm I am working on (scales O(\chi^6)). Thus I am looking for ways that can be improved. I understand the zip-up algorithm can improve that to O(c \chi^3) for MPS-MPO contractions (based on a review of Minimally entangled typical thermal state algorithms, where c is the bond size of the MPO). I also understand performance can vary but I’d still like to experiment with it.
Having said that - I checked the methods in iTensor and see that zip-up is currently only implemented for MPO-MPO contractions. I could still utilize it but it would be a bit more cumbersome (having to convert my MPS to MPOs using copy tensors and then zipping-up, then removing any left over extra indices).
My questions then are:
Why is zip-up only implemented for MPO-MPO contractions but not for MPS-MPO contractions?
Any plans to implement it a O(c \chi^3) scheme (ala zip-up) for MPS-MPO contractions?
Thanks for the questions. You’re right that zip-up has a good efficiency for MPS-MPO contractions. There’s not such a deep reason we haven’t implemented it, other than that we favored implementing some more “controlled” algorithms for MPS-MPO first. (Zip-up is technically uncontrolled, in the sense that the error can grow large in some cases, in a way not revealed by the SVD spectrum.) The reason we did implement it for MPO-MPO is that we weren’t as aware of better algorithms for that case at the time, though now I think I know some.
One thing I’m not tracking with your question is how your task of taking a hadamard product (is this equivalent to like an outer product?) of two MPS is related to MPS-MPO multiplication. Is there a way to map one onto the other that you are thinking about?
Finally, I recently implemented a different algorithm for MPS-MPO, the “fitting” algorithm, that has a competitive scaling with zip-up so that might offer what you need. It’s currently available through a different package (ITensorTDVP) and I can give you more information about that.
One thing I’m not tracking with your question is how your task of taking a hadamard product (is this equivalent to like an outer product?) of two MPS is related to MPS-MPO multiplication. Is there a way to map one onto the other that you are thinking about?
My initial thought was you convert one MPS into an MPO using the copy tensor at each site (making sure to prime those indices). Then use zipup to contract that MPO with the other MPS. The hope being it would scale better than naive Hadamard.
Finally, I recently implemented a different algorithm for MPS-MPO, the “fitting” algorithm, that has a competitive scaling with zip-up so that might offer what you need. It’s currently available through a different package (ITensorTDVP) and I can give you more information about that.
Yes, that sounds interesting. I had not heard of ITensorTDVP but now that you’ve pointed it out I will take a look. Do you have any background or papers you could point me to regarding the algorithm?
Thanks for the further background on what you’re trying to do.
The fitting algorithm for MPOxMPS is mainly discussed in this paper: https://iopscience.iop.org/article/10.1088/1367-2630/12/5/055026/meta
shortly after equation 16 and illustrated a bit in Fig. 4. Basically one makes a “sandwich” of the MPO you want to apply in the middle to the MPS on the bottom. The MPS on the top is the one you are trying to compute, and will become the product. You sweep back and forth just like in DMRG, but unlike DMRG you leave the MPS on the bottom of the sandwich unchanged and only update the one on top. Also instead of calling an “eigensolver” like Lanczos, you just contract the tensors, SVD the result, and go on to the next bond as shown in the figure. If you assume the MPS on top has the maximum possible bond dimension, you can convince yourself that this procedure would perfectly compute the MPOxMPS product. It’s very efficient, but like DMRG it can sometimes fail to find the correct result, so it needs to be initialized well.