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 iteration 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. arXiv:1805.03662, Phys. Rev. X 8, 041015, 2018.