Partial Select

For a number c of control qubits and some target qubits, a Select operator applies a (usually distinct) gate to the target qubits for each computational state of the control qubits. This means that the pattern accomodates for up to 2^c different gates to be applied.

Here, we present a simplification trick for cases where fewer than 2^c gates are required, and we have a guarantee about the state of the control qubits [1]. As we could just skip a control qubit altogether if we had 2^{c-1} or fewer gates to apply, we will assume the number of gates K to satisfy 2^{c-1}<K<2^c. We call such a Select operator with unused control states a partial Select operator.

As an example, consider the case c=3 and K=6 with 2 target qubits. A Select operator for this case takes the form

0: ─╭○──╭○──╭○──╭○──╭●──╭●──┤
1: ─├○──├○──├●──├●──├○──├○──┤
2: ─├○──├●──├○──├●──├○──├●──┤
3: ─├U0─├U1─├U2─├U3─├U4─├U5─┤
4: ─╰U0─╰U1─╰U2─╰U3─╰U4─╰U5─┤.

Some control logic properties

We will need the following properties and small tricks for control logic.

First, note that operators that are controlled on disjoint (sets of) basis states commute:

0: ─╭○──╭●──┤ = 0: ─╭●──╭○──┤
1: ─╰U──╰V──┤   1: ─╰V──╰U──┤.

This is equivalent to operators being controlled by the same qubits, but with control values that are not exactly the same. This commutation property allows us to rearrange them as is convenient for us in the following steps.

Second, there is a simplification rule for complementary control values on equal operators that is derived from the "lazy Select" rule (also used in LCU(QSVT)). In its simplest form, it reads:

0: ─╭○──╭●──┤ = 0: ───┤
1: ─╰U──╰U──┤   1: ─U─┤.

Third, and last, note that applying a controlled operator to a state that we know to have zero amplitude in the state(s) on which the controlled operator is applied yields no change. While this may sound trivial, it is worth mentioning prior to its application below.

Skip trailing off-controls

In virtually all cases where uniform control, i.e., the Select pattern, is employed, it is part of a larger circuit. Usually, a specific state is prepared on the control qubits before applying the Select pattern, and it is unprepared afterwards, c.f. PrepSelPrep,

0: ─╭|Ψ⟩─╭Select─╭|Ψ⟩†─┤
1: ─╰|Ψ⟩─├Select─╰|Ψ⟩†─┤
2: ──────╰Select───────┤.

Thus, if K<2^c, i.e., if the Select is a partial Select, the basis states of the control qubits |i\rangle with i\geq K (using zero-based indexing) will have zero amplitude.

By the third property from above, applying additional operators controlled on these unpopulated basis states will not have any effect on the overall computation. Thus, we may insert additional unitaries controlled by those states at will. For our example from above, we insert two operators, V_6 and V_7:

0: ─╭○──╭○──╭○──╭○──╭●──╭●─────╭●──╭●──┤
1: ─├○──├○──├●──├●──├○──├○─────├●──├●──┤
2: ─├○──├●──├○──├●──├○──├●─────├○──├●──┤
3: ─├U0─├U1─├U2─├U3─├U4─├U5────├V6─├V7─┤
4: ─╰U0─╰U1─╰U2─╰U3─╰U4─╰U5────╰V6─╰V7─┤.

We can exploit this freedom together with the commutation property to simplify the Select operator. For this, we pick V6=U4 and V7=U5, and position the equal operators next to each other:

0: ─╭○──╭○──╭○──╭○────╭●──╭●────╭●──╭●──┤
1: ─├○──├○──├●──├●────├○──├●────├○──├●──┤
2: ─├○──├●──├○──├●────├○──├○────├●──├●──┤
3: ─├U0─├U1─├U2─├U3───├U4─├U4───├U5─├U5─┤
4: ─╰U0─╰U1─╰U2─╰U3───╰U4─╰U4───╰U5─╰U5─┤.

Subsequently, we apply the merging rule for complementary controls, as presented above, to these pairs of operators, interpreting the additional control qubits with equal control values as part of the unitary U in the merge rule. This yields

