# Resource-Dependent Complexity of Quantum Channels

Roy Araiza  Department of Mathematics, University of Illinois at Urbana-
Champaign<EMAIL_ADDRESS>,  Yidong Chen  Department of Physics,
University of Illinois at Urbana-Champaign<EMAIL_ADDRESS>,  Marius
Junge  Department of Mathematics, University of Illinois at Urbana-Champaign
<EMAIL_ADDRESS>and  Peixue Wu  Department of Mathematics, University of
Illinois at Urbana-Champaign<EMAIL_ADDRESS>
###### Abstract.

Quantum complexity theory is concerned with the amount of elementary quantum
resources needed to build a quantum system or a quantum operation. The
fundamental question in quantum complexity is to define and quantify suitable
complexity measures. This non-trivial question has attracted the attention of
quantum information scientists, computer scientists, and high energy
physicists alike. In this paper, we combine the approach in [LBK+22] and well-
established tools from noncommutative geometry [Con90, Rie99, CS03] to propose
a unified framework for resource-dependent complexity measures of general
quantum channels. This framework is suitable to study the complexity of both
open and closed quantum systems. We explore the mathematical consequences of
the proposed axioms. The central class of examples in this paper is the so-
called Lipschitz complexity [LBK+22, PMTL21]. We use geometric methods to
provide upper and lower bounds on this class of complexity measures [Nie06,
NDGD06a, NDGD06b]. Finally, we study the dynamics of Lipschitz complexity in
open quantum systems. In particular, we show that generically the Lipschitz
complexity grows linearly in time and then saturates at a maximum value. This
is the same qualitative behavior conjecture by Brown and Susskind [BS18,
BS19].

RA was supported as a JL. Doob research assistant professor

MJ was partially supported by NSF Grant DMS 2247114, NSF Grant DMS 1800872 and
NSF RAISE-TAQS 1839177

###### Contents

  1. 1 Introduction
  2. 2 Axioms of Resource-Dependent Complexity Measures of Quantum Channels
    1. 2.1 Single-System Resource-Dependent Complexity
    2. 2.2 Composite-System Resource-Dependent Quantum Complexity
    3. 2.3 Expected length and its estimates
      1. 2.3.1 A Priori Estimates of Expected Lengths for Continuous Resources
      2. 2.3.2 A Priori Estimates of Expected Lengths for Discrete Resources
  3. 3 Resource-dependent complexity estimates for open systems
    1. 3.1 Discrete gates as resource
    2. 3.2 Continuous case: infinitesimal generators as resource
  4. 4 Hörmander Systems, Carnot-Caratheodory Distance, and Nielsen’s Complexity
  5. 5 More examples: Clifford Gates as Resources

##  1\. Introduction

Quantum complexity is a fundamental concept in quantum information and quantum
computation theory. It is a generalization of classical computational
complexity and characterizes the inherent difficulty of various quantum
information tasks. Compared with classical complexity, quantum complexity is
much more difficult to quantify and measure. By now, there are numerous
inequivalent quantum complexity measures [OT08, RW05, Wat03, FR99, DP85,
Kla00, BT09, BV97, BASTS08, BGS95, BS07]. On one hand, quantum information
specialists primarily focus on the quantum circuit complexity, which
emphasizes on the number of elementary gates required to simulate a complex
unitary transformation [Nie06, NDGD06a, NDGD06b, LBK+22, HFK+22, FGHZ05]. On
the other hand, high energy physicists have adapted the notion of complexity
to systems with infinite degrees of freedom [JM17, HR23, BS18, BS19, Ali15]
and to chaotic quantum systems [PCA+19, DS21, AAS22, RSGSS21, RSGSS22].

From information theoretic perspective, any computational task can be
characterized as an information channel. This is certainly the case in
classical computers, where different logical and memory components communicate
with each other and accomplish complex computational tasks in coordination.
Therefore, when studying quantum complexity measures, it is reasonable to
focus on the complexity of general quantum channels. In addition, any
reasonable complexity measure must take into consideration the amount of
available computational resources. Plainly, if given infinite resources (e.g.
all possible unitary gates), then any computational task would have low
complexity. The resources for quantum computation typically come in the form
of a set of simple unitary gates or a set of simple infinitesimal generators
that can drive the time evolution of a quantum system. When considering time
evolution in this paper, we do not restrict to the unitary evolution of closed
quantum systems. Since any realistic quantum system must interact with the
environment, it is more natural to consider time evolution of open quantum
systems.

With these considerations in mind and following the axiomatic approach in
[LBK+22], we propose a set of general axioms that any resource-dependent
complexity measure of quantum channels should satisfy. The main novelty of our
axiomatic framework is a combination of complexity theory [LBK+22] and well-
established operator algebraic tools [Con90, Rie99, CS03, GJL20a, CM17, CM20,
Wir18]. Our proposed axioms do not require the resources to have a particular
form. Therefore it provides a unified framework that can be applied to unitary
gate sets and infinitesmial generators. In addition, the axioms consider
general quantum channels and hence are suitable to study the complexity of
time evolution of both closed and open systems. Finally, our axioms can also
be used to study the dynamics of complexity measures.

The main example of complexity measure in this paper is the so-called
Lipschitz complexity [LBK+22, PMTL21]. This is a complexity measure based on a
noncommutative analog of the classical Lipschitz norm [CM17, CM20, Wir18,
GJL20a]. It is well-known that the Wasserstein 1-norm is dual to the Lipschitz
norm. Our definition of the Lipschitz norm is based on noncommutative geometry
[Con90, Rie99]. And it is a generalization of the existing notion [PMTL21].
Since the noncommutative Lipschitz norm (or dually the Wasserstein norm)
studies the noncommutative differential structure on the state space (or
dually the observables), the Lipschitz complexity naturally adopts the
geometric perspective on quantum complexity first introduced by Nielsen
[Nie06, NDGD06a, NDGD06b]. Depending on the applications, we will introduce
several different notions of noncommutative Lipschitz norms. Each definition
leads to a different quantum complexity measure satisfying the proposed
axioms.

One of the central problems in quantum complexity theory is to provide tight
estimates on the complexity measures. Typically a lower bound on the
complexity is more informative for the purpose of classification. In this
paper, we will provide various upper and lower bounds for the Lipschitz
complexity. The upper bound estimates are typically derived from geometric
arguments similar to the original Nielsen’s estimates [Nie06, NDGD06a,
NDGD06b], while the lower bound estimate relies on the noncommutative return
time estimate and a notion of size of the Lipschitz space. In the
noncommutative setting, it is simply the Lipschitz complexity of the
conditional expectation onto the fixed point of a quantum channel. Since the
conditional expectation itself is a special type of quantum channel, we will
have better control over its Lipschitz complexity. And by relating the
Lipschitz complexity of general channels to that of the conditional
expectations, we will be able to bound the complexity of general channeles.

As mentioned above, our approach to quantum complexity is suitable to study
the evolution of complexity with time. Given a time-dependent quantum channel
(e.g. a quantum Markov semigroup), we can study the time evolution of its
Lipschitz complexity. This is closely related to the Brown-Susskind conjecture
[BS18, BS19, HFK+22]. The conjecture states that for a generic quantum
circuit, its circuit complexity grows linearly with time (measured in terms of
the depth of the circuit and the number of gates used in the circuit) and the
complexity saturates at a value that is exponential in the system size [BS18,
BS19]. This conjecture was proved for random quantum circuits [HFK+22]. We
will show that, for a quantum Markov semigroup, the Lipschitz complexity first
grows linearly in time and then saturates at a maximal value. In addition, the
time scale to saturate the maximum can be calculated by the return time of the
quantum Markov semigroup. Qualitatively, this is the same behavior as
conjectured by Brown and Susskind [BS18, BS19]. Our result suggests that for
any generic time-dependent quantum channel (not necessarily given by a quantum
circuit), its complexity should have the qualitative behavior of the Brown-
Susskind type.

##  2\. Axioms of Resource-Dependent Complexity Measures of Quantum Channels

In this section, we present the axioms of resource-dependent complexity
measures of quantum channels. We state the axioms for finite-dimensional
quantum systems. But it is possible to generalize these axioms to any finite
von Neumann algebras as in [GJL20a].

Let $\mathcal{H}$ be a Hilbert space and let $\mathbb{B}(\mathcal{H})$ be the
bounded operators on $\mathcal{H}$. Suppose
$\mathcal{N}\subset\mathbb{B}(\mathcal{H})$ is a finite dimensional von
Neumann algebra. Denote the canonical trace on $\mathcal{N}$ by
$\operatorname{tr}$. Recall that a quantum channel is a normal, trace-
preserving, completely positive map:

$\displaystyle\Phi:\mathcal{N}_{*}\to\mathcal{N}_{*},$

where $\mathcal{N}_{*}\cong L_{1}(\mathcal{N})$ is the space of normal density
functionals.

The dual map $\Phi^{*}:\mathcal{N}\to\mathcal{N}$ defined via
$\operatorname{tr}(\Phi^{*}(\rho)x)=\operatorname{tr}(\rho\Phi(x))$ for any
$\rho\in L_{1}(\mathcal{N}),x\in\mathcal{N}$, is a normal unital completely
positive map.

As mentioned in the introduction, typically the resources for quantum
computations can be characterized by a set of simple unitaries or a set of
simple infinitesimal generators. Heuristically, the goal of resource-dependent
complexity measure is to quantify the amount of resources needed to construct
a given quantum channel. Mathematically, motivated by [LBK+22, HR23, PMTL21]
our goal is to find an appropriate complexity function $C$ defined on quantum
channels

$C:CP(\mathcal{N})\to\mathbb{R}_{\geq 0},$

where $CP(\mathcal{N})$ is the set of all the quantum channels on
$\mathcal{N}$, such that it satisfies some of the following axioms:

######  Axioms 1.

  1. (1)

$C(\Phi)=0$ if and only if $\Phi=\rm{id}$.

  2. (2)

(subadditivity under concatenation) $C(\Phi\Psi)\leq C(\Phi)+C(\Psi)$.

  3. (3)

(Convexity) For any probability distribution $\\{p_{i}\\}_{i\in I}$ and any
channels $\\{\Phi_{i}\\}_{i\in I}$, we have

(2.1) $C(\sum_{i\in I}p_{i}\Phi_{i})\leq\sum_{i\in I}p_{i}C(\Phi_{i}).$

  4. (4)

(Tensor additivity) For finitely many channels $\\{\Phi_{i}\\}_{1\leq i\leq
m}$, we have

(2.2) $C(\bigotimes_{i=1}^{m}\Phi_{i})=\sum_{i=1}^{m}C(\Phi_{i}).$

  5. (5)

(Normalization) $C(\Phi)\leq\log d$, where $d$ is the dimension of the
underlying Hilbert space.

The physical intuition behind these axioms is clear. The first clause
axiomatizes the fact that the trivial identity channel should have no
complexity. The subadditivity clause axiomatizes the fact that, when building
complex channels from simpler ones, the overall complexity cannot be larger
than the sum of the individual complexities. In other words, one cannot create
complexity out of thin air. On the other hand, a decrease in complexity should
be allowed. For example, when concatenating two unitary channels $Ad_{u}$ and
$Ad_{u^{*}}$, the product is the identity channel. Such cancelation occurs
generically. The convexity clause is another manifestation of the principle
that complexity cannot be created out of thin air. Hence a statistical
ensemble of channels cannot create more complexity than the statistical mean
of the individual complexities. Tensor additivity clause is the fact that the
complexity of building independent quantum channels should be the same as the
sum of complexity of building each channel. Finally, the normalization clause
gives us a limit based on the number of qubits we have. To propose such a
complexity function, motivated by [LBK+22], we will introduce a Lipschitz
norm, which is widely used in [Con90, Rie99, CS03, GJL20a, CM17, CM20, Wir18]
and fruitful theories were built there.

Recall that a derivation triple is given by $(\mathcal{A},D,\mathcal{H})$,
where $D:\mathcal{A}\to\mathcal{M}$ where $\mathcal{M}$ is a larger von
Neumann algebra, is a non-commutative differential operator and
$\mathcal{A}\subset\mathbb{B}(\mathcal{H})$ is a $*$-subalgebra such that
$\|D(a)\|<\infty$ for any $a\in\mathcal{A}$. Typically, $D(x)=[d,x]$ where $d$
is a self-adjoint operator.

###  2.1. Single-System Resource-Dependent Complexity

We are ready to introduce the resource-dependent complexity function for
single system. The resources are nothing but a set of operators. To be
specific, suppose $S\subset\mathcal{N}$ is a subset containing identity, the
induced Lipschitz (semi-)norm is defined by

(2.3) $|||f|||_{S}:=\sup_{s\in S}\|[s,f]\|_{\infty},\ f\in\mathcal{N}.$

To make $|||f|||_{S}$ a true norm, we define the space of mean 0 Lipschitz
space $\mathcal{A}$ as the quotient space

$\mathcal{A}:=\mathcal{N}/\\{f\in\mathcal{N}:|||f|||_{S}=0\\}.$

Recall the commutant of $S$ is given by

(2.4) $S^{\prime}=\\{f\in\mathcal{N}:[s,f]=0,\ \forall s\in S\\}.$

Denote the trace-preserving conditional expectation onto $S^{\prime}$ as
$E_{S^{\prime}}:\mathcal{N}\to S^{\prime}$. Then it is easy to see that

(2.5) $\mathcal{A}\cong\\{f\in\mathcal{N}:E_{S^{\prime}}(f)=0\\}.$

In other word, $\mathcal{A}$ is orthogonal to the algebra $S^{\prime}$. The
definition of complexity for single system is given as follows:

######  Definition 2.1.

For a quantum channel $\Phi:\mathcal{N}_{*}\to\mathcal{N}_{*}$, the complexity
is defined as

(2.6)
$C_{S}(\Phi):=\|\Phi^{*}-\rm{id}:(\mathcal{A},|||\cdot|||_{S})\to\mathbb{B}(\mathcal{H})\|.$

We denote the above norm by $\|\phi^{*}-\rm{id}\|_{Lip\to\infty}$ for
simplicity. The elementary properties are summarized in the following lemma:

######  Lemma 2.2.

  1. (1)

$C_{S}(\Phi)=0$ if and only if $\Phi=\rm{id}$.

  2. (2)

