Wrong indices orders after optimization with SABipartite

[ChenZhao44]

Version information:

• Julia v1.7.3
• OMEinsum v0.6.13
• OMEinsumContractionOrders v0.6.8

Example:

using OMEinsum, OMEinsumContractionOrders
using Test

function z_tensor(n, α)
    t = zeros(ComplexF64, 1<<n)
    t[1] = 1
    t[end] = exp(im*α)
    return reshape(t, fill(2, n)...)
end

function x_gate()
    return ComplexF64[0 1; 1 0]
end

ec = EinCode([[1,2,3,4], [2,5], [3,6], [4,7]], [5,6,7,1])
ts = [z_tensor(4, pi), x_gate(), x_gate(), x_gate()]
ec_opt = optimize_code(ec, uniformsize(ec, 2), SABipartite())
@test ec(ts...)[:] ≈ ec_opt(ts...)[:] # error

[GiggleLiu]

julia> ec = EinCode([[1,2,3,4], [2,5], [3,6], [4,7]], [5,6,7,1])
1∘2∘3∘4, 2∘5, 3∘6, 4∘7 -> 5∘6∘7∘1

julia> ec_opt = optimize_code(ec, uniformsize(ec, 2), SABipartite())
1∘3∘7∘5, 3∘6 -> 1∘5∘6∘7
├─ 3∘6
└─ 1∘2∘3∘7, 2∘5 -> 1∘3∘7∘5
   ├─ 2∘5
   └─ 1∘2∘3∘4, 4∘7 -> 1∘2∘3∘7
      ├─ 4∘7
      └─ 1∘2∘3∘4

The problem is caused by the incorrect permutation in the output. I will fix it ASAP. Thanks for the issue!

[GiggleLiu]

It is a single line fix. This issue happens only in a very rare case. So you do not need to worry about the correctness of your previous result if it does not fall into the following category:

• You use KaHyParBipartite or SABiPartite, and the problem scale is small (default: number of tensors <= 40) such that there is only one valid partition.

I would suggest use TreeSA in most cases, with proper hyper-parameters, this one usually gives the best contraction order. And this one is the most tested one is practise.