# Optimal synthesis of general multi-qutrit quantum computation

Gui-Long Jiang1, Wen-Qiang Liu2 and Hai-Rui Wei1<EMAIL_ADDRESS>1School of
Mathematics and Physics, University of Science and Technology Beijing, Beijing
100083, China
2Center for Quantum Technology Research and Key Laboratory of Advanced
Optoelectronic Quantum Architecture and Measurements (MOE), School of Physics,
Beijing Institute of Technology, Beijing 100081, China

###### Abstract

Quantum circuits of a general quantum gate acting on multiple $d$-level
quantum systems play a prominent role in multi-valued quantum computation. We
first propose a new recursive Cartan decomposition of semi-simple unitary Lie
group $U(3^{n})$ (arbitrary $n$-qutrit gate). Note that the decomposition
completely decomposes an $n$-qutrit gate into local and non-local operations.
We design an explicit quantum circuit for implementing arbitrary two-qutrit
gates, and the cost of our construction is 21 generalized controlled $X$ (GCX)
and controlled increment (CINC) gates less than the earlier best result of 26
GGXs. Moreover, we extend the program to the $n$-qutrit system, and the
quantum circuit of generic $n$-qutrit gates contained $\frac{41}{96}\cdot
3^{2n}-4\cdot 3^{n-1}-(\frac{n^{2}}{2}+\frac{n}{4}-\frac{29}{32})$ GGXs and
CINCs is presented. Such asymptotically optimal structure is the best known
result so far.

###### pacs:

03.67.Hk, 03.65.Ud, 03.67.Mn, 03.67.Pp

##  I Introduction

In recent decades, quantum computing has been extensively researched and has
gradually formed a complete theoretical system 1 . Compared to established
computational theory, quantum computers are qualitatively stronger 2 ; 3 ; 4
and capable of solving classical computational puzzles, e.g., Grover’s
algorithm Grover1 ; Grover2 , Shor’s algorithm Shor , and Deutsch-Jozsa
algorithm Deutsch1992 , more efficiently due to the powerful features of
quantum mechanics. It is well known that a $d$-level quantum system, so-called
qudit (qubit when $d=2$; qutrit when $d=3$), and its state space can be
described by a complex $d$-dimensional Hilbert space $\mathcal{H}_{d}$ with
the basis $\\{|0\rangle,|1\rangle,\cdots,|d-1\rangle\\}$. Higher-dimensional
Hilbert space exhibits unique advantages such as enlarging channel capacities
capacity , improving resistance to noise noise ; Wang2022 , supporting fault
tolerance tolerance , enhancing robustness to quantum cloning clone , reducing
the experimental requirements and quantum resource overheads resource ,
completing some tasks which are impossible to achieve with standard qubit-
based technologies task1 ; task2 ; task3 , and so on. Nowadays, tremendous
progress both in theory and experiment has been made in qudit-based quantum
information processing, e.g., $d$-dimensional quantum gate high-comput1 ;
high-comput2 , Grover’s algorithm high-algorithm , entangled state high-
entagled1 ; high-entagled2 ; high-entagled3 , quantum teleportation high-
teleportation1 ; high-teleportation2 ; high-teleportation3 , quantum key
distribution QKD1 ; QKD2 , and quantum tomography Tomography .

The quantum circuit model is the most popular paradigm for implementing
complex quantum computing circuit1 ; circuit2 . An efficient synthesis of
quantum circuits should be as low-cost and shallow as possible because the
growth of qubits increases the length and time scales of quantum gates, leads
to more complex procedures, and makes the quantum system further susceptible
to their environment circuit3 ; circuit4 . The controlled-NOT (CNOT) gate is
the most popular universal gate for qubit-based quantum computing Barenco1995
. Nowadays, using CNOT gates as elementary gates of synthesis, the optimal
quantum circuit for arbitrary two-qubit gates has been completed small1 ;
small2 , and considerable progress has been made on the physical
implementation of CNOT CNOT1 ; CNOT2 ; CNOT3 . To simplify multi-qubit quantum
computation, several synthesis programs are proposed using QR decomposition
Barenco1995 ; Vartiainen2004 , Cosine-Sine decomposition (CSD) Mottonen2004 ,
quantum Shannon decomposition (QSD) Shende2006 , and some specific Cartan
decompositions Khaneja2001 ; Bullock2004 ; Alessandro2007 . However, the above
results are much higher than the lower bound of $\frac{1}{4}(4^{n}-3n-1)]$
CNOT gates small2 . Lanyon _et al_. task1 ; task2  showed that the cost of the
qubit-based quantum circuit may be further reduced using higher-dimensional
Hilbert spaces.

Qudit-based quantum computation is in the infant. Earlier in 2003, universal
gates GXOR GXOR , SUM, and double SUM sum  for $d$-level system were proposed,
but the quantum circuits were not constructed in terms of these gates. Bullock
_et al_. Bullock2005  in 2005 proposed an asymptotically optimal quantum
circuit for implementing arbitrary $n$-qudit gates where $\Theta(d^{2n})$ two-
qudit gates are required. They later proved that the controlled increment
(CINC) gate is universal and presented another asymptotically optimal quantum
synthesis for $d$-level quantum computation using CINC as the elementary gate
Brennen2005 . In addition, based on CSD, Nakajima _et al._ Nakajima2009
suggested a synthesis algorithm for any operations on $n$-qudits, which
reduces the 156 CINCs required in Ref. Brennen2005  to 36 in the case of two-
qutrit. A universal generalized controlled $X$ (GCX) gate was proposed by Di
_et al_. Di2013  in 2013, and the GCX-based simplified synthesis of a generic
$n$-qudit gate was presented with extended QSD. Later in 2015, they Di2015
refined CSD to further reduce the cost (i.e., the number of GCX gates) of
synthetic circuits for an arbitrary $n$-qudit gate. Nevertheless, this is
still far from the theoretical lower bound of $[d^{2n}-n(d^{2}-1)-1]/[4(d-1)]$
GCXs Di2015 . In particular, for two-qutrit ($d=3$, $n=2$), the cost of
optimal synthesis is currently 26 GCXs Di2015 , while the theoretical lower
bound is only 8. Additionally, so far the efficient synthesis for a general
$n$-qutrit gate via Cartan decomposition remains an open question.

In this paper, we give an explicit program to synthesize arbitrary $n$-qutrit
computation with the shortest possible cost. We first propose a recursive
Cartan decomposition of the unitary operator acting on $n$-qutrit, and such a
new recursive algorithm first completely decomposes generic $n$-qutrit gates
into a product of simple local and non-local components. Based on the
decomposition shown in Fig. 9, we then present an explicit quantum circuit for
generic $n$-qutrit gates in terms of single-qutrit type rotations and two-
qutrit GCX gates. Note that $\frac{47}{96}\cdot 3^{2n}-4\cdot
3^{n-1}-(\frac{n^{2}}{2}+\frac{3n}{4}-\frac{27}{32})$ GCX gates contained in
our construction are minimal compared to the previous ones. If restricted to
universal CINC and GCX gates, the cost can be further reduced to
$\frac{41}{96}\cdot 3^{2n}-4\cdot
3^{n-1}-(\frac{n^{2}}{2}+\frac{n}{4}-\frac{29}{32})$ elementary two-qutrit
gates, and only 21 CINC and GCX gates are required in the worst to simulate an
arbitrary two-qutrit gate, while the previous optimum one required 26 Di2015 .

The paper is organized as follows: In Sec. II, we briefly review the Cartan
decomposition, the elementary-gate library, and propose two Theorems. In Sec.
III, the Cartan decomposition of an arbitrary two-qutrit gate is proposed and
a synthesis of generic two-qutrit gates is designed. In Sec. IV, this program
is promoted to synthesize $n$-qutrit gates, and a rigorous proof for the
Cartan decomposition of $n$-qutrit gates is presented. Finally, the conclusion
is provided in Sec. V.

##  II Cartan decomposition and three-valued elementary gate library

First, let us briefly review the Cartan decomposition of Lie groups and three-
valued elementary gate library containing the single-qutrit gate
$R_{\varphi}^{ij}(\theta)$ and two-qutrit GCX gate, and Theorem 1 and Theorem
2 are proposed.

###  II.1 Cartan decomposition of Lie group

Assume that $G$ is a compact semi-simple Lie group and $\mathfrak{g}$ is its
associated real semi-simple Lie algebra. Given a direct sum decomposition of
$\mathfrak{g}$ cartan

$\displaystyle\mathfrak{g}=\mathfrak{l}\oplus\mathfrak{p},$ (1)

if the Lie subalgebra $\mathfrak{l}$ and its complement space $\mathfrak{p}$
satisfy the following commutation relations:

$\displaystyle[\mathfrak{l},\mathfrak{l}]\subseteq\mathfrak{l},\;\;[\mathfrak{l},\mathfrak{p}]\subseteq\mathfrak{p},\;\;[\mathfrak{p},\mathfrak{p}]\subseteq\mathfrak{l},$
(2)

then Eq. (1) is called Cartan decomposition of $\mathfrak{g}$. If
$\mathfrak{a}$ is a maximally Abelian subalgebra contained in $\mathfrak{p}$,
then $\mathfrak{a}$ is called a Cartan subalgebra of the pair
$(\mathfrak{g},\mathfrak{l})$.

Based on Eq. (1) and the relation between the Lie group and the Lie algebra,
any element $M\in G$ can be decomposed as

$\displaystyle M=K_{1}\cdot A\cdot K_{2},$ (3)

where $K_{1},K_{2}\in\mathrm{exp}(\mathfrak{l})$ and
$A\in\mathrm{exp}(\mathfrak{a})$. Eq. (3) is called Cartan decomposition of
the Lie group $G$.

###  II.2 Synthesis of single-qutrit gate

Let $U(3^{n})$ denote the unitary group of $3^{n}\times 3^{n}$ unitary
matrices and $\mathfrak{u}(3^{n})$ be its associated Lie algebra. It is known
that the matrix of any single-qutrit gate is an element of $U(3)$. The basis
of $\mathfrak{u}(3)$, where $\mathfrak{u}(3)$ is a 9-dimensional linear space
of $3\times 3$ skew-Hermitian matrices, can be given by Di2008

$\displaystyle\begin{aligned}
\mathfrak{u}(3)=\textrm{span}\\{&\textrm{i}\sigma_{x}^{01},\textrm{i}\sigma_{x}^{02},\textrm{i}\sigma_{x}^{12},\textrm{i}\sigma_{y}^{01},\textrm{i}\sigma_{y}^{02},\\\
&\textrm{i}\sigma_{y}^{12},\textrm{i}\sigma_{z}^{01},\textrm{i}\sigma_{z}^{02},\textrm{i}I_{3}\\},\end{aligned}$
(4)

where

$\displaystyle\begin{aligned}
\sigma_{x}^{01}&=\left(\begin{array}[]{ccc}0&1&0\\\ 1&0&0\\\ 0&0&0\\\
\end{array}\right),\;\;\;\;\sigma_{x}^{02}=\left(\begin{array}[]{ccc}0&0&1\\\
0&0&0\\\ 1&0&0\\\ \end{array}\right),\\\
\sigma_{x}^{12}&=\left(\begin{array}[]{ccc}0&0&0\\\ 0&0&1\\\ 0&1&0\\\
\end{array}\right),\;\;\;\;\sigma_{y}^{01}=\left(\begin{array}[]{cccc}0&-\mathrm{i}&0\\\
\mathrm{i}&0&0\\\ 0&0&0\\\ \end{array}\right),\\\
\sigma_{y}^{02}&=\left(\begin{array}[]{cccc}0&0&-\mathrm{i}\\\ 0&0&0\\\
\mathrm{i}&0&0\\\
\end{array}\right),\;\;\sigma_{y}^{12}=\left(\begin{array}[]{ccc}0&0&0\\\
0&0&-\mathrm{i}\\\ 0&\mathrm{i}&0\\\ \end{array}\right),\\\
\sigma_{z}^{01}&=\left(\begin{array}[]{cccc}1&0&0\\\ 0&-1&0\\\ 0&0&0\\\
\end{array}\right),\;\sigma_{z}^{02}=\left(\begin{array}[]{cccc}1&0&0\\\
0&0&0\\\ 0&0&-1\\\ \end{array}\right),\\\
I_{3}&=\left(\begin{array}[]{cccc}1&0&0\\\ 0&1&0\\\ 0&0&1\\\
\end{array}\right).\end{aligned}$ (5)

Here and afterward, span$\\{A\\}$ denotes the space given by all linear
combinations of elements in $A$ with real coefficients.

Imitating single-qubit rotation gates, we define a single-qutrit
$\varphi$-axes type rotation gate as

$\displaystyle
R_{\varphi}^{ij}(\theta)=\textrm{exp}(-\textrm{i}\frac{\theta}{2}\sigma_{\varphi}^{ij})$
(6)

where $\varphi\in\\{x,y,z\\}$, $i,j\in\\{0,1,2\\}$. Based on the
$\mathrm{AIII}$-type Cartan decomposition of $U(3)$, an arbitrary single-
qutrit gate can be simulated by certain $R_{z}^{ij}(\theta)$
($R_{x}^{ij}(\theta)$) gates and $R_{y}^{i^{\prime}j^{\prime}}(\theta)$ gates
Di2013 . In addition, we present the transformation relation between
$R_{x}^{ij}(\theta)$ and $R_{z}^{ij}(\theta)$.

Theorem 1. $R_{y}^{ij}(-\frac{\pi}{2})\cdot R_{x}^{ij}(\theta)\cdot
R_{y}^{ij}(\frac{\pi}{2})=R_{z}^{ij}(\theta)$.

Proof 1. This can be obtained directly from matrix
multiplication.$\hfill\blacksquare$

###  II.3 Two-qutrit universal gate

Let $\\{|0\rangle,|1\rangle,|2\rangle\\}$ be the base state of a single-qutrit
system. The generalized controlled $X$ gate,
$\textrm{GCX}_{l}^{k}(m\rightarrow X^{ij})$, can be recognized as a two-qutrit
universal gate Di2013 . Here $\textrm{GCX}_{l}^{k}(m\rightarrow X^{ij})$ is to
perform an $X^{ij}$ operation on the target qutrit (the $k$th qutrit) if and
only if the state of the control qutrit (the $l$th qutrit) is $|m\rangle$
$(m\in\\{0,1,2\\})$. In the $\\{|0\rangle,|1\rangle,|2\rangle\\}$ basis,
$X^{01}$, $X^{02}$, and $X^{12}$ are given by

$\displaystyle\begin{aligned} X^{01}&=\left(\begin{array}[]{ccc}0&1&0\\\
1&0&0\\\ 0&0&1\\\ \end{array}\right),\\\
X^{02}&=\left(\begin{array}[]{ccc}0&0&1\\\ 0&1&0\\\ 1&0&0\\\
\end{array}\right),\\\ X^{12}&=\left(\begin{array}[]{ccc}1&0&0\\\ 0&0&1\\\
0&1&0\\\ \end{array}\right).\end{aligned}$ (7)

Some two adjacent GCX gates can be simplified as a GCX gate and an $X^{ij}$
gate.

Theorem 2. For an $n$-qutrit system, if
$m,m^{\prime},m^{\prime\prime}\in\\{0,1,2\\}$ are not equal to each other,
there is

$\displaystyle\begin{aligned} &\textrm{GCX}_{l}^{k}(m\rightarrow
X^{ij})\cdot\textrm{GCX}_{l}^{k}(m^{\prime}\rightarrow X^{ij})\\\
&=\textrm{GCX}_{l}^{k}(m^{\prime\prime}\rightarrow X^{ij})\cdot
I_{3^{k-1}}\otimes X^{ij}\otimes I_{3^{n-k}}\\\ &=I_{3^{k-1}}\otimes
X^{ij}\otimes I_{3^{n-k}}\cdot\textrm{GCX}_{l}^{k}(m^{\prime\prime}\rightarrow
X^{ij}).\end{aligned}$ (8)

Here $I_{d}$ is the $d\times d$ identity matrix.

Proof 2. The conclusion follows directly from matrix
multiplication.$\hfill\blacksquare$

In particular, with a two-qutrit system, when $l=1$ and $k=2$, Theorem 2 can
be illustrated by the quantum circuit shown in Fig. 1.

Figure 1: (a) The quantum circuit of Theorem 2 with $n=2$, $l=1$, $k=2$, and
$mm^{\prime}m^{\prime\prime}=210$. (b) The quantum circuit of Eq. (10) with
$l=1$ and $k=2$.

Aside from GCX gates, the controlled increment gate,
$\textrm{CINC}_{l}^{k}(m\rightarrow\textrm{INC})$, is another common two-
qutrit universal gate Di2013 . Here
$\textrm{CINC}_{l}^{k}(m\rightarrow\textrm{INC})$ is defined as implementing
the INC operation on the target qutrit (the $k$th qutrit) if and only if the
state of the control qutrit (the $l$th qutrit) is $|m\rangle$, where

