Bandwidth minimization

Nobody has claimed this yet.

Add functionality for reordering the vertices of a tensor network/graph to minimize the graph bandwidth.

It appears that a popular algorithm for this is the Cuthill-McKee algorithm. There is a discussion of Julia implementations on Julia Discourse. Some Julia implementations are:

This may be relevant for finding an MPS ordering for a graph of Hamiltonian interactions or mutual information that may be beneficial for entanglement (@JoeyT1994 is this what you use for your dense-graph DMRG calculations?), or finding an MPS embedding of a more general graph if you are looking to approximate a general tensor network as an MPS (though @LinjianMa has a more specialized algorithm for that in #11 which takes into account a tensor network the resulting MPS might contract with in order to try to minimize future swapping, which would be good to split off into a separate function).

It also may be relevant for finding network layouts for tensor networks/graphs that are known to be linear or have some linear structure.

Finally, this problem appears to be related to the minimum linear arrangement (MinLA) problem, which is known to be NP-hard. See:

which is a special 1D case of the more general grid arrangement problem:

https://www.sciencedirect.com/science/article/pii/S157252861200045X

which could be relevant for visualizing hypercubic-like tensor networks and also automatically approximating tensor networks as PEPS networks (say for a generalized boundary PEPS algorithm for contracting cube-like graphs).

The issue names no repository files, tests, or entry points to begin with. Start by reviewing the linked Cuthill-McKee Julia implementations and the project context around tensor-network vertex ordering; done would require a defined API and an implemented reordering method that minimizes graph bandwidth.

Written by the indexing model from the issue text.

Description

Contributor guide

First steps

Research direction

Assessment