Fast Tensor Disentangling Algorithm

In his manuscript, the author proposes a novel numerical algorithm, aimed at finding a unitary transformation that minimizes the entanglement across some particular set of legs of a multi-index tensor. Such a procedure is an important part of certain tensor network based algorithms, such as the multi-scale entanglement renormalization ansatz (MERA) and the related tensor network renormalization (TNR) procedure. It also has significance on its own: in the context of quantum computation, one is often interested in the minimal number of unitary gates needed to prepare a particular quantum state, known as the state's circuit complexity.

The paper clearly explains the proposed algorithm and provides evidence that it is significantly faster than previously existing methods, especially for large tensors, while it is almost as effective in minimizing the entanglement. While the benchmarking results presented are somewhat limited (i.e., they focus mostly on toy examples of various randomly chosen tensors, rather than using the method in the context of a particular algorithm such as TNR), based on them, it is reasonable to assume that the new 'fast disentangling' method will be a useful addition into the numerical arsenal of tensor network algorithms. For this reason, I think it is well suited for publication in SciPost.

One shortcoming of the paper is that, while there is some intuition provided for the algorithm, it is somewhat unclear what are the necessary conditions for it to work well. Are there examples of states where it fares much worse than previous disentangling methods? In the application presented in the paper, the algorithm is used to disentangle a completely random states, which is a 'worst case' scenario. One might wonder if the method still continues to outperform existing ones for states that are known to be easy to disentangle in principle. I think it would improve the manuscript if the author could comment on this question.

As a technical comment: when testing the algorithm, I have noticed a small issue. In the Schmidt orthonormalization step, when rows of the matrix are not exactly linearly dependent, only within machine precision, the algorithm fails to detect this and sometimes returns results that are not unitary. As far as I can see, this can be easily remedied by replacing the condition 'norm == 0' with some small cutoff instead.

I have found a small number of typos in the manuscript.
1) 'tensor project' (presumably should be 'tensor product')
2) In the line following footnote 3: chi1 -> chi_1

The paper introduces and numerically demonstrates an algorithm that quickly generates disentangling unitaries for use in tensor network algorithms. The author also provides readable example Python code through GitHub. I recommend the work for publication in SciPost Physics: the work introduces a relevant new tool for operator disentangling, proves better asymptotic scaling than iterative algorithms in some regimes, and numerically demonstrates a significant speedup over a gradient descent algorithm.

In its base form, the "fast-disentangling algorithm" provides a single unitary $U$ that reduces the entanglement across a specified cut of an input four-index tensor $A$ by an a priori unknown amount. On the analytical side, equation 9 gives rigorous lower bounds for the number of Schmidt coefficients of $UA$ that are identically zero. The author further motivates the algorithm by showing it maximally reduces the entanglement for a restricted class of tensors given in equation 1.

The author demonstrates numerically that the algorithm is considerably faster than iterative methods by timing how long an iterative method (gradient descent) takes to reach the same reduction in entanglement entropy as the fast-disentangling algorithm. (The iterative algorithm may ultimately reduce the entanglement entropy more than the fast-disentangling algorithm, which, when straightforwardly applied, does not give improvements upon iteration.) The author also proves that the asymptotic scaling of the fast-disentangling algorithm is better than that of single steps of iterative algorithms. The asymptotic difference is largest for tensors $A$ with different dimension indices where the disentangling unitary is contracted with the two smallest dimensional indices of $A$.

Finally, the author demonstrates how to disentangle a wavefunction using a brickwork circuit generated by the fast-disentangling algorithm iterated over location of the entanglement cut. This example also shows that the fast-disentangling algorithm can be paired well with iterative ones for further reduction of entanglement entropy.

Overall, the algorithm is simple but powerful, the asymptotics follow straightforwardly from the algorithm, and the numerical demonstration is convincing. I recommend publication in SciPost Physics. There are a couple places where the clarity can be improved, and I request a couple changes and suggest several more. Please see the requested changes for more details.

1. What is the definition of $S^{min}$ in table 1? How does one compute it and the tensor corresponding to it? Please specify this in a few sentences in section 2.

2. Section 1 shows that the algorithm gives optimal results for entanglement minimization for the restricted form of the tensor $A$ given in equation 1. Equation 9, detailing the minimum number of singular values that are set identically zero, applies to more general tensors $A$ than just the restricted form given in equation 1. This difference should be explicitly reiterated/emphasized in the final paragraph of section 1 for clarity’s sake.
--------------------------------------------------------
The following suggestions are optional.

3. On the right hand side of equation 1, consider including a three-indexed unitary block (with shape [$\chi_1\chi_2$, $\chi_1$, $\chi_2$]) contracted with the left hand side of $M^{(1)}$ and $M^{(2)}$. That will make the difference between the right hand sides of equation 1 and equation 2 clearer. I think it will also help introduce the idea of "projecting out $M^{(3)}$" in order to isolate the piece of the tensor $A$ that is easily and optimally modified by left multiplication by a unitary.

4. Assuming for ease that all the legs of $A$ have the same dimension, $\chi_1 = \chi_2=\chi_3=\chi_4$, are there drawbacks to skipping immediately to the final step, 6, of the algorithm, using $A$ in the place of $B$? Running that step alone will ensure the same minimum number of identically vanishing singular values. The drawback would be that the resulting algorithm would likely no longer be an optimal algorithm for tensors $A$ with forms similar to that given in equation 1. Nevertheless, might it give comparable results for the unstructured, random matrices? Including a declarative statement on this, or an additional column or two in table 1, will help further emphasize that steps 1-5 are important for fast disentangling of structured tensors and less important for unstructured ones.

5. Section 3 discusses disentangling a wavefunction with the fast-disentangling algorithm. The procedure quickly, non-iteratively reduces the entanglement entropy across a given cut using the fast-disentangling algorithm, and then iterates over the location of the cut. Additional iteration is then possible by applying gradient descent algorithms to the resulting brickwork circuit, or loading the resulting state as the initial state of another iterative algorithm. Even without those additional iterative procedures, this application of the fast-disentangling algorithm is iterative given the iteration over the location of the cut and the generation of many layers of a brickwork circuit. Please comment in a sentence in section 3 how this is consistent with the following sentence from section 1: “The (statistical) result of the algorithm is not affected if $A$ is multiplied by a unitary matrix on any of its three indices. As such, [it] is not useful to iterate this algorithm.” From a little thought on the reader’s part, the consistency stems from the resulting brickwork layers multiplying more than a single index at once, but this should be explicitly spelled out.

6. Does the iterative approach (generating a brickwork circuit by iterating over entanglement cuts) referenced in point 4 generalize? For example, for an order-4 tensor with $\chi_1 = \chi_2 = \chi_3 = \chi_4 = 16$, what of treating the $k$ index with dimension $\chi_1^2$ as a set of eight 2-dimensional indices and iterating over “local” pairs of them similarly to the wavefunction disentangler mentioned above? The new $\chi_1’$ would be $2$, and $\chi_3’=128$. The resulting scaling, $O(\chi_1^4 \chi_3 + \chi_1^6)$, would be in principle reduced by a factor of 10000 per unitary relative to one-off use of the fast-disentangling algorithm. The drawback might be that the small size of the disentangling unitaries and the fact that many do not directly reduce the entanglement across the original cut of interest would reduce the efficacy. Nevertheless, could the iterated fast-disentangling algorithm’s brickwork be “better” (in e.g. final entanglement entropy after some large number of iterations or time to reach a low entanglement entropy) than a one-off use of the fast-disentangling algorithm? Please briefly comment in a couple sentences on the applicability/future potential of the iterative approach beyond wavefunctions.