$C_{S}(\Phi\Psi)\leq C_{S}(\Phi)+C_{S}(\Psi)$ for any quantum channels
$\Phi,\Psi$.

  3. (3)

For any probability distribution $\\{p_{i}\\}_{i\in I}$ and any channels
$\\{\Phi_{i}\\}_{i\in I}$, we have

(2.7) $C_{S}(\sum_{i\in I}p_{i}\Phi_{i})\leq\sum_{i\in
I}p_{i}C_{S}(\Phi_{i}).$

  4. (4)

$C_{S}(\Phi)\leq
C_{S}(E_{S^{\prime}})\|\Phi^{*}-\rm{id}:\mathcal{N}\to\mathcal{N}\|$.

###### Proof.

Property $(1)$ follows from the faithfulness of the norm and property $(3)$
follows from the triangle inequality of norm. We only need to show $(2),(4)$.
To show $(2)$, note that

$\displaystyle\begin{split}C_{S}(\Phi\circ\Psi)&=||\Psi^{*}(\Phi^{*}-id)+\Psi^{*}-id||_{Lip\to\infty}\leq||\Psi^{*}||_{\infty\rightarrow\infty}||\Phi^{*}-id||_{Lip\rightarrow\infty}+||\Psi^{*}-id||_{Lip\rightarrow\infty}\\\
&\leq C_{S}(\Psi)+C_{S}(\Phi)\end{split}$

where for the first inequality, we use the following diagram and
submultiplicativity of norms:

${(\mathcal{A},|||\cdot|||_{S})}$${\mathcal{N}}$${\mathcal{N}}$$\scriptstyle{\Phi^{*}-id}$$\scriptstyle{\Psi^{*}(\Phi^{*}-id)}$$\scriptstyle{\Psi^{*}}$

and for the last inequality, we used the fact that a unital completely
positive map $\Psi^{*}$ satisfies
$||\Psi^{*}||_{\infty\to\infty}\leq||\Psi^{*}||_{cb}\leq 1$. To show $(4)$, we
use the following diagram and submultiplicativity of norms:

${(\mathcal{A},|||\cdot|||_{S})}$${\mathcal{N}}$${\mathcal{N}}$$\scriptstyle{\Phi^{*}-id}$$\scriptstyle{\rm{id}}$$\scriptstyle{\Phi^{*}-id}$
$\displaystyle||\Phi^{*}-id||_{Lip\rightarrow\infty}$
$\displaystyle\leq||id||_{Lip\rightarrow\infty}||\Phi^{*}-id||_{\infty\rightarrow\infty}$
$\displaystyle=||id-
E_{S^{\prime}}^{*}||_{Lip\rightarrow\infty}||\Phi^{*}-id||_{\infty\rightarrow\infty}=C_{S}(E_{S^{\prime}})||\Phi^{*}-id||_{\infty\rightarrow\infty},$

where for the second last equality, we used the fact that for any
$x\in\mathcal{A},E_{S^{\prime}}(x)=0$. ∎

The effects of the environment on quantum systems are usually taken into
consideration, which means we need to allow our system to couple with an
additional system. Next we define a complete version of the complexity, or
correlation assisted version.

Given a resource set $S\subset\mathcal{N}$, the $n$-th amplification of the
Lipschitz norm is defined as

(2.8) $|||f|||^{n}_{S}=\sup_{s\in S}\|[I_{n}\otimes
s,f]\|,f\in\mathbb{M}_{n}(\mathcal{A}).$

This enables us to define complete complexity:

######  Definition 2.3.

The complete complexity of a quantum channel $\Phi$ is defined by

(2.9) $C_{S}^{cb}(\Phi):=\sup_{n\geq
1}\|\rm{id}_{n}\otimes(\Phi^{*}-\rm{id}):(\mathbb{M}_{n}(\mathcal{A}),|||\cdot|||^{n}_{S})\to\mathbb{M}_{n}(\mathbb{B}(\mathcal{H}))\|.$

All the above elementary properties hold true by the same argument. We
summarize the results as follows:

######  Lemma 2.4.

  1. (1)

$C_{S}^{cb}(\Phi)=0$ if and only if $\Phi=\rm{id}$.

  2. (2)

$C_{S}^{cb}(\Phi\Psi)\leq C_{S}^{cb}(\Phi)+C_{S}^{cb}(\Psi)$ for any quantum
channels $\Phi,\Psi$.

  3. (3)

For any probability distribution $\\{p_{i}\\}_{i\in I}$ and any channels
$\\{\Phi_{i}\\}_{i\in I}$, we have

(2.10) $C_{S}^{cb}(\sum_{i\in I}p_{i}\Phi_{i})\leq\sum_{i\in
I}p_{i}C_{S}^{cb}(\Phi_{i}).$

  4. (4)

$C_{S}^{cb}(\Phi)\leq C_{S}^{cb}(E_{S^{\prime}})\|\Phi-\rm{id}\|_{\diamond}$.

Before ending this subsection, we emphasize that it is not possible to
construct all possible channels out of the given resources $S$. Thus the class
of channels must be restricted given the resources. We denote
$CP_{S}(\mathcal{N})$ as the subset of all quantum channels $CP(\mathcal{N})$,
which can be constructed from the resource $S$. In this paper, we focus on two
distinct resource-dependent channel sets:

  1. (1)

(Discrete case) The resource set $\mathcal{U}=\\{u_{i}\in
U(\mathcal{H})\\}_{1\leq i\leq 2n+1}$ is a symmetric set of unitaries in
$\mathcal{N}$ 111Here symmetric means that if $u\in\mathcal{U}$, then
$u^{*}\in\mathcal{U}$. In addition, we always assume that $id\in\mathcal{U}$.
Then

(2.11) $\displaystyle\begin{split}&CP_{\mathcal{U}}(\mathcal{N}):=\\{\Phi\in
CP(\mathcal{N}):\exists\\{u_{j_{i}}\in\mathcal{U}\\}_{1\leq i\leq N}\text{
such that }\\\ &\Phi\text{ is a convex combination of products of unitary
channels }\prod_{1\leq i\leq N}Ad_{u_{j_{i}}}\\}\hskip 2.84544pt.\end{split}$

In other words, the channel set depending on $\mathcal{U}$ contains all
channels that can be built from finite iterations of the simple unitary gates.

  2. (2)

(Continuous case) The resource set $\Delta=\\{a_{i}\in\mathcal{N}\\}_{1\leq
i\leq n}$ is a set of elements in $\mathcal{N}$ 222In the application, the
$a_{j}$’s are either self-adjoint (related to symmetric Lindbladian) or
unitary (related to the decoherence Lindbladian:
$Lx=\sum_{j}a_{j}xa_{j}^{*}-x$). They characterize the infinitesimal
generators (e.g. Hamiltonians) that can be used to construct complex channels.
Then

(2.12) $\displaystyle\begin{split}&CP_{\Delta}(\mathcal{N}):=\\{\Phi\in
CP(\mathcal{N}):\exists\\{X_{i}=\sum_{j_{i}}\alpha_{j_{i}}b_{j_{i}}\
\text{self-adjoint}\\}_{1\leq i\leq N}\text{ such that }\\\ &\Phi\text{ is a
convex combination of products of the form }\prod_{1\leq i\leq
N}Ad_{e^{iX_{i}}}\\}\end{split}$

where the self-adjoint $X_{i}$ is a linear combination of the $b_{j_{i}}$’s
with coefficients $\alpha_{j_{i}}$ and each $b_{j_{i}}$ is a finite iterated
brackets of the generators $a_{j}$’s.

As an example, consider the symmetric quantum Markov semigroup
$\\{\Phi_{t}=e^{tL}\\}$ generated by $Lx=-\frac{1}{2}\sum_{1\leq j\leq
n}[a_{j},[a_{j},x]]$. At each time $t\geq 0$, the channel $\Phi_{t}$ is in the
set $UCP_{\Delta}(N,N)$ where $\Delta=\\{a_{j}\\}_{1\leq j\leq n}$. In
general, the discrete case is closely related to the quantum circuits since
each quantum circuit is a finite concatenation of unitary channels. On the
other hand, the continuous case is closely related to the Trotter
approximation of Hamiltonian evolution and quantum Markov semigroups. This set
of channels have been considered in the geometric complexity theory of Nielsen
[Nie06, NDGD06a, NDGD06b].

######  Remark 2.5.

Consider $\mathcal{N}=\mathbb{B}(\mathbb{C}_{2}^{\otimes n})$, and define the
resource set

$\mathcal{U}:=\\{X_{i},Y_{i},Z_{i}:1\leq i\leq n\\},$

where

$X_{i}=I_{2}\otimes\cdots\otimes I_{2}\otimes\underbrace{X}_{i-th\
position}\otimes I_{2}\otimes\cdots\otimes I_{2}$

and $X,Y,Z$ are Pauli operators. Then one can show that our definition of
complexity is equivalent up to a dimension-independent constant to the
Wasserstein complexity introduced in [LBK+22]. More details are given in
Section 5.

We can also consider some other examples of single-system resource-dependent
complexity measure. First, recall that our resource-dependent Lipschitz norm
is given by

$\displaystyle|||f|||_{S}=\sup_{s\in S}\|[s,f]\|_{\infty}.$

This can be seen as an $l^{\infty}$ Lipschitz norm. We can also consider an
$l^{2}$ Lipschitz norm when $S=\\{s_{1},\cdots,s_{k}\\}$ is a discrete set:

(2.13) $|||f|||_{S,2}=\|(\sum_{i=1}^{k}|[s_{i},f]|^{2})^{1/2}\|_{\infty}.$

We can define complexity using this norm and get some estimates. The
discussion will be in later sections.

Another example of complexity is a simple universal construction.

######  Definition 2.6.

Let $\mathcal{U}=\\{u_{j}\in U(\mathcal{H})\\}_{1\leq j\leq 2n+1}$ be the
resource set of unitaries in $\mathcal{N}$ containing $id$. Then the maximum
complexity is defined as:

(2.14)
$C_{\mathcal{U}}^{max}:CP_{\mathcal{U}}(\mathcal{N})\rightarrow\mathbb{R}_{\geq
0}:\Phi\mapsto\inf_{\mu,\\{\mu_{i}(\omega)\\}}\\{\int\ell(\omega)d\mu(\omega):\Phi=\int\prod_{\begin{subarray}{c}1\leq
i\leq\ell(\omega)\\\
u_{i}(\omega)\in\mathcal{U}\end{subarray}}Ad_{u_{i}(\omega)}d\mu(\omega)\\}$

where $\mu$ is a probability measure on some standard probability space
$(\Omega,\mathcal{F},\mu)$. The infimum is taken over all possible products of
simple unitary channels whose convex combination is the channel $\Phi$.

Intuitively, the maximum complexity measures the minimum expected number of
simple unitaries in order to construct the channel $\Phi$. For unitary
channels $Ad_{u_{j}}$ where $u_{j}\in\mathcal{U}$, the complexity
$C_{\mathcal{U}}^{max}(Ad_{u_{j}})=1$. This is intuitively correct, since
these channels only require one piece of the resource. In addition, the
subadditivity axiom is satisfied by the definition of infimum. And the
convexity axiom is satisfied by the construction. It is not difficult to see
that all possible $\mathcal{U}$-dependent complexity measure is bounded above
by $C_{\mathcal{U}}^{max}$.

###  2.2. Composite-System Resource-Dependent Quantum Complexity

For composite systems
$\mathbb{B}(\mathcal{H}_{1})\otimes\mathbb{B}(\mathcal{H}_{2})$, the available
resources are given by the union of single-system resources. To be more
specific, let

$S_{1}\subset\mathbb{B}(\mathcal{H}_{1}),S_{2}\subset\mathbb{B}(\mathcal{H}_{2}),$

the resource set for the composite system is given by

(2.15) $S_{1}\vee S_{2}:=\\{s_{1}\otimes
id_{\mathcal{H}_{2}},id_{\mathcal{H}_{1}}\otimes s_{2}:s_{1}\in S_{1},s_{2}\in
S_{2}.\\}$

In general, for $n$-composite system
$\mathbb{B}(\mathcal{H}_{1}\otimes\cdots\otimes\mathcal{H}_{n})$, suppose we
have resources for each single system
$S_{i}\subset\mathbb{B}(\mathcal{H}_{i}),1\leq i\leq n$, the resource set for
the composite system is given by

(2.16) $\vee_{j=1}^{n}S_{j}:=\\{\widetilde{X_{j}}\big{|}X\in S_{j},\ \forall
1\leq j\leq n\\},$

where

$\widetilde{X_{j}}=\rm{id}\otimes\cdots\otimes\rm{id}\otimes\underbrace{X}_{j-th\
position}\otimes\rm{id}\otimes\cdots\otimes\rm{id}.$

Then we can define the Lipschitz norm by

(2.17)
$|||f|||_{\vee_{j=1}^{n}S_{j}}=\sup_{\widetilde{X}\in\vee_{j=1}^{n}S_{j}}\|[\widetilde{X},f]\|_{\infty},\
\forall f\in\mathbb{B}(\mathcal{H}_{1}\otimes\cdots\otimes\mathcal{H}_{n}).$

Similar to single system, we need to define the subspace of mean zero
elements. Define
$\mathcal{A}_{i}:=\\{x\in\mathbb{B}(\mathcal{H}_{i}):E_{S_{i}^{\prime}}(x)=0\\}$
and

(2.18) $\widetilde{\mathcal{A}}:=\bigotimes_{i=1}^{n}\mathcal{A}_{i}.$

Then it can be shown that
$\widetilde{\mathcal{A}}=\\{x\in\mathbb{B}(\mathcal{H}_{1}\otimes\cdots\mathcal{H}_{n}):E_{S_{1}^{\prime}}\otimes\cdots\otimes
E_{S_{n}^{\prime}}(x)=0\\}$ and $|||\cdot|||_{\vee_{j=1}^{n}S_{j}}$ is a norm
on $\widetilde{\mathcal{A}}$. We are ready to give the formal definition of
resource-dependent quantum complexity on composite systems:

######  Definition 2.7.

For any quantum channel $\Phi$ on
$\mathbb{B}(\mathcal{H}_{1}\otimes\cdots\mathcal{H}_{n})$, with resources
$S_{i}\subset\mathbb{B}(\mathcal{H}_{i})$ individually, the complete
complexity of $\Phi$ is defined as

