Patch controlled multi-SWAP optimisation

[TysonRayJones]

Issue #595 describes the utility of the multi-SWAP operation, whereby a sequence of SWAP gates are performed to change the target qubits of a many-target gate. Here, we'll consider what happens to the control qubits.

Consider the below three subcircuits.

It is clear that the left and middle circuits are equivalent. QuEST sometimes uses this equivalence, like here, to simulate the left operation using the middle circuit, working around distribution constraints.

In the middle circuit, the SWAP operations are uncontrolled. This is wasteful! As described in Sec. IV B , the presence of control qubits accelerates the simulation of an operator and reduces communication costs. This is exploited by individual controlled SWAP gates here, which invoke subroutine exchangeAmpsToBuffersWhereQubitsAreInStates() to avoid communicating or processing any amplitude which is unchanged due to the control qubits.

In the image above, the right circuit introduces control qubits to the SWAP gates, and so is more efficient, yet should remain equivalent to the left two circuits. This is because of the distributive property of control qubits; $$\text{ctrl}[\hat{A} \cdot \hat{B}] = \text{ctrl}{[\hat{A}]} \cdot \text{ctrl}[\hat{B}]$$. The green-highlighted ($G$) control qubits are "meta" to the entire operation, unlike the red/orange ($R$) controls, allowing us to express

$$ {\text{ctrl}}_{G \cup R} [\hat{U}] = {\text{ctrl}}_G [{\text{ctrl}}_R [\hat{U}]] = {\text{ctrl}}_G [ \hat{V} ] $$

where $\hat{V}$ is any recompilation of $\text{ctrl}_R [\hat{U}]$. This includes its replacement with SWAPs to the lowest qubits and back. Then ${\text{ctrl}}_G [ \hat{V} ]$ is effected by adding control qubits $G$ to every operation within $\hat{V}$.

The QuEST source code (here) attempts to exploit the equivalence between the left and right circuits, by applying the green, "unmoved" control qubits upon all the swaps, accelerating them. Alas, the approach is bugged! Inclusion of the "unmoved" controls upon the SWAP gates caused the unit tests to fail, and so the source code currently disables this optimisation.

This should be investigated. Is the approach flawed (very possible I am brainfarting), or is there a bug in the constituent functions only exposed by attempting to use this optimisation?