Two-qubit Synthesis

Determine the required number of CNOT

A full recipe for determining the number of necessary CNOT gates in a two-qubit gate decomposition is presented in [2]. The results are summarized in the following table. The column "condition" refers to the mathematical condition for the case, whereas "check" refers to what is checked in practice.

Here $\chi[U](x) = \det\left(x \mathbb{I} - U \right)$ in the table is the characteristic polynomial with scalar variable $x$. The polynomial's roots $\lambda_i$ (as defined by $\chi[U](\lambda_i) = 0$) are the eigenvalues of $U$. $\gamma(U) = U (Y\otimes Y) U^T (Y\otimes Y)$ is a simpler Makhlin invariant introduced by the authors in [1] and [2].

This invariant has the special property that $\gamma(U) = \gamma(V)$ if and only if $U$ and $V$ are equivalent up to local $\text{SU}(2)$ unitaries from the right (see Proposition IV.3 in [1]). This means that

where $G = \text{SU}(2) \otimes \text{SU}(2)$ and the multiplication of a matrix with a group is defined as $U G = \{ U g | g \in G \}$. For example, for the two-qubit case, there exist matrices $u_0 \otimes u_1$ and $v_0 \otimes v_1$ such that $U (u_0 \otimes u_1) = V (v_0 \otimes v_1)$.

Another property of this invariant is that $\chi[\gamma(U)] = \chi[\gamma(V)]$ if and only if $U$ and $V$ are equivalent up to local $\text{SU}(2)$ unitaries from the left and right, i.e.,

In the algorithm to synthesize the optimal two-qubit unitary we are going to compute $E^\dagger \gamma(U) E = (E^\dagger U E) (E^\dagger U E)^T,$ an equivalent invariant to $\gamma(U)$ (also shown in Proposition IV.3 in [1]). $E$ is a so-called magic basis that transforms $A \in \text{SO}(4)$ such that $E A E^{\dagger} \in \text{SU}(2) \otimes \text{SU}(2)$. In qml.ops.two_qubit_decomposition, we define it as

Note that $E$ above has the nice property that $E E^T = - Y \otimes Y,$ which reinforces the connection to the Makhlin invariant defined earlier.

To save some computation, we can perform the checks in the table above with $E^\dagger \gamma(U) E = (E^\dagger U E) (E^\dagger U E)^T$ instead of $\gamma(U)$ due to their equivalence.

Optimal formulae

0 CNOTs

In this case we have $U = A \otimes B$ with both $A, B \in \text{SU}(2)$ and we find the following simple circuit structure.

-A-
-B-

We can compute the coefficients of the matrices $A$ and $B$ analytically by the following formula. First, we write

in terms of its four $2 \times 2$ $C_i$ block matrices. We further define

that fulfills $|a_1|^2 + |a_2|^2 = 1$. Using the Kronecker product definition,

we can identify $C_1 C_4^\dagger = a_1^2$ and $-C_2 C_3^\dagger = a_2$, which yield $a_1$ and $a_2$ up to a sign that can be further resolved using $C_1 C_2^\dagger = a_1 a_2^*$. Now that we have $A$, we can compute $B$ using $B = C_1 / a_1$ or $B = C_2/a_2$, depending on whether $a_1$ or $a_2$ are non-zero.

To obtain the final circuit decomposition, we use qml.ops.one_qubit_decomposition on $A$ and $B$.

1 CNOT

A general circuit ansatz requiring one CNOT is given by the following.

-C--╭●--A-
-D--╰X--B-

In other words, we need to find $A, B, C, D$ such that $U = (A \otimes B) \text{CNOT}_{0 1} (C \otimes D)$. The following subroutine will be reused for the cases of 1 and 2 CNOTs below, but exchanging the singular CNOT operator for other ansätze. Let us first consider a more general case of finding $U$ such that $U = (A \otimes B) V (C \otimes D)$ for some known unitary matrix $V$. This can be mapped back to the original problem by considering $V$ to be a single CNOT gate.