(2.19) $\displaystyle C_{\vee_{j=1}^{n}S_{j}}^{cb}(\Phi)$
$\displaystyle=\|\Phi^{*}-\rm{id}:(\widetilde{\mathcal{A}},|||\cdot|||_{\vee_{j=1}^{n}S_{j}})\to\mathbb{B}(\mathcal{H}_{1}\otimes\cdots\mathcal{H}_{n})\|_{cb}$
$\displaystyle=\sup_{m\geq
1}\|\rm{id}_{m}\otimes(\Phi^{*}-\rm{id}):(\mathbb{M}_{m}(\widetilde{\mathcal{A}}),|||\cdot|||_{\vee_{j=1}^{n}S_{j}}^{m})\to\mathbb{M}_{m}(\mathbb{B}(\mathcal{H}_{1}\otimes\cdots\mathcal{H}_{n}))\|.$

The advantage of complete complexity is that the tensor additivity holds:

######  Proposition 2.8.

Suppose for all $1\leq j\leq n$,
$\Phi_{j}:\mathbb{B}(\mathcal{H}_{j})_{*}\to\mathbb{B}(\mathcal{H}_{j})_{*}$
are quantum channels and $S_{j}\subset\mathbb{B}(\mathcal{H}_{j})$ are the
resources for each single system , then

(2.20)
$C_{\vee_{j=1}^{n}S_{j}}^{cb}(\Phi_{1}\otimes\cdots\otimes\Phi_{n})=\sum_{j=1}^{n}C_{S_{j}}^{cb}(\Phi_{j}).$

###### Proof.

We only need to show the case when $n=2$ because the general case follows from
induction. For subadditivity, we will show

$\displaystyle C_{S_{1}\vee S_{2}}(\Phi_{1}\otimes\Phi_{2})\leq
C_{S_{1}}(\Phi_{1})+C_{S_{2}}(\Phi_{2}),$

and the complete version follows by the same argument. For each individual
$\Phi_{j}:\mathbb{B}(\mathcal{H}_{j})_{*}\to\mathbb{B}(\mathcal{H}_{j})_{*}$,
we have an induced channel on the composite system:
$\widetilde{\Phi_{j}}:\mathbb{B}(\mathcal{H}_{1}\otimes\mathcal{H}_{2})_{*}\to\mathbb{B}(\mathcal{H}_{1}\otimes\mathcal{H}_{2})_{*}$,
where $\widetilde{\Phi_{j}}$ acts nontrivially only on the $j$-th subsystem as
$\Phi_{j}$ and trivially on the other subsystems. We claim that

(2.21) $C_{S_{1}\vee S_{2}}(\widetilde{\Phi_{j}})\leq C_{S_{j}}(\Phi_{j}),$

which is equivalent to for any $f\in\widetilde{A}$, we have

$\|(\widetilde{\Phi_{j}}^{*}-id)f\|_{\infty}\leq
C_{S_{j}}(\Phi_{j})|||f|||_{S_{1}\vee S_{2}}.$

By convexity, we only need to show the inequality for $f\in\widetilde{A}$,
$f=f_{1}\otimes f_{2}$. Without loss of generality, assume $j=1$, then

$\displaystyle\|(\widetilde{\Phi_{1}}^{*}-\rm{id})(f)\|_{\infty}$
$\displaystyle=\|(\Phi_{1}^{*}(f_{1})-f_{1})\otimes f_{2}\|_{\infty}$
$\displaystyle=\|\Phi_{1}^{*}(f_{1})-f_{1}\|_{\infty}\|f_{2}\|_{\infty}$
$\displaystyle\leq C_{S_{1}}(\Phi_{1})|||f_{1}|||_{S_{1}}\|f_{2}\|_{\infty}$
$\displaystyle=C_{S_{1}}(\Phi_{1})\sup_{X\in
S_{1}}\|[X\otimes\rm{id}_{\mathcal{H}_{2}},f_{1}\otimes f_{2}]\|_{\infty}$
$\displaystyle\leq C_{S_{1}}(\Phi_{1})\sup_{\widetilde{X}\in S_{1}\vee
S_{2}}\|[\widetilde{X},f]\|_{\infty}=C_{S_{1}}(\Phi_{1})|||f|||_{S_{1}\vee
S_{2}}.$

Therefore, by subadditivity under concatenation, we have

$\displaystyle C_{S_{1}\vee S_{2}}(\Phi_{1}\otimes\Phi_{2})=C_{S_{1}\vee
S_{2}}(\widetilde{\Phi_{1}}\circ\widetilde{\Phi_{2}})\leq C_{S_{1}\vee
S_{2}}(\widetilde{\Phi_{1}})+C_{S_{1}\vee S_{2}}(\widetilde{\Phi_{2}})\leq
C_{S_{1}}(\Phi_{1})+C_{S_{2}}(\Phi_{2}).$

For the superadditivity, by definition, for any $\varepsilon\in(0,1)$, there
exist $m_{1},m_{2}\in\mathbb{N}$, and
$f_{i}\in\mathbb{M}_{m_{i}}(\mathbb{B}(\mathcal{H}_{i}))$, $i=1,2$, such that

$\displaystyle id_{m_{i}}\otimes E_{S_{i}^{\prime}}(f_{i})=0,\
|||f_{i}|||_{S_{i}}^{m_{i}}\leq 1,$

and states $\rho_{i}\in\mathbb{M}_{m_{i}}(\mathbb{B}(\mathcal{H}_{i}))$, such
that

(2.22)
$(1-\varepsilon)C_{S_{i}}^{cb}(\Phi_{i})\leq\operatorname{tr}(((\Phi_{i}^{*})_{n}-id)(f_{i})\rho_{i}),$

where $(\Phi_{i}^{*})_{n}$ denotes the $n$-th amplification. Now we define

(2.23) $F=f_{1}\otimes I_{m_{2}}\otimes id_{\mathcal{H}_{2}}+I_{m_{1}}\otimes
id_{\mathcal{H}_{1}}\otimes
f_{2}\in\mathbb{M}_{m_{1}m_{2}}(\mathbb{B}(\mathcal{H}_{1}\otimes\mathcal{H}_{2})).$

It is routine to check that

$\displaystyle
F\in\mathbb{M}_{m_{1}m_{2}}(\widetilde{A}),i.e.,id_{m_{1}m_{2}}\otimes
E_{S_{1}^{\prime}}\otimes E_{S_{2}^{\prime}}(F)=0.$
$\displaystyle|||F|||_{S_{1}\vee S_{2}}^{m_{1}m_{2}}=\max\\{\sup_{s_{1}\in
S_{1}}\|[I_{m_{1}m_{2}}\otimes s_{1}\otimes
id_{\mathcal{H}_{2}},F]\|,\sup_{s_{2}\in S_{2}}\|[I_{m_{1}m_{2}}\otimes
id_{\mathcal{H}_{1}}\otimes s_{2},F]\|\\}\leq 1.$

Moreover, we have

