Lazy Select

A frequently occurring control pattern in quantum algorithms involves complementary control nodes. Very prominently, they make up Select operators, or uniformly controlled rotations (see qml.SelectPauliRot), which inspired the name "lazy select" for this simplification. These operators are commonly depicted as:

Complementary controls define different operators to be applied on different subspaces of Hilbert space, and some operation is applied to every subspace.

The elementary case is that of a single control qubit and two unitary operators that are controlled on the |0\rangle and |1\rangle state of the control qubit, respectively. The lazy select identity then is particularly simple:

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

Note how the matrix A^\dagger appears on the right in the matrix product to cancel a gate on the left. This is due to the different ordering conventions between circuit diagrams and matrix multiplications.

Inputs

• Select operator U with target operators \{U_i\}.

Outputs

• Decomposition of U into multi-controlled gates with fewer controls and new target operators \{V_i\}.

Intuition

The elementary case from above can be understood, for example, on the level of classical logic. Essentially, we are rewriting the instruction

if control_qubit==0:
    A()
else:
    B()

as the equivalent

A()
if control_qubit==1:
    undo_A()
    B()

This classical logic may be transferred to superposition states because we are dealing with linear operators. Alternatively, we may consider the equivalence on the matrix level; for further details, see the details tab.

Example

Consider the Select circuit

0: ─╭○──╭○──╭●──╭●──┤
1: ─├○──├●──├○──├●──┤
2: ─╰X──╰Y──╰Z──╰H──┤.

Applying the lazy Select simplification, we obtain the equivalent circuit

0: ─────────────╭●─────╭●─────┤  =  0: ──╭●──S──────╭●──╭●──┤
1: ─────╭●──────│──────├●─────┤     1: ──╰S†─S†─╭●──│───├●──┤
2: ──X──╰(-iZ)──╰(iY)──╰(-iH)─┤     2: ───X─────╰Z──╰Y──╰H──┤,

where we computed the new target operators according to the rule in the details tab:

Then we applied some simplifications using rules for controlled phases and complementary control nodes that allow us to extract the prefactors \pm i from the controlled gates.

Typical usage

Typically, the control structure of a Select operator (also known as a multiplexer) or of a uniformly controlled rotation is reduced to contain fewer control nodes. This reduction interacts non-trivially with other compilation techniques for Select operators. For example, it may be combined with partial Select simplifications, but it is neither compatible nor beneficial for use with the unary iterator technique presented in Babbush et al. (2018).

References

[1] "Synthesis of quantum-logic circuits", Vivek V. Shende, Stephen S. Bullock, Igor L. Markov, quant-ph/0406176, 2004.