The equation $U = (A \otimes B) V (C \otimes D)$ is fulfilled if and only if $\chi[\gamma(U)] \equiv \chi[\gamma(V)]$. This invariant equation is equivalently satisfied when we substitute $\gamma(U) \rightarrow E^\dagger U E =: u$ and $\gamma(V) \rightarrow E^\dagger V E =: v.$ Note that $E^\dagger \gamma(U) E = u u^T$ so we have $\chi[u u^T] \equiv \chi[v v^T]$. Given that their characteristic polynomials are equivalent, their eigenvalues must also be the same. Further, $u u^T$ and $v v^T$ can be diagonalized with orthogonal eigenvectors; i.e., $u u^T = a^T D_\lambda a$ and $v v^T = b^T D_\lambda b$. Here, $a$ and $b$ are orthogonal, i.e. $a, b \in \text{SO}(4)$, whereas $u$ and $v$ are unitary. Assuming the eigenvalues in the diagonal matrix $D_\lambda$ are ordered in the same way (which can always be achieved by commuting rows and columns), we obtain,

In the 1 CNOT case, $V = \text{CNOT},$ so the latter diagonalization can be hard-coded.

Solving this equation for $u$ and using the fact that $(v^\dagger b^T a u) (v^\dagger b^T a u)^T = 1 \Leftrightarrow v^T b^T a u^* = v^\dagger b^T a u$ then leads to

where we can identify the desired results

We then use the same process as for the 0 CNOT case above to obtain $A, B, C, D$.

2 CNOT

A general circuit ansatz requiring two CNOTs is given by the following.

-A--╭X--RZ(d)--╭X--C-
-B--╰●--RX(p)--╰●--D-

The procedure for determining $A, B, C, D$ will be similar to the previous case, but now with $V = \text{CNOT}_{10} (a \otimes b) \text{CNOT}_{10}$ instead of a single CNOT gate. Since $X$ commutes with the target of a CNOT gate, and $Z$ with the control, we can cleverly choose a parameterization $a = R_X(\cdot) R_Z(\alpha) R_X(\cdot)$ and $b = R_Z(\cdot) R_X(\beta) R_Z(\cdot)$. This enables us to move the $R_X$ and $R_Z$ through the controls and targets. This leaves us with

We now find ourselves in a similar situation as in the 1-CNOT case, wherein we need this circuit to be equivalent to the target unitary $U$, up to local gates. In particular, we look for $A, B, C, D \in SU(2)$ such that $U = (C \otimes D) V (A \otimes B)$. The characteristic polynomial of this circuit is

We can thus compute the eigenvalues of $u u^T$ again with $u = E^\dagger U E,$ identifying $\lambda_1 = \alpha + \beta$ and $\lambda_2 = \alpha - \beta.$ Here, $\lambda_i$ are the two phases of the eigenvalues of $u u^T$, which can be read out from its characteristic polynomial. This then yields

There is a special case where the two unique eigenvalues are $1$ and $-1$. In such case, we get the following.

-╭U- = -A--╭X--SZ--╭X--C- = -A--╭●--╭X--C-
-╰U- = -B--╰●--SX--╰●--D- = -B--╰X--╰●--D-

The final procedure is now the same as in the case with 1 CNOT, but with the new $V = \text{CNOT}_{10} (R_Z(\alpha) \otimes R_X(\beta)) \text{CNOT}_{10}$.

3 CNOT

The case with 3 CNOTs is derived similarly to the 2-CNOT case, but with the following middle part

The circuit is the following:

-╭U- = -C--╭X--RZ(d)--╭●---------╭X--A-
-╰U- = -D--╰●--RY(b)--╰X--RY(a)--╰●--B-

Similar to the 2 CNOT case, the angles are given by

where $x, y, z$ are the phases of the eigenvalues of $u u^T$.