- 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
whereas the four operators on the right hand side combine as
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
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.