$\displaystyle\begin{aligned} \textrm{INC}=X^{02}\cdot
X^{01}&=\left(\begin{array}[]{ccc}0&0&1\\\ 1&0&0\\\ 0&1&0\\\
\end{array}\right).\end{aligned}$ (9)

By Eq. (9), it is easy to obtain that

$\displaystyle\begin{aligned} &\textrm{GCX}_{l}^{k}(m\rightarrow
X^{02})\cdot\textrm{GCX}_{l}^{k}(m\rightarrow X^{01})\\\
&=\textrm{CINC}_{l}^{k}(m\rightarrow\textrm{INC}).\end{aligned}$ (10)

When $l=1$ and $k=2$, the quantum circuit represented by the above equation is
shown in Fig. 1.

##  III Cartan decomposition of arbitrary two-qutrit gates

###  III.1 Cartan decomposition of Lie group $\mathbf{\emph{U}(9)}$

We provide a successive cartan decomposition of $U(9)$, and refer to Sec. IV.1
for rigorous proof. Without loss of generality, the Lie algebra
$\mathfrak{u}(9)$ can be written as

$\displaystyle\begin{aligned}
\mathfrak{u}(9)=\textrm{span}\\{&\sigma_{x}^{01}\otimes
A,\sigma_{x}^{02}\otimes A,\sigma_{x}^{12}\otimes A,\sigma_{y}^{01}\otimes
A,\\\ &\sigma_{y}^{02}\otimes A,\sigma_{y}^{12}\otimes
A,\sigma_{z}^{01}\otimes A,\sigma_{z}^{02}\otimes A,\\\ &I_{3}\otimes
A|A\in\mathfrak{u}(3)\\}.\end{aligned}$ (11)

Decomposition of $\mathfrak{u}(9)$. We define

$\displaystyle\begin{aligned}
\mathfrak{l}(9)=\textrm{span}\\{&\sigma_{x}^{12}\otimes
A,\sigma_{y}^{12}\otimes A,\sigma_{z}^{01}\otimes A,\\\
&\sigma_{z}^{02}\otimes A,I_{3}\otimes A|A\in\mathfrak{u}(3)\\},\\\
\mathfrak{p}(9)=\textrm{span}\\{&\sigma_{x}^{01}\otimes
A,\sigma_{x}^{02}\otimes A,\sigma_{y}^{01}\otimes A,\\\
&\sigma_{y}^{02}\otimes A|A\in\mathfrak{u}(3)\\}.\end{aligned}$ (12)

Applying the formula

$\displaystyle[A\otimes B,C\otimes D]=[A,C]\otimes(BD)+(CA)\otimes[B,D],$ (13)

it is easily verified that
$\mathfrak{u}(9)=\mathfrak{l}(9)\oplus\mathfrak{p}(9)$ is the Cartan
decomposition of $\mathfrak{u}(9)$ and the corresponding Cartan subalgebra
$\mathfrak{a}(9)$ can be given by

$\displaystyle\mathfrak{a}(9)=\textrm{span}\\{\textrm{i}\sigma_{x}^{01}\otimes\sigma_{z}^{01},\textrm{i}\sigma_{x}^{01}\otimes\sigma_{z}^{02},\textrm{i}\sigma_{x}^{01}\otimes
I_{3}\\}.$ (14)

Decomposition of $\mathfrak{l}(9)$. Note that Lie subalgebra $\mathfrak{l}(9)$
is isomorphic to $\mathfrak{u}(3)\oplus\mathfrak{u}(6)$, and it can be further
decomposed as $\mathfrak{l}(9)=\mathfrak{l}_{1}(9)\oplus\mathfrak{p}_{1}(9)$
with

$\displaystyle\begin{aligned}
&\mathfrak{l}_{1}(9)=\textrm{span}\\{\sigma_{z}^{01}\otimes
A,\sigma_{z}^{02}\otimes A,I_{3}\otimes A|A\in\mathfrak{u}(3)\\},\\\
&\mathfrak{p}_{1}(9)=\textrm{span}\\{\sigma_{x}^{12}\otimes
A,\sigma_{y}^{12}\otimes A,|A\in\mathfrak{u}(3)\\}.\end{aligned}$ (15)

The corresponding Cartan subalgebra can be given by

$\displaystyle\mathfrak{a}_{1}(9)=\textrm{span}\\{\textrm{i}\sigma_{x}^{12}\otimes\sigma_{z}^{01},\textrm{i}\sigma_{x}^{12}\otimes\sigma_{z}^{02},\textrm{i}\sigma_{x}^{12}\otimes
I_{3}\\}.$ (16)

Decomposition of $\mathfrak{l}_{1}(9)$. Lie subalgebra $\mathfrak{l}_{1}(9)$
is isomorphic to $\mathfrak{u}(3)\oplus\mathfrak{u}(3)\oplus\mathfrak{u}(3)$.
In order to faithfully separate the local contents from the nonlocal contained
in $\mathfrak{l}_{1}(9)$, we rewrite the diagonal base elements of
$\mathfrak{u}(3)$ as

$\displaystyle\begin{aligned}
\textrm{span}\\{I_{3},\sigma_{z}^{01},\sigma_{z}^{02}\\}=&\textrm{span}\\{I_{3},D,\sigma_{z}^{12}\\}\\\
=&\textrm{span}\\{I_{3},\overline{D},\sigma_{z}^{01}\\}.\end{aligned}$ (17)

Here

$\displaystyle\begin{aligned}
\sigma_{z}^{12}=&\left(\begin{array}[]{ccc}0&0&0\\\ 0&1&0\\\ 0&0&-1\\\
\end{array}\right)=\sigma_{z}^{02}-\sigma_{z}^{01},\\\
D=&\left(\begin{array}[]{ccc}1&0&0\\\ 0&-1&0\\\ 0&0&-1\\\
\end{array}\right)=\frac{-I_{3}+2\sigma_{z}^{01}+2\sigma_{z}^{02}}{3},\\\
\overline{D}=&\left(\begin{array}[]{ccc}-1&0&0\\\ 0&-1&0\\\ 0&0&1\\\
\end{array}\right)=\frac{-I_{3}+2\sigma_{z}^{01}-4\sigma_{z}^{02}}{3}.\end{aligned}$
(18)

Then $\mathfrak{l}_{1}(9)$ can be written as

$\displaystyle\mathfrak{l}_{1}(9)=\textrm{span}\\{I_{3}\otimes A,D\otimes
A,\sigma_{z}^{12}\otimes A|A\in\mathfrak{u}(3)\\}.$ (19)

We have $\mathfrak{l}_{1}(9)=\mathfrak{l}_{2}(9)\oplus\mathfrak{p}_{2}(9)$ and
the Cartan subalgebra $\mathfrak{a}_{2}(9)$ of the pair
$(\mathfrak{l}_{1}(9),\mathfrak{l}_{2}(9))$, where

$\displaystyle\begin{aligned}
&\mathfrak{l}_{2}(9)=\textrm{span}\\{I_{3}\otimes A,D\otimes
A|A\in\mathfrak{u}(3)\\},\\\
&\mathfrak{p}_{2}(9)=\textrm{span}\\{\sigma_{z}^{12}\otimes
A|A\in\mathfrak{u}(3)\\},\\\
&\mathfrak{a}_{2}(9)=\textrm{span}\\{\textrm{i}\sigma_{z}^{12}\otimes
I_{3},\textrm{i}\sigma_{z}^{12}\otimes
D,\textrm{i}\sigma_{z}^{12}\otimes\sigma_{z}^{12}\\}.\end{aligned}$ (20)

When $\textrm{span}\\{I_{3},\overline{D},\sigma_{z}^{01}\\}$ is chosen,
$\mathfrak{l}_{1}(9)$ can be rewritten as

$\displaystyle\mathfrak{l}_{1}(9)=\textrm{span}\\{I_{3}\otimes
A,\overline{D}\otimes A,\sigma_{z}^{01}\otimes A|A\in\mathfrak{u}(3)\\},$ (21)

and has the Cartan decomposition

$\displaystyle\begin{aligned}
&\mathfrak{l}_{1}(9)=\overline{\mathfrak{l}_{2}}(9)\oplus\overline{\mathfrak{p}_{2}}(9),\\\
&\overline{\mathfrak{l}_{2}}(9)=\textrm{span}\\{I_{3}\otimes
A,\overline{D}\otimes A|A\in\mathfrak{u}(3)\\},\\\
&\overline{\mathfrak{p}_{2}}(9)=\textrm{span}\\{\sigma_{z}^{01}\otimes
A|A\in\mathfrak{u}(3)\\}.\end{aligned}$ (22)

Decomposition of $\mathfrak{l}_{2}(9)$ and $\overline{\mathfrak{l}_{2}}(9)$.
Lie algebra $\mathfrak{l}_{2}(9)$ ($\overline{\mathfrak{l}_{2}}(9)$) is
isomorphic to $\mathfrak{u}(3)\oplus\mathfrak{u}(3)$. Then the local and
nonlocal terms contained in $\mathfrak{l}_{2}(9)$ can be successfully divided
as

$\displaystyle\begin{aligned}
&\mathfrak{l}_{2}(9)=\mathfrak{l}_{3}(9)\oplus\mathfrak{p}_{3}(9),\\\
&\mathfrak{l}_{3}(9)=\textrm{span}\\{I_{3}\otimes A|A\in\mathfrak{u}(3)\\},\\\
&\mathfrak{p}_{3}(9)=\textrm{span}\\{D\otimes
A|A\in\mathfrak{u}(3)\\}.\end{aligned}$ (23)

The Cartan subalgebra $\mathfrak{a}_{3}(9)$ of the pair
$(\mathfrak{l}_{2}(9),\mathfrak{l}_{3}(9))$ is given by

$\displaystyle\mathfrak{a}_{3}(9)=\textrm{span}\\{\textrm{i}D\otimes
I_{3},\textrm{i}D\otimes D,\textrm{i}D\otimes\sigma_{z}^{12}\\}.$ (24)

Likewise, for $\overline{\mathfrak{l}_{2}}(9)$, we have

$\displaystyle\begin{aligned}
&\overline{\mathfrak{l}_{2}}(9)=\mathfrak{l}_{3}(9)\oplus\overline{\mathfrak{p}_{3}}(9),\\\
&\overline{\mathfrak{p}_{3}}(9)=\textrm{span}\\{\overline{D}\otimes
A|A\in\mathfrak{u}(3)\\},\\\
&\overline{\mathfrak{a}_{3}}(9)=\textrm{span}\\{\textrm{i}\overline{D}\otimes
I_{3},\textrm{i}\overline{D}\otimes\overline{D},\textrm{i}\overline{D}\otimes\sigma_{z}^{01}\\}.\end{aligned}$
(25)

Based on the above cascaded Cartan decomposition depicted by Fig. 2 and the
relation between Lie algebra and Lie group, the following Corollary can be
obtained, for a proof of which see Appendix A.

Figure 2: (a) Cartan decomposition of $\mathfrak{u}(9)$ and $\mathfrak{l}(9)$.
(b) Cartan decomposition of $\mathfrak{l}_{1}(9)$ and $\mathfrak{l}_{2}(9)$
with the diagonal basis $\\{I_{3},D,\sigma_{z}^{12}\\}$. (c) Cartan
decomposition of $\mathfrak{l}_{1}(9)$ and $\overline{\mathfrak{l}_{2}}(9)$
with the diagonal basis $\\{I_{3},\overline{D},\sigma_{z}^{01}\\}$. Here
$A\otimes\mathfrak{u}(3)$ denotes the set obtained by tensoring matrix $A$
with each element of $\mathfrak{u}(3)$, i.e., $\\{A\otimes
B|B\in\mathfrak{u}(3)\\}$.

Corollary 1. Any $M\in U(9)$ can be decomposed as

$\displaystyle\begin{aligned} M=&K_{1}\cdot\overline{A}^{(3)}_{1}\cdot
K_{2}\cdot A^{(1)}_{1}\cdot K_{3}\cdot A^{(3)}_{1}\cdot K_{4}\cdot A\cdot
K_{5}\\\ &\cdot\overline{A}^{(3)}_{2}\cdot K_{6}\cdot A^{(1)}_{2}\cdot
K_{7}\cdot A^{(2)}\cdot K_{8}\cdot A^{(3)}_{2}\cdot K_{9}.\end{aligned}$ (26)

Here $A\in\textrm{exp}[\mathfrak{a}(9)]$,
$A^{(1)}_{1,2}\in\textrm{exp}[\mathfrak{a}_{1}(9)]$,
$A^{(2)}\in\textrm{exp}[\mathfrak{a}_{2}(9)]$,
$A^{(3)}_{1,2}\in\textrm{exp}[\mathfrak{a}_{3}(9)]$,
$\overline{A}^{(3)}_{1,2}\in\textrm{exp}[\overline{\mathfrak{a}_{3}}(9)]$, and
$K_{i}\in\textrm{exp}[\mathfrak{l}_{3}(9)]$. Note that $K_{l}\in U(3)$ as
$\mathfrak{l}_{3}(9)$ is isomorphic to $\mathfrak{u}(3)$.

###  III.2 Synthesis of arbitrary two-qutrit gates

As shown in Fig. 3, two-qutrit nonlocal operations $A$, $A_{i}^{(1)}$,
$A_{j}^{(2)}$, and $A_{k}^{(3)}$ play the key role in the construction of an
arbitrary two-qutrit gate. In the following, we provide a program to
synthesize them in detail.

Figure 3: Decomposition of an arbitrary two-qutrit gate based on Eq. (26).

Synthesis of two-qutrit operation $A$. Based on Eq. (14), nonlocal operation
$A$ can be expressed as

$\displaystyle\begin{aligned}
A(\theta_{1},\theta_{2},\theta_{3})=&\textrm{exp}[-\textrm{i}(\theta_{1}\sigma_{x}^{01}\otimes\sigma_{z}^{01}+\theta_{2}\sigma_{x}^{01}\otimes\sigma_{z}^{02}\\\
&+\theta_{3}\sigma_{x}^{01}\otimes I_{3})].\end{aligned}$ (27)

By employing Theorem 1, we find that $A(\theta_{1},\theta_{2},\theta_{3})$ is
equivalent to $\widetilde{A}(\theta_{1},\theta_{2},\theta_{3})$ up to two
local operations $R^{01}_{y}(-\frac{\pi}{2})\otimes I_{3}$ and
$R^{01}_{y}(\frac{\pi}{2})\otimes I_{3}$. Here

$\displaystyle\begin{aligned}
\widetilde{A}(\theta_{1},\theta_{2},\theta_{3})=&R^{01}_{y}(-\frac{\pi}{2})\otimes
I_{3}\cdot A(\theta_{1},\theta_{2},\theta_{3})\\\ &\cdot
R^{01}_{y}(\frac{\pi}{2})\otimes I_{3}\\\
=&\textrm{exp}[-\textrm{i}\sigma_{z}^{01}\otimes(\theta_{1}\sigma_{z}^{01}+\theta_{2}\sigma_{z}^{02}+\theta_{3}I_{3})].\end{aligned}$
(28)

Observe that $\widetilde{A}(\theta_{1},\theta_{2},\theta_{3})$ is a
conditional control gate, which performs $R_{z}^{01}[\theta(m)]$ operations on
the first (target) qutrit when the second (control) qutrit is $|m\rangle$,
where $\theta(m)$ depends on $|m\rangle$. By calculation, we obtain

$\displaystyle\begin{aligned}
\widetilde{A}(\theta_{1},\theta_{2},\theta_{3})=&\textrm{GCX}_{2}^{1}(1\rightarrow
X^{01})\cdot R_{z}^{01}(2\theta_{1}+\theta_{2})\otimes I_{3}\\\
&\cdot\textrm{GCX}_{2}^{1}(1\rightarrow
X^{01})\cdot\textrm{GCX}_{2}^{1}(2\rightarrow X^{01})\\\ &\cdot
R_{z}^{01}(\theta_{1}+2\theta_{2})\otimes
I_{3}\cdot\textrm{GCX}_{2}^{1}(2\rightarrow X^{01})\\\ &\cdot
R_{z}^{01}(2\theta_{3}-\theta_{1}-\theta_{2})\otimes I_{3}.\end{aligned}$ (29)

Based on Eq. (28) and Theorem 2, $A(\theta_{1},\theta_{2},\theta_{3})$ can be
recovered and further simplified as