$\displaystyle\operatorname{tr}\big{(}((\Phi_{1}^{*})_{m_{1}}\otimes(\Phi_{2}^{*})_{m_{2}}-id)(F)\cdot(\rho_{A}\otimes\rho_{B})\big{)}$
$\displaystyle=\operatorname{tr}\big{(}F\cdot((\Phi_{1})_{m_{1}}\otimes(\Phi_{2})_{m_{2}}-id)(\rho_{A}\otimes\rho_{B})\big{)}$
$\displaystyle=\operatorname{tr}\big{(}(f_{1}\otimes I_{m_{2}}\otimes
id_{\mathcal{H}_{2}})\cdot((\Phi_{1})_{m_{1}}\otimes(\Phi_{2})_{m_{2}}-id)(\rho_{A}\otimes\rho_{B})\big{)}$
$\displaystyle+\operatorname{tr}\big{(}(I_{m_{1}}\otimes
id_{\mathcal{H}_{1}}\otimes
f_{2}\cdot((\Phi_{1})_{m_{1}}\otimes(\Phi_{2})_{m_{2}}-id)(\rho_{A}\otimes\rho_{B})\big{)}$
$\displaystyle=\operatorname{tr}(f_{1}\cdot((\Phi_{1})_{m_{1}}-id)(\rho_{A}))+\operatorname{tr}(f_{2}\cdot((\Phi_{2})_{m_{2}}-id)(\rho_{B}))$
$\displaystyle\geq(1-\varepsilon)(C_{S_{1}}^{cb}(\Phi_{1})+C_{S_{2}}(\Phi_{2})).$

For the last equality, we used trace-preserving property of
$(\Phi_{1})_{m_{1}},(\Phi_{2})_{m_{2}}$. ∎

###  2.3. Expected length and its estimates

Recall that $C_{S}^{cb}(E_{S^{\prime}})$ provides an upper bound of the
complexity, see (4) of Lemma 2.4. In this subsection, we aim to provide
several estimates for this quantity. We also name this quantity as the
expected length of the noncommutative Lipschitz space:

######  Definition 2.9.

Given the resource set $S$, the expected length of the Lipschitz space
$\mathcal{A}$ is given by the "Lipschitz complexity" 333Although it is not
clear that $E_{fix}^{*}$ is guaranteed to be in the set of admissible channels
$CP_{S}(\mathcal{N})$, the definition of expected length is completely
analogous to the definition of the Lipschitz complexity. Hence we choose to
use the same terminology but put the Lipschitz complexity in quotation marks.
of the dual channel:

(2.24) $EL_{\mathcal{S}}(\mathcal{A}):=||E^{*}_{fix}-id:\mathcal{A}\rightarrow
N||=||id:\mathcal{A}\rightarrow N||\hskip 2.84544pt.$

Similarly, the correlation-assisted expected length is given by:

(2.25) $EL^{cb}_{\mathcal{S}}(\mathcal{A}):=\sup_{m\geq 0}||E^{*}_{fix}\otimes
id_{m}-id_{\mathcal{N}}\otimes id_{m}:\mathcal{A}\otimes
M_{m}(\mathbb{C})\rightarrow M_{m}(\mathcal{N})||\hskip 2.84544pt.$

In later applications, we often focus on channels $\Phi\in
CP_{S}(\mathcal{N})$ where the fixed point space of the channel
$\Phi:L_{1}(\mathcal{N})\rightarrow L_{1}(\mathcal{N})$ is given by the
annihilator $\mathcal{A}^{\perp}=S^{\prime}$.

Before presenting the a priori estimates on $EL_{\mathcal{S}}(\mathcal{A})$,
we explain why the expected length deserves its name. Recall any
$\mathbb{B}(\mathcal{H})$ contains a maximal Abelian subalgebra
$\ell_{\infty}(\mathcal{H})$ (the diagonal subalgebra). As operators on $H$,
$\ell_{\infty}(\mathcal{H})$ acts by multiplication. It is a well-known fact
that the operator norm of the multiplication $||M_{f}||$ is equal to the sup-
norm of the function $||f||$. In the proof, we will freely use this
identification.

######  Lemma 2.10.

Let $G$ be a finitely generated finite group and let $\mathcal{S}=\\{s^{\pm
1},e\\}_{\\{s\\}\text{ generates $G$}}$ be the symmetric set of generators
along with the identity. Consider the commutative algebra
$\mathcal{N}:=\ell_{\infty}(G)\\!\\!\subset\\!\\!\mathbb{B}(\ell_{2}(G))$ and
the left regular representation $\lambda:G\rightarrow U(\ell_{2}(G))$. Then
the set $\mathcal{S}$ defines a resource set made up of derivations:

(2.26) $\partial_{s}(M_{f}):=\lambda_{s}\circ
M_{f}-M_{f}\circ\lambda_{s}=(Ad_{s}(M_{f})-M_{f})\circ\lambda_{s}=(M_{\lambda_{s}f}-M_{f})\circ\lambda_{s}\hskip
2.84544pt.$

where $M_{f}\in\mathcal{N}$ is the multiplication operator by the function
$f$. The associated Lipschitz space is
$\mathcal{A}=\\{f\in\mathcal{N}:\frac{1}{|G|}\sum_{g}f(g)=0\\}$ and the
Lipschitz norm is given by:

(2.27)
$|||f|||=\sup_{s\in\mathcal{S}}||\partial_{s}M_{f}||_{\infty}=\sup_{s}||M_{\lambda_{s}f}-M_{f}||_{\infty}\hskip
2.84544pt.$

The associated annihilator is
$\mathcal{A}^{\perp}=\mathbb{C}=\text{span}\\{\mathbbm{1}_{G}\\}$. Finally, we
have:

(2.28)
$\frac{1}{|G|}\sum_{g}\ell_{\mathcal{S}}(g)=EL_{\mathcal{S}}(\mathcal{A})$

where $\ell_{\mathcal{S}}(g)$ is the word-length function induced by the
generating set $\mathcal{S}$. 444The same equation holds for the correlation-
assisted expected length, since $N$ is a commutative algebra.

###### Proof.

All the claim follows directly from definitions. We only need to show that
last equation 2.28. Let $\mu$ be the normalized counting measure on $G$ and
let $\mathbb{E}$ be the expectation with respect to $\mu$. Then for
$f\in\mathcal{A}$, we have $\mathbb{E}f=0$. Since $\mathcal{S}$ generates $G$,
for each $g$ we can fix a reduced word representation: $g=\prod_{1\leq
i\leq\ell_{\mathcal{S}}(g)}s_{i}$ where $s_{i}\in\mathcal{S}$ for each $1\leq
i\leq\ell_{\mathcal{S}}(g)$. First we make the following observation:

(2.29)
$\mathbb{E}_{g}\lambda_{g}f(h)=\frac{1}{|G|}\sum_{g}f(g^{-1}h)=\frac{1}{|G|}\sum_{g}f(g)=\mathbb{E}(f)$

where the equation holds point-wise at each $h\in G$. Then for
$f\in\mathcal{A}$, we have:

(2.30)
$\displaystyle\begin{split}||f||&=||f-\mathbb{E}_{g}\lambda_{g}f||\leq\mathbb{E}_{g}||f-\lambda_{g}f||=\mathbb{E}_{g}||f-(\prod_{1\leq
i\leq\ell_{\mathcal{S}}(g)}\lambda_{s_{i}})f||\\\
&\leq\mathbb{E}_{g}\sum_{1\leq
i\leq\ell_{\mathcal{S}}(g)}||f-\lambda_{s_{i}}f||\leq\big{(}\mathbb{E}_{g}\ell_{\mathcal{S}}(g)\big{)}\sup_{s}||f-\lambda_{s}f||=\mathbb{E}(\ell_{\mathcal{S}})|||f|||\hskip
2.84544pt.\end{split}$

Therefore we have
$EL_{\mathcal{S}}(\mathcal{A})\leq\mathbb{E}(\ell_{\mathcal{S}})$.

On the other hand, consider the function:
$f_{\mathcal{S}}(g):=\mathbb{E}(\ell_{\mathcal{S}})-\ell_{\mathcal{S}}(g)$.
Clearly $\mathbb{E}f_{\mathcal{S}}=0$. In addition,
$|||f_{\mathcal{S}}|||=\sup_{s}||\lambda_{s}f_{\mathcal{S}}-f_{\mathcal{S}}||=||\lambda_{s}\ell_{\mathcal{S}}-\ell_{\mathcal{S}}||$.
By triangle inequality of the word length, for all $g\in G$ we have
$|\ell_{\mathcal{(}}s^{-1}g)-\ell_{\mathcal{g}}|\leq\ell_{\mathcal{(}}s^{-1})=1$.
Hence $|||f_{\mathcal{S}}|||\leq 1$. Then we have:

(2.31) $EL_{\mathcal{S}}(\mathcal{A})\geq
EL_{\mathcal{S}}(\mathcal{A})|||f_{\mathcal{S}}|||\geq||f_{\mathcal{S}}||\geq|f_{\mathcal{S}}(e)|=\mathbb{E}(\ell_{\mathcal{S}})\hskip
2.84544pt.$

Hence Equation 2.28 holds. ∎

For a finite group, the expected value of the word length function is
equivalent to the classical diameter
$diam_{G}=\sup_{g,h}\ell_{\mathcal{S}}(h^{-1}g)$. In this sense,
$EL_{\mathcal{S}}(\mathcal{A})$ provides geometric information about the size
of the Lipschitz space $\mathcal{A}$.

As mentioned before, there are two types of resources that are typical in
quantum information science: the discrete type $\mathcal{U}$ and the
continuous type $\Delta$. Quantum circuits are built using the discrete type
of resources while time evolutions (for both open and closed systems) are
built using the continuous type of resources. We will conclude this section by
some a priori estimates on the expected length for these two types of
resources. The proof of these estimates uses similar ideas as the proof of
Lemma 2.10.

####  2.3.1. A Priori Estimates of Expected Lengths for Continuous Resources

Recall the continous type of resource is given by a finite set of
infinitesimal generators $\Delta=\\{a_{j}\\}_{1\leq j\leq n}$. For self-
adjoint Lindbladians or Hamiltonians, $a_{j}$’s are self-adjoint operators.
When the underlying quantum system is finite dimensional, $\mathcal{N}$ is a
finite dimensional von Neumann algebra. In this case, the group of unitaries
$G:=U(\mathcal{N})$ is a real semisimple Lie algebra. In this case, recall the
definition of Hörmander systems.

######  Definition 2.11.

Let $\mathfrak{g}$ be a semisimple Lie algebra. In addition, let
$H=\\{a_{1},...,a_{n}\\}\\!\\!\subset\\!\\!\mathfrak{g}$ be a finite set of
elements in the Lie algebra. Then $H$ is a Hörmander system if there exist a
finite number $\ell_{H}$ such that:

(2.32)
$\text{span}\\{[a_{i_{1}},[a_{i_{2}},...,[a_{i_{j-1}},a_{i_{j}}]]]:j\leq\ell_{H}\text{
and }a_{i}\in H\\}=\mathfrak{g}\hskip 2.84544pt.$

The number $\ell_{H}$ is called the Hörmander length.

For a finite dimensional quantum system, the Lie group of unitaries $G$ is
semisimple and compact. Therefore we can use the norm induced by the Killing-
Cartan form on the associated Lie algebra $\mathfrak{g}$. The norm is bi-
invariant under the adjoint action of $G$ and it is equivalent to the
Euclidean norm. Using this norm and given a Hörmander system, one can define a
compatible Carnot-Caratheodory metric on $G$:

######  Definition 2.12.

Let $H$ be a Hörmander system of a Lie group $G$, the induced Carnot-
Caratheodory metric is given by:

(2.33) $d_{H}(x,y):=\inf\\{\int||\gamma^{\prime}(t)||dt:\gamma(0)=x,\text{
}\gamma(1)=y,\text{
}L_{\gamma(t)^{-1}}\gamma^{\prime}(t)\in\text{span}\\{H\\}\\}$

where $\gamma(t)$ is a piecewise-differentiable curve connecting $x,y$ such
that its derivative is in the subspace spanned by the Hörmander system. And
the norm $||\cdot||$ is induced by the Killing-Cartan form on the Lie algebra.

Hence the Carnot-Caratheodory distance is nothing but the geodesic distance
under the pseudo-Riemannian structure induced by the left translation of the
Hörmander system.

If the set of iterated brackets of the infinitesimal generators does not span
the entire Lie algebra, operationally it means that the resources are not
enough for adequate control over the entire quantum systems. This is a
pathological situation that we shall not consider in this paper.

######  Lemma 2.13.

For a finite dimensional quantum system $\mathcal{N}$. Assume $\mathcal{N}$ is
a factor (i.e. $\mathcal{N}=\mathbb{B}(H)$ for some finite dimensional Hilbert
space $H$). Let $\mu$ be the normalized Haar measure on the group of unitaries
$G$. Assume the resource set $\Delta$ forms a Hörmander system for $G$ and the
generators $a_{j}$’s are orthonormal with respect to the Killing-Cartan inner
product. Consider the Lipschitz space: $(\mathcal{A},|||\cdot|||_{\Delta})$
where the norm is the $\ell_{\infty}$-Lipschitz norm associated with $\Delta$
(c.f. Definition 2.1). Then we have:

(2.34) $\mathbb{E}_{\mu}(\ell_{\Delta})\leq
EL_{\Delta}(\mathcal{A})\leq|\Delta|^{1/2}\mathbb{E}_{\mu}(\ell_{\Delta})\hskip
2.84544pt.$

where $|\Delta|$ is the cardinality of the generating set. And a similar
statement holds for correlation-assisted expected length.

###### Proof.

First observe that since $\Delta$ is a Hörmander system and the annihilator
$\mathcal{A}^{\perp}$ commutes with all generators in $\Delta$, then we have
$\mathcal{A}^{\perp}=\\{x\in\mathcal{N}:uxu^{*}=x\text{ for all }u\in
G\\}=\mathbb{C}$. In particular, for all $x\in\mathcal{N}$,
$\mathbb{E}_{\mu}x:=\int_{G}d\mu(u)uxu^{*}\in\mathcal{A}^{\perp}$. And for
$x\in\mathcal{A}$, $\mathbb{E}_{\mu}x=0$. In addition, for all $u\in G$, since
$G$ is a compact Lie group and $\Delta$ is a Hörmander system, there exists a
piecewise smooth path $\gamma_{u}:[0,1]\rightarrow G$ such that
$\gamma_{u}(0)=id,\gamma_{u}(1)=u$ and
$\gamma^{\prime}_{u}(t)\in(L_{\gamma_{u}(t)})_{*}\Delta$ where
$\gamma_{u}^{\prime}(t)$ is the derivative and $(L_{\gamma_{u}(t)})_{*}\Delta$
is the left-translated Hörmander system. In particular, at each $t\in[0,1]$,
$\gamma^{\prime}_{u}(t)$ can be written as a linear combination of left-
translated vector fields
$(L_{\gamma_{u}(t)})_{*}\Delta=\\{(L_{\gamma_{u}(t)})_{*}a_{1},...,(L_{\gamma_{u}(t)})_{*}a_{n}\\}$:

(2.35) $\gamma_{u}^{\prime}(t)=\sum_{1\leq j\leq
n}u_{j}(t)(L_{\gamma_{u}(t)})_{*}a_{j}$

where $u_{j}(t)$’s are coefficients and depend piece-wise smoothly on $t$. The
Killing-Cartan norm is given by
$||\gamma_{u}^{\prime}(t)||^{2}=\sum_{j}|u_{j}(t)|^{2}$. Now fix a length-
minimizing path for each $u\in G$.

Using these observations, for all $x\in\mathcal{A}$ we have:

(2.36)
$\displaystyle\begin{split}||x||&=||x-\mathbb{E}_{\mu}x||\leq\mathbb{E}_{\mu}||\int_{0}^{1}dt[\gamma_{u}^{\prime}(t),\gamma_{u}(t)x\gamma^{*}_{u}(t)]||\leq\mathbb{E}_{\mu}\int_{0}^{1}dt\sum_{j}|u_{j}(t)||\gamma_{u}(t)[a_{j},x]\gamma_{u}^{*}(t)||\\\
&\leq\mathbb{E}_{\mu}\int_{0}^{1}dt||\gamma_{u}^{\prime}(t)||\big{(}\sum_{j}||[a_{j},x]||^{2}\big{)}^{1/2}=\mathbb{E}_{\mu}(\ell_{\Delta})\sup_{j}||[a_{j},x]|||\Delta|^{1/2}=|\Delta|^{1/2}\mathbb{E}_{\mu}(\ell_{\Delta})|||x|||\hskip
2.84544pt.\end{split}$

Therefore
$EL_{\Delta}(\mathcal{A})\leq|\Delta|^{1/2}\mathbb{E}_{\mu}(\ell_{\Delta})$.

On the other hand, consider the function:
$f_{\Delta}(g):=\mathbb{E}_{\mu}(\ell_{\Delta})-\ell_{\Delta}(g)$. By triangle
inequality, $f_{\Delta}$ is Lipschitz continuous and hence differentiable
almost everywhere. In addition for every $a_{j}\in H$ and $g\in G$ we have:

(2.37) $|\lim_{t\rightarrow
0}\frac{1}{t}(f(e^{ta_{j}}g)-f(g))|\leq\lim_{t\rightarrow
0}\frac{1}{t}\ell_{\Delta}(e^{ta_{j}})\leq||a_{j}||=1$

where we used triangle inequality and the fact that all generators $a_{j}$’s
are normalized in the Killing-Cartan norm. Hence $|||f_{\Delta}|||\leq 1$.
Since
$||f_{\Delta}||\geq|\mathbb{E}_{\mu}(\ell_{\Delta})-\ell_{\Delta}(e)|=\mathbb{E}_{\mu}(\ell_{\Delta})$.
We have the lower bound: $\mathbb{E}_{\mu}(\ell_{\Delta})\leq
EL_{\Delta}(\mathcal{A})$. ∎

####  2.3.2. A Priori Estimates of Expected Lengths for Discrete Resources

For discrete resources $\mathcal{U}$, we assume this is a symmetric set of
unitaries (i.e. if $s\in\mathcal{U}$ then $s^{-1}\in\mathcal{U}$) and we
assume this set contains identity. Two cautionary comments are in order.

  1. (1)

The group $\Gamma$ generated by $\mathcal{U}$ is a discrete subgroup of the
group of unitaries in $\mathcal{N}$. Even when $\mathcal{U}$ is a set of
universal unitaries in the sense of Kitaev-Solovay [DN06], $\Gamma$ does not
contain all unitaries in $\mathcal{N}$. In particular, $\Gamma$ has measure
zero under the Haar measure on the unitary group.

  2. (2)

The Haar measure on $\Gamma$ is the counting measure. If $\Gamma$ is not
finite (which is typically the case), the expected length under the Haar
measure will be infinite.

Hence we must specify another measure on $\Gamma$. Recall the symmetric
generating set $\mathcal{S}:=\mathcal{U}-\\{e\\}$ defines a symmetric random
walk on $\Gamma$ whose transition function is given by convolution with the
finite measure: $\nu:=\frac{1}{2n}\sum_{s\in\mathcal{S}}\delta_{s}$ where $2n$
is the cardinality of $\mathcal{S}$. The Cesaro mean of $\nu^{\star n}$ weakly
converges to a probability measure:

(2.38) $\mu:=\lim_{N\rightarrow\infty}\frac{1}{N}\sum_{0\leq n\leq
N-1}\nu^{\star n}\hskip 2.84544pt.$

For any function $f\in\ell_{\infty}(\Gamma)$, the convolution with $\mu$
projects $f$ onto the fixed point subspace:
$\\{f\in\ell_{\infty}(\Gamma):\nu\star f=f\\}$. Denote this projection as
$P_{\mu}$. Consider the transference map:

(2.39)
$\pi:\mathcal{N}\rightarrow\ell_{\infty}(\Gamma,\mathcal{N}):\pi(x)(g):=g^{*}xg\hskip
2.84544pt.$

This is a faithful normal $*$-homomorphism that intertwines the group action:
$\pi(hxh^{*})=\lambda_{h}\pi(x)$ where $\lambda_{h}$ is the left-regular
action of $\Gamma$. Consequently, $\pi$ intertwines the projections onto the
fixed point subspaces. Recall
$E_{fix}:\mathcal{N}\rightarrow\mathcal{A}^{\perp}=\\{x\in\mathcal{N}:g^{*}xg=x\text{
for all }g\in\Gamma\\}$ is the projection onto the annihilator subspace. Then
we have: $\pi\circ E_{fix}=P_{\mu}\circ\pi$. In particular, for
$x\in\mathcal{A}$, since $E_{fix}x=0$, then we have:
$0=P_{\mu}(\pi(x))=\lim_{N\rightarrow\infty}\frac{1}{N}\sum_{0\leq n\leq
N-1}\nu^{\star n}\star\pi(x)$. In addition, since $\pi$ is a faithful
$*$-homomorphism and it intertwines the group action, we have:

(2.40)
$|||x|||=\sup_{s\in\mathcal{S}}||x-sxs^{*}||=\sup_{s\in\mathcal{S}}||\pi(x)-\lambda_{s}\pi(x)||=|||\pi(x)|||\hskip
2.84544pt.$

Using these observations, we can now prove:

######  Lemma 2.14.

For a finite dimensional quantum system $\mathcal{N}$. Again for simplicity
assume $\mathcal{N}=\mathbb{B}(\mathcal{H})$ for some finite dimensional
Hilbert space $H$. Let $\mathcal{U}$ be a symmetric set of discrete resources
and let $\mathcal{S}=\mathcal{U}-\\{e\\}$ be the set of generators that
generate a discrete subgroup $\Gamma$ in the group of unitaries in
$\mathcal{N}$. Let $\nu,\mu$ be the measures defined in the discussion before
this lemma. Then we have:

(2.41) $EL_{\mathcal{U}}(\mathcal{A})\leq\mathbb{E}_{\mu}(\ell_{\mathcal{S}})$

where $\ell_{\mathcal{S}}$ is the word-length function induced by the
generators $\mathcal{S}$. And a similar result holds for the correlation-
assisted expected length.

###### Proof.

Using the same notation as the discussion before this lemma, the Lipschitz
space $\mathcal{A}=\\{x\in N:E_{fix}x=0\\}=\\{x\in N:g^{*}xg=x\text{ for all
}g\in\Gamma\\}$. The Lipschitz norm is given by:
$|||x|||=\sup_{s\in\mathcal{S}}||x-sxs^{*}||$. Let
$V_{n}:=\\{g\in\Gamma:\ell_{\mathcal{S}}(g)\leq n\\}$. Then on
$\ell_{\infty}(\Gamma,N)$, the convolution by $\nu^{\star n}$ can be written
as:

$\nu^{\star n}\star f=\sum_{g\in V_{n}}\mathbb{P}_{e}^{n}(g)\lambda_{g}f$

where the probability measure $\mathbb{P}_{e}^{n}(g)$ is the probability of
hitting $g$ in $n$-steps starting from the identity $e$. This measure has
support in $V_{n}$. For each $g$, fix the reduced word representation
$g=\prod_{1\leq i\leq\ell_{\mathcal{S}}(g)}s_{i}$ where $s_{i}\in\mathcal{S}$.
Then using the observations before this lemma, for $x\in\mathcal{A}$ we have:

(2.42)
$\displaystyle\begin{split}||x||&=||x-E_{fix}x||=||\pi(x)-P_{\mu}\pi(x)||\leq\lim_{N\rightarrow\infty}\frac{1}{N}\sum_{0\leq
n\leq N-1}||\pi(x)-\nu^{\star n}\star\pi(x)||\\\
&\leq\lim_{N\rightarrow\infty}\frac{1}{N}\sum_{0\leq n\leq N-1}\sum_{g\in
V_{n}}\mathbb{P}^{n}_{e}(g)||\pi(x)-\lambda_{g}\pi(x)||\\\
&=\lim_{N\rightarrow\infty}\frac{1}{N}\sum_{0\leq n\leq N-1}\sum_{g\in
V_{n}}\mathbb{P}_{e}^{n}(g)\sum_{1\leq
i\leq\ell_{\mathcal{S}}}||\pi(x)-\lambda_{s_{i}}\pi(x)||\\\
&\leq\lim_{N\rightarrow\infty}\frac{1}{N}\sum_{0\leq n\leq N-1}\sum_{g\in
V_{n}}\mathbb{P}^{n}_{e}(g)\ell_{\mathcal{S}}(g)\sup_{s\in\mathcal{S}}||\pi(x)-\pi(sxs^{*})||=\mathbb{E}_{\mu}(\ell_{\mathcal{S}})|||x|||\hskip
2.84544pt.\end{split}$

Therefore we have
$EL_{\mathcal{U}}(\mathcal{A})\leq\mathbb{E}_{\mu}(\ell_{\mathcal{S}})$. ∎

Compared with the case of continuous resources, a lower bound by the expected
length is missing for discrete resources. The main difficulty to mimick the
construction in the continuous case is the transference principle. More
specifically, one would like to consider the following function:
$f_{\mathcal{S}}(g):=\mathbb{E}_{\mu}(\ell_{\mathcal{S}})-\ell_{\mathcal{S}}(g)$
for $\ell_{\mathcal{S}}(g)\leq
d_{min}:=\min\\{d\in\mathbb{N}:|d-\mathbb{E}_{\mu}(\ell_{\mathcal{S}})|<1\\}$
and $f_{\mathcal{S}}(g)=0$ for $\ell_{\mathcal{S}}(g)>d_{min}$. It is clear
that for all $s\in S$, we have:

$||\lambda_{s}f_{\mathcal{S}}-f_{\mathcal{S}}||\leq 1\hskip 2.84544pt.$

Then it is not difficult to see that if $\mathcal{N}=\mathbb{C}$ is trivial,
then we have the lower bound: $\mathbb{E}_{\mu}(\ell_{S})\leq
EL_{\mathcal{U}}(\ell_{\infty}(\Gamma))$. Indeed, given Lemma 2.10, this lower
bound should not come as a surprise. However,
$f_{\mathcal{S}}\in\ell_{\infty}(\Gamma)$ is not in the image of the
transference map $\pi(\mathcal{N})$. Therefore, this lower bound on
$\ell_{\infty}(\Gamma)$ cannot be transfered back to a lower bound on
$\mathcal{N}$.

##  3\. Resource-dependent complexity estimates for open systems

###  3.1. Discrete gates as resource

Suppose $S=\\{U_{1},\cdots,U_{l}\\}\subset\mathbb{M}_{d}$ is a set of
unitaries. Moreover, we assume it to be symmetric. The set of channels we will
consider is $CP_{S}(\mathbb{M}_{d})$. For dynamics, recall that the
Hamiltonian-free Lindblad generator is given by the jump operators from the
above gate set. Recall that the Lipschitz norm is given as follows:

(3.1) $|||X|||_{S}:=\sup_{j=1,\cdots,l}\|[U_{j},X]\|_{\infty}.$

The mean zero space is given by
$\mathcal{A}=\\{x\in\mathbb{M}_{d}:E_{S^{\prime}}(x)=0\\}$. The complete
complexity of any channel $\Phi$ is given by

$\displaystyle
C_{S}^{cb}(\Phi):=\|\Phi^{*}-id:(\mathcal{A},|||\cdot|||_{S})\to\mathbb{M}_{d}\|_{cb}.$

Suppose we are given a unitary channel from $S$, i.e.,

$\Phi_{\mu}:=\sum_{i}\mu_{i}U_{i}\cdot U_{i}^{*},$

where $\\{\mu_{i}\\}_{i}$ is a probability measure. Then we are able to give
an upper bound of the complexity of the dynamics driven by $\Phi_{\mu}$:

######  Proposition 3.1.

The evolution

(3.2) $T_{t}:=\exp(t(\Phi_{\mu}-I))$

satisfies

(3.3) $C_{S}^{cb}(T_{t})\leq t.$

###### Proof.

First we claim that

(3.4) $C_{S}^{cb}(\Phi_{\mu})\leq 1.$

In fact, for any $X\in\mathcal{A}$,

$\displaystyle\|\Phi_{\mu}^{*}(X)-X\|_{cb}$
$\displaystyle=\|\sum_{i}\mu_{i}(U_{i}^{*}XU_{i}-X)\|_{cb}\leq\sum_{i}\mu_{i}\|U_{i}^{*}XU_{i}-X\|_{cb}$
$\displaystyle=\sum_{i}\mu_{i}\|U_{i}^{*}X-XU_{i}^{*}\|_{cb}=\sum_{i}\mu_{i}\|[U_{i}^{*},X]\|_{cb}\leq|||X|||^{cb}_{S}.$

Recall that

(3.5)
$T_{t}:=\exp(t(\Phi_{\mu}-I))=\sum_{k=0}^{\infty}\frac{t^{k}}{k!}e^{-t}\Phi_{\mu}^{k}.$

Then by convexity and subadditivity under concatenation, we have

$\displaystyle
C_{S}^{cb}(T_{t})\leq\sum_{k=0}^{\infty}\frac{t^{k}}{k!}e^{-t}C_{S}^{cb}(\Phi_{\mu}^{k})\leq\sum_{k=0}^{\infty}\frac{t^{k}}{k!}e^{-t}k=t.$

∎

For the lower bound estimate, we first connect the complexity of a class of
channels to its return time to its fixed point.

Suppose $\Phi$ is an arbitrary quantum channel with the same fixed point
algebra $\mathcal{N}_{fix}=S^{\prime}$ and we define its (complete) return
time $t^{(cb)}(\varepsilon,\Phi)$:

(3.6)
$t^{(cb)}(\varepsilon,\Phi):=\inf\\{k\in\mathbb{N}:\|(\Phi^{*})^{k}-E_{fix}\|^{(cb)}_{\infty\to\infty}\leq\varepsilon\\},$

where $E_{fix}=E_{S^{\prime}}$ is the trace-preserving conditional expectation
onto the fixed point algebra.

######  Proposition 3.2.

For any channel $\Phi$ with the same fixed point algebra $\mathcal{N}_{fix}$,
and we assume that for some $\varepsilon>0$, the (complete) return time is
finite. Then we have

(3.7) $(1-\varepsilon)C^{(cb)}_{S}(E_{fix})\leq
t^{(cb)}(\varepsilon,\Phi)C^{(cb)}_{S}(\Phi).$

###### Proof.

We only show $(1-\varepsilon)C_{S}(E_{fix})\leq
t(\varepsilon,\Phi)C_{S}(\Phi)$ and the correlation-assisted version holds
true by just replacing every channel by its $m$-th amplification. Without loss
of generality, we assume $k=t(\varepsilon,\Phi)<\infty$, then we have

(3.8) $\|(\Phi^{*})^{k}-E_{fix}\|_{\infty\to\infty}\leq\varepsilon.$

Calculating $C_{Lip_{L}}(E_{fix})$, we have

$\displaystyle C_{S}(E_{fix})$
$\displaystyle=\|E_{fix}-id:(\mathcal{A},|||\cdot|||_{S})\to
L_{\infty}(\mathbb{M}_{d})\|$
$\displaystyle=\|E_{fix}-(\Phi^{*})^{k}+(\Phi^{*})^{k}-id:(\mathcal{A},|||\cdot|||_{S})\to
L_{\infty}(\mathbb{M}_{d})\|$ $\displaystyle\leq
C_{S}(\Phi^{k})+\|E_{fix}-(\Phi^{*})^{k}:(\mathcal{A},|||\cdot|||_{S})\to
L_{\infty}(\mathbb{M}_{d})\|.$

Recall that the fixed point algebra of $\Phi$ is $\mathcal{N}_{fix}$, we have
$(\Phi^{*})^{k}E_{fix}=E_{fix}(\Phi^{*})^{k}=E_{fix}$, then

(3.9) $E_{fix}-(\Phi^{*})^{k}=(id-E_{fix})(E_{fix}-(\Phi^{*})^{k}).$

Using the following diagram

${(\mathcal{A},\|\cdot\|_{S})}$${L_{\infty}(\mathbb{M}_{d})}$${L_{\infty}(\mathbb{M}_{d})}$$\scriptstyle{id-
E_{fix}}$$\scriptstyle{E_{fix}-(\Phi^{*})^{k}}$$\scriptstyle{E_{fix}-(\Phi^{*})^{k}}$

we have

$\displaystyle\|E_{fix}-(\Phi^{*})^{k}:(\mathcal{A},|||\cdot|||_{S})\to
L_{\infty}(\mathbb{M}_{d})\|$ $\displaystyle\leq
C_{S}(E_{fix})\|(\Phi^{*})^{k}-E_{fix}\|_{\infty\to\infty}$
$\displaystyle\leq\varepsilon C_{S}(E_{fix}).$

In summary, we showed that

$\displaystyle C_{S}(E_{fix})\leq\varepsilon
C_{S}(E_{fix})+C_{S}(\Phi^{k})\leq\varepsilon C_{S}(E_{fix})+kC_{S}(\Phi),$

which implies $(1-\varepsilon)C_{Lip_{L}}(E_{fix})\leq
t(\varepsilon,\Phi)C_{Lip_{L}}(\Phi)$. ∎

To provide a lower bound, we need to assume $\Phi_{\mu}$ is symmetric such
that we get bounded return time. The dynamical evolution
$T_{t}=\exp(t(\Phi_{\mu}-id))$ converges to $E_{fix}$ as $t$ goes to infinity
and moreover [GJLL22],

(3.10)
$k^{cb}(\frac{1}{2}):=\inf\\{t>0:\|T_{t}-E_{fix}\|_{cb}\leq\frac{1}{2}\\}<\infty.$

Now we are ready to provide the lower bound of complexity of $T_{t}$:

######  Theorem 3.3.

Suppose $T_{t}$ given by (3.2) is symmetric, i.e., $T_{t}=T_{t}^{*}$, then

(3.11) $C^{cb}_{Lip_{L}}(T_{t})\asymp\begin{cases}t,\ t\leq
k^{cb}(\frac{1}{2}),\\\ C^{cb}_{S}(E_{fix}),\ t\geq
k^{cb}(\frac{1}{2}).\end{cases}$

Here $a\asymp b$ means there exist universal constants $C_{1},C_{2}>0$ such
that $C_{1}b\leq a\leq C_{2}b$.

###### Proof.

We only show the case for $C_{S}(T_{t})$, and the complete version has exactly
the same proof. If $t\leq k^{cb}(\frac{1}{2})$, the upper bound follows from
the previous proposition. For the lower bound, we choose $k\geq 1$ such that

(3.12) $(k-1)t\leq k^{cb}(\frac{1}{2})\leq kt.$

Then

$\displaystyle C_{S}(E_{fix})$
$\displaystyle=\|E_{fix}-id:(\mathcal{A},|||\cdot|||_{S})\to
L_{\infty}(\mathbb{M}_{d})\|$
$\displaystyle=\|E_{fix}-(T_{t})^{k}+(T_{t})^{k}-id:(\mathcal{A},|||\cdot|||_{S})\to
L_{\infty}(\mathbb{M}_{d})\|$ $\displaystyle\leq
C_{S}(T_{t}^{k})+\|E_{fix}-(T_{t})^{k}:(\mathcal{A},|||\cdot|||_{S})\to
L_{\infty}(\mathbb{M}_{d})\|$ $\displaystyle\leq
kC_{S}(T_{t})+C_{S}(E_{fix})\|E_{fix}-(T_{t})^{k}\|_{\infty\to\infty}$
$\displaystyle\leq kC_{S}(T_{t})+\frac{1}{2}C_{S}(E_{fix}).$

Therefore,

$\displaystyle
C_{S}(T_{t})\geq\frac{C_{S}(E_{fix})}{2k}\geq\frac{tC_{S}(E_{fix})}{2(k^{cb}(\frac{1}{2})/t+1)}\geq\frac{tC_{S}(E_{fix})}{4k^{cb}(\frac{1}{2})},$

where in the last two inequalities, we used (3.12) and the fact that $t\leq
k^{cb}(\frac{1}{2})$.

If $t\geq k^{cb}(\frac{1}{2})$, we have
$\|E_{fix}-T_{t}\|_{\infty\to\infty}\leq\frac{1}{2}$,

$\displaystyle C_{S}(E_{fix})$
$\displaystyle=\|E_{fix}-id:(\mathcal{A},|||\cdot|||_{S})\to
L_{\infty}(\mathbb{M}_{d})\|$
$\displaystyle=\|E_{fix}-T_{t}+T_{t}-id:(\mathcal{A},|||\cdot|||_{S})\to
L_{\infty}(\mathbb{M}_{d})\|$ $\displaystyle\leq
C_{S}(T_{t})+\frac{1}{2}C_{S}(E_{fix}),$

thus $C_{S}(T_{t})\geq\frac{1}{2}C_{S}(E_{fix})$. Similarly, we can show that
$C_{S}(T_{t})\leq\frac{3}{2}C_{S}(E_{fix})$, by bounding $C_{S}(T_{t})$. ∎

###  3.2. Continuous case: infinitesimal generators as resource

We take $\mathcal{N}=\mathbb{M}_{d}$ and $L:\mathbb{M}_{d}\to\mathbb{M}_{d}$
as a self-adjoint Lindbladian, i.e.,

(3.13)
$L(x)=\sum_{j}\big{(}a_{j}xa_{j}-\frac{1}{2}(a_{j}^{2}x+xa_{j}^{2})\big{)},$

where $a_{j}$ are self-adjoint. Denote $\tau$ as the normalized trace,
$\mathcal{N}_{fix}=\\{X\in\mathbb{M}_{d}:[a_{j},X]=0,\forall j\\}$ and
$E_{fix}$ is the trace-preserving conditional expectation onto
$\mathcal{N}_{fix}$. The resource set, denoted by $\Delta$ is given by

(3.14) $\Delta:=\\{a_{j}\\}.$

We can define the resource-dependent Lipschitz norm and complexity
$|||\cdot|||_{\Delta},C_{\Delta}$ as before. The mean 0 space is given by
$\mathcal{A}=\\{X\in\mathbb{M}_{d}:E_{fix}(X)=0\\}.$ In order to estimate
$C_{\Delta}(T_{t})$, where $T_{t}=e^{tL}$, we need to introduce the another
Lipschitz norm, induced by the gradient form. Recall the gradient form of $L$
is defined by

(3.15) $\Gamma_{L}(x,y):=L(x^{*}y)-x^{*}L(y)-L(x^{*})y,\
x,y\in\mathbb{M}_{d}.$

We define the Lipschitz norm via the gradient form:

(3.16)
$|||X|||_{\Gamma}:=\max\\{\|\Gamma_{L}(X,X)\|_{\infty}^{\frac{1}{2}},\|\Gamma_{L}(X^{*},X^{*})\|_{\infty}^{\frac{1}{2}}\\}.$

Recall that for any $X\in\mathcal{A}$,
$|||X|||_{\Delta}=\sup_{j}||[a_{j},X]||=\sup_{j}||[a_{j},X^{*}]||=|||X^{*}|||_{\Delta}$,
by definition, we can show that

(3.17) $|||X|||_{\Gamma}\leq\sqrt{|\Delta|}\cdot|||X|||_{\Delta}.$

The Lipschitz norm $|||\cdot|||_{\Gamma}$ induces a quantum metric on the
state space:

(3.18) $\|\rho\|_{\Gamma^{*}}=\sup\\{|\tau(\rho
X)|\big{|}E_{fix}(X)=0,\|X\|_{\Gamma}\leq 1\\}.$

To establish an upper bound, we make use of modified logarithmic Sobolev
inequality. Recall that $\\{T_{t}:=\exp(tL)\\}$ satisfies the
$\lambda$-modified logarithmic Sobolev inequality ($\lambda$-MLSI) if there
exists a constant $\lambda>0$ such that the relative entropy has exponential
decay:

(3.19) $D(T_{t}\rho\|E_{fix}\rho)\leq e^{-\lambda t}D(\rho\|E_{fix}\rho)$

The largest constant $\lambda$ for which the relative entropy decays
exponentially is denoted as $\text{MLSI}(L)$ (the MLSI constant of $L$). We
denote the best constant as $\text{CLSI}(L)$ if we consider the complete
version. By definition, the fixed point algebra $\mathcal{N}_{fix}$ of
$\\{T_{t}\\}_{t\geq 0}$ is tracial-orthogonal to the Lipschitz subspace
$\mathcal{A}$.

Recall the notation of index of a von Neumann subalgebra
$\mathcal{M}\subset\mathcal{N}$. Let
$E_{\mathcal{M}}:\mathcal{N}\rightarrow\mathcal{M}$ be the conditional
expectation onto $M$ (with respect to the trace):

(3.20) $\text{Ind}(\mathcal{N}:\mathcal{M}):=\inf\\{\alpha>0:\rho\leq\alpha
E_{\mathcal{M}}^{*}(\rho)\text{ , }\forall\rho\in
L_{1}(\mathcal{N})_{+}\\}\hskip 2.84544pt.$

For example, $\text{Ind}(M_{n}(\mathbb{C}):\mathbb{C})=n$ and
$\text{Ind}(M_{n}(\mathbb{C}):\ell_{\infty}^{n})=n$. Hence the index is a
proper notion of relative size of $\mathcal{M}$ in $\mathcal{N}$.

We recall the following result from [GJL20a, Corollary 6.8]:

######  Proposition 3.4.

If the Lindbladian $L$ generates a semigroup that satisfies $\lambda$-MLSI,
then we have:

(3.21) $||\rho-E_{fix}^{*}\rho||_{\Gamma^{*}}\leq
4\sqrt{\frac{2D(\rho\|E^{*}_{fix}\rho)}{\lambda}}$

for any state $\rho$, where $||\cdot||_{\Gamma^{*}}$ is dual to the Lipschitz
norm $|||\cdot|||_{Lip_{L}}$.

Note that in the tracial setting, $E_{fix}^{*}=E_{fix}$. Then we can get an
upper estimate for the expected length:

######  Lemma 3.5.

The expected length of $\mathcal{A}$ is bounded above by:

(3.22) $EL_{\Delta}^{cb}(\mathcal{A}):=C_{\Delta}^{cb}(E_{fix})\leq
4\sqrt{\frac{2|\Delta|\sup_{\rho}D^{cb}(\rho\|E_{fix}\rho)}{\text{CLSI}(L)}}\leq
4\sqrt{\frac{2|\Delta|\log(\text{Ind}^{cb}(\mathcal{N}:\mathcal{N}_{fix}))}{\text{CLSI}(L)}}.$

###### Proof.

We only prove the case for $EL_{\Delta}(\mathcal{A})$ and the complete version
follows from the same argument.

First, using the relation between the two Lipschitz norms
$|||\cdot|||_{\Gamma}$ and $|||\cdot|||_{\Delta}$, we have:

(3.23)
$||id:(\mathcal{A},|||\cdot|||_{\Delta})\rightarrow(\mathcal{A},|||\cdot|||_{\Gamma})||\leq\sqrt{|\Delta|}\hskip
2.84544pt.$

Then using the definition of expected length, we have:

(3.24)
$\displaystyle\begin{split}EL_{\Delta}(\mathcal{A})&=||id:(\mathcal{A},|||\cdot|||_{\Delta})\rightarrow\mathcal{N}||\leq\sqrt{|\Delta|}||id:(\mathcal{A},|||\cdot|||_{\Gamma})\rightarrow\mathcal{N}||\\\
&=\sqrt{|\Delta|}\cdot||E_{fix}-id:(\mathcal{A},|||\cdot|||_{\Gamma})\rightarrow\mathcal{N}||\\\
&=\sqrt{|\Delta|}\cdot||E^{*}_{fix}-id:L_{1}(\mathcal{N})\rightarrow(\mathcal{A},|||\cdot|||_{\Gamma})^{*}||\\\
&\leq
4\sqrt{\frac{2|\Delta|\sup_{\rho}D(\rho\|E_{fix}\rho)}{\text{MLSI}(L)}}\end{split}$

where the equation in the second line follows from $E_{fix}(\mathcal{A})=0$
and the inequality follows from Proposition 3.4. This gives the first upper
bound. For the second upper bound, we used the result in [GJL20b]:

(3.25)
$D_{\mathcal{N}_{fix}}\leq\log\text{Ind}(\mathcal{N}:\mathcal{N}_{fix})\hskip
2.84544pt.$

where
$D_{\mathcal{N}_{fix}}:=\sup_{\rho:\operatorname{tr}\rho=1}D(\rho|E^{*}_{fix}\rho)$
is the maximum entropy [GJL20b, GR22] and the maximum entropy is bounded above
by the log-index [GJL20b, GR22]. ∎

Combining the above lemma and the elementary property (4) of Lemma 2.4, the
upper estimate of $C_{\Delta}^{cb}(T_{t})$ is clear:

######  Theorem 3.6.

Suppose $T_{t}=\exp(tL)$ where $L$ is given by (3.13). Then we have the
following upper estimate: for any $t\geq 0$,

(3.26) $C_{\Delta}^{cb}(T_{t})\leq
4\sqrt{\frac{2|\Delta|\log(\text{Ind}^{cb}(\mathcal{N}:\mathcal{N}_{fix}))}{\text{CLSI}(L)}}\|L\|_{cb}t.$

Since the return time argument works for any symmetric quantum channel, the
lower bound can also be derived, as in the last subsection:

######  Theorem 3.7.

Define the return time for $T_{t}=\exp(tL)$ with L given by (3.13):

(3.27)
$k^{cb}(\frac{1}{2}):=\inf\\{t>0:\|T_{t}-E_{fix}\|_{cb}\leq\frac{1}{2}\\}<\infty.$

Then the lower bound estimate of $C_{\Delta}^{cb}(T_{t})$ is given as follows:

(3.28) $\displaystyle
C_{\Delta}^{cb}(T_{t})\geq\frac{tC_{S}(E_{fix})}{4k^{cb}(\frac{1}{2})},t\leq
k^{cb}(\frac{1}{2}).$ (3.29) $\displaystyle C_{\Delta}^{cb}(T_{t})\asymp
C^{cb}_{\Delta}(E_{fix}),\ t>k^{cb}(\frac{1}{2}).$

##  4\. Hörmander Systems, Carnot-Caratheodory Distance, and Nielsen’s
Complexity

In this section, we apply the Lipschitz complexity measure to the canonical
Lipschitz norm associated with a Hörmander system on a compact Lie group. The
geometric approach to characterize the complexity of a unitary operator by its
distance to the identity operator is due to Nielsen [Nie06, NDGD06a, NDGD06b].
In some cases, the geometric notion of complexity is equivalent to the more
familiar quantum circuit cost. The key idea in defining the geometric quantum
complexity measure is to regard the infinitesmial generators of the unitary
operators as resources. Using a given set of infinitesimal generators, one can
iteratively construct an efficient realization of unitary operators. This is
the familiar idea of Hamiltonian simulation. From this perspective, it is
natural and important for us to recast Nielsen’s geometric complexity in the
language of quantum metric spaces and Lipschitz norms. One advantage of this
new framework is the added ability to characterize the Markovian dynamics of
certain open quantum systems. Such dissipative dynamics has been used to
design and engineer entangled states [CEHM99][ED23]. Therefore it is necessary
to be able to characterize the complexity of the dissipative channels used to
prepare these states.

Given the Killing-Cartan inner product on $\mathfrak{g}$, we can define the
following Lipschitz norm:

######  Definition 4.1.

Let $H=\\{X_{1},...,X_{n}\\}\\!\\!\subset\\!\\!\mathfrak{g}$ be a Hörmander
system (c.f. Definition 2.11) where the generators are orthonormal under the
Killing-Cartan form. In addition, fix a finite von Neumann algebra along with
its canonical trace $(\mathcal{N},\tau)$. The Lipschitz norm on
$L_{\infty}(G,\mathcal{N})$ is given by:

(4.1) $\Gamma_{H}(f):=||\sum_{1\leq i\leq n}|[X_{i},f]|^{2}||=||\sum_{1\leq
i\leq n}\langle[X_{i},f],[X_{i},f]\rangle_{G}||$

where $\langle\cdot,\cdot\rangle_{G}$ denotes the bi-invariant metric on $G$
induced by the Killing-Cartan form and $||\cdot||$ is the norm on the von
Neumann algebra $L_{\infty}(G,\mathcal{N})$.

In fact, the definition only depends on the subspace spanned by the generators
in the Hörmander system.

######  Lemma 4.2.

Let $H^{\prime}:=\\{Y_{j}\\}_{1\leq j\leq n}$ be another orthonormal basis of
the subspace $\mathfrak{g}_{H}:=\text{span}\\{X_{i}:X_{i}\in H\\}$. Then
$\Gamma_{H^{\prime}}(f)=\Gamma_{H}(f)$ for any finite von Neumann algebra
$\mathcal{N}$ and any function $f\in L_{\infty}(G,\mathcal{N})$.

###### Proof.

This is simple change-of-basis calculation. Since the norm we used through-out
is the Killing-Cartan norm, we have:

$\displaystyle\begin{split}\sum_{1\leq j\leq n}|[Y_{j},f]|^{2}=\sum_{1\leq
j\leq n,1\leq i\leq
n}\langle\gamma_{ji}[X_{i},f],\gamma_{ji}[X_{i},f]\rangle=\sum_{1\leq i\leq
n}\langle[X_{i},f],[X_{i},f]\rangle=\sum_{1\leq i\leq
n}|[X_{i},f]|^{2}\end{split}$

where $Y_{j}=\sum_{1\leq i\leq n}\gamma_{ji}X_{i}$ is the change of basis, and
the matrix $(\gamma_{ji})_{ji}$ is an orthogonal matrix under the Killing-
Cartan form. ∎

Using the Carnot-Caratheodory metric, we can define a notion of diameter of a
Lie group:

######  Definition 4.3.

Let $H$ be a Hörmander system of $G$, then the Carnot-Caratheodory diameter of
$G$ is given by:

(4.2) $diam_{H}(G):=\sup_{x,y\in G}d_{H}(x,y)\hskip 2.84544pt.$

The Carnot-Caratheodory metric gives us a resource-dependent way to measure
the distance of a given unitary operator to the identity: $d_{H}(x,1)$. This
distance depends on the Hörmander system and thus depends on the resources.
The longer the distance, the more resource one needs to prepare the operator
$x$. This is exactly the original geometric insight of Nielsen [Nie06].

######  Remark 4.4.

One intriguing fact is that the Lipschitz complexity induced by the Lipschitz
metric $\Gamma_{H}$ only depends on the subspace spanned by $H$ (c.f. Lemma
4.2). This observation gives us additional degrees of freedom to potentially
provide tighter bounds on the complexity.

Given a finite dimensional unitary representation $\pi:G\rightarrow U(n)$,
$n\in\mathbb{N}$ the Hörmander system $H$ induces another system $d\pi(H)$ in
the Lie algebra $\mathfrak{su}(n)$. $d\pi(H)$ is a Hörmander system for the
image $\pi(G)$, but it may not be a Hörmander system for the full Lie group
$U(n)$. However, the following dimension-free estimates hold (independent of
the dimension of the representation):

######  Theorem 4.5.

Let $f:G\rightarrow\mathbb{R}^{+}$ be a normalized function
$\int_{G}f(g)dg=1$. Let $\pi:G\rightarrow U(n)$ be a finite-dimensional
unitary representation and let $H\\!\\!\subset\\!\\!\mathfrak{g}$ be a
Hörmander system of $G$. Then we have:

  1. (1)

Consider the channel:

(4.3) $\Phi_{f,\pi}:L_{1}(\mathbb{M}_{n})\rightarrow
L_{1}(\mathbb{M}_{n}):\rho\mapsto\int_{G}f(g)\pi(g)\rho\pi(g)^{*}dg$

where $L_{1}(\mathbb{M}_{n})$ is the trace-class operators on the
$n$-dimensional Hilbert space. Then we have:

(4.4) $C_{H}(\Phi_{f,\pi})\leq diam_{H}(G)$

where
$C_{H}(\Phi_{f,\pi})=||\Phi_{f,\pi}-id:L_{1}(\mathbb{M}_{n})\rightarrow(\mathbb{B}(N),||\cdot||_{\Gamma_{H}})||$
is the complexity of the channel $\Phi_{f,\pi}$ using the Lipschitz norm
$||\cdot||_{H}$ induced by the Hörmander system $H$.

  2. (2)

Fix an orthonormal basis $\\{X_{i}\\}_{1\leq i\leq n}$ of the subspace
$\text{span}\\{H\\}$ spanned by the Hörmander system. Consider the associated
symmetric Lindbladian:

(4.5)
$\mathcal{L}_{H}:\mathbb{M}_{n}\rightarrow\mathbb{M}_{n}:x\mapsto\sum_{1\leq
i\leq n}[d\pi(X_{i}),[d\pi(X_{i}),x]]\hskip 2.84544pt.$

Then we have:

(4.6) $C_{H}(\exp(-t\mathcal{L}_{H}))\leq
C\sqrt{t}\Gamma(\frac{\delta_{H}+3}{2})$

where $\Gamma(\cdot)$ is the usual Gamma function, $\delta_{H}$ is the
Hausdorff dimension of $G$ under the metric topoology induced by the Carnot-
Caratheodory metric, and $C>0$ is an absolute constant.

###### Proof.

For the first statement, the proof is analogous to the original Nielsen’s
argument of complexity upper bound [Nie06]. For every unitary $\pi(g)\in
U(n)$, fix a geodesic $\gamma_{u}(t)$ subordinated to the Carnot-Caratheodory
metric such that $\gamma_{g}(0)=1$ and $\gamma_{g}(1)=\pi(g)$. Then for
$x\in\mathcal{A}:=\\{x\in\mathbb{M}_{n}:E_{fix}x=0\\}$ where $E_{fix}$ is the
projection onto the fixed point algebra of $\Phi_{f,\pi}$, we consider
$x_{g}(t):=\gamma_{g}(t)^{*}x\gamma_{g}(t)$. And we have:

(4.7)
$\displaystyle\begin{split}||x_{g}(1)-x_{g}(0)||_{\infty}&\leq\int_{0}^{1}||[\gamma^{\prime}_{g}(t),x]||_{\infty}dt=\int_{0}^{1}||\sum_{1\leq
i\leq n}[g_{i}(t)X_{i}(t),x]||_{\infty}dt\\\
&\leq\Gamma_{H}(x)^{1/2}\int_{0}^{1}||\sum_{1\leq i\leq
n}|g_{i}(t)|^{2}||^{1/2}dt=\Gamma_{H}(x)^{1/2}\int_{0}^{1}||\gamma^{\prime}_{g}(t)||dt\end{split}$

where $\\{X_{i}\\}_{1\leq i\leq n}$ is an orthonormal basis of the subspace
spanned by the Hörmander system $H$ and $\gamma^{\prime}_{g}(t)=\sum_{1\leq
i\leq n}g_{i}(t)X_{i}(t)$ is the orthonormal expansion of the derivative in
terms of the left-translated basis $\\{X_{i}(t)\\}_{1\leq i\leq n}$. Then by
convexity, we have:

(4.8)
$\displaystyle\begin{split}||\Phi_{f,\pi}^{*}(x)-x||_{\infty}&\leq\int_{G}dgf(g)||\pi(g)^{*}x\pi(g)-x||_{\infty}=\int_{G}dgf(g)||x_{g}(1)-x_{g}(0)||_{\infty}\\\
&\leq\int_{G}dgf(g)\Gamma_{H}(x)^{1/2}d_{H}(x,1)\end{split}$

where $d_{H}(\cdot,1)$ is the Carnot-Caratheodory distance from the identity.
Hence by the definition of the Lipschitz complexity, we have:
$C_{H}(\Phi_{f,\pi})\leq\int_{G}dgf(g)d_{H}(g,1)\leq
diam_{H}(G)\int_{G}dgf(g)=diam_{H}(G)$.

For the second statement, we need the point-wise heat kernel estimates on a
unimodular Lie group [VSCC93]. By a transference principle [GJL21], we
consider the unital $*$-homomorphism: $\varphi:\mathbb{M}_{n}\rightarrow
L_{\infty}(G,\mathbb{M}_{n}):x\mapsto\varphi(x)(g)=\pi(g)^{*}x\pi(g)$. And the
transfered Lindbladian is given by:
$\mathcal{L}_{\Delta}(f)(g)=\Delta_{H}f(g)$ where $\Delta_{H}=\sum_{1\leq
i\leq n}X_{i}^{2}$ is the Laplacian associated with the orthonormal basis
$\\{X_{i}\\}_{i}$. Denote the corresponding heat kernel as
$h_{t}^{\Delta}(g,h)$, then the semi-group acts on $x\in\mathbb{M}_{n}$ by
convolution:

$\exp(-t\mathcal{L}^{*}_{H})x=\int_{G}dgh_{t}^{\Delta}(1,g^{-1})\pi(g)^{*}x\pi(g)\hskip
2.84544pt.$

Thus by the first statement, we have:

(4.9)
$\displaystyle\begin{split}C_{H}(\exp(-t\mathcal{L}_{H}))\leq\int_{G}dgh_{t}^{\Delta}(1,g^{-1})d_{H}(1,g)\hskip
2.84544pt.\end{split}$

Using the pointwise heat kernel estimate [VSCC93], we have:

(4.10) $\displaystyle\begin{split}C_{H}(\exp(-t\mathcal{L}_{H}))&\leq
C\int_{G}dgt^{-\delta_{H}/2}\exp(-\frac{d_{H}(1,g)^{2}}{Ct})d_{H}(1,g)\\\
&\lessapprox\int_{0}^{diam_{H}(G)}drr^{\delta_{H}-1}t^{-\delta_{H}/2}\exp(-\frac{r^{2}}{Ct})r\\\
&\lessapprox\sqrt{t}\int_{0}^{\infty}dss^{\delta_{H}/2}\exp(-s)=C\sqrt{t}\Gamma(\frac{\delta_{H}+2}{2})\end{split}$

where $s:=r^{2}/t$. ∎

##  5\. More examples: Clifford Gates as Resources

In this section, we consider a special type of resources, namely the Clifford
gates. In the fundamental representation of a complex Clifford algebra
$C\ell_{n}(\mathbb{C})\cong M_{2^{[n/2]}}(\mathbb{C})$, the generators of the
Clifford algebra can be taken to satisfy the following conditions:

(5.1) $\\{c_{j},c_{k}\\}=2\delta_{jk}\text{ , }c_{j}=c_{j}^{*}\hskip
2.84544pt.$

In particular, each $c_{j}$ is both unitary and self-adjoint. As such, the set
$\\{c_{j}\\}_{1\leq j\leq n}$ induces a set of discrete quantum resources and
a set of continuous quantum resources (c.f. Section 2). For $1\leq j\leq n$,
let $a_{j}:=-i\log c_{j}$ be the self-adjoint generator of the unitary
$c_{j}$. Then denote the discrete Clifford resource set as:
$\mathcal{S}_{n}:=\\{c_{j}\\}_{1\leq j\leq n}$ and denote the continuous
Clifford resource set as: $\Delta_{n}:=\\{a_{j}\\}_{1\leq j\leq n}$. The two
sets of resources define two different Lipschitz norms on the matrix algebra
$M_{2^{[n/2]}(\mathbb{C})}$:

(5.2) $|||x|||_{\mathcal{S}}:=\sup_{1\leq j\leq
n}||c_{j}xc_{j}^{*}-x||=\sup_{j}||[c_{j},x]||\hskip 2.84544pt,$ (5.3)
$|||x|||_{\Delta}:=\sup_{1\leq j\leq n}||[a_{j},x]||\hskip 2.84544pt.$

The two corresponding notions of Lipschitz complexities have a simple
relation:

######  Lemma 5.1.

On the matrix algebra $M_{2^{[n/2]}}(\mathbb{C})$ the following statements are
true:

  1. (1)

The annihilator subspaces of $\mathcal{S}_{n}$ and $\Delta_{n}$ are the same:

(5.4) $[a_{j},x]=0\text{ , }\forall 1\leq j\leq n\iff[c_{j},x]=0\text{ ,
}\forall 1\leq j\leq n\hskip 2.84544pt;$

  2. (2)

There exists a contraction:

(5.5)
$id:(\mathcal{A},|||\cdot|||_{\Delta})\rightarrow(\mathcal{A},|||\cdot|||_{\mathcal{S}})$

where $\mathcal{A}$ is the tracial-orthogonal subspace to the annihilator
subspace;

  3. (3)

For channel $\Phi\in
CP_{\mathcal{S}}(M_{2^{[n/2]}}(\mathbb{C}),M_{2^{[n/2]}}(\mathbb{C}))\cap
CP_{\Delta}(M_{2^{[n/2]}}(\mathbb{C}),M_{2^{[n/2]}}(\mathbb{C}))$, the
Lipschitz complexity associated with the continuous Clifford resource is
bounded above by the Lipschitz complexity associated with the discrete
Clifford resource:

(5.6) $C_{\Delta}(\Phi)\leq C_{\mathcal{S}}(\Phi)\hskip 2.84544pt.$

Similar statements hold for correlation-assisted complexity where the identity
map is a complete contraction.

###### Proof.

The first statement follows directly from the definition of the Clifford
generators. Then the Lipschitz space is given by $\mathcal{A}=\\{x\in
M_{2^{[n/2]}}(\mathbb{C}):[a_{j},x]=0\text{ , }\forall 1\leq j\leq
n\\}=\\{x\in M_{2^{[n/2]}}(\mathbb{C}):[c_{j},x]=0\text{ , }\forall 1\leq
j\leq n\\}$. To see the contraction, we have:

(5.7)
$\displaystyle\begin{split}|||x|||_{\mathcal{S}}&=\sup_{j}||c_{j}xc_{j}^{*}-x||=\sup_{j}||\exp(ia_{j})x\exp(-ia_{j})-x||\\\
&\leq\sup_{j}\int_{0}^{1}dt||\exp(ita_{j})[a_{j},x]\exp(-ita_{j})||=\sup_{j}\int_{0}^{1}dt||[a_{j},x]||=|||x|||_{\Delta}\hskip
2.84544pt.\end{split}$

A similar proof shows that the identity map is a complete contraction.

For the last statement, we have:

(5.8)
$\displaystyle\begin{split}C_{\Delta}(\Phi)&=||\Phi^{*}-id:(\mathcal{A},|||\cdot|||_{\Delta})\rightarrow
M_{2^{[n/2]}}(\mathbb{C})||\\\ &=||(\Phi^{*}-id)\circ
id:(\mathcal{A},|||\cdot|||_{\Delta})\rightarrow(\mathcal{A},|||\cdot|||_{\mathcal{S}})\rightarrow
M_{2^{[n/2]}}(\mathbb{C})||\\\ &\leq
C_{\mathcal{S}}(\Phi)||id:(\mathcal{A},|||\cdot|||_{\Delta})\rightarrow(\mathcal{A},|||\cdot|||_{\mathcal{S}})||\leq
C_{\mathcal{S}}(\Phi)\hskip 2.84544pt.\end{split}$

Using complete contraction, the analogous statement for correlation-assisted
complexity also holds. ∎

The Clifford resources have been considered before [PMTL21] where the authors
used Pauli gates (a particular example of Clifford resources) to define a
noncommutative Lipschitz norm. In the last part of this section, we consider
the discrete Clifford resources made up of Pauli gates on $n$ qubits:
$\mathcal{P}:=\\{\sigma^{X}_{j},\sigma^{Y}_{j},\sigma^{Z}_{j}\\}_{1\leq j\leq
n}$. We show that the induced Lipschitz norm $|||\cdot|||_{\mathcal{P}}$ is
equivalent to the Lipschitz norm considered in [PMTL21]. Recall the partical
trace on $j$-th qubit can be realized as a simple average of adjoint actions
by Pauli gates:

(5.9)
$\operatorname{tr}_{j}(x)=\frac{x+\sigma^{X}_{j}x\sigma^{X}_{j}+\sigma^{Y}_{j}x\sigma^{Y}_{j}+\sigma^{Z}_{j}x\sigma^{Z}_{j}}{4}$

where $x\in M_{2^{n}}(\mathbb{C})=\bigotimes_{1\leq i\leq
n}M_{2}(\mathbb{C})$. The Lipschitz norm considered in [PMTL21, Section V] can
be written in the following equivalent form 555The original definition
considers the dual version:
$||x||_{L}=\sup_{j}\sup_{\rho:\operatorname{tr}_{j}\rho=0}|\operatorname{tr}(\rho
x)|$. Since the partial trace is tracial self-adjoint, we can rewrite the norm
as: $\sup_{\rho:tr_{j}\rho=0}|tr(\rho
x)|=\sup_{\rho}|tr((x_{t}r_{j}x)\rho)|=||x-\operatorname{tr}_{j}x||$.:

(5.10) $||x||_{L}:=\sup_{1\leq j\leq
n}||x-\operatorname{tr}_{j}x||_{\infty}\hskip 2.84544pt.$

Then it is clear that the following upper bound holds:

(5.11)
$\displaystyle\begin{split}||x||_{L}&\leq\frac{1}{4}\sup_{j}\big{(}||x-\sigma^{X}_{j}x\sigma^{X}_{j}||+||x-\sigma^{Y}_{j}x\sigma^{Y}_{j}||+||x-\sigma^{Z}_{j}x\sigma^{Z}_{j}||\big{)}\\\
&\leq\frac{3}{4}\sup_{j}\max\\{||x-\sigma^{X}_{j}x\sigma^{X}_{j}||,||x-\sigma^{Y}_{j}x\sigma^{Y}_{j}||,||x-\sigma^{Z}_{j}x\sigma^{Z}_{j}||\\}\\\
&=\frac{3}{4}|||x|||_{\mathcal{P}}\hskip 2.84544pt.\end{split}$

On the other hand, we can also bound $||x||_{L}$ from below by the Lipschitz
norm $||x||_{\mathcal{P}}$. Recall that for $x\in M_{2^{n}}(\mathbb{C})$ and
each $1\leq j\leq n$, we can decompose $x$ into a sum:

(5.12) $x=x^{\widehat{j}}_{id}\otimes
id_{j}+x^{\widehat{j}}_{X}\otimes\sigma^{X}_{j}+x^{\widehat{j}}_{Y}\otimes\sigma^{Y}_{j}+x_{Z}^{\widehat{j}}\otimes\sigma^{Z}_{j}$

where the superscript $\hat{j}$ indicates that the matrix acts on all qubits
except the $j$-th one. Then we have:
$x-\operatorname{tr}_{j}x=x^{\widehat{j}}_{X}\otimes\sigma^{X}_{j}+x^{\widehat{j}}_{Y}\otimes\sigma^{Y}_{j}+x_{Z}^{\widehat{j}}\otimes\sigma^{Z}_{j}$.
In addition, the following inequality holds:

(5.13)
$\displaystyle\begin{split}||x-\sigma^{X}_{j}x\sigma^{X}_{j}||&=2||x^{\widehat{j}}_{Y}\otimes\sigma^{Y}_{j}+x_{Z}^{\widehat{j}}\otimes\sigma^{Z}_{j}||\leq
2||x-\operatorname{tr}_{j}x||+2|\operatorname{tr}(\sigma^{X}_{j}x)|\hskip
2.84544pt.\end{split}$

Similarl inequalities hold for $\sigma^{Y}_{j}$ and $\sigma^{Z}_{j}$.
Therefore we have:

(5.14)
$\displaystyle\begin{split}|||x|||_{\mathcal{P}}|&=\sup_{j}\max\\{||x-\sigma^{X}_{j}x\sigma^{X}_{j}||,||x-\sigma^{Y}_{j}x\sigma^{Y}_{j}||,||x-\sigma^{Z}_{j}x\sigma^{Z}_{j}||\\}\\\
&\leq
2\sup_{j}\big{(}||x-\operatorname{tr}_{j}x||+\max\\{|\operatorname{tr}(\sigma^{X}_{j}x)|,|\operatorname{tr}(\sigma^{Y}_{j}x)|,|\operatorname{tr}(\sigma^{Z}_{j}x)|\\}\big{)}\\\
&\leq
2\sup_{j}\big{(}||x-\operatorname{tr}_{j}x||+\sup_{\rho:\operatorname{tr}_{j}\rho=0}|\operatorname{tr}(\rho
x)|\big{)}=4\sup_{j}||x-\operatorname{tr}_{j}x||=4||x||_{L}\hskip
2.84544pt.\end{split}$

Combining these estimates, we have that:

######  Lemma 5.2.

Independent on the number of qubits, the Lipschitz norm in [PMTL21] is
equivalent to the Lipschitz norm associated with the discrete Pauli resources:

(5.15)
$\frac{1}{4}|||x|||_{\mathcal{P}}\leq||x||_{L}\leq\frac{3}{4}|||x|||_{\mathcal{P}}$

where $x\in M_{2^{n}}(\mathbb{C})$ and
$\mathcal{P}=\\{\sigma^{X}_{j},\sigma^{Y}_{j},\sigma^{Z}_{j}\\}_{1\leq j\leq
n}$ is the set of discrete Pauli resources.

In particular, the Wasserstein complexity considered in [PMTL21] is a
particular example of the complexity considered in this paper. Hence our
axiomatic framework can be understood as a generalization of the results in
[PMTL21].

## References

  * [AAS22] andA natoly Dymarsky Alexander Avdoshkin and Michael Smolkin.  Krylov complexity in quantum field theory, and beyond.  arXiv prepring arXiv:2212.14429, 2022.
  * [Ali15] Mohsen Alishahiha.  Holographic complexity.  Phys. Rev. D, 92:126009, Dec 2015.
  * [BASTS08] Avraham Ben-Aroya, Oded Schwartz, and Amnon Ta-Shma.  Quantum expanders: Motivation and constructions.  In 2008 23rd Annual IEEE Conference on Computational Complexity, pages 292–303, 2008.
  * [BGS95] M. Bellare, O. Goldreich, and M. Sudan.  Free bits, pcps and non-approximability-towards tight results.  In Proceedings of IEEE 36th Annual Foundations of Computer Science, pages 422–431, 1995.
  * [BS07] Salman Beigi and Peter W. Shor.  On the complexity of computing zero-error and holevo capacity of quantum channels.  arXiv preprint arXiv:0709.2090, 2007.
  * [BS18] Adam R. Brown and Leonard Susskind.  Second law of quantum complexity.  Phys. Rev. D, 97:086015, Apr 2018.
  * [BS19] Adam R. Brown and Leonard Susskind.  Complexity geometry of a single qubit.  Phys. Rev. D, 100:046020, Aug 2019.
  * [BT09] Hugue Blier and Alain Tapp.  All languages in np have very short quantum proofs.  In 2009 Third International Conference on Quantum, Nano and Micro Technologies, pages 34–37, 2009.
  * [BV97] Ethan Bernstein and Umesh Vazirani.  Quantum complexity theory.  SIAM Journal on Computing, 26(5):1411–1473, 1997.
  * [CEHM99] J. I. Cirac, A. K. Ekert, S. F. Huelga, and C. Macchiavello.  Distributed quantum computation over noisy channels.  Phys. Rev. A, 59:4249–4254, Jun 1999.
  * [CM17] Eric A. Carlen and Jan Maas.  Gradient flow and entropy inequalities for quantum markov semigroups with detailed balance.  Journal of Functional Analysis, 273(5):1810–1869, 2017.
  * [CM20] Eric A. Carlen and Jan Maas.  Non-commutative calculus, optimal transport and functional inequalities in dissipative quantum systems.  J. Stat. Phys., 178:319–378, 2020.
  * [Con90] Alain Connes.  Noncommutative Geometry.  1990\.
  * [CS03] Fabio Cipriani and Jean-Luc Sauvageot.  Derivations as square roots of dirichlet forms.  Journal of Functional Analysis, 201(1):78–120, 2003.
  * [DN06] Christopher M. Dawson and Michael A. Nielsen.  The solovay-kitaev algorithm.  Quantum Info. Comput., 6(1):81–95, jan 2006.
  * [DP85] David Deutsch and Roger Penrose.  Quantum theory, the church–turing principle and the universal quantum computer.  Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 400(1818):97–117, 1985.
  * [DS21] Anatoly Dymarsky and Michael Smolkin.  Krylov complexity in conformal field theory.  Phys. Rev. D, 104:L081702, Oct 2021.
  * [ED23] A. Kamal E. Doucet, L. C. G. Govia.  Scalable entanglement stabilization with modular reservoir engineering.  arXiv preprint arXiv:2301.05725, Jan 2023.
  * [FGHZ05] Stephen Fenner, Frederic Green, Steven Homer, and Yong Zhang.  Bounds on the power of constant-depth quantum circuits.  In Maciej Liskiewicz and Rudiger Reischuk, editors, Fundamentals of Computation Theory, pages 44–55. Springer Berlin Heidelberg, 2005.
  * [FR99] Lance Fortnow and John Rogers.  Complexity limitations on quantum computation.  Journal of Computer and System Sciences, 59(2):240–252, 1999.
  * [GJL20a] Li Gao, Marius Junge, and Nicholas LaRacuente.  Fisher information and logarithmic sobolev inequality for matrix-valued functiond.  Ann. Henri Poincaré, 21:3409 – 3478, 2020.
  * [GJL20b] Li Gao, Marius Junge, and Nicholas LaRacuente.  Relative entropy for von neumann subalgebras.  International Journal of Mathematics, 31(06):2050046, 2020.
  * [GJL21] Li Gao, Marius Junge, and Haojian Li.  Geometric approach towards complete logarithmic sobolev inequalities.  arXiv preprint arXiv:2102.04434, Feb 2021.
  * [GJLL22] Li Gao, Marius Junge, Nicholas LaRacuente, and Haojian Li.  Complete order and relative entropy decay rates.  arXiv preprint arXiv:2209.11684, 2022.
  * [GKS76] Vittorio Gorini, Andrzej Kossakowski, and E.C.G. Sudarshan.  Completely positive dynamical semigroups of n-level systems.  Journal of Mathematical Physics, 17(5):821–825, 1976.
  * [GR22] Li Gao and Cambyse Rouzé.  Complete entropic inequalities for quantum markov chains.  Archive for Rational Mechanics and Analysis, 245:183–238, 2022\.
  * [HFK+22] Jonas Haferkamp, Philippe Faist, Naga B. T. Kothakonda, Jens Eisert, and Nicole Yunger Halpern.  Linear growth of quantum circuit complexity.  Nature Physics, (18):528–532, 2022.
  * [HR23] Stefan Hollands and Alessio Ranallo.  Complexity in algebraic qft.  arXiv preprint arXiv:2302.10013, 2023.
  * [JM17] Robert A. Jefferson and Robert C. Myers.  Circuit complexity in quantum field theory.  Journal of High Energy Physics, (107), 2017.
  * [Kla00] Hartmut Klauck.  Quantum communication complexity.  arXiv preprint arXiv:quant-ph/0005032, 2000.
  * [LBK+22] Lu Li, Kaifeng Bu, Dax Enshan Koh, Arthur Jaffe, and Seth Lloyd.  Wasserstein complexity of quantum circuits.  arXiv preprint arXiv:2208.06306, 2022.
  * [Lin74] G. Lindblad.  Expectations and entropy inequalities for finite quantum systems.  Communications in Mathematical Physics, (39):111–119, 1974.
  * [Lin76] G. Lindblad.  On the generators of quantum dynamical semigroups.  Communications in Mathematical Physics, 48(2):119 – 130, 1976.
  * [NDGD06a] Michael A. Nielsen, Mark R. Dowling, Mile Gu, and Andrew C. Doherty.  Optimal control, geometry, and quantum computing.  Phys. Rev. A, 73:062323, Jun 2006.
  * [NDGD06b] Michael A. Nielsen, Mark R. Dowling, Mile Gu, and Andrew C. Doherty.  Quantum computation as geometry.  Science, 311(5764):1133–1135, 2006.
  * [Nie06] Michael A. Nielsen.  A geometric approach to quantum circuit lower bounds.  Quantum Information and Computation, 6(3):213–262, 2006.
  * [OT08] Roberto Oliveira and Barbara M. Terhal.  The complexity of quantum spin systems on a two-dimensional square lattice.  Quantum Info. Comput., 8(10):900–924, nov 2008.
  * [PCA+19] Daniel E. Parker, Xiangyu Cao, Alexander Avdoshkin, Thomas Scaffidi, and Ehud Altman.  A universal operator growth hypothesis.  Phys. Rev. X, 9:041017, Oct 2019.
  * [PMTL21] Giacomo De Palma, Milad Marvian, Dario Trevisan, and Seth Lloyd.  The quantum wasserstein distance of order 1.  IEEE Transactions on Information Theory, 67(10):6627–6643, 2021\.
  * [Rie99] Marc A. Rieffel.  Metrics on state spaces.  Documenta Math., (4):559–600, 1999.
  * [RSGSS21] E. Rabinovici, A. Sanchez-Garrido, R. Shir, and J. Sonner.  Operator complexity: a journey to the edge of krylov space.  Journal of High Energy Physics, (62), 2021.
  * [RSGSS22] E. Rabinovici, A. Sanchez-Garrido, R. Shir, and J. Sonner.  Krylov complexity from integrability to chaos.  Journal of High Energy Physics, (151), 2022.
  * [RW05] B. Rosgen and J. Watrous.  On the hardness of distinguishing mixed-state quantum computations.  In 20th Annual IEEE Conference on Computational Complexity (CCC’05), pages 344–354, 2005.
  * [VSCC93] Nicholas T. Varopoulos, L. Saloff-Coste, and T. Coulhon.  Analysis and Geometry on Groups.  Cambridge Tracts in Mathematics. Cambridge University Press, 1993.
  * [Wat03] John Watrous.  Pspace has constant-round quantum interactive proof systems.  Theoretical Computer Science, 292(3):575–588, 2003.  Algorithms in Quantum Information Prcoessing.
  * [Wir18] Melchior Wirth.  A noncommutative transport metric and symmetric quantum markov semigroups as gradient flows of the entropy.  arXiv preprint arXiv:1808.05419, 2018.