1. Compilation/

  2. Select-U(2) Decomposition

Select-U(2) Decomposition

We recall the decompositions from the overview page,

0: ─╭◻──┤ = ──────────────────────╭●──────────────────────╭●─┤
1: ─├◻──┤   ──────────╭●──────────│───────────╭●──────────│──┤
2: ─├◻──┤   ────╭●────│─────╭●────│─────╭●────│─────╭●────│──┤
3: ─╰RZ─┤   ─RZ─╰X─RZ─╰X─RZ─╰X─RZ─╰X─RZ─╰X─RZ─╰X─RZ─╰X─RZ─╰X─┤

and

0: ─╭◻─┤ = ──────────────────────╭●──────────────────────────────╭RZ─┤
1: ─├◻─┤   ──────────╭●──────────│───────────╭●──────────────╭RZ─├◻──┤
2: ─├◻─┤   ────╭●────│─────╭●────│─────╭●────│─────╭●────╭RZ─├◻──├◻──┤
3: ─╰U─┤   ─U0─╰X─U2─╰X─U2─╰X─U3─╰X─U4─╰X─U5─╰X─U6─╰X─U7─╰◻──╰◻──╰◻──┤.

Herein, we will show how to arrive at these decompositions. First, we introduce a useful property of multiplexed circuits.

Multiplexer Extension Property (MEP)

A useful fact is the so-called Multiplexer Extension Property (MEP), which states that attaching multiplexer nodes to a circuit identity yields a valid circuit identity again. That is, given a circuit identity

0: ─A─┤ = ─B─┤,

for parametrized circuits, or circuit families, AA and BB, we may conclude that

0: ─╭◻─┤ = ─╭○───╭●──┤ = ─╭○───╭●──┤ = ─╭◻─┤
1: ─╰A─┤   ─╰A0──╰A1─┤   ─╰B0──╰B1─┤   ─╰B─┤,

where A0A_0 and A1A_1 are two instances of the parametrized circuit AA, and B0B_0 and B1B_1 are the equivalent instances of BB.

Applying multiple multiplexing nodes follows the same logic and results in valid circuit identities again.

For static gates, as opposed to parametrized gate families, the MEP actually is trivial: multiplexing a static gate VV does not do anything, because we apply the same gate for all multiplexing control states:

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

Correspondingly, any circuit identity V=WV=W carries over to multiplexed variants.

Decomposing multiplexed rotations

To decompose a multiplexed rotation (SelectPauliRot in PennyLane), we first look at a multiplexed RZR_Z rotation in detail, and then generalize to RXR_X and RYR_Y. These techniques are presented, among other references, in [1] and [2].

Multiplexed RZR_Z

We begin with the following circuit identity:

0: ─╭◻──┤ = ───────╭●───────╭●─┤
1: ─╰RZ─┤   ─RZ(α)─╰X─RZ(β)─╰X─┤.

It can be understood on the matrix level. The multiplexed rotation with angles θ0\theta_0 and θ1\theta_1 has the matrix

(e−i2θ00000ei2θ00000e−i2θ10000ei2θ1),\begin{pmatrix} e^{-\tfrac{i}{2}\theta_0} & 0 & 0 & 0\\ 0 & e^{\tfrac{i}{2}\theta_0} & 0 & 0\\ 0 & 0 & e^{-\tfrac{i}{2}\theta_1} & 0\\ 0 & 0 & 0 & e^{\tfrac{i}{2}\theta_1} \end{pmatrix},

whereas the four operators on the right hand side combine as

(1000010000010010)(e−i2β0000ei2β0000e−i2β0000ei2β)(1000010000010010)(e−i2α0000ei2α0000e−i2α0000ei2α)\begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 \end{pmatrix} \begin{pmatrix} e^{-\tfrac{i}{2}\beta} & 0 & 0 & 0\\ 0 & e^{\tfrac{i}{2}\beta} & 0 & 0\\ 0 & 0 & e^{-\tfrac{i}{2}\beta} & 0\\ 0 & 0 & 0 & e^{\tfrac{i}{2}\beta} \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 \end{pmatrix} \begin{pmatrix} e^{-\tfrac{i}{2}\alpha} & 0 & 0 & 0\\ 0 & e^{\tfrac{i}{2}\alpha} & 0 & 0\\ 0 & 0 & e^{-\tfrac{i}{2}\alpha} & 0\\ 0 & 0 & 0 & e^{\tfrac{i}{2}\alpha} \end{pmatrix}
=(e−i2(α+β)0000ei2(α+β)0000e−i2(α−β)0000ei2(α−β)).= \begin{pmatrix} e^{-\tfrac{i}{2}(\alpha+\beta)} & 0 & 0 & 0\\ 0 & e^{\tfrac{i}{2}(\alpha+\beta)} & 0 & 0\\ 0 & 0 & e^{-\tfrac{i}{2}(\alpha-\beta)} & 0\\ 0 & 0 & 0 & e^{\tfrac{i}{2}(\alpha-\beta)} \end{pmatrix}.

