Einsum

yastn.ncon() and yastn.einsum() (which differ only by syntax) contract a network of tensors pairwise. Two kinds of fermionic swap gate can be requested: between two lines of the network (swap), and between a line and a fixed charge (charge_swap). This page introduces the arguments, and then describes how the gates of swap are placed, including gates on lines that are about to be contracted, so that the result does not depend on the order of contractions.

einsum and ncon

yastn.einsum() follows the notation of numpy.einsum(): each tensor gets a string of one-letter labels; a letter appearing twice, on two tensors or twice on one tensor, marks a contracted line; and the labels after -> fix the outgoing legs. Without -> the labels appearing once are kept, in the order they appear. A * in front of a tensor’s labels conjugates that tensor.

yastn.ncon() takes the same network as a list of tensors and a list of integer labels: positive labels mark contracted lines, and the non-positive labels -0, -1, -2, ... mark the outgoing legs in that order, while conjs conjugates individual tensors. einsum translates its letters into such labels and calls ncon, so the rest of this page speaks of lines labelled by their ncon index.

Three further arguments shape the contraction.

order

The sequence in which the contracted lines are consumed: a string of letters for einsum, alphabetic by default, or a sequence of positive labels for ncon, ascending by default. It selects the contraction path and, with it, how much work the swap gates below need.

swap

The pairs of lines that cross in the fermionic order of the network, each pair contributing a fermionic swap gate: a comma-separated string of letter pairs for einsum, such as swap='ab,cd', or a sequence of label pairs for ncon, such as swap=[(1, 2)].

charge_swap

Swap gates between a line and a fixed charge, e.g. a fermionic string of charge \(q\) crossing that line: a sequence of pairs (line, charge), the line named by its letter for einsum, such as charge_swap=[('a', (1,))], or by its label for ncon, such as charge_swap=[(1, (1,))]. The charge is read in the symmetry of the tensors, like the total charge n of a tensor, and the fermionic flag of their configuration selects the components that enter the sign. Each gate multiplies the blocks by \((-1)^{p(q) \cdot p(\mathrm{line})}\), the same as yastn.swap_gate() with charge.

# matrix multiplication with the first tensor conjugated
yastn.einsum('*ij,jk->ik', a, b)
yastn.ncon([a, b], [(-0, 1), (1, -1)], conjs=(1, 0))

# closing two lines, with a swap gate between them
yastn.einsum('ij,ji', a, b, swap='ij')
yastn.ncon([a, b], [(1, 2), (2, 1)], swap=[(1, 2)])

# a string of charge 1 crossing the contracted line j and the outgoing line k
yastn.einsum('ij,jk->ik', a, b, charge_swap=[('j', (1,)), ('k', (1,))])
yastn.ncon([a, b], [(-0, 1), (1, -1)], charge_swap=[(1, (1,)), (-1, (1,))])

Mechanism

The rest of this page describes how ncon places the swap gates of swap. It is not needed to use yastn.einsum() or yastn.ncon().

Plan and execution

ncon first builds a plan, a tuple of commands, from the index labels alone, and then executes it on the tensors. The plan never looks at tensor data and is cached, so the same plan serves every call with the same inds, order and swap.

command	action
tensordot	contract two tensors (an empty pair of axes is an outer product)
trace	contract pairs of legs of one tensor
swap_gate	apply swap gates between pairs of legs of one tensor
parity_sign	apply the parity string of a jump move
tensordot_psplit	tensordot that records the parity of some contracted legs (gadget)
trace_psplit	trace that records the parity of some contracted legs (gadget)
transpose	order the outgoing legs

A plan can be printed for inspection:

from yastn.tensor._einsum import _meta_ncon

inds = ((1, 2, 3), (1, 2, 4), (3, 5), (4, 5))
for command in _meta_ncon(inds, None, ((1, 5),)):  # inds, order, swap
    print(command)

Tensors are numbered by their position in the list passed to ncon; each contraction result gets the next free number. Legs are numbered by their position on the current tensor.

Swap gates on lines of the network