$\displaystyle\begin{aligned}
A(\theta_{1},\theta_{2},\theta_{3})=&R^{01}_{y}(\frac{\pi}{2})\otimes
I_{3}\cdot\widetilde{A}(\theta_{1},\theta_{2},\theta_{3})\\\ &\cdot
R^{01}_{y}(-\frac{\pi}{2})\otimes I_{3}\\\ =&R^{01}_{y}(\frac{\pi}{2})\otimes
I_{3}\cdot\textrm{GCX}_{2}^{1}(1\rightarrow X^{01})\\\ &\cdot
R_{z}^{01}(2\theta_{1}+\theta_{2})\otimes I_{3}\\\
&\cdot\textrm{GCX}_{2}^{1}(0\rightarrow X^{01})\cdot X^{01}\otimes I_{3}\\\
&\cdot R_{z}^{01}(\theta_{1}+2\theta_{2})\otimes I_{3}\\\
&\cdot\textrm{GCX}_{2}^{1}(2\rightarrow X^{01})\\\ &\cdot
R_{z}^{01}(2\theta_{3}-\theta_{1}-\theta_{2})\otimes I_{3}\\\ &\cdot
R^{01}_{y}(-\frac{\pi}{2})\otimes I_{3}.\end{aligned}$ (30)

Here single-qutrit gate $X^{01}$ can be decomposed into three rotation gates
as follows:

$\displaystyle\begin{aligned}
X^{01}=e^{\textrm{i}\frac{\pi}{3}}R^{01}_{x}(\pi)\cdot
R^{02}_{z}(-\frac{2\pi}{3})\cdot R^{01}_{z}(\frac{\pi}{3}),\end{aligned}$ (31)

Substituting Eq. (31) into Eq. (30) results in a quantum circuit to implement
$A(\theta_{1},\theta_{2},\theta_{3})$, which contains 3 GCX gates and 7
single-qutrit $x$-, $y$-, and $z$-axes type rotations as shown in Fig. 4.

Figure 4: Synthesis of $A(\theta_{1},\theta_{2},\theta_{3})$. Here
$\theta_{1}^{\prime}=2\theta_{3}-\theta_{1}-\theta_{2}$,
$\theta_{2}^{\prime}=\theta_{1}+2\theta_{2}+\frac{\pi}{3}$, and
$\theta_{3}^{\prime}=2\theta_{1}+\theta_{2}$. A global phase
$e^{\textrm{i}\frac{\pi}{3}}$ is missing here as it does not affect our
argument.

Synthesis of two-qutrit operation $A_{1,2}^{(1)}$. Based on Eq. (16),
$A_{1,2}^{(1)}$ can be given by

$\displaystyle\begin{aligned}
A^{(1)}(\theta_{4},\theta_{5},\theta_{6})=&\textrm{exp}[-\textrm{i}(\theta_{4}\sigma_{x}^{12}\otimes\sigma_{z}^{01}+\theta_{5}\sigma_{x}^{12}\otimes\sigma_{z}^{02}\\\
&+\theta_{6}\sigma_{x}^{12}\otimes I_{3})].\end{aligned}$ (32)

With an argument similar to the synthesis of
$A(\theta_{1},\theta_{2},\theta_{3})$, we have the following decomposition

$\displaystyle\begin{aligned}
A^{(1)}(\theta_{4},\theta_{5},\theta_{6})=&R^{12}_{y}(\frac{\pi}{2})\otimes
I_{3}\cdot\textrm{GCX}_{2}^{1}(1\rightarrow X^{12})\\\ &\cdot
R_{z}^{12}(2\theta_{4}+\theta_{5})\otimes I_{3}\\\
&\cdot\textrm{GCX}_{2}^{1}(0\rightarrow X^{12})\cdot X^{12}\otimes I_{3}\\\
&\cdot R_{z}^{12}(\theta_{4}+2\theta_{5})\otimes I_{3}\\\
&\cdot\textrm{GCX}_{2}^{1}(2\rightarrow X^{12})\\\ &\cdot
R_{z}^{12}(2\theta_{6}-\theta_{4}-\theta_{5})\otimes I_{3}\\\ &\cdot
R^{12}_{y}(-\frac{\pi}{2})\otimes I_{3}.\end{aligned}$ (33)

Here $X^{12}$ can be simulated by

$\displaystyle\begin{aligned}
X^{12}=e^{\textrm{i}\frac{\pi}{3}}R^{12}_{x}(\pi)\cdot
R^{01}_{z}(\frac{2\pi}{3})\cdot R^{12}_{z}(\frac{\pi}{3}).\end{aligned}$ (34)

Therefore, as shown in Fig. 5, 3 GCX gates and 7 single-qutrit $x$-, $y$-, and
$z$-axes type rotations are sufficient to simulate
$A^{(1)}(\theta_{4},\theta_{5},\theta_{6})$.

Figure 5: Synthesis of $A^{(1)}(\theta_{4},\theta_{5},\theta_{6})$. Here
$\theta_{4}^{\prime}=2\theta_{6}-\theta_{4}-\theta_{5}$,
$\theta_{5}^{\prime}=\theta_{4}+2\theta_{5}+\frac{\pi}{3}$, and
$\theta_{6}^{\prime}=2\theta_{4}+\theta_{5}$. We ignore the overall phase
$e^{\textrm{i}\frac{\pi}{3}}$ here.

Synthesis of two-qutrit operation $\mathbf{\emph{A}^{(2)}}$. Based on Eq.
(20), $A^{(2)}$ is diagonal and has the following form

$\displaystyle\begin{aligned}
A^{(2)}(\theta_{7},\theta_{8},\theta_{9})=&\textrm{exp}[-\textrm{i}(\theta_{7}\sigma_{z}^{12}\otimes
I_{3}+\theta_{8}\sigma_{z}^{12}\otimes D\\\
&+\theta_{9}\sigma_{z}^{12}\otimes\sigma_{z}^{12})].\end{aligned}$ (35)

By calculation, $A^{(2)}(\theta_{7},\theta_{8},\theta_{9})$ can be decomposed
as follow

$\displaystyle\begin{aligned}
A^{(2)}(\theta_{7},\theta_{8},\theta_{9})=&\textrm{GCX}_{2}^{1}(1\rightarrow
X^{12})\\\ &\cdot R_{z}^{12}(2\theta_{8}-\theta_{9})\otimes I_{3}\\\
&\cdot\textrm{GCX}_{2}^{1}(0\rightarrow X^{12})\cdot X^{12}\otimes I_{3}\\\
&\cdot R_{z}^{12}(2\theta_{8}+\theta_{9})\otimes I_{3}\\\
&\cdot\textrm{GCX}_{2}^{1}(2\rightarrow X^{12})\\\ &\cdot
R_{z}^{12}(2\theta_{7}-2\theta_{8})\otimes I_{3}.\end{aligned}$ (36)

As a consequence of substituting Eq. (34) into Eq. (36), the structure of
$A^{(2)}(\theta_{7},\theta_{8},\theta_{9})$ contains 3 GCXs and 5 $x$-,
$z$-axes type rotations, see Fig. 6.

Figure 6: Synthesis of $A^{(2)}(\theta_{7},\theta_{8},\theta_{9})$. Here
$\theta_{7}^{\prime}=2\theta_{7}-2\theta_{8}$,
$\theta_{8}^{\prime}=2\theta_{8}+\theta_{9}+\frac{\pi}{3}$, and
$\theta_{9}^{\prime}=2\theta_{8}-\theta_{9}$. We omit the global phase factor
$e^{\textrm{i}\frac{\pi}{3}}$ here.

Synthesis of two-qutrit operation $A^{(3)}_{1,2}$. Based on Eq. (24),
$A^{(3)}_{1,2}$ is of the form

$\displaystyle\begin{aligned}
A^{(3)}(\theta_{10},\theta_{11},\theta_{12})=&\textrm{exp}[-\textrm{i}(\theta_{10}D\otimes
I_{3}+\theta_{11}D\otimes D\\\
&+\theta_{12}D\otimes\sigma_{z}^{12})].\end{aligned}$ (37)

Firstly $A^{(3)}(\theta_{10},\theta_{11},\theta_{12})$ can be decomposed into
the following simple gates

$\displaystyle\begin{aligned}
A^{(3)}(\theta_{10},\theta_{11},\theta_{12})=&\textrm{GCX}_{1}^{2}(0\rightarrow
X^{02})\\\ &\cdot I_{3}\otimes
R_{z}^{02}(-2\theta_{12}-\frac{4\theta_{11}}{3})\\\
&\cdot\textrm{GCX}_{1}^{2}(0\rightarrow X^{02})\\\
&\cdot\textrm{GCX}_{1}^{2}(0\rightarrow X^{01})\\\ &\cdot I_{3}\otimes
R_{z}^{01}(2\theta_{12}-\frac{4\theta_{11}}{3})\\\
&\cdot\textrm{GCX}_{1}^{2}(0\rightarrow X^{01})\\\
&\cdot\textrm{exp}[-\textrm{i}(\theta_{10}-\frac{\theta_{11}}{3})D]\otimes
I_{3}.\end{aligned}$ (38)

Returning $\textrm{span}\\{I_{3},D,\sigma_{z}^{12}\\}$ to
$\textrm{span}\\{\sigma_{z}^{01},\sigma_{z}^{02},I_{3}\\}$ as explained in Eq.
(18), we can obtain that

$\displaystyle\begin{aligned}
\textrm{exp}[-\textrm{i}(\theta_{10}-\frac{\theta_{11}}{3})D]=e^{\textrm{i}\frac{\theta^{\prime}_{10}}{4}}R_{z}^{01}(\theta^{\prime}_{10})\cdot
R_{z}^{02}(\theta^{\prime}_{10}),\end{aligned}$ (39)

where $\theta^{\prime}_{10}=\frac{4\theta_{10}}{3}-\frac{4\theta_{11}}{9}$. As
$R_{z}^{ij}(\theta)\otimes I_{3}$ is commutable with both
$\textrm{GCX}_{1}^{2}(0\rightarrow X^{01})$ and
$\textrm{GCX}_{1}^{2}(0\rightarrow X^{02})$, substituting Eq. (39) into (38)
induces

$\displaystyle\begin{aligned}
A^{(3)}(\theta_{10},\theta_{11},\theta_{12})=&e^{\textrm{i}\frac{\theta^{\prime}_{10}}{4}}\textrm{GCX}_{1}^{2}(0\rightarrow
X^{02})\\\ &\cdot R_{z}^{02}(\theta^{\prime}_{10})\otimes
R_{z}^{02}(\theta^{\prime}_{11})\\\ &\cdot\textrm{GCX}_{1}^{2}(0\rightarrow
X^{02})\\\ &\cdot\textrm{GCX}_{1}^{2}(0\rightarrow X^{01})\\\ &\cdot
R_{z}^{01}(\theta^{\prime}_{10})\otimes R_{z}^{01}(\theta^{\prime}_{12})\\\
&\cdot\textrm{GCX}_{1}^{2}(0\rightarrow X^{01}),\end{aligned}$ (40)

where $\theta_{11}^{\prime}=-2\theta_{12}-\frac{4\theta_{11}}{3}$ and
$\theta_{12}^{\prime}=2\theta_{12}-\frac{4\theta_{11}}{3}$. Thus, up to a
global phase $e^{\textrm{i}\frac{\theta^{\prime}_{10}}{4}}$, 4 GCX gates and 4
$z$-axes type rotations suffice to build a quantum circuit of
$A^{(3)}(\theta_{10},\theta_{11},\theta_{12})$, see Fig. 7. In fact, following
Fig. 1, two adjacent GCX gates in Eq. (40) can be combined into a CINC gate.

Figure 7: Synthesis of $A^{(3)}(\theta_{10},\theta_{11},\theta_{12})$. Here
$\theta^{\prime}_{10}=\frac{4\theta_{10}}{3}-\frac{4\theta_{11}}{9}$,
$\theta_{11}^{\prime}=-2\theta_{12}-\frac{4\theta_{11}}{3}$, and
$\theta_{12}^{\prime}=2\theta_{12}-\frac{4\theta_{11}}{3}$.

Synthesis of two-qutrit operation $\overline{A}^{(3)}_{1,2}$. Based on Eq.
(25), $\overline{A}^{(3)}_{1,2}$ can be written in the following form and has
the following decomposition

$\displaystyle\begin{aligned}
\overline{A}^{(3)}(\theta_{13},\theta_{14},\theta_{15})=&\textrm{exp}[-\textrm{i}(\theta_{13}\overline{D}\otimes
I_{3}+\theta_{14}\overline{D}\otimes\overline{D}\\\
&+\theta_{15}\overline{D}\otimes\sigma_{z}^{01})]\\\
=&\textrm{GCX}_{1}^{2}(2\rightarrow X^{02})\\\ &\cdot I_{3}\otimes
R_{z}^{02}(\frac{8\theta_{14}}{3})\\\ &\cdot\textrm{GCX}_{1}^{2}(2\rightarrow
X^{02})\\\ &\cdot\textrm{GCX}_{1}^{2}(2\rightarrow X^{01})\\\ &\cdot
I_{3}\otimes R_{z}^{01}(-2\theta_{15}-\frac{4\theta_{14}}{3})\\\
&\cdot\textrm{GCX}_{1}^{2}(2\rightarrow X^{01})\\\
&\cdot\textrm{exp}[-\textrm{i}(\theta_{13}-\frac{\theta_{14}}{3})\overline{D}]\otimes
I_{3}.\end{aligned}$ (41)

Expressing $\overline{D}$ in terms of $\sigma_{z}^{01}$, $\sigma_{z}^{02}$,
and $I_{3}$, we get

$\displaystyle\begin{aligned}
\textrm{exp}[-\textrm{i}(\theta_{13}-\frac{\theta_{14}}{3})\overline{D}]=e^{\textrm{i}\frac{\theta^{\prime}_{13}}{4}}R_{z}^{01}(\theta^{\prime}_{13})\cdot
R_{z}^{02}(-2\theta^{\prime}_{13}),\end{aligned}$ (42)

where $\theta^{\prime}_{13}=\frac{4\theta_{13}}{3}-\frac{4\theta_{14}}{9}$.
Since $R_{z}^{ij}(\theta)\otimes I_{3}$ is commutable with both
$\textrm{GCX}_{1}^{2}(2\rightarrow X^{01})$ and
$\textrm{GCX}_{1}^{2}(2\rightarrow X^{02})$, substituting Eq. (42) into (41)
results in

$\displaystyle\begin{aligned}
\overline{A}^{(3)}(\theta_{13},\theta_{14},\theta_{15})=&e^{\textrm{i}\frac{\theta^{\prime}_{13}}{4}}\textrm{GCX}_{1}^{2}(2\rightarrow
X^{02})\\\ &\cdot R_{z}^{02}(-2\theta^{\prime}_{13})\otimes
R_{z}^{02}(\theta^{\prime}_{14})\\\ &\cdot\textrm{GCX}_{1}^{2}(2\rightarrow
X^{02})\\\ &\cdot\textrm{GCX}_{1}^{2}(2\rightarrow X^{01})\\\ &\cdot
R_{z}^{01}(\theta^{\prime}_{13})\otimes R_{z}^{01}(\theta^{\prime}_{15})\\\
&\cdot\textrm{GCX}_{1}^{2}(2\rightarrow X^{01}),\end{aligned}$ (43)

where $\theta_{14}^{\prime}=\frac{8\theta_{14}}{3}$ and
$\theta_{15}^{\prime}=-2\theta_{15}-\frac{4\theta_{14}}{3}$. Thus, similar to
Fig. 7, 4 GCX gates and 4 $z$-axes type rotations are sufficient to synthesize
$\overline{A}^{(3)}(\theta_{13},\theta_{14},\theta_{15})$ up to a global phase
$e^{\textrm{i}\frac{\theta^{\prime}_{13}}{4}}$, see Fig. 8.

Figure 8: Synthesis of
$\overline{A}^{(3)}(\theta_{13},\theta_{14},\theta_{15})$. Here
$\theta^{\prime}_{13}=\frac{4\theta_{13}}{3}-\frac{4\theta_{14}}{9}$,
$\theta_{14}^{\prime}=\frac{8\theta_{14}}{3}$, and
$\theta_{15}^{\prime}=-2\theta_{15}-\frac{4\theta_{14}}{3}$. The quantum
circuit on the right is obtained by applying Fig. 1.

Synthesis of the arbitrary two-qutrit gate. Embedding Fig. 4, Fig. 5, Fig. 6,
Fig. 7, and Fig. 8 in Fig. 3, one can find that the synthesis of a generic
two-qutrit gate requires 21 universal two-qutrit gates (or 25 GCX gates) at
most. In this process, the rightmost GCXs of Fig. 4 and Fig. 5 have been
absorbed into the block diagonal matrices occurring in the proof of Corollary
1, see Appendix A for details. Hence, our Cartan-decomposition-based program
can be used to simulate arbitrary two-qutrit gates in terms of GCXs and
single-qutrit $R_{\varphi}^{ij}(\theta)$ gates.

##  IV Recursive decomposition of arbitrary multi-qutrit gates