This means that the circuit identity is verified for α=12(θ0+θ1)\alpha = \tfrac{1}{2}(\theta_0+\theta_1) and β=12(θ0−θ1)\beta=\tfrac{1}{2}(\theta_0-\theta_1). The identity also holds with the reverse gate order, that is

0: ─╭◻──┤ = 0: ──────────────╭◻──┤ = 0: ────────╭◻────────┤ = ─╭●───────╭●───────┤
1: ─╰RZ─┤   1: ─RZ(-α)─RZ(α)─╰RZ─┤   1: ─RZ(-α)─╰RZ─RZ(α)─┤   ─╰X─RZ(β)─╰X─RZ(α)─┤,

with the same angles α,β\alpha, \beta. Here, we used that the multiplexed RZR_Z rotation and single-qubit RZR_Z rotations on the same qubit commute.

In the next step, we may apply the MEP to the two-qubit identity, which results in

0: ─╭◻──┤ = ─╭◻──╭◻─╭◻──╭◻─┤
1: ─├◻──┤   ─│───├●─│───├●─┤
2: ─╰RZ─┤   ─╰RZ─╰X─╰RZ─╰X─┤.

The multiplexed CNOT gate is typically not denoted like this, for the reason discussed in the section on the MEP previously; CNOT is a static gate and thus is unaffected by adding multiplexing nodes, consequently, we can skip these nodes:

0: ─╭◻──┤ = ─╭◻─────╭◻─────┤
1: ─├◻──┤   ─│───╭●─│───╭●─┤
2: ─╰RZ─┤   ─╰RZ─╰X─╰RZ─╰X─┤.

Then, we may apply the MEP for any number of multiplexing wires, and apply the identity that we just derived (or its reverse-ordered variant) iteratively. For example, we find the following decomposition for three multiplexing wires:

0: ─╭◻──┤ = ─────╭●─────╭●─┤
1: ─├◻──┤   ─╭◻──│──╭◻──│──┤
2: ─├◻──┤   ─├◻──│──├◻──│──┤
3: ─╰RZ─┤   ─╰RZ─╰X─╰RZ─╰X─┤
=
───────────────╭●───────────────╭●─┤
─────╭●─────╭●─│──╭●─────╭●─────│──┤
─╭◻──│──╭◻──│──│──│──╭◻──│──╭◻──│──┤
─╰RZ─╰X─╰RZ─╰X─╰X─╰X─╰RZ─╰X─╰RZ─╰X─┤
=
────────────────────────────────────────╭●────────────────────────────────────────╭●─┤
──────────────────╭●──────────────────╭●│─╭●──────────────────╭●──────────────────│──┤
───────╭●───────╭●│─╭●───────╭●───────│─│─│────────╭●───────╭●│─╭●───────╭●───────│──┤
─RZ(α)─╰X─RZ(β)─╰X╰X╰X─RZ(γ)─╰X─RZ(δ)─╰X╰X╰X─RZ(ε)─╰X─RZ(ζ)─╰X╰X╰X─RZ(η)─╰X─RZ(λ)─╰X─┤.

The alternating application of the original identity and its reverse-ordered variant causes CNOT gate cancellations, thereby resulting in the following decomposition for a multiplexed RZR_Z rotation:

0: ─╭◻──┤ = ──────────────────────────────────╭●──────────────────────────────────╭●─┤
1: ─├◻──┤   ────────────────╭●────────────────│─────────────────╭●────────────────│──┤
2: ─├◻──┤   ───────╭●───────│────────╭●───────│────────╭●───────│────────╭●───────│──┤
3: ─╰RZ─┤   ─RZ(α)─╰X─RZ(β)─╰X─RZ(γ)─╰X─RZ(δ)─╰X─RZ(ε)─╰X─RZ(ζ)─╰X─RZ(η)─╰X─RZ(λ)─╰X─┤.

More generally, we find 2c2^c single-qubit rotations and 2c2^c CNOT gates for cc multiplexing wires.

How do we obtain the rotation parameters α,β,…\alpha, \beta, \dots for multiple multiplexing wires? By iterating the relationship from the two-qubit case, we find