A swap gate between lines \(a\) and \(b\) multiplies each block by

\[(-1)^{p(a) \cdot p(b)}, \qquad p(a) \cdot p(b) = \sum_i p_i(a)\, p_i(b),\]

where \(p_i(a)\) is the parity of the \(i\)-th charge component carried by line \(a\), and the sum runs over the components selected by the fermionic flag of the tensor configuration. The sign depends only on the charges carried by the two lines, so the gate can be applied on any tensor that has both lines as legs. While planning, a pair whose lines end on a common tensor is applied there with swap_gate; the other pairs wait until contractions bring their lines onto one tensor.

A pair is a bad swap when one of its lines is contracted in the current step and the other line touches neither of the two tensors being contracted: after the step the first line is gone and the gate has nowhere to go. Every bad swap is removed exactly before the step, by jump moves where possible and by a parity gadget otherwise.

Diagrams. In the figures below circles are tensors and black lines are their legs, labelled by the ncon index. A red dot marks a swap gate between the two lines crossing there; lines drawn across each other with a gap cross without a swap gate. A blue square labelled \(P_T\) on a line \(d\) is the parity string \((-1)^{P_T \cdot p(d)}\) of tensor \(T\), where \(P_T\) is the parity of the total charge T.n; this is what ('parity_sign', T, ...) applies, via yastn.swap_gate() with charge=T.n.

Jump move

A symmetric tensor \(T\) with legs \(l_1, \dots, l_m\) satisfies, for any line \(d\),

\[\prod_{j=1}^{m} \mathrm{swap}(l_j, d) = (-1)^{P_T \cdot p(d)},\]

because on every block of \(T\) the parities of the legs add up to \(P_T\). Moving line \(d\) across \(T\) therefore trades the swap gate with one leg for swap gates with all the other legs and a parity string on \(d\). A self-loop of \(T\) (a pair of legs still to be traced, or a gadget pair) appears twice in the product and drops out.

Jump move over \(T\): \(\mathrm{swap}(l_1, d) = \mathrm{swap}(l_2, d)\, \mathrm{swap}(l_3, d)\, (-1)^{P_T \cdot p(d)}\).

Resolving the bad swaps of one step

Consider a step contracting tensors \(P\) and \(Q\) over lines \(e_1, \dots, e_K\); for a trace \(P = Q\). The rest of the network is a graph \(H = (V, E)\). Its vertices are the tensors other than \(P\) and \(Q\), the set \(V\), plus one external vertex \(\infty\) on which every open line ends. Its edges \(E\) are the lines with both ends among those vertices. A line that ends on \(P\) or \(Q\) is therefore not an edge: a swap gate between it and a contracted line has both lines on \(P\) or \(Q\) and is applied there, so it is never a bad swap. Every bad swap of the step pairs a contracted line \(e_k\) with an edge \(L \in E\). The following notions describe them.

Symmetric difference

For sets \(A\) and \(B\), \(A + B = (A \cup B) \setminus (A \cap B)\) is the set of elements in exactly one of them. A swap gate applied twice cancels, so applying a set of swap gates on top of the present ones leaves their symmetric difference.

Rows and columns

The bad swaps form a table with one row per contracted line \(e_k\) and one column per edge \(L \in E\), with an entry where \(\mathrm{swap}(e_k, L)\) is present (see the example below). Row \(k\) is the set of edges \(Y_k = \{ L \in E : \mathrm{swap}(e_k, L) \text{ is present} \}\); column \(L\) is the set of contracted lines whose swap with \(L\) is present. The step can proceed once every row is empty.

Coboundary

For \(F \subseteq V\), the coboundary \(\delta F \subseteq E\) is the set of edges with exactly one end in \(F\); the external vertex \(\infty\) is never in \(F\). For a single tensor, \(\delta T = \delta \{T\}\) is the set of legs of \(T\) that are edges of \(H\), self-loops excluded. Physically, \(\delta F\) represents the field generated from the source \(F\).

Cut