The program described in Sec. III can be extended to synthesize an arbitrary
$n$-qutrit gate.

###  IV.1 Cartan decomposition of Lie group $\mathbf{\emph{U}(3^{\emph{n}})}$

Without any loss of generality, let the Lie algebra $\mathfrak{u}(3^{n})$ is
spanned as

$\displaystyle\begin{aligned}
\mathfrak{u}(3^{n})=\textrm{span}\\{&\sigma_{x}^{01}\otimes
A,\sigma_{x}^{02}\otimes A,\sigma_{x}^{12}\otimes A,\sigma_{y}^{01}\otimes
A,\\\ &\sigma_{y}^{02}\otimes A,\sigma_{y}^{12}\otimes
A,\sigma_{z}^{01}\otimes A,\sigma_{z}^{02}\otimes A,\\\ &I_{3}\otimes
A|A\in\mathfrak{u}(3^{n-1})\\}.\end{aligned}$ (44)

Decomposition of $\mathfrak{u}(3^{n})$. By calculation, we find that the
decomposition of $\mathfrak{u}(3^{n})$ has the following Theorem.

Theorem 3. $\mathfrak{u}(3^{n})=\mathfrak{l}(3^{n})\oplus\mathfrak{p}(3^{n})$
is the Cartan decomposition, where

$\displaystyle\begin{aligned}
\mathfrak{l}(3^{n})=\textrm{span}\\{&\sigma_{x}^{12}\otimes
A,\sigma_{y}^{12}\otimes A,\sigma_{z}^{01}\otimes A,\\\
&\sigma_{z}^{02}\otimes A,I_{3}\otimes A|A\in\mathfrak{u}(3^{n-1})\\},\\\
\mathfrak{p}(3^{n})=\textrm{span}\\{&\sigma_{x}^{01}\otimes
A,\sigma_{x}^{02}\otimes A,\sigma_{y}^{01}\otimes A,\\\
&\sigma_{y}^{02}\otimes A|A\in\mathfrak{u}(3^{n-1})\\}.\end{aligned}$ (45)

Further, let

$\displaystyle\begin{aligned}
&\alpha(3)=\\{\textrm{i}I_{3},\textrm{i}\sigma_{z}^{01},\textrm{i}\sigma_{z}^{02}\\},\\\
&\alpha(3^{n})=\\{I_{3}\otimes A,\sigma_{z}^{01}\otimes
A,\sigma_{z}^{02}\otimes A|A\in\alpha(3^{n-1})\\}.\end{aligned}$ (46)

The Cartan subalgebra of $(\mathfrak{u}(3^{n}),\mathfrak{l}(3^{n}))$ can be
picked as

$\displaystyle\begin{aligned}
\mathfrak{a}(3^{n})=\textrm{span}\\{\sigma_{x}^{01}\otimes
A|A\in\alpha(3^{n-1})\\}\subset\mathfrak{p}(3^{n}).\end{aligned}$ (47)

Proof 3. Firstly, we prove that
$[\mathfrak{l}(3^{n}),\mathfrak{l}(3^{n})]\subseteq\mathfrak{l}(3^{n})$.

Given that any $M_{1},M_{2}\in\mathfrak{l}(3^{n})$, then $M_{1}$ and $M_{2}$
can be denoted as

$\displaystyle\begin{aligned} M_{1}=&I_{3}\otimes A_{1}+\sigma_{z}^{01}\otimes
A_{2}+\sigma_{z}^{02}\otimes A_{3}+\sigma_{x}^{12}\otimes A_{4}\\\
&+\sigma_{y}^{12}\otimes A_{5}\\\
=&\left(\begin{array}[]{ccc}A_{1}+A_{2}+A_{3}&\textbf{0}&\textbf{0}\\\
\textbf{0}&A_{1}-A_{2}&A_{4}-\textrm{i}A_{5}\\\
\textbf{0}&A_{4}+\textrm{i}A_{5}&A_{1}-A_{3}\\\
\end{array}\right),\end{aligned}$ (48) $\displaystyle\begin{aligned}
M_{2}=&I_{3}\otimes B_{1}+\sigma_{z}^{01}\otimes B_{2}+\sigma_{z}^{02}\otimes
B_{3}+\sigma_{x}^{12}\otimes B_{4}\\\ &+\sigma_{y}^{12}\otimes B_{5}\\\
=&\left(\begin{array}[]{ccc}B_{1}+B_{2}+B_{3}&\textbf{0}&\textbf{0}\\\
\textbf{0}&B_{1}-B_{2}&B_{4}-\textrm{i}B_{5}\\\
\textbf{0}&B_{4}+\textrm{i}B_{5}&B_{1}-B_{3}\\\
\end{array}\right).\end{aligned}$ (49)

Here $A_{i},B_{j}\in\mathfrak{u}(3^{n-1})$, i.e., $A_{i}$ and $B_{j}$ are
$3^{n-1}\times 3^{n-1}$ skew-Hermitian matrices. $M_{1}$ and $M_{2}$ obey the
commutator relations

$\displaystyle\begin{aligned} &=M_{1}\cdot M_{2}-M_{2}\cdot M_{1}\\\
&=\left(\begin{array}[]{ccc}M_{11}&\textbf{0}&\textbf{0}\\\
\textbf{0}&M_{22}&M_{23}\\\ \textbf{0}&M_{32}&M_{33}\\\
\end{array}\right),\end{aligned}$ (50)

where $M_{11}^{\dagger}=-M_{11}$, $M_{22}^{\dagger}=-M_{22}$,
$M_{33}^{\dagger}=-M_{33}$, and $M_{23}^{\dagger}=-M_{32}$. Here $\dagger$
denotes a conjugate transposition.

By setting

$\displaystyle\begin{aligned} &X_{1}=\frac{M_{11}+M_{22}+M_{33}}{3},\\\
&X_{2}=\frac{M_{11}-2M_{22}+M_{33}}{3},\\\
&X_{3}=\frac{M_{11}+M_{22}-2M_{33}}{3},\\\ &X_{4}=\frac{M_{23}+M_{32}}{3},\\\
&X_{5}=\textrm{i}\frac{M_{23}-M_{32}}{3},\end{aligned}$ (51)

$[M_{1},M_{2}]$ shown in Eq. (50) can be rewritten as

$\displaystyle\begin{aligned}
\left(\begin{array}[]{ccc}X_{1}+X_{2}+X_{3}&\textbf{0}&\textbf{0}\\\
\textbf{0}&X_{1}-X_{2}&X_{4}-\textrm{i}X_{5}\\\
\textbf{0}&X_{4}+\textrm{i}X_{5}&X_{1}-X_{3}\\\
\end{array}\right).\end{aligned}$ (52)

This form is the same as that presented in Eqs. (48) and (49) due to
$X_{i}^{\dagger}=-X_{i}$. Hence, $[M_{1},M_{2}]\in\mathfrak{l}(3^{n})$, and
than $[\mathfrak{l}(3^{n}),\mathfrak{l}(3^{n})]\subseteq\mathfrak{l}(3^{n})$.

Secondly, we prove that
$[\mathfrak{p}(3^{n}),\mathfrak{p}(3^{n})]\subseteq\mathfrak{l}(3^{n})$.

Suppose $M_{3},M_{4}\in\mathfrak{p}(3^{n})$, then $M_{3}$ and $M_{4}$ have the
following generic forms

$\displaystyle\begin{aligned} M_{3}=&\sigma_{x}^{01}\otimes
C_{1}+\sigma_{x}^{02}\otimes C_{2}+\sigma_{y}^{01}\otimes
C_{3}+\sigma_{y}^{02}\otimes C_{4}\\\
=&\left(\begin{array}[]{ccc}\textbf{0}&C_{1}-\textrm{i}C_{3}&C_{2}-\textrm{i}C_{4}\\\
C_{1}+\textrm{i}C_{3}&\textbf{0}&\textbf{0}\\\
C_{2}+\textrm{i}C_{4}&\textbf{0}&\textbf{0}\\\
\end{array}\right),\end{aligned}$ (53) $\displaystyle\begin{aligned}
M_{4}=&\sigma_{x}^{01}\otimes D_{1}+\sigma_{x}^{02}\otimes
D_{2}+\sigma_{y}^{01}\otimes D_{3}+\sigma_{y}^{02}\otimes D_{4}\\\
=&\left(\begin{array}[]{ccc}\textbf{0}&D_{1}-\textrm{i}D_{3}&D_{2}-\textrm{i}D_{4}\\\
D_{1}+\textrm{i}D_{3}&\textbf{0}&\textbf{0}\\\
D_{2}+\textrm{i}D_{4}&\textbf{0}&\textbf{0}\\\
\end{array}\right),\end{aligned}$ (54)

where $C_{k},D_{l}\in\mathfrak{u}(3^{n-1})$. By multiplication of the block
matrices, we get

$\displaystyle\begin{aligned}
=\left(\begin{array}[]{ccc}\overline{M}_{11}&\textbf{0}&\textbf{0}\\\
\textbf{0}&\overline{M}_{22}&\overline{M}_{23}\\\
\textbf{0}&\overline{M}_{32}&\overline{M}_{33}\\\
\end{array}\right),\end{aligned}$ (55)

where $\overline{M}_{11}^{\dagger}=-\overline{M}_{11}$,
$\overline{M}_{22}^{\dagger}=-\overline{M}_{22}$,
$\overline{M}_{33}^{\dagger}=-\overline{M}_{33}$, and
$\overline{M}_{23}^{\dagger}=-\overline{M}_{32}$. Therefore, in conjunction
with the previous argument, it is clear that
$[\mathfrak{p}(3^{n}),\mathfrak{p}(3^{n})]\subseteq\mathfrak{l}(3^{n})$.

Thirdly, we prove that
$[\mathfrak{l}(3^{n}),\mathfrak{p}(3^{n})]\subseteq\mathfrak{p}(3^{n})$.

Calculate $[M_{1},M_{3}]$ to get

$\displaystyle\begin{aligned}
&[M_{1},M_{3}]=\left(\begin{array}[]{ccc}\textbf{0}&M_{12}&M_{13}\\\
M_{21}&\textbf{0}&\textbf{0}\\\ M_{31}&\textbf{0}&\textbf{0}\\\
\end{array}\right),\end{aligned}$ (56)

where $M_{12}^{\dagger}=-M_{21}$, $M_{13}^{\dagger}=-M_{31}$. Setting

$\displaystyle\begin{aligned} &Y_{1}=\frac{M_{12}+M_{21}}{2},\\\
&Y_{2}=\frac{M_{13}+M_{31}}{2},\\\
&Y_{3}=\textrm{i}\frac{M_{12}-M_{21}}{2},\\\
&Y_{4}=\textrm{i}\frac{M_{13}-M_{31}}{2},\end{aligned}$ (57)

Eq. (56) is written as follows

$\displaystyle\begin{aligned}
&[M_{1},M_{3}]=\left(\begin{array}[]{ccc}\textbf{0}&Y_{1}-\textrm{i}Y_{3}&Y_{2}-\textrm{i}Y_{4}\\\
Y_{1}+\textrm{i}Y_{3}&\textbf{0}&\textbf{0}\\\
Y_{2}+\textrm{i}Y_{4}&\textbf{0}&\textbf{0}\\\
\end{array}\right).\end{aligned}$ (58)

Since $Y_{i}^{\dagger}=-Y_{i}$, Eq. (58) has the same form as Eq. (53).
Therefore, $[M_{1},M_{3}]\in\mathfrak{p}(3^{n})$, and
$[\mathfrak{l}(3^{n}),\mathfrak{p}(3^{n})]\subseteq\mathfrak{p}(3^{n})$.

Lastly, we prove that $\mathfrak{a}(3^{n})$ described by Eq. (47) is the
Cartan subalgebra of $(\mathfrak{u}(3^{n}),\mathfrak{l}(3^{n}))$. Obviously,
any element in $\mathfrak{a}(3^{n})$ commutes to each other. In the following,
we prove that $\mathfrak{a}(3^{n})$ is maximally Abelian contained in
$\mathfrak{p}(3^{n})$.

Given that any $A\in\mathfrak{p}(3^{n})$, $A$ can be expressed as

$\displaystyle A=\sigma_{x}^{01}\otimes A_{1}+\sigma_{y}^{01}\otimes
A_{2}+\sigma_{x}^{02}\otimes A_{3}+\sigma_{y}^{02}\otimes A_{4},$ (59)

where $A_{i}\in\mathfrak{u}(3^{n-1})$. Assume that $A$ and
$\mathfrak{a}(3^{n})$ are commutable, i.e.,
$[A,\mathfrak{a}(3^{n})]=\textbf{0}$, let us prove that
$A\in\mathfrak{a}(3^{n})$. Since $\sigma_{x}^{01}\otimes
I_{3^{n-1}}\in\mathfrak{a}(3^{n})$, we have

$\displaystyle A\cdot\sigma_{x}^{01}\otimes I_{3^{n-1}}=\sigma_{x}^{01}\otimes
I_{3^{n-1}}\cdot A.$ (60)

This leads to $A_{2}=A_{3}=A_{4}=\mathbf{0}$, and then
$A=\sigma_{x}^{01}\otimes A_{1}$.

Thus, $[A,\mathfrak{a}(3^{n})]=\textbf{0}$ implies that
$[A_{1},\alpha(3^{n-1})]=\textbf{0}$. By Lemma (see Appendix B), it follows
that $A_{1}\in\textrm{span}\\{\alpha(3^{n-1})\\}$, and then
$A\in\mathfrak{a}(3^{n})$. Therefore, $\mathfrak{a}(3^{n})$ is maximally
Abelian in $\mathfrak{p}(3^{n})$. $\hfill\blacksquare$

Decomposition of $\mathfrak{l}(3^{n})$. Note that $\mathfrak{l}(3^{n})$ is
isomorphic to $\mathfrak{u}(3^{n-1})\oplus\mathfrak{u}(2\times 3^{n-1})$.
Similarly to the two-qutrit case, $\mathfrak{l}(3^{n})$ can be further
decomposition.

Theorem 4.
$\mathfrak{l}(3^{n})=\mathfrak{l}_{1}(3^{n})\oplus\mathfrak{p}_{1}(3^{n})$ is
a Cartan decomposition of Lie subalgebra $\mathfrak{l}(3^{n})$ with

$\displaystyle\begin{aligned}
&\mathfrak{l}_{1}(3^{n})=\textrm{span}\\{\sigma_{z}^{01}\otimes
A,\sigma_{z}^{02}\otimes A,I_{3}\otimes A|A\in\mathfrak{u}(3^{n-1})\\},\\\
&\mathfrak{p}_{1}(3^{n})=\textrm{span}\\{\sigma_{x}^{12}\otimes
A,\sigma_{y}^{12}\otimes A,|A\in\mathfrak{u}(3^{n-1})\\},\\\
&\mathfrak{a}_{1}(3^{n})=\textrm{span}\\{\sigma_{x}^{12}\otimes
A|A\in\alpha(3^{n-1})\\}.\end{aligned}$ (61)

Here $\mathfrak{a}_{1}(3^{n})$ is the Cartan subalgebra of
$(\mathfrak{l}(3^{n}),\mathfrak{l}_{1}(3^{n}))$.

Proof 4. Firstly, we prove that
$[\mathfrak{l}_{1}(3^{n}),\mathfrak{l}_{1}(3^{n})]\subseteq\mathfrak{l}_{1}(3^{n})$.

For any $A_{1},A_{2}\in\mathfrak{u}(3^{n-1})$, we have the following relations

$\displaystyle\begin{aligned} &[I_{3}\otimes A_{1},\sigma_{z}^{0i}\otimes
A_{2}]=\sigma_{z}^{0i}\otimes[A_{1},A_{2}],\\\ &[\sigma_{z}^{0i}\otimes
A_{1},\sigma_{z}^{0j}\otimes
A_{2}]=\frac{I_{3}+\sigma_{z}^{0i}+\sigma_{z}^{0j}}{3}\otimes[A_{1},A_{2}],\\\
&[\sigma_{z}^{0i}\otimes A_{1},\sigma_{z}^{0i}\otimes
A_{2}]=\frac{2I_{3}+2\sigma_{z}^{0j}-\sigma_{z}^{0i}}{3}\otimes[A_{1},A_{2}],\end{aligned}$
(62)

where $i,j\in\\{0,1\\}$ and $i\neq j$. Eq. (62) and
$[A_{1},A_{2}]\in\mathfrak{u}(3^{n-1})$ indicate that
$[\mathfrak{l}_{1}(3^{n}),\mathfrak{l}_{1}(3^{n})]\subseteq\mathfrak{l}_{1}(3^{n})$.

Secondly, we prove that
$[\mathfrak{p}_{1}(3^{n}),\mathfrak{p}_{1}(3^{n})]\subseteq\mathfrak{l}_{1}(3^{n})$.