(αβγδϵζηλ)=18(111111111−11−11−11−11−1−111−1−1111−1−111−1−111−1−1−1−1111−1−11−111−11−11−1−11−111111−1−1−1−1)(θ0θ1θ2θ3θ4θ5θ6θ7).\begin{pmatrix} \alpha \\ \beta \\ \gamma \\ \delta \\ \epsilon \\ \zeta \\ \eta \\ \lambda \end{pmatrix} = \frac{1}{8} \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 \\ 1 & -1 & -1 & 1 & 1 & -1 & -1 & 1 \\ 1 & 1 & -1 & -1 & 1 & 1 & -1 & -1 \\ 1 & 1 & -1 & -1 & -1 & -1 & 1 & 1 \\ 1 & -1 & -1 & 1 & -1 & 1 & 1 & -1 \\ 1 & -1 & 1 & -1 & -1 & 1 & -1 & 1 \\ 1 & 1 & 1 & 1 & -1 & -1 & -1 & -1 \end{pmatrix} \begin{pmatrix} \theta_0 \\ \theta_1 \\ \theta_2 \\ \theta_3 \\ \theta_4 \\ \theta_5 \\ \theta_6 \\ \theta_7 \end{pmatrix}.

The matrix in this expression is a row-permuted version of the Walsh-Hadamard transformation matrix. Interestingly, the single-qubit gate angles α,β,…\alpha, \beta,\dots can be computed from the multiplexed angles θj\theta_j by interpreting θ⃗\vec{\theta} as a state vector, applying a layer of Hadamard gates to it (implementing the Walsh-Hadamard transform), and then applying a ladder of CNOT gates (implementing the permutation). That is, if we feed θ⃗\vec{\theta} as the initial state into the following circuit,

0: ──H─╭●───────┤
1: ──H─╰X─╭●────┤
2: ──H────╰X─╭●─┤
3: ──H───────╰X─┤,

the output state will be a vector encoding the gate angles.

Multiplexed RYR_Y

For RYR_Y rotations, the elementary two-qubit circuit identity from the previous section still holds:

0: ─╭◻──┤ = ───────╭●───────╭●─┤
1: ─╰RY─┤   ─RY(α)─╰X─RY(β)─╰X─┤.

We therefore find the same decomposition as for multiplexed RZR_Z rotations, simply replacing the rotation axis of all single-qubit operators:

0: ─╭◻──┤ = ──────────────────────────────────╭●──────────────────────────────────╭●─┤
1: ─├◻──┤   ────────────────╭●────────────────│─────────────────╭●────────────────│──┤
2: ─├◻──┤   ───────╭●───────│────────╭●───────│────────╭●───────│────────╭●───────│──┤
3: ─╰RY─┤   ─RY(α)─╰X─RY(β)─╰X─RY(γ)─╰X─RY(δ)─╰X─RY(ε)─╰X─RY(ζ)─╰X─RY(η)─╰X─RY(λ)─╰X─┤.

Multiplexed RXR_X

For RXR_X rotations, we can't use the same elementary circuit identity as for RYR_Y and RZR_Z, because the CNOT gates commute with RXR_X rotations on the target qubit. However, we may apply a basis change to the identity for RZR_Z, by applyig a Hadamard gate to the target qubit on both sides.

0: ───╭◻────┤ = ─────────╭●───────╭●───┤ = ───────╭●───────╭●─┤
1: ─H─╰RZ─H─┤   ─H─RZ(α)─╰X─RZ(β)─╰X─H─┤   ─RX(α)─╰●─RX(β)─╰●─┤.

Using this new identity yields a decomposition for multiplexed RXR_X rotations:

0: ─╭◻──┤ = ──────────────────────────────────╭●──────────────────────────────────╭●─┤
1: ─├◻──┤   ────────────────╭●────────────────│─────────────────╭●────────────────│──┤
2: ─├◻──┤   ───────╭●───────│────────╭●───────│────────╭●───────│────────╭●───────│──┤
3: ─╰RX─┤   ─RX(α)─╰●─RX(β)─╰●─RX(γ)─╰●─RX(δ)─╰●─RX(ε)─╰●─RX(ζ)─╰●─RX(η)─╰●─RX(λ)─╰●─┤.

With this, we know how to decompose any uniformly controlled single-qubit Pauli rotation, SelectPauliRot.

Decomposing multiplexed U(2) operators

Here we discuss how to decompose multiplexed single-qubit, or Select-U(2), operators, following Möttönen et al. [3].

The first step is to obtain a special decomposition for a Select-U(2) operator with a single multiplexing wire, namely:

0: ─╭◻─┤ = ────╭●────╭RZ─┤
1: ─╰U─┤   ─U0─╰X─U1─╰◻──┤,

where U0U_0 and U1U_1 are SU(2)SU(2) gates (c.f. Fig. 4 in [3]). Note that by decomposing U1U_1 into RXRZRXR_XR_ZR_X (via one-qubit synthesis), one degree of freedom can be absorbed into U0U_0. This leaves us with three parameters for U0U_0, and two parameters for the (reduced) U1U_1 and multiplexed RZR_Z rotation each, which matches the 7 degrees of freedom of a Select-U(2) operator (ignoring a global phase).

