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.