A calculation yields the following relations

$\displaystyle\begin{aligned} &[\sigma_{x}^{12}\otimes
A_{1},\sigma_{y}^{12}\otimes
A_{2}]=\sigma_{z}^{12}\otimes\textrm{i}(A_{1}A_{2}+A_{2}A_{1}),\\\
&[\sigma_{x}^{12}\otimes A_{1},\sigma_{x}^{12}\otimes
A_{2}]=\frac{2I_{3}-\sigma_{z}^{01}-\sigma_{z}^{02}}{3}\otimes[A_{1},A_{2}],\\\
&[\sigma_{y}^{12}\otimes A_{1},\sigma_{y}^{12}\otimes
A_{2}]=\frac{2I_{3}-\sigma_{z}^{01}-\sigma_{z}^{02}}{3}\otimes[A_{1},A_{2}].\end{aligned}$
(63)

Eq. (63) and $\sigma_{z}^{12}=\sigma_{z}^{02}-\sigma_{z}^{01}$ results in
$[\mathfrak{p}_{1}(3^{n}),\mathfrak{p}_{1}(3^{n})]\subseteq\mathfrak{l}_{1}(3^{n})$.

Thirdly, we prove that
$[\mathfrak{l}_{1}(3^{n}),\mathfrak{p}_{1}(3^{n})]\subseteq\mathfrak{p}_{1}(3^{n})$.

Any $M_{1}\in\mathfrak{l}_{1}(3^{n})$ and $M_{2}\in\mathfrak{p}_{1}(3^{n})$
can write as

$\displaystyle\begin{aligned} M_{1}=&I_{3}\otimes B_{1}+\sigma_{z}^{01}\otimes
B_{2}+\sigma_{z}^{02}\otimes B_{3}\\\
=&\left(\begin{array}[]{ccc}B_{1}+B_{2}+B_{3}&\textbf{0}&\textbf{0}\\\
\textbf{0}&B_{1}-B_{2}&\textbf{0}\\\ \textbf{0}&\textbf{0}&B_{1}-B_{3}\\\
\end{array}\right),\end{aligned}$ (64) $\displaystyle\begin{aligned}
M_{2}=&\sigma_{x}^{12}\otimes C_{1}+\sigma_{y}^{12}\otimes C_{2}\\\
=&\left(\begin{array}[]{ccc}\textbf{0}&\textbf{0}&\textbf{0}\\\
\textbf{0}&\textbf{0}&C_{1}-\textrm{i}C_{2}\\\
\textbf{0}&C_{1}+\textrm{i}C_{2}&\textbf{0}\\\
\end{array}\right).\end{aligned}$ (65)

Here $B_{k},C_{l}\in\mathfrak{u}(3^{n-1})$. $M_{1}$ and $M_{2}$ satisfy the
following relation

$\displaystyle\begin{aligned}
&[M_{1},M_{2}]=\left(\begin{array}[]{ccc}\textbf{0}&\textbf{0}&\textbf{0}\\\
\textbf{0}&\textbf{0}&M_{23}\\\ \textbf{0}&M_{32}&\textbf{0}\\\
\end{array}\right)\end{aligned}$ (66)

where $M_{23}^{\dagger}=-M_{32}$. By setting

$\displaystyle\begin{aligned}
&X_{1}=\frac{M_{23}+M_{32}}{2}\in\mathfrak{u}(3^{n-1}),\\\
&X_{2}=\textrm{i}\frac{M_{23}-M_{32}}{2}\in\mathfrak{u}(3^{n-1}),\end{aligned}$
(67)

Eq. (66) can be written as

$\displaystyle[M_{1},M_{2}]=\sigma_{x}^{12}\otimes
X_{1}+\sigma_{y}^{12}\otimes X_{2}.$ (68)

This means that $[M_{1},M_{2}]\in\mathfrak{p}_{1}(3^{n})$, and than
$[\mathfrak{l}_{1}(3^{n}),\mathfrak{p}_{1}(3^{n})]\subseteq\mathfrak{p}_{1}(3^{n})$.

Finally, we prove that $\mathfrak{a}_{1}(3^{n})$ described by Eq. (61) is a
Cartan subalgebra of the pair $(\mathfrak{l}(3^{n}),\mathfrak{l}_{1}(3^{n}))$.
It is clear that $\mathfrak{a}_{1}(3^{n})$ is Abelian. We now prove that
$\mathfrak{a}_{1}(3^{n})$ is maximally Abelian in $\mathfrak{p}_{1}(3^{n})$.

For any $A\in\mathfrak{p}_{1}(3^{n})$, let

$\displaystyle A=\sigma_{x}^{12}\otimes A_{1}+\sigma_{y}^{12}\otimes A_{2}$
(69)

where $A_{i}\in\mathfrak{u}(3^{n-1})$. Supposing that $A$ and
$\mathfrak{a}_{1}(3^{n})$ are commutable, as $\sigma_{x}^{12}\otimes
I_{3^{n-1}}\in\mathfrak{a}(3^{n})$, we have

$\displaystyle A\cdot\sigma_{x}^{12}\otimes I_{3^{n-1}}=\sigma_{x}^{12}\otimes
I_{3^{n-1}}\cdot A.$ (70)

Thus, $A=\sigma_{x}^{12}\otimes A_{1}$. By assumption, it follows that $A_{1}$
and $\textrm{span}\\{\alpha(3^{n-1})\\}$ are commutable. From Lemma, we have
$A\in\mathfrak{a}_{1}(3^{n})$. Therefore, the theorem follows.
$\hfill\blacksquare$

Decomposition of $\mathfrak{l}_{1}(3^{n})$. One can find that
$\mathfrak{l}_{1}(3^{n})$ is isomorphic to
$\mathfrak{u}(3^{n-1})\oplus\mathfrak{u}(3^{n-1})\oplus\mathfrak{u}(3^{n-1})$.
Utilizing Eq. (17), $\mathfrak{l}_{1}(3^{n})$ is rewritten as

$\displaystyle\begin{aligned}
\mathfrak{l}_{1}(3^{n})&=\textrm{span}\\{I_{3}\otimes A,D\otimes
A,\sigma_{z}^{12}\otimes A|A\in\mathfrak{u}(3^{n-1})\\}.\\\
&=\textrm{span}\\{I_{3}\otimes A,\overline{D}\otimes A,\sigma_{z}^{01}\otimes
A|A\in\mathfrak{u}(3^{n-1})\\}.\end{aligned}$ (71)

Then $\mathfrak{l}_{1}(3^{n})$ becomes decomposable and the decomposition
complies with the following Theorem.

Theorem 5. $\mathfrak{l}_{1}(3^{n})$ has the following Cartan decomposition

$\displaystyle\begin{aligned}
&\mathfrak{l}_{1}(3^{n})=\mathfrak{l}_{2}(3^{n})\oplus\mathfrak{p}_{2}(3^{n}),\\\
&\mathfrak{l}_{2}(3^{n})=\textrm{span}\\{I_{3}\otimes A,D\otimes
A|A\in\mathfrak{u}(3^{n-1})\\},\\\
&\mathfrak{p}_{2}(3^{n})=\textrm{span}\\{\sigma_{z}^{12}\otimes
A|A\in\mathfrak{u}(3^{n-1})\\},\\\
&\mathfrak{a}_{2}(3^{n})=\textrm{span}\\{\sigma_{z}^{12}\otimes
A|A\in\widetilde{\alpha}(3^{n-1})\\}\subset\mathfrak{p}_{2}(3^{n}).\end{aligned}$
(72)

Here $\mathfrak{a}_{2}(3^{n})$ is the Cartan subalgebra of
$(\mathfrak{l}_{1}(3^{n}),\mathfrak{l}_{2}(3^{n}))$ and

$\displaystyle\begin{aligned}
&\widetilde{\alpha}(3)=\\{\textrm{i}I_{3},\textrm{i}D,\textrm{i}\sigma_{z}^{12}\\},\\\
&\widetilde{\alpha}(3^{n})=\\{I_{3}\otimes A,D\otimes A,\sigma_{z}^{12}\otimes
A|A\in\widetilde{\alpha}(3^{n-1})\\}.\end{aligned}$ (73)

In addition, there is another Cartan decomposition of
$\mathfrak{l}_{1}(3^{n})$ as follows

$\displaystyle\begin{aligned}
&\mathfrak{l}_{1}(3^{n})=\overline{\mathfrak{l}_{2}}(3^{n})\oplus\overline{\mathfrak{p}_{2}}(3^{n}),\\\
&\overline{\mathfrak{l}_{2}}(3^{n})=\textrm{span}\\{I_{3}\otimes
A,\overline{D}\otimes A|A\in\mathfrak{u}(3^{n-1})\\},\\\
&\overline{\mathfrak{p}_{2}}(3^{n})=\textrm{span}\\{\sigma_{z}^{01}\otimes
A|A\in\mathfrak{u}(3^{n-1})\\}.\end{aligned}$ (74)

Proof 5. Given any $A_{1},A_{2}\in\mathfrak{u}(3^{n-1})$, there are the
following commutation relations

$\displaystyle\begin{aligned} &[I_{3}\otimes A_{1},D\otimes
A_{2}]=D\otimes[A_{1},A_{2}],\end{aligned}$ (75) $\displaystyle\begin{aligned}
&[D\otimes A_{1},D\otimes A_{2}]=I_{3}\otimes[A_{1},A_{2}],\end{aligned}$ (76)
$\displaystyle\begin{aligned} &[I_{3}\otimes A_{1},\sigma_{z}^{12}\otimes
A_{2}]=\sigma_{z}^{12}\otimes[A_{1},A_{2}],\end{aligned}$ (77)
$\displaystyle\begin{aligned} &[D\otimes A_{1},\sigma_{z}^{12}\otimes
A_{2}]=-\sigma_{z}^{12}\otimes[A_{1},A_{2}],\end{aligned}$ (78)
$\displaystyle\begin{aligned} &[\sigma_{z}^{12}\otimes
A_{1},\sigma_{z}^{12}\otimes
A_{2}]=\frac{I_{3}-D}{2}\otimes[A_{1},A_{2}].\end{aligned}$ (79)

Eqs. (75) and (76) indicate that
$[\mathfrak{l}_{2}(3^{n}),\mathfrak{l}_{2}(3^{n})]\subseteq\mathfrak{l}_{2}(3^{n})$.
Eqs. (77) and (80) indicate that
$[\mathfrak{l}_{2}(3^{n}),\mathfrak{p}_{2}(3^{n})]\subseteq\mathfrak{p}_{2}(3^{n})$.
Eq. (79) indicates that
$[\mathfrak{p}_{2}(3^{n}),\mathfrak{p}_{2}(3^{n})]\subseteq\mathfrak{l}_{2}(3^{n})$.
Similarly, Eq. (74) is found to hold by simply replacing $D$ with
$\overline{D}$ and $\sigma_{z}^{12}$ with $\sigma_{z}^{01}$ in Eqs. (75-79).

Now prove that $\mathfrak{a}_{2}(3^{n})$ is a Cartan subalgebra of the pair
$(\mathfrak{l}_{1}(3^{n}),\mathfrak{l}_{2}(3^{n}))$. From Eq. (17), it can be
found that

$\displaystyle\textrm{span}\\{\widetilde{\alpha}(3^{n})\\}=\textrm{span}\\{\alpha(3^{n})\\}.$
(80)

Under Lemma, it follows that $\textrm{span}\\{\widetilde{\alpha}(3^{n-1})\\}$
is the maximally Abelian in $\mathfrak{u}(3^{n-1})$. Recalling the definition
of $\mathfrak{a}_{2}(3^{n})$ results in $\mathfrak{a}_{2}(3^{n})$ being
maximally Abelian in $\mathfrak{p}_{2}(3^{n})$. $\hfill\blacksquare$

Decomposition of $\mathfrak{l}_{2}(3^{n})$ and
$\overline{\mathfrak{l}_{2}}(3^{n})$. Note that both $\mathfrak{l}_{2}(3^{n})$
and $\overline{\mathfrak{l}_{2}}(3^{n})$ are isomorphic to
$\mathfrak{u}(3^{n-1})\oplus\mathfrak{u}(3^{n-1})$. It is possible to further
distinguish between local contents and the nonlocal among them.

Theorem 6.
$\mathfrak{l}_{2}(3^{n})=\mathfrak{l}_{3}(3^{n})\oplus\mathfrak{p}_{3}(3^{n})$
is a Cartan decomposition of $\mathfrak{l}_{2}(3^{n})$ with a Cartan
subalgebra $\mathfrak{a}_{3}(3^{n})$, where

$\displaystyle\begin{aligned}
&\mathfrak{l}_{3}(3^{n})=\textrm{span}\\{I_{3}\otimes
A|A\in\mathfrak{u}(3^{n-1})\\},\\\
&\mathfrak{p}_{3}(3^{n})=\textrm{span}\\{D\otimes
A|A\in\mathfrak{u}(3^{n-1})\\},\\\
&\mathfrak{a}_{3}(3^{n})=\textrm{span}\\{D\otimes
A|A\in\widetilde{\alpha}(3^{n-1})\\}.\end{aligned}$ (81)

$\overline{\mathfrak{l}_{2}}(3^{n})$ has the following Cartan decomposition

$\displaystyle\begin{aligned}
&\overline{\mathfrak{l}_{2}}(3^{n})=\mathfrak{l}_{3}(3^{n})\oplus\overline{\mathfrak{p}_{3}}(3^{n}),\\\
&\overline{\mathfrak{p}_{3}}(3^{n})=\textrm{span}\\{\overline{D}\otimes
A|A\in\mathfrak{u}(3^{n-1})\\},\\\
&\overline{\mathfrak{a}_{3}}(3^{n})=\textrm{span}\\{\overline{D}\otimes
A|A\in\overline{\alpha}(3^{n-1})\\}.\\\ \end{aligned}$ (82)

Here $\overline{\mathfrak{a}_{3}}(3^{n})$ is the Cartan subalgebra of
$(\overline{\mathfrak{l}_{2}}(3^{n}),\mathfrak{l}_{3}(3^{n}))$ and

$\displaystyle\begin{aligned}
&\overline{\alpha}(3)=\\{\textrm{i}I_{3},\textrm{i}\overline{D},\textrm{i}\sigma_{z}^{01}\\},\\\
&\overline{\alpha}(3^{n})=\\{I_{3}\otimes A,\overline{D}\otimes
A,\sigma_{z}^{01}\otimes A|A\in\overline{\alpha}(3^{n-1})\\}.\end{aligned}$
(83)

Proof 6. Given any $A_{1},A_{2}\in\mathfrak{u}(3^{n-1})$, the following
relations

$\displaystyle\begin{aligned} &[I_{3}\otimes A_{1},D\otimes
A_{2}]=D\otimes[A_{1},A_{2}],\\\ &[D\otimes A_{1},D\otimes
A_{2}]=I_{3}\otimes[A_{1},A_{2}],\\\ &[I_{3}\otimes A_{1},\overline{D}\otimes
A_{2}]=\overline{D}\otimes[A_{1},A_{2}],\\\ &[\overline{D}\otimes
A_{1},\overline{D}\otimes A_{2}]=I_{3}\otimes[A_{1},A_{2}],\end{aligned}$ (84)

indicate that $\mathfrak{l}_{3}(3^{n})$ and $\mathfrak{p}_{3}(3^{n})$
($\overline{\mathfrak{p}_{3}}(3^{n})$) satisfy Eq. (2). From Eq. (17), it is
obvious that

$\displaystyle\textrm{span}\\{\overline{\alpha}(3^{n})\\}=\textrm{span}\\{\widetilde{\alpha}(3^{n})\\}=\textrm{span}\\{\alpha(3^{n})\\},$
(85)

By Lemme 1, $\mathfrak{a}_{3}(n)$ and $\overline{\mathfrak{a}_{3}}(n)$ are
Cartan subalgebras. $\hfill\blacksquare$

Figure 9: (a) Cartan decomposition of $\mathfrak{u}(3^{n})$ and
$\mathfrak{l}(3^{n})$. (b) Cartan decomposition of $\mathfrak{l}_{1}(3^{n})$
and $\mathfrak{l}_{2}(3^{n})$ with the diagonal basis
$\widetilde{\alpha}(3^{n})$. (c) Cartan decomposition of
$\mathfrak{l}_{1}(3^{n})$ and $\overline{\mathfrak{l}_{2}}(3^{n})$ with the
diagonal basis $\overline{\alpha}(3^{n})$.

Based on the above successive Cartan decompositions of $\mathfrak{u}(3^{n})$
depicted by Fig. 9, we can reduce the $n$-qutrit gate to local and nonlocal
operations, see Corollary 2. Its proof is a direct extension of that of
Corollary 1.

Corollary 2. Any $M\in U(3^{n})$ can be decomposed as

