Strange behavior with diagonal gates.

Hi,

I constructed a simple 6-qubit circuit with a brickwork pattern, and generate the corresponding expression for calculating an amplitude. The alternating two-qubit gates are generally not diagonal, but some can be decomposed into local single-qubit gates followed by a diagonal gate. Diagonal decomposition, with the introduction of hyperedges, should reduce the computational cost. Although the example provided below should not result in a reduction of cost that is very noticeable, we are still seeing some very unexpected behaviors. The contraction path results in a very large number of open indices in intermediate tensors, even though the graph should be almost a ring graph, which has a tree width of 2.

Code:

import numpy as np
from cuquantum import contract_path

# Filler for operands, values don't matter
value = np.zeros(2, dtype=complex)
cz = np.zeros([2, 2], dtype=complex)
single_qubit_gate = np.zeros([2, 2], dtype=complex)
two_qubit_gate = np.zeros([2, 2, 2, 2], dtype=complex)

# Regular no diagonal decomposition
exp_str = 'a,b,c,d,e,f,ag,bh,ci,dj,ek,fl,ghmn,ijop,klqr,mrsx,notu,pqvw,sy,tz,uA,vB,wC,xD,y,z,A,B,C,D->'
operands = [value] * 6 + [single_qubit_gate] * 6 + [two_qubit_gate] * 6 + [single_qubit_gate] * 6 + [value] * 6
path, info = contract_path(exp_str, *operands)
cost = info.opt_cost
largest_intermediate = info.largest_intermediate
intermediate_modes = info.intermediate_modes
print(f'No diagonal gate: cost {cost}, largest_intermediate {largest_intermediate}.')
print('Intermediate modes: ', intermediate_modes)

# Diagonal decomposition
exp_str = 'a,b,c,d,e,f,ag,bh,ci,dj,ek,fl,gh,ij,kl,gm,hn,io,jp,kq,lr,mr,no,pq,ms,nt,ou,pv,qw,rx,s,t,u,v,w,x'
operands = [value] * 6 + [single_qubit_gate] * 6 + [cz] * 3 + [single_qubit_gate] * 6 + [cz] * 3 + [single_qubit_gate] * 6 + [value] * 6
path, info = contract_path(exp_str, *operands)
cost = info.opt_cost
largest_intermediate = info.largest_intermediate
intermediate_modes = info.intermediate_modes
print(f'Diagonal gate: cost {cost}, largest_intermediate {largest_intermediate}.')
print('Intermediate modes: ', intermediate_modes)

Output:

No diagonal gate: cost 724.0, largest_intermediate 16.0.
Intermediate modes: ('jopc', 'jop', 'g', 'hmn', 'h', 'j', 'elqr', 'l', 'ymrx', 'znou', 'u', 'Bpqw', 'w', 'x', 'lqr', 'qr', 'pqw', 'pq', 'op', 'mn', 'nou', 'no', 'pn', 'mp', 'qm', 'rm', 'yx', 'x', '')
Diagonal gate: cost 5072.0, largest_intermediate 256.0.
Intermediate modes: ('i', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 'ji', 'hg', 'nh', 'pj', 'lk', 'rl', 'gm', 'on', 'io', 'qp', 'kq', 'mr', 'jimr', 'hglk', 'gmon', 'rlqp', 'nhjimr', 'pjhglk', 'kqgmon', 'iorlqp', 'nimrpglk', 'kgmnirlp', '')