Partial Select

A frequently occurring control pattern in quantum algorithms is that of uniformly controlled rotations, called SelectPauliRot in PennyLane, or more generally of Select operators. They are commonly depicted as follows:

This pattern applies $K$ operators to the target qubit(s), controlled by $c$ control qubits. If the Select operator applies fewer target operators than the maximally supported number ($2^c$) and the state on the control qubits is guaranteed to have no overlap with the unused basis states, the control structure of Select can be simplified [1].

Inputs

• Select operator $U$ with $c$ controls and $K<2^c$ target operators.
• Control state without overlap on the states $|i\rangle$ for $i\geq K$.

Outputs

• Decomposition of $U$ with reduced number of control nodes.

Example

Consider a Select operator with $c=4$ control qubits, two target qubits, and $K=11<16=2^c$ target operators:

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

Applying the partial Select simplification allows us to remove the trailing turned-off control nodes on qubit $1$ and qubit $3$, as well as $2^c-K=5$ intermediate turned-off control nodes on qubit $0$ and a single intermediate control node on qubit $2$:

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

Typical usage

Typically, this transformation reduces the control structure of a Select operator, also called a multiplexer, or of a uniformly controlled rotation (qml.SelectPauliRot). This reduction interacts non-trivially with other compilation techniques for Select operators. For example, it may be combined with lazy Select simplifications. However, it is only to a limited extent compatible with, or beneficial for use with, the unary iterator technique presented in [1] or with generic Select-U(2) decompositions.

References

[1] "Encoding electronic spectra in quantum circuits with linear T complexity", Ryan Babbush et al. 1805.03662, Phys. Rev. X 8, 041015, (2018).