$\displaystyle\begin{aligned} M=&K_{1}\cdot\overline{A}^{(3)}_{1}\cdot
K_{2}\cdot A^{(1)}_{1}\cdot K_{3}\cdot A^{(3)}_{1}\cdot K_{4}\cdot A\cdot
K_{5}\\\ &\cdot\overline{A}^{(3)}_{2}\cdot K_{6}\cdot A^{(1)}_{2}\cdot
K_{7}\cdot A^{(2)}\cdot K_{8}\cdot A^{(3)}_{2}\cdot K_{9}.\end{aligned}$ (86)

Here $A\in\textrm{exp}[\mathfrak{a}(3^{n})]$,
$A^{(1)}_{1,2}\in\textrm{exp}[\mathfrak{a}_{1}(3^{n})]$,
$A^{(2)}\in\textrm{exp}[\mathfrak{a}_{2}(3^{n})]$,
$A^{(3)}_{1,2}\in\textrm{exp}[\mathfrak{a}_{3}(3^{n})]$,
$\overline{A}^{(3)}_{1,2}\in\textrm{exp}[\overline{\mathfrak{a}_{3}}(3^{n})]$,
and $K_{i}\in\textrm{exp}[\mathfrak{l}_{3}(3^{n})]$ is an ($n-1$)-qutrit gate.

###  IV.2 Synthesis of arbitrary _n_ -qutrit gates

Note that $K_{i}$ can be decomposed again into the form of Eq. (86) as
$\mathfrak{l}_{3}(3^{n})$ is isomorphic to $\mathfrak{u}(3^{n-1})$. To
complete the construction of arbitrary $n$-qutrit gates in terms of single-
qutrit type rotations and GCXs, next we synthesize nonlocal operations $A$,
$A^{(1)}_{1,2}$, $A^{(2)}$, $A^{(3)}_{1,2}$, and $\overline{A}^{(3)}_{1,2}$.

Synthesis of _n_ -qutrit operation $A$. Based on Eq. (47), $n$-qutrit nonlocal
operation $A$ has the form

$\displaystyle\begin{aligned}
A(\hat{\theta})=\textrm{exp}[-\textrm{i}\sigma_{x}^{01}\otimes
A_{1}(\hat{\theta})].\end{aligned}$ (87)

Here $\textrm{i}A_{1}(\hat{\theta})\in\text{span}\\{\alpha(3^{n-1})\\}$ is a
$3^{n-1}\times 3^{n-1}$ diagonal matrix depending on $3^{n-1}$ real
parameters. Hence without loss of generality $A_{1}(\hat{\theta})$ has the
form

$\displaystyle\begin{aligned}
A_{1}(\hat{\theta})=\textrm{diag}\\{&\underline{\theta_{11},\theta_{12},\theta_{13}},\underline{\theta_{21},\theta_{22},\theta_{23}},\underline{\theta_{31},\theta_{32},\theta_{33}},\\\
&\cdots,\underline{\theta_{3^{n-2}1},\theta_{3^{n-2}2},\theta_{3^{n-2}3}}\\}.\end{aligned}$
(88)

Using Theorem 1, we obtain

$\displaystyle\begin{aligned}
A(\hat{\theta})=&R_{y}^{01}(\frac{\pi}{2})\otimes
I_{3^{n-1}}\cdot\textrm{exp}[-\textrm{i}\sigma_{z}^{01}\otimes
A_{1}(\hat{\theta})]\\\ &\cdot R_{y}^{01}(-\frac{\pi}{2})\otimes
I_{3^{n-1}}\\\ =&R_{y}^{01}(\frac{\pi}{2})\otimes
I_{3^{n-1}}\cdot\textrm{GCX}_{n}^{1}(1\rightarrow X^{01})\\\
&\cdot\textrm{exp}[-\textrm{i}\sigma_{z}^{01}\otimes
A_{2}(\hat{\theta}_{1})]\otimes I_{3}\\\
&\cdot\textrm{GCX}_{n}^{1}(0\rightarrow X^{01})\cdot X^{01}\otimes
I_{3^{n-1}}\\\ &\cdot\textrm{exp}[-\textrm{i}\sigma_{z}^{01}\otimes
A_{2}(\hat{\theta}_{2})]\otimes I_{3}\\\
&\cdot\textrm{GCX}_{n}^{1}(2\rightarrow X^{01})\\\
&\cdot\textrm{exp}[-\textrm{i}\sigma_{z}^{01}\otimes
A_{2}(\hat{\theta}_{3})]\otimes I_{3}\\\ &\cdot
R_{y}^{01}(-\frac{\pi}{2})\otimes I_{3^{n-1}},\end{aligned}$ (89)

where

$\displaystyle\begin{aligned}
A_{2}(\hat{\theta}_{1})=\textrm{diag}\\{&\frac{\theta_{11}-\theta_{12}}{2},\frac{\theta_{21}-\theta_{22}}{2},\cdots,\\\
&\frac{\theta_{3^{n-2}1}-\hat{\theta}_{3^{n-2}2}}{2}\\},\\\
A_{2}(\hat{\theta}_{2})=\textrm{diag}\\{&\frac{\theta_{11}-\theta_{13}}{2},\frac{\theta_{21}-\theta_{23}}{2},\cdots,\\\
&\frac{\theta_{3^{n-2}1}-\hat{\theta}_{3^{n-2}3}}{2}\\},\\\
A_{2}(\hat{\theta}_{3})=\textrm{diag}\\{&\frac{\theta_{12}+\theta_{13}}{2},\frac{\theta_{22}+\theta_{23}}{2},\cdots,\\\
&\frac{\theta_{3^{n-2}2}+\hat{\theta}_{3^{n-2}3}}{2}\\}.\end{aligned}$ (90)

It is remarkable that
$\textrm{i}A_{2}(\hat{\theta}_{i})\in\textrm{span}\\{\alpha(3^{n-2})\\}$.
Thus, Eq. (89) is a recursive decomposition until
$\textrm{i}A_{n-1}\in\textrm{span}\\{\alpha(3)\\}$, see Fig. 10.

Figure 10: The recursive decomposition of $n$-qutrit gate $A(\hat{\theta})$.
Here $\textrm{i}A_{k}\in\text{span}\\{\alpha(3^{n-k})\\}$ and
$\textrm{exp}[-\textrm{i}\sigma_{z}^{01}\otimes A_{k}]$ is an $(n-k+1)$-qutrit
gate.

Synthesis of _n_ -qutrit operation $A^{(1)}_{1,2}$. A similar argument as that
made in $A$, the iterative decomposition of $A_{1,2}^{(1)}$ is given by

$\displaystyle\begin{aligned}
A^{(1)}(\hat{\theta})=&\textrm{exp}[-\textrm{i}\sigma_{x}^{12}\otimes
A_{1}(\hat{\theta})]\\\ =&R_{y}^{12}(\frac{\pi}{2})\otimes
I_{3^{n-1}}\cdot\textrm{GCX}_{n}^{1}(1\rightarrow X^{12})\\\
&\cdot\textrm{exp}[-\textrm{i}\sigma_{z}^{12}\otimes
A_{2}(\hat{\theta}_{1})]\otimes I_{3}\\\
&\cdot\textrm{GCX}_{n}^{1}(0\rightarrow X^{12})\cdot X^{12}\otimes
I_{3^{n-1}}\\\ &\cdot\textrm{exp}[-\textrm{i}\sigma_{z}^{12}\otimes
A_{2}(\hat{\theta}_{2})]\otimes I_{3}\\\
&\cdot\textrm{GCX}_{n}^{1}(2\rightarrow X^{12})\\\
&\cdot\textrm{exp}[-\textrm{i}\sigma_{z}^{12}\otimes
A_{2}(\hat{\theta}_{3})]\otimes I_{3}\\\ &\cdot
R_{y}^{12}(-\frac{\pi}{2})\otimes I_{3^{n-1}}.\end{aligned}$ (91)

An $n$-qutrit gate with matrix form
$\textrm{exp}[-\textrm{i}\sigma_{\varphi}^{ij}\otimes A_{1}(\hat{\theta})]$ or
$\textrm{exp}[-\textrm{i}A_{1}(\hat{\theta})\otimes\sigma_{\varphi}^{ij}]$ is
a three-valued uniformly $(n-1)$-fold controlled $R_{\varphi}^{ij}$ rotation
in Ref. Di2013 . In quantum circuit diagrams, the square ($\Box$) denotes the
control qutrits of such logic gate and the slash ($/$) denotes multiple
qutrits on the line. Following this manner, the synthesized circuit of
$A(\hat{\theta})$ and $A^{(1)}(\hat{\theta})$ is presented in Fig. 11.

Figure 11: Synthesis of $n$-qutrit gate $A$ with $ij=01$ or $A^{(1)}_{1,2}$
with $ij=12$. Note that $X^{ij}$ can be decomposed into three single-qutrit
type rotation gates by Eq. (31) or (34) up to a global phase
$e^{\textrm{i}\frac{\pi}{3}}$.

Synthesis of _n_ -qutrit operation $A^{(2)}$. Since the relation
span$\\{\widetilde{\alpha}(3^{n})\\}=\text{span}\\{\alpha(3^{n})\\}$, we can
obtain

$\displaystyle\begin{aligned}
A^{(2)}(\hat{\theta})=&\textrm{exp}[-\textrm{i}\sigma_{z}^{12}\otimes
A_{1}(\hat{\theta})]\\\ =&R_{y}^{12}(-\frac{\pi}{2})\otimes
I_{3^{n-1}}\cdot\textrm{exp}[-\textrm{i}\sigma_{x}^{12}\otimes
A_{1}(\hat{\theta})]\\\ &\cdot R_{y}^{12}(\frac{\pi}{2})\otimes
I_{3^{n-1}}.\end{aligned}$ (92)

Based on Eq. (91), one can get that the recursive decomposition of
$A^{(2)}(\hat{\theta})$ as follows

$\displaystyle\begin{aligned}
A^{(2)}(\hat{\theta})=&\textrm{GCX}_{n}^{1}(1\rightarrow X^{12})\\\
&\cdot\textrm{exp}[-\textrm{i}\sigma_{z}^{12}\otimes
A_{2}(\hat{\theta}_{1})]\otimes I_{3}\\\
&\cdot\textrm{GCX}_{n}^{1}(0\rightarrow X^{12})\cdot X^{12}\otimes
I_{3^{n-1}}\\\ &\cdot\textrm{exp}[-\textrm{i}\sigma_{z}^{12}\otimes
A_{2}(\hat{\theta}_{2})]\otimes I_{3}\\\
&\cdot\textrm{GCX}_{n}^{1}(2\rightarrow X^{12})\\\
&\cdot\textrm{exp}[-\textrm{i}\sigma_{z}^{12}\otimes
A_{2}(\hat{\theta}_{3})]\otimes I_{3}.\end{aligned}$ (93)

The synthesis of $A^{(2)}$ is given by Fig. 12.

Figure 12: Synthesis of $n$-qutrit gate $A^{(2)}$.

Synthesis of _n_ -qutrit operation $A_{1,2}^{(3)}$ and
$\overline{A}^{(3)}_{1,2}$. Based on Eq. (81), $A^{(3)}_{1,2}$ can be given by

$\displaystyle\begin{aligned}
A^{(3)}(\hat{\theta})=&\textrm{exp}[-\textrm{i}D\otimes
A_{1}(\hat{\theta})]\\\ =&\textrm{GCX}_{1}^{n}(0\rightarrow X^{02})\\\ &\cdot
I_{3}\otimes\textrm{exp}[-\textrm{i}A_{2}(\hat{\theta}_{4})\otimes\sigma_{z}^{02}]\\\
&\cdot\textrm{GCX}_{1}^{n}(0\rightarrow X^{02})\\\
&\cdot\textrm{GCX}_{1}^{n}(0\rightarrow X^{01})\\\ &\cdot
I_{3}\otimes\textrm{exp}[-\textrm{i}A_{2}(\hat{\theta}_{5})\otimes\sigma_{z}^{01}]\\\
&\cdot\textrm{GCX}_{1}^{n}(0\rightarrow X^{01})\\\
&\cdot\textrm{exp}[-\textrm{i}D\otimes A_{2}(\hat{\theta}_{6})]\otimes
I_{3},\end{aligned}$ (94)

where

$\displaystyle\begin{aligned}
A_{2}(\hat{\theta}_{4})=\textrm{diag}\\{&\frac{2\theta_{13}-\theta_{11}-\theta_{12}}{3},\frac{2\theta_{23}-\theta_{21}-\theta_{22}}{3},\\\
&\cdots,\frac{2\theta_{3^{n-2}3}-\theta_{3^{n-2}1}-\theta_{3^{n-2}2}}{3}\\},\\\
A_{2}(\hat{\theta}_{5})=\textrm{diag}\\{&\frac{2\theta_{12}-\theta_{11}-\theta_{13}}{3},\frac{2\theta_{22}-\theta_{21}-\theta_{23}}{3},\\\
&\cdots,\frac{2\theta_{3^{n-2}2}-\theta_{3^{n-2}1}-\theta_{3^{n-2}3}}{3}\\},\\\
A_{2}(\hat{\theta}_{6})=\textrm{diag}\\{&\frac{\theta_{11}+\theta_{12}+\theta_{13}}{3},\frac{\theta_{21}+\theta_{22}+\theta_{23}}{3},\\\
&\cdots,\frac{\theta_{3^{n-2}1}+\theta_{3^{n-2}2}+\theta_{3^{n-2}3}}{3}\\}.\end{aligned}$
(95)

Observe that Eq. (94) can be applied to recursively decompose the last term
$\textrm{exp}[-\textrm{i}D\otimes A_{2}(\hat{\theta}_{6})]$.

Since span$\\{\overline{\alpha}(3^{n})\\}=\text{span}\\{\alpha(3^{n})\\}$,
$\overline{A}^{(3)}_{1,2}$ has a decomposition form similar to $A^{(3)}_{1,2}$
as follows

$\displaystyle\begin{aligned}
\overline{A}^{(3)}(\hat{\theta})=&\textrm{exp}[-\textrm{i}\overline{D}\otimes
A_{1}(\hat{\theta})]\\\ =&\textrm{GCX}_{1}^{n}(2\rightarrow X^{02})\\\ &\cdot
I_{3}\otimes\textrm{exp}[-\textrm{i}A_{2}(\hat{\theta}_{4})\otimes\sigma_{z}^{02}]\\\
&\cdot\textrm{GCX}_{1}^{n}(2\rightarrow X^{02})\\\
&\cdot\textrm{GCX}_{1}^{n}(2\rightarrow X^{01})\\\ &\cdot
I_{3}\otimes\textrm{exp}[-\textrm{i}A_{2}(\hat{\theta}_{5})\otimes\sigma_{z}^{01}]\\\
&\cdot\textrm{GCX}_{1}^{n}(2\rightarrow X^{01})\\\
&\cdot\textrm{exp}[-\textrm{i}\overline{D}\otimes
A_{2}(\hat{\theta}_{6})]\otimes I_{3},\end{aligned}$ (96)

In addition, the synthetic circuit of the $n$-qutrit gate
$\textrm{exp}[-\textrm{i}A_{1}(\hat{\theta})\otimes\sigma_{z}^{0t}]$ $(t=1,2)$
is shown in Fig. 13. Thus, we have completed the recursive decompositions of
$A^{(3)}_{1,2}(\hat{\theta})$ and $\overline{A}^{(3)}_{1,2}(\hat{\theta})$ and
Fig. 14 presents the first step of the decomposition.

Figure 13: Synthesis of $n$-qutrit gate
$\textrm{exp}[-\textrm{i}A_{1}(\hat{\theta})\otimes\sigma_{z}^{0t}]$
$(t=1,2)$. Figure 14: Synthesis of $n$-qutrit gate $A_{1,2}^{(3)}$ with $m=0$
or $\overline{A}_{1,2}^{(3)}$ with $m=2$. Here the $(n-1)$-qutrit gates
$\widetilde{A}_{0}^{(3)}=\textrm{exp}[-\textrm{i}D\otimes
A_{2}(\hat{\theta}_{6})]$ and
$\widetilde{A}_{2}^{(3)}=\textrm{exp}[-\textrm{i}\overline{D}\otimes
A_{2}(\hat{\theta}_{6})]$. Note that two adjacent GCX gates here can be
combined into a CINC gate.

Synthesis of the arbitrary _n_ -qutrit gate. By successively applying
Corollary 2 to decompose $K_{i}$, $M$ can be decomposed into generic two-
qutrit gates and specific non-local operations $A$, $A^{(1)}$, $A^{(2)}$,
$A^{(3)}$, and $\overline{A}^{(3)}$. The synthesis of components as two-qutrit
gates is presented in Sec. III, and then in conjunction with Fig. 11, Fig. 12,
Fig. 13, and Fig. 14, the synthesis of arbitrary $n$-qutrit gates is
accomplished.