0: ─╭○──╭○──╭○──╭○──╭●──╭●──┤
1: ─├○──├○──├●──├●──│───│───┤
2: ─├○──├●──├○──├●──├○──├●──┤
3: ─├U0─├U1─├U2─├U3─├U4─├U5─┤
4: ─╰U0─╰U1─╰U2─╰U3─╰U4─╰U5─┤.

Comparing this with the original control structure, we find that we can simply skip all controls nodes that are turned off, i.e., controlling on the |0\rangle state, for a "trailing streak". That is, the control to be skipped must be turned off for an entire sequence of operators that includes the last operator.

This rule continues to apply for multiple parallel streaks. For example, for K=5 we have the following simplification:

0: ─╭○──╭○──╭○──╭○──╭●──┤
1: ─├○──├○──├●──├●──├○──┤
2: ─├○──├●──├○──├●──├○──┤
3: ─├U0─├U1─├U2─├U3─├U4─┤
4: ─╰U0─╰U1─╰U2─╰U3─╰U4─┤
-->
0: ─╭○──╭○──╭○──╭○──╭●────╭●──╭●──╭●─┤
1: ─├○──├○──├●──├●──├○────├○──├●──├●─┤
2: ─├○──├●──├○──├●──├○────├●──├○──├●─┤
3: ─├U0─├U1─├U2─├U3─├U4───├U4─├U4─├U4┤
4: ─╰U0─╰U1─╰U2─╰U3─╰U4───╰U4─╰U4─╰U4┤
=
0: ─╭○──╭○──╭○──╭○──╭●──┤
1: ─├○──├○──├●──├●──│───┤
2: ─├○──├●──├○──├●──│───┤
3: ─├U0─├U1─├U2─├U3─├U4─┤
4: ─╰U0─╰U1─╰U2─╰U3─╰U4─┤.

Skip additional off-controls

Additional controls can be omitted due to the same rules as presented above. These are addressed in this separate section for two primary reasons: the simplification is less simple to phrase and compute, and the additional optimization turns out to be hindering other, more powerful techniques, like unary iteration [1].

In our example, assume that we already removed the trailing streaks of turned-off controls as above. We may add more operators controlled on the unpopulated states |110\rangle |111\rangle:

0: ─╭○──╭○──╭○──╭○──╭●──╭●─────╭●──╭●──┤
1: ─├○──├○──├●──├●──│───│──────├●──├●──┤
2: ─├○──├●──├○──├●──├○──├●─────├○──├●──┤
3: ─├U0─├U1─├U2─├U3─├U4─├U5────├U2─├U3─┤
4: ─╰U0─╰U1─╰U2─╰U3─╰U4─╰U5────╰U2─╰U3─┤
=
0: ─╭○──╭○────╭○──╭●────╭○──╭●────╭●──╭●──┤
1: ─├○──├○────├●──├●────├●──├●────│───│───┤
2: ─├○──├●────├○──├○────├●──├●────├○──├●──┤
3: ─├U0─├U1───├U2─├U2───├U3─├U3───├U4─├U5─┤
4: ─╰U0─╰U1───╰U2─╰U2───╰U3─╰U3───╰U4─╰U5─┤
=
0: ─╭○──╭○──────────╭●──╭●──┤
1: ─├○──├○──╭●──╭●──│───│───┤
2: ─├○──├●──├○──├●──├○──├●──┤
3: ─├U0─├U1─├U2─├U3─├U4─├U5─┤
4: ─╰U0─╰U1─╰U2─╰U3─╰U4─╰U5─┤.

We were able to remove two additional control nodes.

How can we determine which nodes we are allowed to remove? The crucial property is that the state on which the operator is controlled must differ from one of the zero-amplitude states by a single bit flip. The bit that needs to be flipped then marks the control that can be skipped. In the example above, the operators controlled on |010\rangle=|\overline{1}10\rangle and on |011\rangle=|\overline{1}11\rangle could be simplified, and for each, the control on the first qubit could be removed.

This rule can be applied iteratively to remove multiple controls on the same operator: The state on the remaining controls after the first simplification must differ from a combination of zero-amplitude states by a single bit flip. This occurs in the example below.

Final example

We show the example from Fig. 3 in [1], but skip the first control qubit because the figure shows ctrl(Select) with one additional control that is turned on for all operators. The original circuit without said control is

