Lazy Select

A frequently occurring control pattern in quantum algorithms, for example in uniformly controlled rotations or Select operators, is complementary control nodes. These define specific operators to be applied to different subspaces of Hilbert space, and the complementary control structure implies that a particular operation is applied to each subspace. In the following, we will explain a simplification for such complementary controls, first for a single control qubit and two gates and then, by applying the trick recursively, for any number $c$ of control qubits and $2^c$ gates.

The base case: single control qubit

Consider a two-qubit quantum circuit consisting of two controlled gates, with complementary control values between the two:

0: ─╭○──╭●──┤
1: ─╰A──╰B──┤.

In this pattern, the first gate applies an operation A on qubit $1$, but only to the subspace of Hilbert space in which qubit $0$ is in the state $|0\rangle$, and the second gate applies B to qubit $1$, but only to the subspace where qubit $0$ is in the state $|1\rangle$. The complementary controls decomposition then results from the simple observation that we might as well apply A on qubit $1$ for either state of qubit $0$, and undo it by applying its adjoint together with B on the $|1\rangle$ subspace:

0: ────╭●─────┤
1: ──A─╰(BA†)─┤.

Note that this decomposition is only feasible if the inverse of A can be implemented. Above, we assumed unitarity, such that the adjoint exactly implements the inverse. Also note that this decomposition is useful if the operations applied to the different subspaces have similar structure and the product BA† is easy enough to compute.

One may ask why we are left with a $|1\rangle$ control and not a $|0\rangle$ control. Of course we could have decided otherwise and removed the $|1\rangle$ control instead:

0: ─╭○───────┤
1: ─╰(B†A)─B─┤.

To condense the decomposition into a neat simplification rule, we state

If two gates $A,B$ are controlled complementarily by a single control qubit, the control of $A$ ($B$) can be removed if the other gate is replaced by $BA^\dagger$ ($B^\dagger A)$.

Matrix perspective

At the matrix level, two complementary controls applying the operators $A$ and $B$ take the form of a block matrix, up to reordering of qubits. For the example circuit above, the matrix reads

where $A$ and $B$ are the $(2\times 2)$-shaped matrices for the single qubit gates A and B, respectively. We may easily rewrite this as the product

which are the matrices for $A$ applied to qubit $1$ without control and for applying $B A^\dagger$ to qubit $1$, controlled on qubit $0$ being in state $|1\rangle$. Note that we read the matrix product from right to left, consistent with the order in which operations are applied in the circuit.

To trace back the other choice of simplification, we may write

Recurse: From one to two control qubits

To derive a more general decomposition of complementary controls, we will now recurse on the number of control qubits $c$. We start with a concrete example for the recursion: adding one control qubit to move from the base case $c=1$ above to the case $c=2$. A circuit with this structure may look like this:

0: ─╭○──╭○──╭●──╭●──┤
1: ─├○──├●──├○──├●──┤
2: ─╰A──╰B──╰C──╰D──┤.

First, we apply the base case to the first two and last two gates. This simplification trick holds if one (or multiple) more control is present, as long as it controls the gates to be simplified with the same control values:

0: ─╭○──╭○─────╭●──╭●─────┤
1: ─│───├●─────│───├●─────┤
2: ─╰A──╰(BA†)─╰C──╰(DC†)─┤.

Next, we may apply the base case again, this time to qubit $0$ as control qubit, and interpreting the blocks that we just obtained from the two-gate groups as new $A$ and $B$. For this, we need to multiply the adjoint of the first block from the right to the second block, or apply it before the second block.

0: ────────────╭●─────╭●────╭●──╭●─────┤
1: ─────╭●─────├●─────│─────│───├●─────┤
2: ──A──╰(BA†)─╰(AB†)─╰(A†)─╰C──╰(DC†)─┤.

At this stage we can read off the effect of the four gates still being controlled by qubit $0$: if qubit $1$ is in state $|0\rangle$, we apply $C A^\dagger$. If it is in state $|1\rangle$, we apply $DC^\dagger C A^\dagger A B^\dagger=D B^\dagger$. This insight allows us to rewrite the circuit one last time:

0: ────────────╭●─────╭●────────┤
1: ─────╭●─────│──────├●────────┤
2: ──A──╰(BA†)─╰(CA†)─╰(DB†AC†)─┤.

Recurse: $c$ control qubits

The generalization to arbitrary numbers $c$ of control qubits consists of two parts: the control structure of the resulting circuit, and the applied operators for each controlled gate.

The former is rather simple to understand, as it corresponds to the original control structure with "empty" controls (i.e., those on the state $|0\rangle$) removed. The resulting pattern is that the first half of all gates is not controlled on the first qubit while the second half is, the first and third quarter is not controlled on the second qubit while the second and fourth quarters are, and so on. Using zero-based indexing for the fractions of gates, we write the index $i$ of a gate as bit string. Then the gate will be controlled by the $k$th control qubit if the $k$th bit in the string is set.

Regarding the operators to be applied, gate $i$ is sequentially right-multiplied by the adjoints of all preceding (already modified) operators, if they are controlled by a subset of the controls of gate $i$. For $c=2$, we can confirm this explicitly: $B$ was right multiplied by $A^\dagger$, the only operator applied before it. $C$ was right multiplied by $A^\dagger$ as well, but not by $(BA^\dagger)^\dagger$ because the latter was controlled by qubit $1$, which is not part of the controls of $C$. Finally, $D$ was right multiplied by $A^\dagger$, then by $(BA^\dagger)^\dagger$, and then by $(CA^\dagger)^\dagger$, because all previous gates were controlled by subsets of the controls of D, qubits $0$ and $1$.

These operators, like the control structure, naturally can be reused for higher-level recursions, so the first four operators for $c=3$ are those given above for $c=2$.