Unary Iteration

A frequently occurring control pattern in quantum algorithms is that of Select operators.

While they can be implemented as a sequence of multi-controlled operations like displayed above, this comes at notable cost. It requires each multi-controlled operation to recompute the combined logic of all the control qubits, even though this logic only varies slowly along the sequence.

To remedy this cost overhead, Babbush et al. (2018) [1] introduced unary iteration. This technique caches control values combined through AND, or Toffoli, gates between operations, and additionally reduces their cost by leveraging qml.TemporaryAND gates, also known as qml.Elbow gates. This decomposition significantly reduces the cost of Select in terms of T or Toffoli gates, but it requires additional c-1 clean auxiliary qubits for a Select operator with c control qubits.

Inputs

• Select operator U with c controls and K target operators \{U_i\}.
• c-1 clean auxiliary qubits (in zeroed state |0\rangle).

Outputs

• Decomposition of U into single-controlled versions of the \{U_i\}, about 4K T gates, and \mathcal{O}(K) Clifford gates. The auxiliary wires are returned in the zeroed state.

Example

Consider the following Select operator with c=3 controls and K=7 target operators.

import pennylane as qml
from pennylane import X, Y, Z
ops = [qml.SWAP([3, 4]), Y(3), Z(4), X(3) @ Z(4), X(3), Y(4), Z(3) @ X(4)]
op = qml.Select(ops, control=[0, 1, 2])

Its generic multi-control decomposition is given by

>>> print(qml.draw(op.decomposition)())
0: ─╭○────╭○─╭○─╭○───╭●─╭●─╭●───┤
1: ─├○────├○─├●─├●───├○─├○─├●───┤
2: ─├○────├●─├○─├●───├○─├●─├○───┤
3: ─├SWAP─╰Y─│──├X@Z─╰X─│──├Z@X─┤
4: ─╰SWAP────╰Z─╰X@Z────╰Y─╰Z@X─┤.

Unary iteration replaces the above multi-control structure by the following decomposition, using c-1=2 auxiliary qubits ["aux0", "aux1"]:

>>> unary_iterator = qml.list_decomps(qml.Select)[1]
>>> kwargs = {"work_wires": ["aux0", "aux1"], "partial": False}
>>> print(qml.draw(unary_iterator)(ops=ops, control=[0, 1, 2], **kwargs))
   0: ─╭○──X─────────────────╭●──X────────────────╭●────────────────────╭●──────────────●╮─┤
   1: ─├○────────────────────│────────────────────│──╭●─────────────────│───────────────●┤─┤
aux0: ─╰──╭●───────╭●─────●╮─╰X─╭●────╭●───────●╮─╰X─╰X─╭●────╭●─────●╮─╰X─╭●───────●╮───╯─┤
   2: ────├○───────│──────●┤────├○────│────────●┤───────├○────│──────●┤────├○───────○┤─────┤
aux1: ────╰──╭●────╰X─╭●───╯────╰──╭●─╰X─╭●─────╯───────╰──╭●─╰X─╭●───╯────╰──╭●─────╯─────┤
   3: ───────├SWAP────╰Y───────────│─────├X@Z──────────────╰X────│────────────├Z@X─────────┤
   4: ───────╰SWAP─────────────────╰Z────╰X@Z────────────────────╰Y───────────╰Z@X─────────┤.

Here, the left elbow (qml.TemporaryAND) and right elbow (its adjoint) are drawn as

─╭●─       ─●╮─
─├●─  and  ─●┤─
─╰──       ──╯─,

respectively, with control nodes indicating control on |0\rangle (○) or |1\rangle (●) as usual. Observe how all target operators occur only with a single control, even reducing many of them to Clifford operators. The elbow gates can be decomposed further, either into a Toffoli gate, or directly into a cheaper-than-default decomposition thereof, by leveraging the known input state |0\rangle on the auxiliary qubits.

Typical usage

Unary iteration significantly reduces the control structure of a Select operator (also known as a multiplexer) at the expense of auxiliary qubits. Correspondingly, this technique is frequently used when a little extra space is considered cheaper than a significant amount of additional gates. In [1], unary iteration is already combined with the partial Select simplification, but it can be used without it as well. It is not compatible nor beneficial to use together with the lazy Select simplification.

Unary iteration is particularly useful if the target operators of the Select pattern are Clifford operators, producing Toffoli, CS or CH gates at worst.

If the K target operators are restricted even further to the Pauli group, unary iteration only requires Clifford operators and \mathcal{O}(K) qml.TemporaryAND, or elbow, gates.

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.