Gates on disjoint wires commute

Fix a computational basis vector $\mathrm{\mid }x⟩$. For an ordered wire tuple $w$, write $x_w$ for its ordered bit subtuple and $x^{w\leftarrow u}$ for the full bitstring obtained by replacing those positions by $u$. By [F1], the embedding of the first gate with matrix coefficients $U_{u,x_S}$ acts as $\mathrm{\mid }x⟩\mapsto {\sum }_u{U}_{u,x_S}\mathrm{\mid }{x}^{S\leftarrow u}⟩\mathrm{.}$ Applying the second gate on the disjoint tuple $T$ gives ${\sum }_{u,v}{U}_{u,x_S}{V}_{v,x_T}\mathrm{\mid }{x}^{S\leftarrow u,T\leftarrow v}⟩\mathrm{.}$ In the reverse order the result is the same sum with scalar factors $V_{v,x_T}{U}_{u,x_S}$, which agree because complex scalars commute; the replacement bitstrings are identical because $S\cap T=\mathrm{\varnothing }$. Thus both composites agree on this basis vector.

The computation in step 1.1 holds for every computational basis vector, which spans ${\mathcal{Q}}_n$. Therefore the two global linear maps agree on a basis and are equal, so the embedded gates commute.