Where does the two-qubit decomposition above come from? The details can be found in Sec. III in [3]. Roughly, the derivation goes as follows: note that the Select-U(2) operator has a block-diagonal matrix with two U(2)U(2) matrices AA and BB on the diagonal. The decomposition above then arises from an eigenvalue decomposition of the matrix AB†AB^\dagger, combined with some basis rotations. This technique is closely related to the numerical implementation of (type-A) Cartan decompositions and usually is part of demultiplexing [1]. Below, it will be useful that the derivation first produces a specific diagonal gate D=exp⁡(iπ4Z⊗Z)D=\exp(i\tfrac{\pi}{4}Z\otimes Z) in place of the CNOT gate. The CNOT is then produced from DD with single-qubit rotations.

And this already concludes the hard part! We may apply the MEP to the two-qubit multiplexer decomposition above to find

0:       ───╭◻─┤ = ──────╭●─────╭RZ─┤
1...k-1: ─/─├◻─┤   ─/╭◻──│──╭◻──├◻──┤                   (1)
k:       ───╰U─┤   ──╰U0─╰X─╰U1─╰◻──┤,

also see Fig. 5 in [3]. Here, we used again the fact that the static CNOT remains unchanged under multiplexing.

Note that if we want to use the identity (1) recursively, we find

0:       ───╭◻─┤ = ────────────────────╭●──────────────────╭RZ─┤
1:       ───├◻─┤   ────────╭●──────╭RZ─│───────╭●──────╭RZ─├◻──┤
2...k-1: ─/─├◻─┤   ─/─╭◻───│──╭◻───├◻──│──╭◻───│──╭◻───├◻──├◻──┤
k:       ───╰U─┤   ───╰U00─╰X─╰U01─╰◻──╰X─╰U10─╰X─╰U11─╰◻──╰◻──┤,

which has two multiplexed RZR_Z rotations with k−1k-1 control qubits, instead of the one that is present in the final decomposition.

This can be resolved by rotating the CNOT gate controlled on qubit 00 into a CZ gate before applying the decomposition at the next level. Then, after decomposing the multiplexed U0U_0, the created multiplexed RZR_Z rotation can be merged into the multiplexed U1U_1 gate before decomposing this one as well. In summary:

0:       ───╭◻─┤
1:       ───├◻─┤
2...k-1: ─/─├◻─┤
k:       ───╰U─┤
= (apply (1) to multiplexed U)
──────╭●─────╭RZ─┤
──╭◻──│──╭◻──├◻──┤
─/├◻──│──├◻──├◻──┤
──╰U0─╰X─╰U1─╰◻──┤
= (rotate CNOT to CZ and absorb Hadamards)
──────╭●─────╭RZ─┤
──╭◻──│──╭◻──├◻──┤
─/├◻──│──├◻──├◻──┤
──╰V0─╰●─╰V1─╰◻──┤
= (apply (1) to multiplexed V0)
────────────────────╭●──────╭RZ─┤
────────╭●──────╭RZ─│──╭◻───├◻──┤
─/─╭◻───│──╭◻───├◻──│──├◻───├◻──┤
───╰V00─╰X─╰V01─╰◻──╰●─╰V1──╰◻──┤
= (commute multiplexed RZ to the right and rotate CZ back into CNOT)
──────────────────╭●────────────╭RZ─┤
────────╭●────────│────╭RZ─╭◻───├◻──┤
─/─╭◻───│──╭◻─────│────├◻──├◻───├◻──┤
───╰V00─╰X─╰V01─H─╰X─H─╰◻──╰V1──╰◻──┤
= (absorb Hs; merge H, multiplexed RZ and V1; and apply (1) to merge result)
────────────────╭●──────────────────╭RZ─┤
────────╭●──────│───────╭●──────╭RZ─├◻──┤
─/─╭◻───│──╭◻───│──╭◻───│──╭◻───├◻──├◻──┤
───╰V00─╰X─╰W01─╰X─╰W10─╰X─╰W11─╰◻──╰◻──┤,

where Vi=HUiV_i=H U_i and W01=HV01W_{01} = H V_{01}. The right half results from merging a Hadamard, the (k−1)(k-1)-multiplexed RZR_Z rotation as well as the multiplexe V1V_1 operator, and applying the circuit identity (1) to it.

As for the two-qubit multiplexer, the single-qubit unitaries can be reduced by applying XZXXZX decompositions and fusing RXR_X rotations between neighbouring unitaries. This reduces the parameter count to 2⋅2k+1+1+2k+1−2=4⋅2k−12\cdot 2^{k+1}+1+2^{k+1}-2=4\cdot 2^k-1, which is the number of degrees of freedom in the multiplexer, again ignoring a potential global phase.