Select-U(2) Decomposition

David Wierichs

Compilation/
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, $A$ and $B$ , we may conclude that

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

where $A_0$ and $A_1$ are two instances of the parametrized circuit $A$ , and $B_0$ and $B_1$ are the equivalent instances of $B$ .

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 $V$ 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=W$ carries over to multiplexed variants.

Decomposing multiplexed rotations

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

Multiplexed $R_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 $\theta_0$ and $\theta_1$ has the matrix

\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

\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}

= \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 $\alpha = \tfrac{1}{2}(\theta_0+\theta_1)$ and $\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 $R_Z$ rotation and single-qubit $R_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 $R_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 $2^c$ single-qubit rotations and $2^c$ CNOT gates for $c$ 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

\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 $\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 $R_Y$

For $R_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 $R_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 $R_X$

For $R_X$ rotations, we can't use the same elementary circuit identity as for $R_Y$ and $R_Z$ , because the CNOT gates commute with $R_X$ rotations on the target qubit. However, we may apply a basis change to the identity for $R_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 $R_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 $U_0$ and $U_1$ are $SU(2)$ gates (c.f. Fig. 4 in [3]). Note that by decomposing $U_1$ into $R_XR_ZR_X$ (via one-qubit synthesis), one degree of freedom can be absorbed into $U_0$ . This leaves us with three parameters for $U_0$ , and two parameters for the (reduced) $U_1$ and multiplexed $R_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)$ matrices $A$ and $B$ on the diagonal. The decomposition above then arises from an eigenvalue decomposition of the matrix $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\tfrac{\pi}{4}Z\otimes Z)$ in place of the CNOT gate. The CNOT is then produced from $D$ 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 $R_Z$ rotations with $k-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 $0$ into a CZ gate before applying the decomposition at the next level. Then, after decomposing the multiplexed $U_0$ , the created multiplexed $R_Z$ rotation can be merged into the multiplexed $U_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 $V_i=H U_i$ and $W_{01} = H V_{01}$ . The right half results from merging a Hadamard, the $(k-1)$ -multiplexed $R_Z$ rotation as well as the multiplexe $V_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 $XZX$ decompositions and fusing $R_X$ rotations between neighbouring unitaries. This reduces the parameter count to $2\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.

About

Software & Documentation

Resources

Topics

Community & Support

Select-U(2) Decomposition

Multiplexer Extension Property (MEP)

Decomposing multiplexed rotations

Multiplexed $R_Z$

Multiplexed $R_Y$

Multiplexed $R_X$

Decomposing multiplexed U(2) operators

Select-U(2) Decomposition

Multiplexer Extension Property (MEP)

Decomposing multiplexed rotations

Multiplexed R_Z

Multiplexed R_Y

Multiplexed R_X

Decomposing multiplexed U(2) operators

Multiplexed $R_Z$

Multiplexed $R_Y$

Multiplexed $R_X$