Similarly to the case of $n=2$, the rightmost GCX of Fig. 11 can be absorbed.
Since $\textrm{GCX}^{k}_{l_{1}}(m_{1}\rightarrow X^{ij})$ and
$\textrm{GCX}^{k}_{l_{2}}(m_{2}\rightarrow X^{ij})$ are commutative, the
structure shown in the dotted box of Fig. 11 has two GCX gates that are
cancelled out in the next step of the decomposition. Based on the above
discussion, the required GCX gates for these non-local operators are shown in
Table 1.

Table 1: The GCX gate count for the synthesis of $n$-qutrit gates $A$, $A^{(1)}_{1,2}$, $A^{(2)}$, $A^{(3)}_{1,2}$, and $\overline{A}^{(3)}_{1,2}$.  | 2 | 3 | 4 | $n\geq 2$
---|---|---|---|---
$A/A^{(1)}_{1,2}$ | 2 | 8 | 26 | $3^{n-1}-1$
$A^{(2)}$ | 3 | 10 | 29 | $3^{n-1}+n-2$
$A^{(3)}_{1,2}/\overline{A}^{(3)}_{1,2}$ | 4 | 14 | 38 | $3^{n-1}+n^{2}-n-1$

According to Table 1, the GCX gate count for an exact synthesis of $M$ can be
calculated as

$\displaystyle\begin{aligned} \frac{47}{96}\cdot 3^{2n}-4\cdot
3^{n-1}-(\frac{n^{2}}{2}+\frac{3n}{4}-\frac{27}{32}).\end{aligned}$ (97)

##  V Conclusion

Multi-valued quantum computing is currently a well-attended research area, as
the advantages of qudit circuits are gradually being discovered. In this
paper, we propose a Cartan decomposition of $U(3^{2})$ that divides arbitrary
two-qutrit gates into single-qutrit gates and non-local transitions, i.e.,
$A$, $A^{(1)}$, $A^{(2)}$, $A^{(3)}$, and $\overline{A}^{(3)}$. Based on
Corollary 1 derived from the decomposition, we design a quantum circuit of
generic two-qutrit gates as shown in Fig. 3, where the non-local operations
are simulated exactly by simple elementary gates, i.e., GCX, CINC, and
$R_{\varphi}^{ij}(\theta)$ gates. In the presented two-qutrit circuit, up to
21 GCXs and CINCs are necessary, whereas the previously optimal circuit
required 26 in the worst case Di2015 .

Furthermore, a recursive Cartan decomposition of $U(3^{n})$ and its proof are
given, which divides arbitrary $n$-qutrit gates into $(n-1)$-qutrit gates that
can be decomposed again and non-local transformations described in Corollary
2. Relying on Corollary 2, we propose a recursive algorithm to synthesize an
arbitrary $n$-qutrit gate that terminates in the two-qutrit case. The quantum
circuit of generic $n$-qutrit gates constructed by the recursive program is
asymptotically optimal. When only GCX gates are chosen as the elementary two-
qutrit gate to simulate the non-local operators, the total number of GCX gates
required for the synthetic circuit is shown as Eq. (97), which is less than
the previously optimal QSD-based circuit Di2013 ; Di2015 . Remarkably, when
the CINC gates have been introduced as elementary gates, the cost of the
presented circuit can be further reduced by $\frac{1}{16}\cdot
3^{2n}-\frac{n}{2}-\frac{1}{16}$ elementary two-qutrit gates. As shown in
Table 2, we have compared it with the previous QR-, CSD-, and QSD-based
synthesis, which concludes our program is the optimum.

Table 2: The comparison of elementary two-qutrit gate count for the synthesis of a general $n$-qutrit gate. | 2 | 3 | 4 | $n\geq 2$
---|---|---|---|---
QR Bullock2005  | 45 | 675 | 6561 | $3^{2n}+3^{n}\cdot(2n-8)$
CSD Nakajima2009  | 36 | 3360 | 20088 | ——
QSD Di2013  | 44 | 692 | 6860 | ——
QSD,optimal Di2015  | 26 | 344 | 3458 | $O(\alpha 3^{2n})$
Our work | 21 | 217 | 2686 | $\frac{41}{96}\cdot 3^{2n}-4\cdot 3^{n-1}$
$-(\frac{n^{2}}{2}+\frac{n}{4}-\frac{29}{32})$

With the improvement of optical implementations of three-valued quantum
systems, the proposed synthesis facilitates the physical implementation of
$n$-qutrit gates. In addition, to coincide with the lower bound of complexity
for generic $n$-qutrit circuits, there may be room for improvement through
optimizing non-local transformations and reducing $(n-1)$-qutrit gates
generated by the first step of the decomposition.

## ACKNOWLEDGEMENTS

This work is supported by the National Natural Science Foundation of China
under Grant No. 62371038 and the Fundamental Research Funds for the Central
Universities under Grant No. FRF-TP-19-011A3.

## appendix

##  Appendix A Proof of Corollary 1

Based on the Cartan decomposition of $\mathfrak{u}(9)$ and $\mathfrak{l}(9)$
as shown Fig. 2, for any $M\in U(9)$, we have

$\displaystyle\begin{aligned} M=K_{1}^{\prime}\cdot A^{(1)}_{1}\cdot
K_{2}^{\prime}\cdot A\cdot K_{3}^{\prime}\cdot A^{(1)}_{2}\cdot
K_{4}^{\prime}.\end{aligned}$ (98)

Here $K_{i}^{\prime}\in\textrm{exp}[\mathfrak{l}_{1}(9)]$,
$A\in\textrm{exp}[\mathfrak{a}(9)]$, and
$A^{(1)}_{1,2}\in\textrm{exp}[\mathfrak{a}_{1}(9)]$. From the definition of
$\mathfrak{l}_{1}(9)$, $K_{i}^{\prime}$ can be written as

$\displaystyle\begin{aligned}
K_{i}^{\prime}=\left(\begin{array}[]{ccc}U_{i1}&\textbf{0}&\textbf{0}\\\
\textbf{0}&U_{i2}&\textbf{0}\\\ \textbf{0}&\textbf{0}&U_{i3}\\\
\end{array}\right),\end{aligned}$ (99)

where $U_{ij}\in U(3)$ and $i=1,2,3,4$, $j=1,2,3$. According to the
subalgebras $\mathfrak{a}(9)$ and $\mathfrak{a}_{1}(9)$ chosen as in Eqs. (12)
and (14), $A$ and $A^{(1)}_{1,2}$ can be expressed as

$\displaystyle\begin{aligned}
A&=\left(\begin{array}[]{ccc}C_{0}&-\textrm{i}S_{0}&\textbf{0}\\\
-\textrm{i}S_{0}&C_{0}&\textbf{0}\\\ \textbf{0}&\textbf{0}&I_{3}\\\
\end{array}\right),\\\
A^{(2)}_{1}&=\left(\begin{array}[]{ccc}I_{3}&\textbf{0}&\textbf{0}\\\
\textbf{0}&C_{1}&-\textrm{i}S_{1}\\\ \textbf{0}&-\textrm{i}S_{1}&C_{1}\\\
\end{array}\right),\\\
A^{(2)}_{2}&=\left(\begin{array}[]{ccc}I_{3}&\textbf{0}&\textbf{0}\\\
\textbf{0}&C_{2}&-\textrm{i}S_{2}\\\ \textbf{0}&-\textrm{i}S_{2}&C_{2}\\\
\end{array}\right).\end{aligned}$ (100)

Here
$C_{k}=\textrm{diag}\\{\textrm{cos}\alpha_{k1},\textrm{cos}\alpha_{k2},\textrm{cos}\alpha_{k3}\\}$
and
$S_{k}=\textrm{diag}\\{\textrm{sin}\alpha_{k1},\textrm{sin}\alpha_{k2},\textrm{sin}\alpha_{k3}\\}$,
and $k=0,1,2$.

Substituting Eqs. (99) and (100) into Eq. (98) and using the multiplication of
the block diagonal matrices, we can get

$\displaystyle\begin{aligned} M=K_{1}^{\prime\prime}\cdot A^{(1)}_{1}\cdot
K_{2}^{\prime\prime}\cdot A\cdot K_{3}^{\prime\prime}\cdot A^{(1)}_{2}\cdot
K_{4}^{\prime\prime}.\end{aligned}$ (101)

where

$\displaystyle\begin{aligned}
&K_{1}^{\prime\prime}=\left(\begin{array}[]{ccc}U_{12}&\textbf{0}&\textbf{0}\\\
\textbf{0}&U_{12}&\textbf{0}\\\ \textbf{0}&\textbf{0}&U_{13}\\\
\end{array}\right),\\\
&K_{2}^{\prime\prime}=\left(\begin{array}[]{ccc}U_{12}^{{\dagger}}U_{11}U_{21}&\textbf{0}&\textbf{0}\\\
\textbf{0}&U_{22}&\textbf{0}\\\ \textbf{0}&\textbf{0}&U_{22}\\\
\end{array}\right),\\\
&K_{3}^{\prime\prime}=\left(\begin{array}[]{ccc}U_{32}&\textbf{0}&\textbf{0}\\\
\textbf{0}&U_{32}&\textbf{0}\\\
\textbf{0}&\textbf{0}&U_{22}^{{\dagger}}U_{23}U_{33}\\\ \end{array}\right),\\\
&K_{4}^{\prime\prime}=\left(\begin{array}[]{ccc}U_{32}^{{\dagger}}U_{31}U_{41}&\textbf{0}&\textbf{0}\\\
\textbf{0}&U_{42}&\textbf{0}\\\ \textbf{0}&\textbf{0}&U_{43}\\\
\end{array}\right).\end{aligned}$ (102)

Observe that
$K_{1,3}^{\prime\prime}\in\textrm{exp}[\overline{\mathfrak{l}_{2}}(9)$],
$K_{2}^{\prime\prime}\in\textrm{exp}[\mathfrak{l}_{2}(9)]$, and
$K_{4}^{\prime\prime}\in\textrm{exp}[\mathfrak{l}_{1}(9)]$. Based on the
Cartan decomposition of $\mathfrak{l}_{2}(9)$ and
$\overline{\mathfrak{l}_{2}}(9)$ given by Eqs. (23) and (25), we then have

$\displaystyle\begin{aligned}
&K_{1}^{\prime\prime}=K_{1}\cdot\overline{A}^{(3)}_{1}\cdot K_{2},\\\
&K_{2}^{\prime\prime}=K_{3}\cdot A^{(3)}_{1}\cdot K_{4},\\\
&K_{3}^{\prime\prime}=K_{5}\cdot\overline{A}^{(3)}_{2}\cdot K_{6},\\\
\end{aligned}$ (103)

where $A^{(3)}_{1}\in\textrm{exp}[\mathfrak{a}_{3}(9)]$,
$\overline{A}^{(3)}_{1,2}\in\textrm{exp}[\overline{\mathfrak{a}_{3}}(9)]$, and
$K_{r}\in\textrm{exp}[\mathfrak{l}_{3}(9)]$, $r=1,2,\cdots,6$.

As for $K_{4}^{\prime\prime}$, the decomposition of $\mathfrak{l}_{1}(9)$
shown in Eq. (20) leads to

$\displaystyle\begin{aligned} K_{4}^{\prime\prime}=K_{7}^{\prime}\cdot
A^{(2)}\cdot K_{8}^{\prime},\end{aligned}$ (104)

where $K_{7,8}^{\prime}\in\textrm{exp}[\mathfrak{l}_{2}(9)]$ and
$A^{(2)}\in\textrm{exp}[\mathfrak{a}_{2}(9)]$. Then we can let

$\displaystyle\begin{aligned}
K_{7}^{\prime}=\left(\begin{array}[]{ccc}V_{1}&\textbf{0}&\textbf{0}\\\
\textbf{0}&V_{2}&\textbf{0}\\\ \textbf{0}&\textbf{0}&V_{2}\\\
\end{array}\right),K_{8}^{\prime}=\left(\begin{array}[]{ccc}W_{1}&\textbf{0}&\textbf{0}\\\
\textbf{0}&W_{2}&\textbf{0}\\\ \textbf{0}&\textbf{0}&W_{2}\\\
\end{array}\right),\end{aligned}$ (105)

where $V_{1,2},W_{1,2}\in U(3)$. And $A^{(2)}$ can be written in the following
form

$\displaystyle\begin{aligned}
A^{(2)}=\left(\begin{array}[]{ccc}I_{3}&\textbf{0}&\textbf{0}\\\
\textbf{0}&T&\textbf{0}\\\ \textbf{0}&\textbf{0}&T^{{\dagger}}\\\
\end{array}\right),\end{aligned}$ (106)

where $T\in U(3)$ and $T$ is diagonal. Substituting Eqs. (105) and (106) into
Eq. (104), we can get

$\displaystyle\begin{aligned} K_{4}^{\prime\prime}=K_{7}\cdot A^{(2)}\cdot
K_{8}^{\prime\prime},\end{aligned}$ (107)

where $K_{7}=I_{3}\otimes V_{2}\in\textrm{exp}[\mathfrak{l}_{3}(9)]$ and

$\displaystyle\begin{aligned}
K_{8}^{\prime\prime}=\left(\begin{array}[]{ccc}V_{2}^{{\dagger}}V_{1}W_{1}&\textbf{0}&\textbf{0}\\\
\textbf{0}&W_{2}&\textbf{0}\\\
\textbf{0}&\textbf{0}&W_{2}\end{array}\right)\in\textrm{exp}[\mathfrak{l}_{2}(9)].\end{aligned}$
(108)

Finally, following the Cartan decomposition of $\mathfrak{l}_{3}(9)$ we can
obtain

$\displaystyle\begin{aligned} K_{8}^{\prime\prime}=K_{8}\cdot A^{(3)}_{2}\cdot
K_{9},\end{aligned}$ (109)

where $A^{(3)}_{2}\in\textrm{exp}[\mathfrak{a}_{3}(9)]$ and
$K_{8,9}\in\textrm{exp}[\mathfrak{l}_{3}(9)]$.

Substituting Eqs. (103), (107), and (109) into Eq. (101) in turn results in
Corollary 1. $\hfill\blacksquare$

Combining the above proof, the rightmost GCX gate in the synthesis of $A$
($A^{(1)}_{1,2}$) shown in Fig. 4 (Fig. 5) can be absorbed by the block
diagonal matrix $K_{i}^{\prime}$ in Eq. (98). Concretely, following the matrix
representation of $A$ shown in Eq. (100), we can get

$\displaystyle\begin{aligned}
A=\left(\begin{array}[]{ccc}Z^{01}&\textbf{0}&\textbf{0}\\\
\textbf{0}&I_{3}&\textbf{0}\\\
\textbf{0}&\textbf{0}&I_{3}\end{array}\right)\cdot\left(\begin{array}[]{ccc}Z^{01}C_{0}&-\textrm{i}Z^{01}S_{0}&\textbf{0}\\\
-\textrm{i}S_{0}&C_{0}&\textbf{0}\\\ \textbf{0}&\textbf{0}&I_{3}\\\
\end{array}\right),\end{aligned}$ (110)

where $Z^{01}=\textrm{diag}\\{1,-1,1\\}$. Let the left diagonal matrix in the
above equation be GCZ and the matrix on the right side be $A^{\prime}$. Note
that GCZ can be absorbed by $K_{2}^{\prime}$ and this does not affect the
later deduction. Furthermore, since

$\displaystyle\begin{aligned} \textrm{GCZ}=&R^{01}_{y}(\frac{\pi}{2})\otimes
I_{3}\cdot\textrm{GCX}_{2}^{1}(1\rightarrow X^{01})\\\ &\cdot
R^{01}_{y}(-\frac{\pi}{2})\otimes I_{3},\end{aligned}$ (111)

combined with the decomposition of $A$ given in Eq. (30), one can find that

$\displaystyle\begin{aligned} A^{\prime}=&R^{01}_{y}(\frac{\pi}{2})\otimes
I_{3}\cdot R_{z}^{01}(2\theta_{1}+\theta_{2})\otimes I_{3}\\\
&\cdot\textrm{GCX}_{2}^{1}(0\rightarrow X^{01})\cdot X^{01}\otimes I_{3}\\\
&\cdot R_{z}^{01}(\theta_{1}+2\theta_{2})\otimes
I_{3}\cdot\textrm{GCX}_{2}^{1}(2\rightarrow X^{01})\\\ &\cdot
R_{z}^{01}(2\theta_{3}-\theta_{1}-\theta_{2})\otimes I_{3}\cdot
R^{01}_{y}(-\frac{\pi}{2})\otimes I_{3}.\end{aligned}$ (112)

Therefore, only two GCX gates are necessary to synthesize $A^{\prime}$, which
means that the rightmost GCX gate in Fig. 4 can be absorbed.

