On finding a good ordering of sites in an MPS

[RaimelMedina]

Hi guys! I recently saw a pull request extending TreeSA to support path decomposition finding and got curious about the comment on using this to find a good ordering of the sites in an MPS. Is there some documentation or example on how to use the algo for this purpose? I’m trying to find a good reordering of the legs on an MPS (the local dimensions are not uniform) and was wondering on what to use for that. Thanks!

[GiggleLiu]

Here is a sample code to obtaining a "good" MPS ordering. We first generate a sample tensor network with 3-regular graph topology, which has one tensor in each edge, and each tensor has rank 2 (this is for demonstration purpose, OMEinsumContractionOrders has not such constraint).

julia> using OMEinsumContractionOrders, Graphs

julia> rg3 = Graphs.random_regular_graph(100, 3; seed=42);  # graph topology

julia> code = OMEinsumContractionOrders.EinCode([[e.src, e.dst] for e in edges(rg3)], Int[]);  # one tensor for each edge

Then we optimize the path decomposition for the sample tensor network:

julia> optcode = optimize_code(code, uniformsize(code, 2), PathSA());

julia> contraction_complexity(optcode, uniformsize(code, 2))  # check pathwidth
Time complexity: 2^19.29432458408747
Space complexity: 2^14.0   <---- this one
Read-write complexity: 2^19.67212316041469

The path decomposition can be characterized by the elimination ordering or vertices, which is when a vertex is removed from the graph. It can be viewed as the site ordering of MPS I think.

julia> OMEinsumContractionOrders.label_elimination_order(optcode)
100-element Vector{Int64}:
  33
  34
  39
 100
...

Here, "good" means low path width, which is a graph characteristic that measures how similar a graph is to a line.
When you sqeeze a graph into a line in one direciton, the edges will have overlap in other directions. By minizing the largest number of overlapped edges, we obtain an optimal vertex ordering.

[RaimelMedina]

Thanks for the clear explanation! So if I understand correctly, this helps to find a good 1D arrangement for a generic graph tensor network (more on the topology side of things...)
I also had in mind the case where you have an MPS and you want to reorder the legs of the MPS in order to disentangle it as much as possible. I guess this falls into a different category as what you nicely described above?

[GiggleLiu]

I am not sure if disentangle mps by rearranging legs is well defined. It would be great if you could provide some references. Here, the setup is, given a irregular TN, what is the best MPS equivalence in terms of bond dimension.

[RaimelMedina]

Got it, thanks for clarifying this. I'm aware of these two papers (paper1 and paper2). Essentially, they perform spectral clustering on the pairwise mutual information matrix to find a decent/good reordering of the legs of the MPS.

[GiggleLiu]

Thank you, they seem to have a different starting point.

[RaimelMedina]

Yes. Sorry for the confusion on my side!