0: ─╭○──╭○──╭○──╭○──╭○──╭○──╭○──╭○──╭●──╭●──╭●───┤
1: ─├○──├○──├○──├○──├●──├●──├●──├●──├○──├○──├○───┤
2: ─├○──├○──├●──├●──├○──├○──├●──├●──├○──├○──├●───┤
3: ─├○──├●──├○──├●──├○──├●──├○──├●──├○──├●──├○───┤
4: ─╰U0─╰U1─╰U2─╰U3─╰U4─╰U5─╰U6─╰U7─╰U8─╰U9─╰U10─┤.

We first remove the trailing streaks of turned-off controls:

0: ─╭○──╭○──╭○──╭○──╭○──╭○──╭○──╭○──╭●──╭●──╭●───┤
1: ─├○──├○──├○──├○──├●──├●──├●──├●──│───│───│────┤
2: ─├○──├○──├●──├●──├○──├○──├●──├●──├○──├○──├●───┤
3: ─├○──├●──├○──├●──├○──├●──├○──├●──├○──├●──│────┤
4: ─╰U0─╰U1─╰U2─╰U3─╰U4─╰U5─╰U6─╰U7─╰U8─╰U9─╰U10─┤.

Next, we identify the control states with vanishing amplitude, i.e. the bitstrings for i\geq K. They are |1011\rangle (11), |1100\rangle (12), |1101\rangle (13), |1110\rangle (14), and |1111\rangle (15).

Controls appearing in the current circuit that differ by one bit flip from those are

• |0011\rangle = |\overline{1}011\rangle
• |0100\rangle = |\overline{1}100\rangle
• |0101\rangle = |\overline{1}101\rangle
• |0110\rangle = |\overline{1}110\rangle
• |0111\rangle = |\overline{1}111\rangle

Removing the corresponding control nodes (always on the first qubit) yields the circuit

0: ─╭○──╭○──╭○──────────────────────╭●──╭●──╭●───┤
1: ─├○──├○──├○──╭○──╭●──╭●──╭●──╭●──│───│───│────┤
2: ─├○──├○──├●──├●──├○──├○──├●──├●──├○──├○──├●───┤
3: ─├○──├●──├○──├●──├○──├●──├○──├●──├○──├●──│────┤
4: ─╰U0─╰U1─╰U2─╰U3─╰U4─╰U5─╰U6─╰U7─╰U8─╰U9─╰U10─┤.

Finally, there is an additional opportunity to remove control nodes from already reduced operators. For this, note that the zero-ampltiude states can be combined into the following three-qubit control states:

• |1011\rangle \& |1111\rangle\ \ \Rightarrow\ \ |1x11\rangle
• |1100\rangle \& |1101\rangle\ \ \Rightarrow\ \ |110x\rangle
• |1100\rangle \& |1110\rangle\ \ \Rightarrow\ \ |11x0\rangle
• |1101\rangle \& |1111\rangle\ \ \Rightarrow\ \ |11x1\rangle
• |1110\rangle \& |1111\rangle\ \ \Rightarrow\ \ |111x\rangle

The only set of three qubits that matches with any three-qubit-controlled operator is the first set, with operators U8 and U9. Indeed |1x01\rangle=|1x\overline{1}1\rangle, where ther former is the control state of U9, so that we may skip its second control:

0: ─╭○──╭○──╭○──────────────────────╭●──╭●──╭●───┤
1: ─├○──├○──├○──╭○──╭●──╭●──╭●──╭●──│───│───│────┤
2: ─├○──├○──├●──├●──├○──├○──├●──├●──├○──│───├●───┤
3: ─├○──├●──├○──├●──├○──├●──├○──├●──├○──├●──│────┤
4: ─╰U0─╰U1─╰U2─╰U3─╰U4─╰U5─╰U6─╰U7─╰U8─╰U9─╰U10─┤.

Iterating further, the following two-qubit state can be reached by combining zero-amplitude states:

• |110x\rangle \& |111x\rangle\ \ \Rightarrow\ \ |11xx\rangle
• |11x0\rangle \& |11x1\rangle\ \ \Rightarrow\ \ |11xx\rangle

No matches were found with the two-qubit-controlled operators (U9 and U10) , indicating that no further simplification is possible at that stage. Additionally, the absence of any singly-controlled operators leads us to conclude that no more nodes can be removed.