Likewise, for $A^{(1)}_{i}$ ($i=1,2$), it can be found that

$\displaystyle\begin{aligned}
A^{(1)}_{i}=&\left(\begin{array}[]{ccc}I_{3}&\textbf{0}&\textbf{0}\\\
\textbf{0}&Z^{01}&\textbf{0}\\\
\textbf{0}&\textbf{0}&I_{3}\end{array}\right)\cdot\left(\begin{array}[]{ccc}I_{3}&\textbf{0}&\textbf{0}\\\
\textbf{0}&Z^{01}C_{i}&-\textrm{i}Z^{01}S_{i}\\\
\textbf{0}&-\textrm{i}S_{i}&C_{i}\\\ \end{array}\right).\end{aligned}$ (113)

The left diagonal matrix in the above equation can be decomposed as

$\displaystyle\begin{aligned} R^{12}_{y}(\frac{\pi}{2})\otimes
I_{3}\cdot\textrm{GCX}_{2}^{1}(1\rightarrow X^{12})\cdot
R^{12}_{y}(-\frac{\pi}{2})\otimes I_{3}.\end{aligned}$ (114)

Thus, in connection with Eq. (33) it follows that the rightmost GCX gate in
the synthesis of $A^{(1)}_{1}$ ($A^{(1)}_{2}$) shown in Fig. 5 can be absorbed
by $K_{1}^{\prime}$ ($K_{3}^{\prime}$).

##  Appendix B Maximally Abelian subalgebra in
$\mathbf{\mathfrak{u}(3^{\emph{n}})}$

Note that $\alpha(3^{n})$ defined by Eq. (46) is Abelian as the elements in
$\alpha(3^{n})$ are all diagonal matrices. The following Lemma is essential
for constructing Cartan subalgebras.

Lemma. The $\textrm{span}\\{\alpha(3^{n})\\}$ is maximally Abelian in
$\mathfrak{u}(3^{n})$.

Proof. Clearly, $\textrm{span}\\{\alpha(3)\\}$ is maximally Abelian in
$\mathfrak{u}(3)$. Assume that $\textrm{span}\\{\alpha(3^{n-1})\\}$ is
maximally Abelian in $\mathfrak{u}(3^{n-1})$, and we prove below that
$\textrm{span}\\{\alpha(3^{n})\\}$ is maximally Abelian in
$\mathfrak{u}(3^{n})$.

For any $A\in\mathfrak{u}(3^{n})$, $A$ can be denoted as

$\displaystyle\begin{aligned} A=&I_{3}\otimes A_{1}+\sigma_{z}^{01}\otimes
A_{2}+\sigma_{z}^{02}\otimes A_{3}\\\ &+\sigma_{x}^{01}\otimes
A_{4}+\sigma_{y}^{01}\otimes A_{5}+\sigma_{x}^{02}\otimes A_{6}\\\
&+\sigma_{y}^{02}\otimes A_{7}+\sigma_{x}^{12}\otimes
A_{8}+\sigma_{y}^{12}\otimes A_{9},\end{aligned}$ (115)

where $A_{i}\in\mathfrak{u}(3^{n-1})$. Assume $A$ and
$\textrm{span}\\{\alpha(3^{n})\\}$ be commutable, then it is sufficient to
prove that $A\in\textrm{span}\\{\alpha(3^{n})\\}$. As $\sigma_{z}^{01}\otimes
I_{3^{n-1}}\in\textrm{span}\\{\alpha(3^{n})\\}$, we have
$[A,\sigma_{z}^{01}\otimes I_{3^{n-1}}]=\textbf{0}$. From this, we get
$A_{j}=\mathbf{0},j=4,5,\cdots,9$, that is,

$\displaystyle\begin{aligned} A=I_{3}\otimes A_{1}+\sigma_{z}^{01}\otimes
A_{2}+\sigma_{z}^{02}\otimes A_{3}.\end{aligned}$ (116)

And for any $B\in\textrm{span}\\{\alpha(3^{n-1})\\}$, then $I_{3}\otimes
B\in\textrm{span}\\{\alpha(3^{n})\\}$. Thus, we have $[A,I_{3}\otimes
B]=\textbf{0}$, which is equivalent to $[A_{k},B]=\textbf{0}$, $k=1,2,3$. By
assumption and the arbitrariness of $B$, it follows that
$A_{k}\in\textrm{span}\\{\alpha(3^{n-1})\\}$, and then
$A\in\textrm{span}\\{\alpha(3^{n})\\}$. Hence
$\textrm{span}\\{\alpha(3^{n})\\}$ is maximally Abelian in
$\mathfrak{u}(3^{n})$. By induction the conclusion holds.$\hfill\blacksquare$

## References

  * (1) M. A. Nielsen and I. L. Chuang, _Quantum Computation and Quantum Information_ (Cambridge University Press, Cambridge, 2000).
  * (2) T. Li and G. L. Long, Hyper-parallel optical quantum computation assisted by atomic ensemble embedded indouble-sided optical cavities, Phys. Rev. A 94, 022343 (2016).
  * (3) X. X. Hu, F. H. Zhang, Y. S. Li, and G. L. Long, Optimizing quantum gates within decoherence-free subspaces, Phys. Rev. A 104, 062612 (2021).
  * (4) X. Y. Long, W. T. He, N. N. Zhang, K. Tang, Z. D. Lin, H. F. Liu, X. F. Nie, G. R. Feng, J. Li, T. Xin, Q. Ai, and D. W. Lu, Entanglement-Enhanced Quantum Metrology in Colored Noise by Quantum Zeno Effect, Phys. Rev. Lett. 129, 070502 (2022).
  * (5) L. K. Grover, Quantum mechanics helps in searching for a needle in a haystack, Phys. Rev. Lett. 79, 325 (1997).
  * (6) G. L. Long, Grover algorithm with zero theoretical failure rate, Phys. Rev. A 64, 022307 (2001).
  * (7) P. W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Rev. 41, 303 (1999).
  * (8) D. Deutsch and R. Jozsa, Rapid solution of problems by quantum computation, Proc. R. Soc. London Ser. A 439, 553 (1992).
  * (9) Y. Chi, J. Huang, Z. Zhang, J. Mao, Z. Zhou, X. Chen, C. Zhai, J. Bao, T. Dai, H. Yuan, M. Zhang, D. Dai, B. Tang, Y. Yang, Z. Li, Y. Ding, L. K. Oxenløwe, M. G. Thompson, J. L. O’Brien, Y. Li, Q. Gong, and J. Wang, A programmable qudit-based quantum processor, Nat. Commun. 13, 1166 (2022).
  * (10) N. T. Islam, C. C. W. Lim, C. Cahall, J. Kim, and D. J. Gauthier, Provably secure and high-rate quantum key distribution with time-bin qudits, Sci. Adv. 3, e1701491 (2017).
  * (11) W. X. Duan and T. J. Wang, Control power of high-dimensional controlled dense coding, Phys. Rev. A 105, 052417 (2022).
  * (12) E. T. Campbell, B. M. Terhal, and C. Vuillot, Roads towards fault-tolerant universal quantum computation, Nature 549, 172 (2017).
  * (13) F. Bouchard, R. Fickler, R. W. Boyd, and E. Karimi, High-dimensional quantum cloning and applications to quantum hacking, Sci. Adv. 3, e1601915 (2017).
  * (14) H. H. Lu, Z. Hu, M. S. Alshaykh, A. J. Moore, Y. Wang, P. Imany, A. M. Weiner, and S. Kais, Quantum phase estimation with time-frequency qudits in a single photon, Adv. Quantum Technol. 3, 1900074 (2020).
  * (15) B. P. Lanyon, M. Barbieri, M. P. Almeida, T. Jennewein, T. C. Ralph, K. J. Resch, G. J. Pryde, J. L. O’Brien, A. Gilchrist, and A. G. White, Simplifying quantum logic using higher-dimensional Hilbert spaces, Nat. Phys. 5, 134 (2009).
  * (16) W. Q. Liu, H. R. Wei, and L. C. Kwek, Low-cost Fredkin gate with auxiliary space, Phys. Rev. Appl. 14, 054057 (2020).
  * (17) H. Zhang, L. Wan, T. Haug, W. K. Mok, S. Paesani, Y. Shi, H. Cai, L. K. Chin, M. F. Karim, L. Xiao, X. Luo, F. Gao, B. Dong, S. Assad, M. S. Kim, A. Laing, L. C. Kwek, and A. Q. Liu, Resource-efficient high-dimensional subspace teleportation with a quantum autoencoder, Sci. Adv. 8, eabn9783 (2022).
  * (18) Q. P. Su, Y. Zhang, L. Bin, and C. P. Yan, Hybrid controlled-SUM gate with one superconducting qutrit and one cat-state qutrit and application in hybrid entangled state preparation, Phys. Rev. A 105, 042434 (2022).
  * (19) Y. Wang, S. Ru, F. Wang, P. Zhang, and F. Li, Experimental demonstration of efficient high-dimensional quantum gates with orbital angular momentum, Quantum Sci. Technol. 7, 015016 (2022).
  * (20) A. Saha, R. Majumdar, D. Saha, A. Chakrabarti, and S. Sur-Kolay, Asymptotically improved circuit for a $d$-ary Grover’s algorithm with advanced decomposition of the $n$-qudit Toffoli gate, Phys. Rev. A 105, 062453 (2022).
  * (21) X. M. Hu, W. B. Xing, C. Zhang, B. H. Liu, M. Pivoluska, M. Huber, Y. F. Huang, C. F. Li, and G. C. Guo, Experimental creation of multi-photon high-dimensional layered quantum states, npj Quantum Inform. 6, 88 (2020).
  * (22) M. Erhard, M. Krenn, and A. Zeilinger, Advances in high-dimensional quantum entanglement, Nat. Rev. Phys. 2, 365 (2020).
  * (23) T. J Bell, J. F F Bulmer, A. E Jones, S. Paesani, D. P S McCutcheon, and A. Laing, Protocol for generation of high-dimensional entanglement from an array of non-interacting photon emitters, New J. Phys. 24, 013032 (2022).
  * (24) Y. H. Luo, H. S. Zhong, M. Erhard, X. L. Wang, L. C. Peng, M. Krenn, X. Jiang, L. Li, N. L. Liu, C. Y. Lu, A. Zeilinger, and J. W. Pan, Quantum Teleportation in High Dimensions, Phys. Rev. Lett. 123, 070505 (2019).
  * (25) X. M. Hu, C. Zhang, B. H. Liu, Y. Cai, X. J. Ye, Y. Guo, W. B. Xing, C. X. Huang, Y. F. Huang, C. F. Li, and G. C. Guo, Experimental High-Dimensional Quantum Teleportation, Phys. Rev. Lett. 125, 230501 (2020).
  * (26) T. J. Wang, G. Q. Yang, and C. Wang, Control power of high-dimensional controlled teleportation, Phys. Rev. A 101, 012323 (2020).
  * (27) Y. Ding, D. Bacco, K. Dalgaard, X. Cai, X. Zhou, K. Rottwitt, and L. K. Oxenløwe, High-dimensional quantum key distribution based on multicore fiber using silicon photonic integrated circuits, npj Quantum Inform. 3, 25 (2017).
  * (28) Ö. Erkılıç, L. Conlon, B. Shajilal, S. Kish, S. Tserkis, Y. S. Kim, P. K. Lam, and S. M. Assad, High-dimensional quantum key distribution based on multicore fiber using silicon photonic integrated circuits, npj Quantum Inform. 9, 29 (2023).
  * (29) Y. Li, S. Y. Huang, M. Wang, C. H. Tu, X. L. Wang, Y. N. Li, and H. T. Wang, Two-Measurement Tomography of High-Dimensional Orbital Angular Momentum Entanglement, Phys. Rev. Lett. 130, 050805 (2023).
  * (30) W. Bogaerts, D. Pérez, J. Capmany, D. A. B. Miller, J. Poon, D. Englund, F. Morichetti, and A. Melloni, Programmable photonic circuits, Nature 586, 207 (2020).
  * (31) A. Chanana, H. Larocque, R. Moreira, J. Carolan, B. Guha, E. G. Melo, V. Anant, J. Song, D. Englund, D. J. Blumenthal, K. Srinivasan, and M. Davanco, Ultra-low loss quantum photonic circuits integrated with single quantum emitters, Nat. Commun. 13, 7693 (2022).
  * (32) W. R. Clements, P. C. Humphreys, B. J. Metcalf, W. S. Kolthammer, and I. A. Walmsley, Optimal design for universal multiport interferometers, Optica 3, 1460 (2016).
  * (33) M. Y. Saygin, I. V. Kondratyev, I. V. Dyakonov, S. A. Mironov, S. S. Straupe, and S. P. Kulik, Robust Architecture for Programmable Universal Unitaries, Phys. Rev. Lett. 124, 010501 (2020).
  * (34) A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter, Elementary gates for quantum computation, Phys. Rev. A 52, 3457 (1995).
  * (35) F. Vatan and C. Williams, Optimal quantum circuits for general two-qubit gates, Phys. Rev. A 69, 032315 (2004).
  * (36) V. V. Shende, I. L. Markov, and S. S. Bullock, Minimal universal two-qubit controlled-NOT-based circuits, Phys. Rev. A 69, 062321 (2004).
  * (37) K. Xu, W. Ning, X. J. Huang, P. R. Han, H. Li, Z. B. Yang, D. N. Zheng, H. Fan, and S. B. Zheng, Demonstration of a non-Abelian geometric controlled-NOT gate in a superconducting circuit, Optica 8, 972 (2021).
  * (38) A. Hida and K. Ishibashi, Exciton Controlled-NOT Gate Using Coupled Quantum Dots in Carbon Nanotube, ACS Photonics 9, 3398 (2022).
  * (39) T. Y. Xie, Z. Y. Zhao, S. Y. Xu, X. Kong, Z. P. Yang, M. Q. Wang, Y. Wang, F. Z. Shi, and J. F. Du, 99.92%-Fidelity cnot Gates in Solids by Noise Filtering, Phys. Rev. Lett. 130, 030601 (2023).
  * (40) J. J. Vartiainen, M. Möttönen, and M. M. Salomaa, Efficient Decomposition of Quantum Gates, Phys. Rev. Lett. 92, 177902 (2004).
  * (41) M. Möttönen, J. J. Vartiainen, V. Bergholm, and M. M. Salomaa, Quantum Circuits for General Multiqubit Gates, Phys. Rev. Lett. 93, 130502 (2004).
  * (42) V. V. Shende, S. S. Bullock, and I. L. Markov, Synthesis of quantum-logic circuits, IEEE Trans. on CAD 25, 1000 (2006).
  * (43) N. Khaneja and S. J. Glaser, Cartan decomposition of SU($2^{n}$) and control of spin systems, Chem. Phys. 267, 11 (2001).
  * (44) S. S. Bullock and G. K. Brennen, Canonical decompositions of $n$-qubit quantum computations and concurrence, J. Math. Phys. 45, 2447 (2004).
  * (45) D. D’Alessandro and F. Albertini, Quantum symmetries and Cartan decomposition in arbitrary dimensions, J. Phys. A: Math. Theor. 40, 2439 (2007).
  * (46) A. B. Klimov, R. Guzmán, J. C. Retamal, and C. Saavedra, Qutrit quantum computer with trapped ions, Phys. Rev. A 67, 062313 (2003).
  * (47) X. G. Wang, B. C. Sanders, and D. W. Berry, Entangling power and operator entanglement in qudit systems, Phys. Rev. A 67, 042323 (2003).
  * (48) S. S. Bullock, D. P. O’Leary, and G. K. Brennen, Asymptotically Optimal Quantum Circuits for $d$-Level Systems, Phys. Rev. Lett. 94, 230502 (2005).
  * (49) G. K. Brennen, S. S. Bullock, and D. P. O’Leary, Effcient circuits for exact-universal computations with qudits, Quantum Inf. Comput. 6, 436 (2006).
  * (50) Y. Nakajima, Y. Kawano, H. Sekigawa, M. Nakanishi, S. Yamashita, and Y. Nakashima, Synthesis of quantum circuits for $d$-level systems by using cosine-sine decomposition, Quantum Inf. Comput. 9, 423 (2009).
  * (51) Y. M. Di and H. R. Wei, Synthesis of multivalued quantum logic circuits by elementary gates, Phys. Rev. A 87, 012325 (2013).
  * (52) Y. M. Di and H. R. Wei, Optimal synthesis of multivalued quantum circuits, Phys. Rev. A 92, 062317 (2015).
  * (53) S. Helgason, _Differential Geometry and Symmetric Spaces_ (American Mathematical Society, Rhode Island, 2001).
  * (54) Y. M. Di, J. Zhang, and H. R. Wei, Cartan decomposition of a two-qutrit gate, Sci. China Ser. G-Phys. Mech. Astron. 51, 1668 (2008).