A set \(\Delta \subseteq E\) is a cut if \(\Delta = \delta F\) for some \(F \subseteq V\). Equivalently, the vertices can be coloured with two colours, \(\infty\) keeping the first, so that the edges joining different colours are exactly those of \(\Delta\); the vertices of the second colour then form \(F\). Since \(\delta F + \delta F' = \delta (F + F')\), the symmetric difference of two cuts is a cut.

Class

Rows \(k\) and \(k'\) are in the same class if they differ by a coboundary, \(Y_k + Y_{k'} = \delta F\) for some \(F \subseteq V\), i.e., if \(Y_k + Y_{k'}\) is a cut. This is an equivalence relation: \(\delta \emptyset = \emptyset\), the symmetric difference is symmetric, and \((Y_k + Y_{k'}) + (Y_{k'} + Y_{k''}) = Y_k + Y_{k''}\) is a cut when both terms are. The class of row \(k\) consists of the rows \(Y_k + \Delta\) with \(\Delta\) a cut.

Two kinds of jump move change the rows. The figure below applies each of them to the same configuration, and shows what each does to the table.

Row jump. A jump over a tensor \(T \in V\), with partner line \(e_k\), changes row \(k\) by the coboundary of \(T\), \(Y_k \to Y_k + \delta T\). The swap gates it creates between \(e_k\) and the lines from \(T\) to \(P\) or \(Q\) have both lines on \(P\) or \(Q\), and are applied there before the step (therefore not included in \(\delta T\)).

Column jump. A jump over \(P\) (or \(Q\)), with partner edge \(L \in E\), changes column \(L\), toggling \(L\) in every row at once: \(Y_k \to Y_k + \{L\}\) for all \(k\). It also creates swap gates between \(L\) and the uncontracted legs of \(P\), which are ordinary swaps for later steps. For a trace the contracted lines are self-loops of \(P\), and a column jump changes no row.

Either jump on the same configuration. \(P\) and \(Q\) are contracted over \(e_1\) and \(e_2\); \(V\) holds \(S\), \(T\), \(U\), joined by the edges \(a, b, c\), which are the columns of the table. The line \(m\) to \(Q\) and the open leg \(u\) of \(P\) end on the contracted tensors, so they get no column. Left: the bad swaps \((e_1, a)\) and \((e_2, b)\). Middle: the row jump over \(T\) with partner \(e_2\) adds \(\delta T = \{a, b\}\) to row 2 alone, so \(e_2\) stops crossing \(b\) and starts crossing \(a\); the swap it picks up with \(m\) has both lines on \(Q\) and is applied there. Right: the column jump over \(P\) with partner \(a\), on the same starting configuration, toggles \(a\) in both rows, and the swap it creates with \(u\) waits for a later step.

Which rows can be emptied. Row jumps over the tensors of a set \(F \subseteq V\) change a row by the cut \(\delta F\), which keeps the row in its class, and a column jump changes all rows by the same set, which keeps every \(Y_k + Y_{k'}\). No jump therefore changes which rows share a class. Rows that can be emptied together must end up equal, so they must have been in one class from the start. Conversely, the rows of one class can be emptied together: row jumps first make them equal, and column jumps then empty them all. A trace step has no column jumps, so only the class of \(\emptyset\), i.e., the rows that are cuts themselves, can be emptied.

The row jumps commute with the column jumps, so only the set of jumps matters, not their order. The planner emits all row jumps first and the column jumps afterwards.

From jumps to a 2-colouring. To bring row \(k\) onto the representative row \(r\) of its class, the planner needs tensors in \(V\) whose row jumps, all with partner \(e_k\), change row \(k\) by \(\Delta = Y_k + Y_r\). Jumping over the tensors of a set \(F \subseteq V\) changes the row by \(\delta F\). Record the choice of \(F\) as a colour, \(c_T = 1\) for \(T \in F\) and \(c_T = 0\) for the other vertices, with \(c_\infty = 0\), as the external vertex cannot be jumped over. An edge \(L\) between vertices \(S\) and \(T\) lies in \(\delta F\) exactly when \(c_S \neq c_T\), so \(\delta F = \Delta\) becomes one condition per edge,

\[c_S + c_T \equiv [L \in \Delta] \pmod 2 ,\]

where \([L \in \Delta]\) is 1 for \(L \in \Delta\) and 0 otherwise: the colour has to change across the edges of \(\Delta\) and stay the same across all other edges. The planner solves these conditions by propagating colours along the edges of \(H\), starting from one vertex in each connected part. An edge whose ends already carry colours that violate its condition shows that no \(F\) exists, and row \(k\) then does not belong to the class. Otherwise the colouring is the list of jumps: one row jump with partner \(e_k\) over every tensor of colour 1. In a connected part with an open line the colours are fixed by the external vertex. In a part without open lines the two colours can be exchanged, which replaces the vertices to jump over by all the others of that part; both choices change the row by \(\Delta\), and the planner takes the one with fewer vertices of colour 1, i.e., fewer jumps and parity strings (on a tie, the one that keeps the starting tensor at colour 0).

Example. The remaining illustrations follow the first step of

yastn.ncon([P, Q, A, B, C], [(1, 2, 6), (1, 2, 7), (3, 4), (3, 5, 6), (4, 5, 0, 7)],
           swap=[(1, 3), (2, 4)])

which contracts \(P\) and \(Q\) over \(e_1\) and \(e_2\) (lines 1 and 2). In \(H\), the vertices \(V\) are A, B, C and the edges \(E\) are \(x\), \(y\), \(z\) (lines 3, 4, 5) together with the open line \(w\) of C. The lines \(u\) and \(v\) (lines 6 and 7) join B to \(P\) and C to \(Q\); they end on \(P\) or \(Q\), so they are not edges of \(H\) and have no column in the table of bad swaps. The two bad swaps give the rows \(Y_1 = \{x\}\) and \(Y_2 = \{y\}\).

The colouring for \(\Delta = Y_1 + Y_2 = \{x, y\}\) starts at C, whose colour 0 is fixed by its open line \(w\). Edge \(y \in \Delta\) gives \(c_A = 1\), edge \(z \notin \Delta\) gives \(c_B = 0\), and edge \(x \in \Delta\), between A and B, is consistent. Hence \(\Delta = \delta A\) is a cut, and row 2 is brought onto row 1 by the single row jump over A shown above.

The vertices of \(H\) coloured for the cut test; \(P\), \(Q\) and the lines ending on them (the contracted lines, \(u\) and \(v\)) are grey. Left: colouring A alone changes the colour exactly across \(x\) and \(y\) (orange), so \(\{x, y\} = \delta A\) is a cut. Right: had the only bad swap been \((e_1, x)\), the rows would differ by \(\{x\}\), and the colour would have to change across \(x\) but not across \(y\) and \(z\). As \(x, y, z\) form a cycle, B cannot satisfy both; in the drawing, \(z\) has to cross \(e_1\) without a swap gate.

Recipe. The planner groups the rows into classes, each represented by its first row. Since no jump moves a row out of its class, at most one class can be emptied in a step; with more than one class the jumps cannot resolve all the bad swaps of the step, and the rows left over are handled by the parity gadget below. The planner chooses this emptied class as the largest one, so that the fewest rows need a gadget (on a tie, the class whose first row comes first; for a trace, the class of the empty row, i.e., the rows that are cuts), and emits

1. row jumps that bring every row of the emptied class onto its representative row,

2. column jumps, over whichever of \(P\) and \(Q\) has fewer uncontracted legs (\(P\) on a tie), one for each line of the representative row,

each group followed by swap_gate commands for the pairs that now sit on one tensor. Rows outside the emptied class get a parity gadget. Any other row of the class, or any set of edges that differs from it by a cut, would serve equally well as the representative: the result is the same, and only the number of jumps changes.

In the example both rows form one class, represented by row 1. The figures show the network and its table of bad swaps after each group of jumps.

The example and its table: row \(e_k\) has a red dot in column \(L\) when line \(L\) crosses \(e_k\) with a swap gate, so \(Y_1 = \{x\}\) and \(Y_2 = \{y\}\). The columns are the edges \(x, y, z, w\); the lines \(u\) and \(v\), which end on \(P\) or \(Q\), get none.

Row jump over A (the set \(F\) of the cut test) with partner \(e_2\): line \(e_2\) passes over A, stops crossing \(y\), starts crossing \(x\) and carries the parity string \(P_A\). In the table, \(\delta A = \{x, y\}\) is added to row 2 (shaded cells), which now equals the representative row 1.

Column jump over \(P\) with partner \(x\), the only edge of the representative row; \(P\) and \(Q\) keep one uncontracted leg each, \(u\) and \(v\), so the tie goes to \(P\). Line \(x\) passes around \(P\) and carries the parity string \(P_P\). On the way it also crosses \(u\), the uncontracted leg of \(P\); as \(u\) and \(x\) both end on B, that swap is applied there with swap_gate and never enters the table. In the table, column \(x\) is toggled in both rows, which are now empty, and the step can proceed.

The plan of the example starts with exactly these two jumps and the swap left on B:

('parity_sign', 2, 0, (1,))                  # row jump over A: string P_A on leg 1 of P (e_2)
('parity_sign', 0, 2, (0,))                  # column jump over P: string P_P on leg 0 of A (x)
('swap_gate', 3, 3, (0, 2))                  # swap (x, u) on B
('tensordot', 5, (0, 1), ((0, 1), (0, 1)))   # P.Q over e_1 and e_2

Unresolvable diagrams. A diagram one can draw, with a swap gate at every crossing, is always resolvable by jump moves alone, whatever the contraction order. Open legs are lines running out to infinity, so the crossings they make on the way belong in swap like any other. A set that leaves them out, or that is written down without a drawing behind it, can keep bad swaps that survive every jump; the planner warns whenever this happens and falls back on the parity gadget. Two rows on a cycle: parity gadget below is such a case.

Parity gadget

A parity gadget is the fallback for the rows that no jump can empty. The sign \((-1)^{p(e_k) \cdot p(L)}\) of such a bad swap depends on the parity of the contracted line, which the step sums over; the gadget carries that parity past the step. Each row outside the emptied class gets one, and the planner warns whenever it has to use them.

Splitting by parity. The identity on line \(e_k\) is the sum of the projectors \(\Pi_p\) onto its sectors of parity \(p\). On the sector \(p\) the swap gate \((e_k, L)\) reduces to the parity string \((-1)^{p \cdot p(L)}\) on \(L\): a gate on a line that survives the step, but a different one for each \(p\).

Left: a bad swap of a row outside the emptied class. Right: one term of the sum over the parity \(p\) of \(e_k\). The purple box restricts \(e_k\) to parity \(p\), the two lines cross without a swap gate, and the blue square is the parity string of charge \(p\) on \(L\).

Recording the parity. tensordot_psplit (trace_psplit for a trace) contracts each sector separately, restricting leg \(e_k\) of \(P\), and appends to each result \(R_p\) a pair of one-dimensional legs \((\mathrm{aux}, \mathrm{aux}')\) with signatures \(+1\) and \(-1\) and charge \(p\); the results are added, \(R = \sum_p R_p\). The pair carries no net charge, so \(R\) keeps the total charge of \(P\) and \(Q\), and on each block of \(R\) the leg \(\mathrm{aux}\) carries the parity of \(e_k\). A swap gate between \(\mathrm{aux}\) and \(L\) therefore gives the string \((-1)^{p \cdot p(L)}\) of each sector, and every remaining swap \((e_k, L)\) is replaced by \((\mathrm{aux}, L)\).

Removing the pair. \((\mathrm{aux}, L)\) is an ordinary swap gate: it waits until \(L\) and \(\mathrm{aux}\) are legs of one tensor and is applied there with swap_gate. As soon as no swap touches the pair, it is traced. On each block \(\mathrm{aux}\) and \(\mathrm{aux}'\) carry the same charge, so the trace adds the sectors back together, now each with its own sign; the final tensor has no gadget legs.

Left: the result \(R\) of the step with its gadget pair; the swap \((e_k, L)\) has become \((\mathrm{aux}, L)\). Right: once \(L\) is a leg of the same tensor \(R'\), the swap gate is applied there and the pair is traced, drawn as the closed purple line.

Later steps. Until it is traced, the pair is a self-loop of the tensor that carries it. If that tensor is \(P\) or \(Q\) of a later step, a swap between the pair and a contracted line has both lines on that tensor and is applied there. If it is a tensor of \(V\), the pair is an edge that no cut contains, so row jumps cannot change whether a row contains it, and a row that the column jumps do not free from it gets a gadget of its own.

In the plan. In ('tensordot_psplit', out, (P, Q), axes, paxes) the last entry lists the legs of \(P\) whose parity is recorded, one per gadget; their pairs are the last legs of out, in the same order. The cycle example below follows one gadget through its plan, from tensordot_psplit to the trace of the pair.

Several charge components and cost. With several fermionic charge components the recorded parity is a vector with one entry per fermionic component, and the split runs over all \(2^{n_f}\) of its values. The sectors are disjoint slices of \(P\), so the step adds contraction calls but no arithmetic. The parts are added with lazy_threshold=1, so \(R\) stores only the blocks some sector fills, as many as the contraction without the gadget; a plain sum would lay out every block its legs allow, including combinations of \((\mathrm{aux}, \mathrm{aux}')\) with the other legs that no sector produces (about four times as many elements for one U(1) fermionic charge in a small test). Later contractions keep this only when lazy_threshold is set in the configuration; with lazy off they lay out every allowed block again until the pair is traced. Which steps need a gadget depends on the contraction order.

Examples

In the three networks below tensors A, B, C, D have numbers 0, 1, 2, 3, the default order contracts A and B first, and the swap gate is bad in that step. The value of ncon equals the swap gate applied by hand after an outer product that puts both lines on one tensor. For the second example, with Z2 fermions:

import yastn

cfg = yastn.make_config(sym='Z2', fermionic=True)
leg = lambda: yastn.Leg(cfg, s=1, t=(0, 1), D=(1, 1))
l1, l2, l3, l4, l5 = (leg() for _ in range(5))
A = yastn.rand(cfg, n=1, legs=[l1, l2, l3])
B = yastn.rand(cfg, n=1, legs=[l1.conj(), l2.conj(), l4])
C = yastn.rand(cfg, n=1, legs=[l3.conj(), l5])
D = yastn.rand(cfg, n=1, legs=[l4.conj(), l5.conj()])

x = yastn.ncon([A, B, C, D], [(1, 2, 3), (1, 2, 4), (3, 5), (4, 5)], swap=[(1, 5)])

AC = yastn.tensordot(A, C, axes=((), ()))  # lines 1, 2, 3, 3, 5 on one tensor
AC = AC.swap_gate(axes=(0, 4))              # swap gate between lines 1 and 5
ref = yastn.ncon([AC, B, D], [(1, 2, 3, 3, 5), (1, 2, 4), (4, 5)])
assert abs(x.item() - ref.item()) < 1e-12

One row: column jump

A(1) B(1) C(2) D(2) with swap=[(1, 2)]. The only row, \(Y_1 = \{2\}\), is emptied by a column jump over A with partner line 2. A has no other legs, so line 2 slides past A and only the parity string of A remains on line 2.

('parity_sign', 0, 2, (0,))              # jump over A: string P_A on leg 0 of C (line 2)
('tensordot', 4, (0, 1), ((0,), (0,)))   # A.B over line 1
('tensordot', 5, (2, 3), ((0,), (0,)))   # C.D over line 2
('tensordot', 6, (4, 5), ((), ()))       # outer product of the two scalars

Two rows on a tree: row jump and column jump

A(1, 2, 3) B(1, 2, 4) C(3, 5) D(4, 5) with swap=[(1, 5)]. The first step contracts \(P =\) A and \(Q =\) B over lines 1 and 2. Lines 3 and 4 end on \(P\) and \(Q\), so \(V\) holds C and D, and \(E\) holds line 5 alone. The bad swap gives the rows \(Y_1 = \{5\}\) and \(Y_2 = \emptyset\). The figures below follow the steps of the planner; in each, the partner line of the jump is orange and the tensor jumped over is shaded.

The network: \(Y_1 = \{5\}\), \(Y_2 = \emptyset\).

Classes. \(Y_1 + Y_2 = \{5\} = \delta D\) is a cut of \(H\), so rows 1 and 2 form one class, represented by row 1.

Row jumps. Row 2 is brought onto the representative by a row jump over D with partner line 2; D is the set \(F\) given by the 2-colouring, as \(\delta D = \{5\}\). Line 2 now passes around D: it crosses both legs of D and carries the parity string \(P_D\). The new swap (2, 5) makes \(Y_2 = \{5\}\); the new swap (2, 4) has both lines on B and is applied there with swap_gate.

After the row jump over D: \(Y_1 = Y_2 = \{5\}\).

Column jumps. A and B keep one uncontracted leg each, so the column jump is over \(P =\) A, with partner line 5, the only edge of the representative row. Line 5 now crosses leg 3 of A instead of legs 1 and 2, and carries the parity string \(P_A\): the swaps (1, 5) and (2, 5) are removed, and the new swap (3, 5) has both lines on C and is applied there with swap_gate.

After the column jump over A: \(Y_1 = Y_2 = \emptyset\). Lines 1 and 2 no longer cross line 5 and are redrawn shorter.

The bad swap is thus replaced by ordinary swap gates on B and C and two parity strings,

\[\mathrm{swap}(1, 5) = \mathrm{swap}(2, 4)\, (-1)^{P_D \cdot p(2)}\; \mathrm{swap}(3, 5)\, (-1)^{P_A \cdot p(5)} .\]

('parity_sign', 3, 0, (1,))     # row jump over D: string P_D on leg 1 of A (line 2)
('swap_gate', 1, 1, (1, 2))     # swap (2, 4) on B
('parity_sign', 0, 2, (1,))     # column jump over A: string P_A on leg 1 of C (line 5)
('swap_gate', 2, 2, (0, 1))     # swap (3, 5) on C
('tensordot', 4, (0, 1), ((0, 1), (0, 1)))
('tensordot', 5, (2, 4), ((0,), (0,)))
('tensordot', 6, (3, 5), ((0, 1), (1, 0)))

Two rows on a cycle: parity gadget

Adding line 6 between C and D, A(1, 2, 3) B(1, 2, 4) C(3, 5, 6) D(4, 5, 6), puts line 5 on the cycle C-5-D-6. A jump over C or D toggles lines 5 and 6 together, so \(\{5\}\) is not a cut and the two rows fall into different classes. No drawing has this swap set: line 1 cannot reach B after crossing line 5 without also crossing line 6. Each class holds one row, so one row is emptied and the other pays for a gadget either way. Taking the class of row 2, the empty row, as the emptied class needs no jump at all:

1. row 2 is already empty; no jump is emitted;

2. row 1 gets a gadget: A.B is contracted separately for each parity of line 1, the parity is recorded on the gadget pair (aux, aux′) of the result AB, and (1, 5) becomes (aux, 5);

3. once C is merged with AB, (aux, 5) sits on one tensor and is applied; the gadget pair is traced after the last contraction.

('tensordot_psplit', 4, (0, 1), ((0, 1), (0, 1)), (0,))   # A.B split by the parity of line 1
('tensordot', 5, (2, 4), ((0,), (0,)))                    # C.AB, legs (5, 6, 4, aux, aux')
('swap_gate', 5, 5, (0, 3))                               # swap (5, aux)
('tensordot', 6, (3, 5), ((0, 1, 2), (2, 0, 1)))          # D.(C.AB) over lines 4, 5, 6
('trace', 6, 6, ((0,), (1,)))                             # trace the gadget pair

With order=(3, 4, 5, 6, 1, 2) the same network needs no gadget: lines 1 and 5 reach a common tensor before line 1 is contracted, and the swap is applied there.