# A note on quantum expanders

Cécilia Lancien  and  Pierre Youssef  Cécilia Lancien. CNRS & Institut
Fourier, Université Grenoble Alpes, 118 rue des maths, 38610 Gières, France.
<EMAIL_ADDRESS>Pierre Youssef. Division of Science,
NYU Abu Dhabi, Saadiyat Island, Abu Dhabi, UAE & Courant Institute of
Mathematical Sciences, New York University, 251 Mercer st, New York, NY 10012,
USA<EMAIL_ADDRESS>
(Date: February 23 2023)

###### Abstract.

We prove that a wide class of random quantum channels with few Kraus
operators, sampled as random matrices with some moment assumptions, exhibit a
large spectral gap, and are therefore optimal quantum expanders. In
particular, our result provides a recipe to construct random quantum expanders
from their classical (random or deterministic) counterparts. This considerably
enlarges the list of known constructions of optimal quantum expanders, which
was previously limited to few examples. Our proofs rely on recent progress in
the study of the operator norm of random matrices with dependence and non-
homogeneity, which we expect to have further applications in several areas of
quantum information.

##  1\. Introduction

###  1.1. Quantum states and channels

In what follows, for every $m\in\mathbb{N}$, we denote by
$\mathcal{M}_{m}(\mathbb{C})$ the set of $m\times m$ matrices with complex
entries. Given $X\in\mathcal{M}_{m}(\mathbb{C})$, we denote by $X^{*}$ its
adjoint, by $X^{t}$ its transpose and by $\mkern
1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu$ its (entry-wise)
conjugate, and we write $X\succeq 0$ when $X$ is Hermitian positive
semidefinite.

In quantum physics, the state of an $n$-dimensional system is described by a
density operator on $\mathbb{C}^{n}$, i.e.
$\rho\in\mathcal{M}_{n}(\mathbb{C})$ a Hermitian positive semidefinite matrix
with trace $1$. A transformation of such quantum system is described by a
quantum channel, i.e.
$\Phi:\mathcal{M}_{n}(\mathbb{C})\to\mathcal{M}_{n}(\mathbb{C})$ a completely
positive and trace-preserving linear map. Recall that a linear map
$\Phi:\mathcal{M}_{n}(\mathbb{C})\to\mathcal{M}_{n}(\mathbb{C})$ is said to be

  * •

positive if, for all $X\in\mathcal{M}_{n}(\mathbb{C})$, $X\succeq
0\Rightarrow\Phi(X)\succeq 0$, and completely positive (CP) if $\Phi\otimes
I:\mathcal{M}_{n^{2}}(\mathbb{C})\to\mathcal{M}_{n^{2}}(\mathbb{C})$ is
positive (where $I:\mathcal{M}_{n}(\mathbb{C})\to\mathcal{M}_{n}(\mathbb{C})$
denotes the identity map),

  * •

trace-preserving (TP) if, for all $X\in\mathcal{M}_{n}(\mathbb{C})$, ${\rm
Tr}(\Phi(X))={\rm Tr}(X)$.

The action of a CP map $\Phi$ on $\mathcal{M}_{n}(\mathbb{C})$ can always be
described in the following (non-unique) way, called a Kraus representation
(see e.g. [AS17, Section 2.3.2] or [Wol12, Chapter 2]):

(1)
$\Phi:X\in\mathcal{M}_{n}(\mathbb{C})\mapsto\sum_{s=1}^{d}K_{s}XK_{s}^{*}\in\mathcal{M}_{n}(\mathbb{C}),$

for some $d\in\mathbb{N}$ and some
$K_{1},\ldots,K_{d}\in\mathcal{M}_{n}(\mathbb{C})$, called Kraus operators of
$\Phi$. The fact that $\Phi$ is TP is equivalent to the following constraint
on the $K_{s}$’s:

$\sum_{s=1}^{d}K_{s}^{*}K_{s}=I.$

The smallest $d$ such that an expression of the form of equation (1) for
$\Phi$ exists is called the Kraus rank of $\Phi$.

An equivalent way of characterizing the Kraus rank of a CP map
$\Phi:\mathcal{M}_{n}(\mathbb{C})\to\mathcal{M}_{n}(\mathbb{C})$ is as the
rank (i.e. the number of non-zero eigenvalues) of its associated Choi matrix
$C_{\Phi}\in\mathcal{M}_{n^{2}}(\mathbb{C})$ (see again [AS17, Section 2.3.2]
or [Wol12, Chapter 2]). The latter is defined as

$C_{\Phi}:=\Phi\otimes I\left(\sum_{i,j=1}^{n}E_{ij}\otimes
E_{ij}\right)=\sum_{i,j=1}^{n}\Phi(E_{ij})\otimes E_{ij},$

where $E_{ij}\in\mathcal{M}_{n}(\mathbb{C})$ has its entry $(i,j)$ equal to
$1$ and all other entries equal to $0$. As a consequence of this alternative
definition, it is clear that the Kraus rank of a CP map on
$\mathcal{M}_{n}(\mathbb{C})$ is always at most $n^{2}$ (as is the rank of a
matrix on $\mathbb{C}^{n^{2}}$).

By the analogue of Perron-Frobenius theory to this context (see e.g. [Wol12,
Chapter 6]), a quantum channel $\Phi$ on $\mathcal{M}_{n}(\mathbb{C})$ always
has largest (in modulus) eigenvalue $\lambda_{1}(\Phi)$ equal to $1$ with an
associated eigenvector which is a positive semidefinite matrix. Hence $\Phi$
always has a fixed state, i.e. a quantum state $\hat{\rho}$ such that
$\Phi(\hat{\rho})=\hat{\rho}$. $\Phi$ is said to be unital if its fixed state
is the so-called maximally mixed state, i.e. $\hat{\rho}=I/n$. The constraint
of being unital is dual to that of being TP (in the sense that a CP map $\Phi$
is unital if and only if its dual CP map $\Phi^{*}$, for the Hilbert-Schmidt
inner product, is TP). It thus reads at the level of Kraus operators as

$\sum_{s=1}^{d}K_{s}K_{s}^{*}=I.$

Note that, identifying $\mathcal{M}_{n}(\mathbb{C})$ with
$\mathbb{C}^{n}\otimes\mathbb{C}^{n}$, a linear map
$\Phi:\mathcal{M}_{n}(\mathbb{C})\to\mathcal{M}_{n}(\mathbb{C})$ can
equivalently be seen as a linear map
$M_{\Phi}:\mathbb{C}^{n}\otimes\mathbb{C}^{n}\to\mathbb{C}^{n}\otimes\mathbb{C}^{n}$,
i.e. an element of $\mathcal{M}_{n^{2}}(\mathbb{C})$. Concretely, a CP linear
map

$\Phi:X\in\mathcal{M}_{n}(\mathbb{C})\mapsto\sum_{s=1}^{d}K_{s}XK_{s}^{*}\in\mathcal{M}_{n}(\mathbb{C})$

can be identified with

$M_{\Phi}=\sum_{s=1}^{d}K_{s}\otimes\mkern
1.5mu\overline{\mkern-1.5muK\mkern-1.5mu}\mkern
1.5mu_{s}\in\mathcal{M}_{n^{2}}(\mathbb{C}).$

This identification preserves the spectrum, i.e.
$\mathrm{spec}(\Phi)=\mathrm{spec}(M_{\Phi})$.

###  1.2. Quantum expanders

Let $\mathbf{\Phi}:=(\Phi_{n,d_{n}})_{n\in\mathbb{N}}$ be a sequence of
quantum channels, where for each $n\in\mathbb{N}$, $\Phi_{n,d_{n}}$ acts on
$\mathcal{M}_{n}(\mathbb{C})$ and has Kraus rank $d_{n}$. $\mathbf{\Phi}$ is
called an expander if it satisfies the following properties, the third one
being actually less crucial, as we will explain below:

  1. (1)

The $\Phi_{n,d_{n}}$’s have asymptotically a small Kraus rank, i.e.

$\frac{d_{n}}{n^{2}}\underset{n\to\infty}{\longrightarrow}0.$

  2. (2)

The $\Phi_{n,d_{n}}$’s have asymptotically a large spectral gap between their
two largest (in modulus) eigenvalues, i.e. there exist $0\leq\varepsilon<1$
and $n_{0}\in\mathbb{N}$ such that, for all $n\geq n_{0}$,

$\Delta\left(\Phi_{n,d_{n}}\right):=\left|\lambda_{1}\left(\Phi_{n,d_{n}}\right)\right|-\left|\lambda_{2}\left(\Phi_{n,d_{n}}\right)\right|\geq
1-\varepsilon,\text{ or equivalently
}\left|\lambda_{2}\left(\Phi_{n,d_{n}}\right)\right|\leq\varepsilon.$

  3. (3)

The $\Phi_{n,d_{n}}$’s have asymptotically a fixed state with large entropy,
i.e. denoting by $\hat{\rho}_{n,d_{n}}$ the fixed state of $\Phi_{n,d_{n}}$,

$S\left(\hat{\rho}_{n,d_{n}}\right)\underset{n\to\infty}{\longrightarrow}\infty.$

In condition (3) above, $S(\cdot)$ stands for the von Neumann entropy,
defined, for any state $\rho$, as $S(\rho):=-{\rm Tr}(\rho\log\rho)$. Note
that, given a state $\rho$ on $\mathbb{C}^{n}$, we always have $0\leq
S(\rho)\leq\log n$, with equality in the first inequality iff $\rho$ is a pure
state (i.e. a rank-$1$ projector) and equality in the second inequality iff
$\rho$ is the maximally mixed state. The entropy of a quantum state can thus
be seen as a measure of how mixed it is: if $S(\rho)\geq\log r$ for some
$1\leq r\leq n$, then the rank of $\rho$ is at least $r$. The advantage of the
entropy over the rank is that it is a smoother quantity (which captures how
uniformly distributed the non-zero eigenvalues of $\rho$ are rather than just
how many they are).

Given a quantum channel $\Phi$ with fixed state $\hat{\rho}$, its second
largest eigenvalue can be seen as quantifying how far $\Phi$ is from the
“ideal” quantum channel $\Phi_{\hat{\rho}}:X\mapsto({\rm Tr}X)\hat{\rho}$,
which sends any input state on $\hat{\rho}$. Indeed,
$|\lambda_{2}(\Phi)|=|\lambda_{1}(\Phi-\Phi_{\hat{\rho}})|$, so the smallest
$|\lambda_{2}(\Phi)|$, the closest, in a sense, $\Phi$ to $\Phi_{\hat{\rho}}$.
Now, the fact that $\hat{\rho}$ has a large entropy implies that
$\Phi_{\hat{\rho}}$ has a large Kraus rank. More precisely, if
$S(\hat{\rho})\geq\alpha\log n$ for some $0\leq\alpha\leq 1$, then
$\hat{\rho}$ has rank at least $n^{\alpha}$, and therefore $\Phi_{\hat{\rho}}$
has Kraus rank at least $n^{1+\alpha}$. The latter claim can be checked by
observing that the Choi matrix associated to $\Phi_{\hat{\rho}}$ is simply
$C_{\Phi_{\hat{\rho}}}=\hat{\rho}\otimes I$, which indeed has rank
$n^{1+\alpha}$. Consequently, the fact that $\Phi$ has a small Kraus rank
means that it is an approximation of $\Phi_{\hat{\rho}}$ which is much more
economical than $\Phi_{\hat{\rho}}$ itself. This is what makes it particularly
useful in practice. We see from this discussion that what we actually need for
the quantum channel $\Phi$ to provide a significant Kraus rank reduction
compared to $\Phi_{\hat{\rho}}$ is that it satisfies a joint condition (1) and
(3) which would be: $d\ll n^{1+\alpha}$, where $\alpha=S(\hat{\rho})/\log n$.
In particular, if $d\ll n$, then $\Phi$ fulfils the latter condition whatever
the entropy of $\hat{\rho}$.

Let us briefly comment here on the fact that expander quantum channels can be
seen as an analogue of classical expander graphs (see e.g. [HLW06] for a
complete review on the topic). An expander graph is usually defined as a
regular graph $G$ (i.e. whose vertices all have the same degree) that combines
the two properties of being sparse (i.e. the degree is small compared to the
number of vertices) and of having a normalized adjacency matrix $A$ that has a
large upper spectral gap (i.e. $|\lambda_{2}(A)|$ is small compared to $1$).
Since $G$ is regular, we have that $A$ leaves the uniform probability vector
$u$ (which has maximal entropy) invariant. And the second largest eigenvalue
of $A$ measures the distance of $A$ to $A_{u}$, the transition matrix that
sends any input probability vector on $u$, as
$|\lambda_{2}(A)|=|\lambda_{1}(A-A_{u})|$. Now, $A_{u}$ is nothing else than
the normalized adjacency matrix of the complete graph. So an expander can be
seen as a graph which approximates, in a sense, the complete graph, even
though it is sparse. To transpose this to the quantum setting, probability
vectors are replaced by density operators, transition matrices are replaced by
quantum channels, and the corresponding definition of an expander indeed
becomes the one that we have given earlier.

In both the classical and quantum settings, the definition of expansion that
we gave here is a spectral one. The latter is closely related to a more
geometrical characterization of expansion, that quantifies either how
uniformly distributed the edges of the graph are or how uniformly spread the
output directions of the quantum channel are. Both classically and quantumly,
spectral and geometrical expansion are known to be somewhat equivalent
notions, in the sense that there are two-way inequalities relating the
parameters measuring one or the other [Alo86, BBLM20]. We work with spectral
expansion here, as people often do, as it is mathematically more tractable.

###  1.3. Previously known results and our contribution

Recently, several attempts have been made at exhibiting examples of such
quantum expanders. It is known that any quantum channel $\Phi$ with Kraus rank
$d$ verifies $|\lambda_{2}(\Phi)|\geq c/\sqrt{d}$, where $c$ is a universal
constant (independent of the underlying dimension $n$) [Has07, BASTS08]. Note
that this is in complete analogy with the classical case and the corresponding
Alon-Boppana bound for the second largest eigenvalue of the normalized
adjacency matrix of a $d$-regular graph [Alo86, Nil91] (where in addition the
constant $c$ is explicit). An “optimal” quantum expander can thus be defined
as a quantum channel $\Phi_{n,d}$ on $\mathcal{M}_{n}(\mathbb{C})$ having
Kraus rank $d$ and satisfying $|\lambda_{2}(\Phi_{n,d})|\leq C/\sqrt{d}$ for
some universal constant $C$. In a similar fashion, classical $d$-regular
expanders are called Ramanujan when the second largest eigenvalue of their
normalized adjacency matrix is bounded above by $2\sqrt{d-1}/d$.

In the classical setting, explicit constructions of families of Ramanujan
graphs were achieved by Margulis [Mar88] and Lubotzky, Philips and Sarnak
[LPS88] for specific values of $d$. The existence of Ramanujan $d$-regular
bipartite graphs for every $d\geq 3$ was proved in a breakthrough work of
Marcus, Spielman and Srivastava [MSS15]. Moreover, several models of random
graphs have been shown to be almost Ramanujan. For instance, random
$d$-regular graphs with fixed degree $d\geq 3$ [Fri08, Bor20], random
$d$-regular graphs with growing degree $d$ [BFSU99, CGJ18, TY19, BHKY20,
Sar22], and dense Erdős-Rényi graphs [LvHY18, BGBK19, TY21].

The first attempts at exhibiting quantum expanders were inspired by classical
constructions, in particular those based on Cayley graphs. This provided
(semi-)explicit examples of quantum expanders, but none of them was optimal,
either because the classical one was not (for an Abelian underlying group
[AS04]) or because something was lost in the classical-to-quantum embedding
(for a non-Abelian underlying group [BASTS08, Har08, EG08]). In fact, there
are only three known constructions of optimal quantum expanders up to date,
all of which being random. The first model that was considered, originally by
Hastings [Has07] and later analyzed differently by Pisier [Pis14], was a model
where Kraus operators are sampled as $d$ independent Haar distributed
unitaries on $\mathbb{C}^{n}$. Then González-Guillén, Junge and Nechita
[GGJN18] studied the case where Kraus operators are blocks of a Haar
distributed isometry from $\mathbb{C}^{n}$ to
$\mathbb{C}^{n}\otimes\mathbb{C}^{d}$. Finally, Lancien and Pérez-García
[LPG22] looked at a model where Kraus operators are sampled as $d$ independent
Gaussian matrices on $\mathbb{C}^{n}$.

The goal of this work is to show that many other models of random quantum
channels, beyond the three mentioned above, provide examples of optimal
expanders as well. We will see that quantum expanders can be constructed by
taking Kraus operators to be random matrices with some sparsity and moment
assumptions on their entries. The model we introduce is general enough so that
it incapsulates random sparse matrices (hence being a first step towards
derandomization of optimal constructions) or random matrices with a variance
profile. Informally, the recipe to construct quantum expanders with Kraus rank
at most $d$ goes as follows:

  1. (1)

Take $P$ to be the transition matrix of an irreducible Markov chain on $n$
sites with second singular value of order at most $1/\sqrt{d}$ (and with one
extra assumption on the sparsity of the chain). As an illustrative example,
consider the transition matrix of the random walk on an almost Ramanujan
$d$-regular graph on $n$ vertices (with the extra assumption that $d$ is at
least some power of $\log n$).

  2. (2)

Take a random $n\times n$ matrix $W$ with independent centered entries,
variance profile given by $P^{t}$, and satisfying some moment growth
conditions.

  3. (3)

Take $W_{1},\ldots,W_{d}$ independent copies of $W$ and define the random CP
map $\Phi$ on $\mathcal{M}_{n}(\mathbb{C})$ whose matrix representation is

$M_{\Phi}=\frac{1}{d}\sum_{s=1}^{d}W_{s}\otimes\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{s}.$

Then $\Phi$ is on average TP and an optimal quantum expander, as we prove in
this note.

This general procedure illustrates the abundance of examples of quantum
expanders which could be realized. It is worth highlighting that the above
recipe uses a classical expander (either random or deterministic) in order to
construct a (random) quantum one. The exact moment assumptions as well as the
conditions on the variance profile are stated in Section 2.1 (Assumptions 1,
2, 3, 4) and Section 3 (Assumption 5). To keep the introduction light, we will
state our main result in an informal way here and differ the precise
definition of the class of models as well as corresponding examples to the
next sections.

######  Theorem 1 (Main result - Informal).

Let $W\in\mathcal{M}_{n}(\mathbb{C})$ be a random matrix with independent
centered entries, satisfying some constraints on the growth of their moments.
Let $W_{1},\ldots,W_{d}$ be independent copies of $W$. Define the random CP
map $\Phi$ on $\mathcal{M}_{n}(\mathbb{C})$, having Kraus rank at most $d$
with $d\geq(\log n)^{4}$, as

$\Phi:X\in\mathcal{M}_{n}(\mathbb{C})\mapsto\frac{1}{d}\sum_{s=1}^{d}W_{s}XW_{s}^{*}\in\mathcal{M}_{n}(\mathbb{C}).$

Then, on average, $\Phi$ is TP and such that $|\lambda_{1}(\Phi)|\geq 1$ and
$|\lambda_{2}(\Phi)|\leq C/\sqrt{d}$, for some universal constant $C>0$.

The rigorous statement corresponding to the previous theorem, as well as to
the description preceding it, is stated as Theorem 4. The proof of this result
crucially relies on recent progress in the understanding of the operator norm
of non-homogeneous random matrices, and more precisely on refinements of the
noncommutative Khintchine inequality (see [BvH16, LvHY18, BBvH21, BvH22] and
references therein). One of the motivations of the current work, beyond the
specific result about quantum expanders, is in fact to bring these powerful
results to the attention of the quantum information community. We expect them
to find further applications in view of their generality.

###  1.4. Organization of the paper and notation

The remainder of this paper is organized as follows. In Section 2 we introduce
a very general random matrix model with tensor product structure and prove an
upper bound on its operator norm. The key technical tool that we use is a
recent powerful result from [BBvH21, BvH22], which allows to estimate the
operator norm of random matrices whose entries have dependence and non-
homogeneity. In Section 3 we then show how the main result from Section 2
implies that a wide class of random quantum channels are on average expanders.
Finally, in Section 4, we discuss some consequences and perspectives.

In what follows, given $x\in\mathbb{C}^{m}$, we denote by $\|x\|$ its
Euclidean norm. And given $X\in\mathcal{M}_{m}(\mathbb{C})$, we denote by
$\|X\|_{p}:=({\rm Tr}(|X|^{p}))^{1/p}$ its Schatten $p$-norm, for all $p\geq
1$. In particular, $\|X\|_{\infty}$ stands for its operator (or spectral) norm
(i.e. its largest singular value) and $\|X\|_{2}$ stands for its Hilbert-
Schmidt norm. Also, given a linear map $T$ (either on $\mathbb{C}^{m}$ or on
$\mathcal{M}_{m}(\mathbb{C})$), we denote by
$\lambda_{1}(T),\lambda_{2}(T),\ldots$ its eigenvalues, with modulus in non-
increasing order, and by $s_{1}(T),s_{2}(T),\ldots$ its singular values, in
non-increasing order.

##  2\. Operator norm estimate for a random matrix model with tensor product
structure

###  2.1. Random matrix model

Let $W=(W_{ij})_{1\leq i,j\leq n}$ be an $n\times n$ random matrix (either
real or complex) satisfying the following assumptions:

######  Assumption 1.

The entries $W_{ij}$, $1\leq i,j\leq n$, are independent, of mean $0$ and of
variance $\eta_{ij}$, i.e.

$\forall\ 1\leq i,j\leq n,\ \mathbb{E}\left(W_{ij}\right)=0\ \text{ and }\
\mathbb{E}\left(\left|W_{ij}\right|^{2}\right)=\eta_{ij}.$

######  Assumption 2.

The variance matrix $\eta=(\eta_{ij})_{1\leq i,j\leq n}$ is doubly sub-
stochastic, i.e. each of its rows and columns sums up to at most $1$:

$\forall\ 1\leq i\leq n,\ \sum_{j=1}^{n}\eta_{ij}\leq
1\quad\text{and}\quad\forall\ 1\leq j\leq n,\ \sum_{i=1}^{n}\eta_{ij}\leq 1.$

######  Assumption 3.

There exist a universal constant $\mathbf{C}>0$ and a parameter $\beta\geq 0$
such that, for every $p\in\mathbb{N}$,

$\forall\ 1\leq i,j\leq n,\
\left(\mathbb{E}\left(\left|W_{ij}\right|^{2p}\right)\right)^{\frac{1}{p}}\leq\mathbf{C}p^{\beta}\eta_{ij}.$

######  Assumption 4.

There exists a universal constant $\mathbf{C^{\prime}}>0$ such that

$\max_{1\leq i,j\leq n}\eta_{ij}\leq\frac{\mathbf{C^{\prime}}}{(\log
n)^{2+\beta}}.$

The class of random matrices satisfying the above assumptions is quite large.
We provide below some examples.

######  Example 1 (i.i.d. heavy-tailed entries).

Consider a random variable $\xi$ (either real or complex) of mean $0$,
variance $1$ and satisfying, for some universal constant $C>0$ and some
parameter $\beta\geq 0$, the moment growth condition

$\forall\ p\in\mathbb{N},\ \left(\mathbb{E}|\xi|^{2p}\right)^{\frac{1}{p}}\leq
Cp^{\beta}.$

Special cases include $\beta=1$, where $\xi$ is called sub-Gaussian, and
$\beta=2$, where $\xi$ is called sub-exponential. But we also allow for larger
$\beta$, i.e. for $\xi$ having heavier tails. Consider an $n\times n$ random
matrix $M$ whose entries are i.i.d. copies of $\xi$, and set $W=M/\sqrt{n}$.
Clearly, $W$ satisfies all required assumptions, provided $n$ is large enough.

######  Example 2 (Gaussian matrices with variance profile).

Consider an $n\times n$ random matrix $W$ whose entries are independent and,
for every $1\leq i,j\leq n$, $W_{ij}$ is a Gaussian random variable (either
real or complex) with mean $0$ and variance $\sigma_{ij}^{2}$. Assume that the
variance profile matrix $\sigma=(\sigma_{ij}^{2})_{1\leq i,j\leq n}$ is doubly
stochastic (i.e. each of its rows and columns sums up to $1$) and satisfies

$\max_{1\leq i,j\leq n}\sigma_{ij}^{2}\leq\frac{1}{(\log n)^{3}}.$

Then $W$ satisfies all required assumptions, with $\beta=1$.

######  Example 3 (Random matrices with deterministic sparsity pattern).

Let $n,r\in\mathbb{N}$ with $r\geq(\log n)^{2}$. Consider any undirected
$r$-regular graph on $n$ vertices and let $A=(A_{ij})_{1\leq i,j\leq n}$ be
the corresponding adjacency matrix. Let $\xi$ be a uniformly bounded random
variable (either real or complex) of mean $0$ and variance $1$. Let
$(\xi_{ij})_{1\leq i,j\leq n}$ be i.i.d copies of $\xi$ and for every $1\leq
i,j\leq n$, set $W_{ij}=A_{ij}\xi_{ij}/\sqrt{r}$. Then $W=(W_{ij})_{1\leq
i,j\leq n}$ inherits the sparsity pattern of the undirected $r$-regular graph.
Moreover, since $\eta_{ij}=\eta_{ji}=A_{ij}/r$ for every $1\leq i,j\leq n$,
$W$ clearly satisfies Assumptions 1 and 2. Finally, since $\xi$ is bounded and
$r\geq(\log n)^{2}$, one can check that $W$ satisfies Assumptions 3 and 4,
with $\beta=0$.

Equipped with the class of random matrices introduced above, we now construct
the random quantum channel, which will be proven in the sequel to have a large
spectral gap between its first and second largest eigenvalues. We let $W_{s}$,
$1\leq s\leq d$, be independent copies of $W$ and set

(2) $Y=\frac{1}{d}\sum_{s=1}^{d}W_{s}\otimes\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{s}.$

Suppose further that

(3) $(\log n)^{4}\leq d\leq n^{2}.$

Our goal will consist in controlling the spectral gap of $Y$, and hence of the
corresponding quantum channel

$\Phi_{Y}:X\in\mathcal{M}_{n}(\mathbb{C})\mapsto\frac{1}{d}\sum_{s=1}^{d}W_{s}XW_{s}^{*}\in\mathcal{M}_{n}(\mathbb{C}).$

In order to do this, we will first aim at deriving an upper bound for
$\|Y-\mathbb{E}(Y)\|_{\infty}$. The final result that we obtain is stated
below.

######  Theorem 2.

Let $W$ be an $n\times n$ random matrix satisfying Assumptions 1, 2, 3 and 4.
Let $Y=\frac{1}{d}\sum_{s=1}^{d}W_{s}\otimes\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{s}$, where $W_{s}$,
$1\leq s\leq d$, are independent copies of $W$, with $d$ satisfying condition
(3). Then,

$\mathbb{E}\|Y-\mathbb{E}(Y)\|_{\infty}\leq\frac{C}{\sqrt{d}},$

for some universal constant $C>0$.

The remainder of this section is devoted to the proof of this theorem.

###  2.2. Operator norm of random matrices with dependence and non-homogeneity

Understanding the spectrum of a random matrix and in particular its operator
norm is an extremely well studied topic. While models with independent and
identically distributed entries were initially considered and well understood,
there has been a lot of recent activity considering models with dependence and
non-homogeneity. Since our model exhibits both some dependence (because of the
tensor product structure) and non-homogeneity, we will make use of recent
advances in the study of the operator norm of such random matrices. More
precisely, we will rely on the following result which can be deduced by
combining [BvH22, Theorem 5.8] with [BBvH21, Theorem 2.7].

######  Theorem 3 ([BBvH21, BvH22]).

Let $Z_{1},\ldots,Z_{T}$ be independent and centered $m\times m$ random
matrices (either real or complex) and let $X=\sum_{t=1}^{T}Z_{t}$. Let ${\rm
Cov}(X)$ denote the $m^{2}\times m^{2}$ covariance matrix associated to $X$,
i.e. ${\rm Cov}(X)_{ijkl}={\rm cov}(X_{ij},X_{kl})$ for every $1\leq
i,j,k,l\leq m$. Then, we have

$\displaystyle\mathbb{E}\|X\|_{\infty}$ $\displaystyle\leq
2\|\mathbb{E}(XX^{*})\|_{\infty}^{\frac{1}{2}}+2\|\mathbb{E}(X^{*}X)\|_{\infty}^{\frac{1}{2}}+C(\log
m)^{\frac{3}{2}}\|{\rm Cov}(X)\|_{\infty}^{\frac{1}{2}}$
$\displaystyle\qquad+C(\log m)^{2}\left(\sum_{t=1}^{T}\mathbb{E}\,{\rm
Tr}(|Z_{t}|^{2p})\right)^{\frac{1}{2p}},$

for $p=\lfloor C^{\prime}\log m\rfloor$, where $C,C^{\prime}>0$ are universal
constants.

It should be noted that the results from [BBvH21, BvH22] also imply that the
constant $2$ in both leading terms on the right-hand side could be made
arbitrary close to $1$. As we will not optimize constants in the sequel, we
opted to state the above lighter version. It is worth noting that Theorem 3 is
only one particular formulation of several other corollaries which could be
stated as a combination of the works [BBvH21] and [BvH22]. Indeed, the former
derives sharp estimates on the norm of a Gaussian matrix while the latter
establishes a universality principle allowing to transfer bounds on the
Gaussian model to a more general setting.

###  2.3. Proof of Theorem 2

In order to apply Theorem 3 above to random matrix models of the form given by
equation (2), our task will reduce to estimating all the parameters appearing
on the right-hand side of the inequality. Before doing that, we start with the
following decoupling lemma. It is not strictly necessary for our proof and we
only use it to make the subsequent calculations more straightforward. It
should be noted that working directly with $Y$ as in (2), without applying the
decoupling procedure, and using Theorem 3 with the leading constant $2$ made
arbitrary close to $1$, it will be possible to derive Theorem 2 with the
universal constant $C$ there made arbitrary close to $2$.

######  Lemma 1.

Let $W$ be an $n\times n$ random matrix satisfying Assumptions 1, 2, 3, and 4.
Let $Y=\frac{1}{d}\sum_{s=1}^{d}W_{s}\otimes\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{s}$, where $W_{s}$,
$1\leq s\leq d$, are independent copies of $W$. Then,

$\mathbb{E}\|Y-\mathbb{E}(Y)\|_{\infty}\leq\frac{C_{\beta}}{\sqrt{d}}+4\,\mathbb{E}\left\|\frac{1}{d}\sum_{s=1}^{d}W_{s}\otimes\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{s}^{\prime}\right\|_{\infty},$

where $W_{s}^{\prime}$ is an independent copy of $W_{s}$, $1\leq s\leq d$, and
$C_{\beta}>0$ is a constant depending only on $\beta$.

###### Proof.

We start by writing

$\mathbb{E}\|Y-\mathbb{E}(Y)\|_{\infty}=\frac{1}{d}\,\mathbb{E}\Bigg{\|}\sum_{\begin{subarray}{c}1\leq
s\leq d\\\ 1\leq i,j,k,l\leq n\end{subarray}}\left(W_{s,ij}\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{s,kl}-\mathbb{E}\left(W_{s,ij}\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{s,kl}\right)\right)E_{ij}\otimes E_{kl}\Bigg{\|}_{\infty},$

where $E_{ij}$ denotes the $n\times n$ matrix whose entry $(i,j)$ is equal to
$1$ while all others are $0$, and $W_{s,ij}$ denotes the entry $(i,j)$ of
$W_{s}$. Now by a standard decoupling result (see e.g. [dlPnG99, Theorem
3.1.1]), we can write

$\mathbb{E}\Bigg{\|}\sum_{\begin{subarray}{c}1\leq s\leq d\\\ 1\leq
i,j,k,l\leq n\\\ (i,j)\neq(k,l)\end{subarray}}W_{s,ij}\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{s,kl}E_{ij}\otimes
E_{kl}\Bigg{\|}_{\infty}\leq
4\,\mathbb{E}\Bigg{\|}\sum_{\begin{subarray}{c}1\leq s\leq d\\\ 1\leq
i,j,k,l\leq n\\\ (i,j)\neq(k,l)\end{subarray}}W_{s,ij}\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{s,kl}^{\prime}E_{ij}\otimes E_{kl}\Bigg{\|}_{\infty},$

where $(W_{s,ij}^{\prime})_{1\leq i,j\leq n}$ are independent copies of
$(W_{s,ij})_{1\leq i,j\leq n}$. Putting the two (in)equalities above together
and using the triangle inequality, we get

(4) $\mathbb{E}\|Y-\mathbb{E}(Y)\|_{\infty}\leq
4\,\mathbb{E}\left\|\frac{1}{d}\sum_{s=1}^{d}W_{s}\otimes\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{s}^{\prime}\right\|_{\infty}+\frac{1}{d}\,\mathbb{E}\|A\|_{\infty}+\frac{4}{d}\,\mathbb{E}\|B\|_{\infty},$

where $W_{s}^{\prime}$ denotes an independent copy of $W_{s}$, while $A$ and
$B$ are two $n\times n$ random matrices whose entries are given by

$\forall\ 1\leq i,j\leq n,\ A_{ij}=\sum_{s=1}^{d}W_{s,ij}\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{s,ij}^{\prime}\ \text{
and }\ B_{ij}=\sum_{s=1}^{d}\left(|W_{s,ij}|^{2}-\eta_{ij}\right).$

To estimate the operator norm of these matrices $A$ and $B$, we write

$A=\sum_{\begin{subarray}{c}1\leq s\leq d\\\ 1\leq i,j\leq
n\end{subarray}}U_{sij}\quad\text{ and }\quad B=\sum_{\begin{subarray}{c}1\leq
s\leq d\\\ 1\leq i,j\leq n\end{subarray}}V_{sij},$

where $U_{sij}=W_{s,ij}\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{s,ij}^{\prime}\,E_{ij}$ and
$V_{sij}=(|W_{s,ij}|^{2}-\eta_{ij})\,E_{ij}$. Note that the $U_{sij}$’s and
the $V_{sij}$’s form each a family of independent centered random matrices and
we can therefore make use of Theorem 3. To this aim, note that
$\mathbb{E}(AA^{*})$ and $\mathbb{E}(BB^{*})$ are both diagonal matrices, and
for every $1\leq i\leq n$, we have

$\mathbb{E}(AA^{*})_{ii}=\mathbb{E}\left(\sum_{j=1}^{n}\left|\sum_{s=1}^{d}W_{s,ij}\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{s,ij}^{\prime}\right|^{2}\right)=d\sum_{j=1}^{n}\eta_{ij}^{2},$
$\mathbb{E}(BB^{*})_{ii}=\mathbb{E}\left(\sum_{j=1}^{n}\left|\sum_{s=1}^{d}\left(|W_{s,ij}|^{2}-\eta_{ij}\right)\right|^{2}\right)=d\sum_{j=1}^{n}{\rm
var}\left(|W_{ij}|^{2}\right).$

Now, using Assumption 2, we have

$\sum_{j=1}^{n}\eta_{ij}^{2}\leq\left(\max_{1\leq j\leq
n}\eta_{ij}\right)\left(\sum_{j=1}^{n}\eta_{ij}\right)\leq\max_{1\leq i,j\leq
n}\eta_{ij}.$

And using Assumptions 2 and 3, we have

$\sum_{j=1}^{n}{\rm var}\left(|W_{ij}|^{2}\right)\leq
C_{\beta}\sum_{j=1}^{n}\eta_{ij}^{2}\leq C_{\beta}\max_{1\leq i,j\leq
n}\eta_{ij},$

where $C_{\beta}$ is a constant depending only on $\beta$. Doing the same
analysis for $\mathbb{E}(A^{*}A)$ and $\mathbb{E}(B^{*}B)$, we can deduce that

$\displaystyle\|\mathbb{E}(AA^{*})\|_{\infty},\|\mathbb{E}(A^{*}A)\|_{\infty}$
$\displaystyle\leq d\max_{1\leq i,j\leq n}\eta_{ij},$
$\displaystyle\|\mathbb{E}(BB^{*})\|_{\infty},\|\mathbb{E}(B^{*}B)\|_{\infty}$
$\displaystyle\leq C_{\beta}\,d\max_{1\leq i,j\leq n}\eta_{ij}.$

Now since the entries of $A$, resp. $B$, are independent, then ${\rm Cov}(A)$,
resp. ${\rm Cov}(B)$, is a diagonal matrix whose diagonal entries are given by
$(d\eta_{ij}^{2})_{1\leq i,j\leq n}$, resp. $(d\,{\rm
var}(|W_{ij}|^{2}))_{1\leq i,j\leq n}$. Hence, we get

$\|{\rm Cov}(A)\|_{\infty}\leq d\max_{1\leq i,j\leq n}\eta_{ij}^{2},$

and using Assumption 3, we get

$\|{\rm Cov}(B)\|_{\infty}\leq d\max_{1\leq i,j\leq n}{\rm
var}\left(|W_{ij}|^{2}\right)\leq C_{\beta}\,d\max_{1\leq i,j\leq
n}\eta_{ij}^{2}.$

Finally, note that, using that $W_{s}$ and $W_{s}^{\prime}$ are independent
and identically distributed and making use of Assumption 3, we can write for
every $p\in\mathbb{N}$

$\left(\mathbb{E}\,{\rm
Tr}\left(\left|U_{sij}\right|^{2p}\right)\right)^{\frac{1}{2p}}=\left(\mathbb{E}\left|W_{s,ij}\right|^{2p}\right)^{\frac{1}{p}}\leq\mathbf{C}p^{\beta}\eta_{ij}$

and

$\left(\mathbb{E}\,{\rm
Tr}\left(\left|V_{sij}\right|^{2p}\right)\right)^{\frac{1}{2p}}=\left(\mathbb{E}\left|\left|W_{s,ij}\right|^{2}-\eta_{ij}\right|^{2p}\right)^{\frac{1}{2p}}\leq
C_{\beta}^{\prime}\,p^{\beta}\eta_{ij},$

where $C_{\beta}^{\prime}$ is a constant depending only on $\beta$. We now
just have to observe that, for $p=\lfloor C^{\prime}\log n\rfloor$,

$\displaystyle\Bigg{(}\sum_{\begin{subarray}{c}1\leq s\leq d\\\ 1\leq i,j\leq
n\end{subarray}}\mathbb{E}\,{\rm
Tr}\left(\left|U_{sij}\right|^{2p}\right)\Bigg{)}^{\frac{1}{2p}}$
$\displaystyle\leq
d^{\frac{1}{2p}}n^{\frac{1}{p}}\max_{\begin{subarray}{c}1\leq s\leq d\\\ 1\leq
i,j\leq n\end{subarray}}\left(\mathbb{E}\,{\rm
Tr}\left(\left|U_{sij}\right|^{2p}\right)\right)^{\frac{1}{2p}}$
$\displaystyle\leq C\max_{\begin{subarray}{c}1\leq s\leq d\\\ 1\leq i,j\leq
n\end{subarray}}\left(\mathbb{E}\,{\rm
Tr}\left(\left|U_{sij}\right|^{2p}\right)\right)^{\frac{1}{2p}},$

where $C$ is a universal constant. And similarly for the $V_{sij}$’s.

Hence, applying Theorem 3 and making use of the above calculations, with
$p=\lfloor C^{\prime}\log n\rfloor$, we obtain that

$\mathbb{E}\|A\|_{\infty},\mathbb{E}\|B\|_{\infty}\leq
C^{\prime\prime}_{\beta}\sqrt{d}\left(\max_{1\leq i,j\leq
n}\sqrt{\eta_{ij}}+(\log n)^{2+\beta}\max_{1\leq i,j\leq
n}\eta_{ij}\right)\leq\tilde{C}_{\beta}\sqrt{d},$

for some constants $C_{\beta}^{\prime\prime},\tilde{C}_{\beta}$ depending only
on $\beta$, where we also made use of Assumption 4 to obtain the last
inequality. The proof of the lemma follows after replacing this inequality
back into equation (4). ∎

Next, we upper bound the operator norm of the decoupled random matrix
appearing on the right-hand side of the inequality in Lemma 1. To this aim, we
will again make use of Theorem 3 and therefore estimate the corresponding
parameters.

######  Lemma 2.

Let $W$ be an $n\times n$ random matrix satisfying Assumptions 1 and 2. Let
$X=\frac{1}{d}\sum_{s=1}^{d}W_{s}\otimes\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{s}^{\prime}$, where
$W_{s}$, $W_{s}^{\prime}$, $1\leq s\leq d$, are independent copies of $W$.
Then,

$\|\mathbb{E}(XX^{*})\|_{\infty},\|\mathbb{E}(X^{*}X)\|_{\infty}\leq\frac{1}{d}.$

###### Proof.

For every $1\leq s\leq d$, set

$A_{s}=\left(W_{s}\otimes\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{s}^{\prime}\right)\left(W_{s}\otimes\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{s}^{\prime}\right)^{*}=\left(W_{s}W_{s}^{*}\right)\otimes\left(\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{s}^{\prime}\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{s}^{\prime*}\right).$

A short calculation shows that

$A_{s}=\sum_{1\leq i,j,k,l\leq
n}\big{\langle}\,W_{s,i}\,,W_{s,j}\,\big{\rangle}\big{\langle}\,\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{s,k}^{\prime}\,,\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{s,l}^{\prime}\,\big{\rangle}E_{ij}\otimes E_{kl},$

where we denoted by $(W_{s,i})_{1\leq i\leq n}$, resp.
$(W_{s,i}^{\prime})_{1\leq i\leq n}$, the rows of $W_{s}$, resp.
$W_{s}^{\prime}$, and by $E_{ij}$ the $n\times n$ matrix whose entry $(i,j)$
is equal to $1$ while all others are $0$. Using the independence of the
$W_{s,i},W_{s,k}^{\prime}$, $1\leq i,k\leq n$, we can write

$\mathbb{E}(A_{s})=\sum_{1\leq i,k\leq
n}\mathbb{E}\left(\big{\|}W_{s,i}\big{\|}^{2}\right)\mathbb{E}\left(\big{\|}W_{s,k}^{\prime}\big{\|}^{2}\right)E_{ii}\otimes
E_{kk}=\sum_{1\leq i,k\leq n}\left(\sum_{1\leq j,l\leq
n}\eta_{ij}\eta_{kl}\right)E_{ii}\otimes E_{kk}.$

Since the above matrix is diagonal, we deduce using Assumption 2 that

$\|\mathbb{E}(A_{s})\|_{\infty}\leq 1.$

Using the independence of the $W_{s},W_{s}^{\prime}$, $1\leq s\leq d$, we have

$\mathbb{E}(XX^{*})=\frac{1}{d^{2}}\sum_{s=1}^{d}\mathbb{E}(A_{s}).$

Therefore, we get using the triangle inequality

$\|\mathbb{E}(XX^{*})\|_{\infty}\leq\frac{1}{d}.$

Following the same argument, one can show a similar bound
$\|\mathbb{E}(X^{*}X)\|\leq 1/d$ to finish the proof. ∎

######  Lemma 3.

Let $W$ be an $n\times n$ random matrix satisfying Assumptions 1 and 2. Let
$X=\frac{1}{d}\sum_{s=1}^{d}W_{s}\otimes\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{s}^{\prime}$, where
$W_{s}$, $W_{s}^{\prime}$, $1\leq s\leq d$, are independent copies of $W$.
Then,

$\|{\rm Cov}(X)\|_{\infty}\leq\frac{1}{d}\max_{1\leq i,j\leq n}\eta_{ij}^{2}.$

###### Proof.

First note that by the independence of the $W_{s},W_{s}^{\prime}$, $1\leq
s\leq d$, we have

${\rm Cov}(X)=\frac{1}{d^{2}}\sum_{s=1}^{d}{\rm Cov}\left(W_{s}\otimes\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{s}^{\prime}\right).$

Thus, using the triangle inequality, we get

$\|{\rm Cov}(X)\|_{\infty}\leq\frac{1}{d^{2}}\sum_{s=1}^{d}\left\|{\rm
Cov}\left(W_{s}\otimes\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{s}^{\prime}\right)\right\|_{\infty}.$

It is not difficult to check that, for every $1\leq s\leq d$,

$\left\|{\rm Cov}\left(W_{s}\otimes\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{s}^{\prime}\right)\right\|_{\infty}=\sup_{\|M\|_{2}\leq
1}\mathbb{E}\left(\left|{\rm Tr}\left(MW_{s}\otimes\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{s}^{\prime}\right)\right|^{2}\right),$

where the supremum is taken over $n^{2}\times n^{2}$ matrices $M$. Denoting
the entries of $M$ by $M_{ijkl}$, $1\leq i,j,k,l\leq n$, we have

$\displaystyle\left\|{\rm Cov}\left(W_{s}\otimes\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{s}^{\prime}\right)\right\|_{\infty}$ $\displaystyle=\sup_{\|M\|_{2}\leq
1}\mathbb{E}\left(\left|\sum_{1\leq i,j,k,l\leq n}M_{ijkl}W_{s,ij}\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{s,kl}^{\prime}\right|^{2}\right)$ $\displaystyle=\sup_{\|M\|_{2}\leq
1}\sum_{1\leq i,j,k,l\leq n}|M_{ijkl}|^{2}\eta_{ij}\eta_{kl}$
$\displaystyle=\max_{1\leq i,j\leq n}\eta_{ij}^{2}.$

This finishes the proof. ∎

We are now ready to prove the upper bound on $\|Y-\mathbb{E}(Y)\|_{\infty}$
promised in Theorem 2.

###### Proof of Theorem 2.

In view of Lemma 1, it is enough to show that

$\mathbb{E}\left\|\frac{1}{d}\sum_{s=1}^{d}W_{s}\otimes\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{s}^{\prime}\right\|_{\infty}\leq\frac{C_{\beta}}{\sqrt{d}},$

for some constant $C_{\beta}$ depending only on $\beta$. To this aim, we will
make use of Theorem 3. We set

$X=\frac{1}{d}\sum_{s=1}^{d}W_{s}\otimes\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{s}^{\prime}=\sum_{1\leq
s\leq d}Z_{s},$

defining, for every $1\leq s\leq d$,

$Z_{s}=\frac{W_{s}\otimes\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{s}^{\prime}}{d}.$

Applying Theorem 3 and using Lemmas 2 and 3, we get that, for $p=\lfloor
C^{\prime}\log n\rfloor$,

(5) $\mathbb{E}\|X\|_{\infty}\leq\frac{4}{\sqrt{d}}+\frac{C(\log
n)^{\frac{3}{2}}}{\sqrt{d}}\max_{1\leq i,j\leq n}\eta_{ij}+C(\log
n)^{2}\max_{1\leq s\leq d}\left(\mathbb{E}\,{\rm
Tr}\left(\left|Z_{s}\right|^{2p}\right)\right)^{\frac{1}{2p}},$

where $C,C^{\prime}$ are universal constants.

Clearly, using that $W_{s}$ and $W_{s}^{\prime}$ are independent and
identically distributed, we can write

$\left(\mathbb{E}\,{\rm
Tr}\left(\left|Z_{s}\right|^{2p}\right)\right)^{\frac{1}{2p}}=\frac{1}{d}\left(\mathbb{E}\,{\rm
Tr}\left(\left|W_{s}\right|^{2p}\right)\right)^{\frac{1}{p}}.$

To estimate the latter, we can make use of [LvHY18, Theorem 4.2] with $p$ as
above or of [BvH16, Corollary 3.5] (with the corresponding adaptation to the
setting here), to deduce that

$\left(\mathbb{E}\,{\rm
Tr}\left(\left|W_{s}\right|^{2p}\right)\right)^{\frac{1}{p}}\leq
C_{\beta}^{\prime}\big{(}1+(\log n)^{1+\beta}\max_{1\leq i,j\leq
n}\eta_{ij}\big{)}\leq\tilde{C}_{\beta},$

for some constants $C_{\beta}^{\prime},\tilde{C}_{\beta}$ depending only on
$\beta$, where we made use of Assumption 4. Putting the above inequality back
into equation (5) and using Assumption 4 and the condition on $d$, we deduce
the result. ∎

##  3\. Implications in terms of random quantum channels

The goal of this section is to use the previous estimates in order to design
an optimal quantum expander. Let $W$ be an $n\times n$ random matrix
satisfying Assumptions 1, 2, 3 and 4 and let $Y$ be defined as in equation
(2). The result of the previous section ensures that $Y$ concentrates, on
average, around its expectation. In order for this to imply that $Y$ has a
large spectral gap (and thus corresponds to an optimal quantum expander), we
need to ensure that $\mathbb{E}(Y)$ itself has a large spectral gap. We will
now make the following extra assumption on the variances $(\eta_{ij})_{1\leq
i,j\leq n}$ to ensure this, and to additionally guarantee that the CP map
corresponding to $Y$ is TP on average.

######  Assumption 5.

The $n\times n$ matrix $\eta:=(\eta_{ij})_{1\leq i,j\leq n}$ is such that
$\eta^{t}$ is the transition matrix of an irreducible Markov chain on
$\\{1,\ldots,n\\}$ satisfying: there exists a universal constant
$\mathbf{C}^{\prime\prime}>0$ such that

$s_{2}(\eta)\leq\frac{\mathbf{C}^{\prime\prime}}{\sqrt{d}},$

where $s_{2}(\eta)$ denotes the second largest singular value of $\eta$.

Note that the above assumption ensures that $\eta$ is (left-)stochastic, i.e.
for each $1\leq j\leq n$, $\sum_{i=1}^{n}\eta_{ij}=1$, which implies that
$\lambda_{1}(\eta)=1$. The assumption on $s_{2}(\eta)$ provides, among other,
a quantitative control on the rate of convergence of the corresponding Markov
chain to its equilibrium measure. The simplest example is when $\eta=J/n$,
where $J$ is the $n\times n$ matrix whose entries are all equal to $1$. In
this case, the leading eigenvector is the uniform probability $u$ on
$\\{1,\ldots,n\\}$ and $s_{2}(\eta)=0$, so there is convergence to $u$ in only
$1$ step. More generally, we allow $\eta$ to have a unique fixed probability
which is not necessarily uniform and a second largest singular value which is
small but not necessarily $0$.

######  Example 4.

Let us look at the three examples of random matrix models presented in Section
2.1, which were shown to already satisfy Assumptions 1, 2, 3 and 4, and see
what extra restriction is needed in order to satisfy Assumption 5 as well.
First note that, in all examples, the considered random matrix $W$ has an
associated variance matrix $\eta$ which is doubly stochastic. In Example 1, we
have $\eta=J/n$, so it satisfies Assumption 5 since $s_{2}(\eta)=0$. For
Example 2, we will restrict the variance profile of the Gaussian matrix to
those satisfying Assumption 5. Finally, for Example 3, we will choose the
degree $r$ of the regular graph equal to the Kraus rank $d$, and we will
impose that the graph is itself an optimal expander. This can for instance be
achieved by picking such $d$-regular graph uniformly at random (see [Sar22]
and references therein).

With this assumption at hand, we can now state and prove the main result of
this note. We recall that, given a CP map $\Phi$, we denote by
$|\lambda_{1}(\Phi)|,|\lambda_{2}(\Phi)|$ its largest and second largest (in
modulus) eigenvalues, and by $s_{1}(\Phi),s_{2}(\Phi)$ its largest and second
largest singular values.

######  Theorem 4.

Let $n,d\in\mathbb{N}$ and consider $W_{1},\ldots,W_{d}$ independent copies of
an $n\times n$ random matrix $W$ satisfying Assumptions 1, 2, 3, 4 and 5.
Define the random CP map $\Phi$ on $\mathcal{M}_{n}(\mathbb{C})$, having Kraus
rank at most $d$ with $d$ satisfying condition (3), as

$\Phi:X\in\mathcal{M}_{n}(\mathbb{C})\mapsto\frac{1}{d}\sum_{s=1}^{d}W_{s}XW_{s}^{*}\in\mathcal{M}_{n}(\mathbb{C}).$

Then, $\Phi$ is on average TP and such that

$1\leq\mathbb{E}|\lambda_{1}(\Phi)|\leq\mathbb{E}(s_{1}(\Phi))\leq
1+\frac{C}{\sqrt{d}}\qquad\text{and}\qquad\max\left(\mathbb{E}|\lambda_{2}(\Phi)|,\mathbb{E}(s_{2}(\Phi))\right)\leq\frac{C}{\sqrt{d}},$

for some universal constant $C>0$.

###### Proof.

We start by noting that

$\mathbb{E}\left(W^{*}W\right)=\sum_{i,j,k=1}^{n}\mathbb{E}\left(\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{ji}W_{jk}\right)E_{ik}=\sum_{i=1}^{n}\left(\sum_{j=1}^{n}\eta_{ji}\right)E_{ii}=\sum_{i=1}^{n}E_{ii}=I,$

where the second equality is because $\mathbb{E}(\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{ji}W_{jk})=0$ if $i\neq
k$ and $\mathbb{E}(\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{ji}W_{jk})=\eta_{ji}$ if $i=k$, while the third equality is because
$\sum_{j=1}^{n}\eta_{ji}=1$. This shows that $\Phi$ is on average TP since

$\mathbb{E}\left(\frac{1}{d}\sum_{s=1}^{d}W_{s}^{*}W_{s}\right)=\frac{1}{d}\sum_{s=1}^{d}\mathbb{E}\left(W_{s}^{*}W_{s}\right)=I.$

Similarly, we have

$\mathbb{E}\left(W\otimes\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu\right)=\sum_{i,j,k,l=1}^{n}\mathbb{E}\left(W_{ij}\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{kl}\right)E_{ij}\otimes
E_{kl}=\sum_{i,j=1}^{n}\eta_{ij}E_{ij}\otimes E_{ij},$

where the second equality is because $\mathbb{E}(W_{ij}\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{kl})=0$ if $i\neq k$ or
$j\neq l$ and $\mathbb{E}(W_{ij}\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{kl})=\eta_{ij}$ if
$i=k$ and $j=l$. And thus,

$\mathbb{E}(M_{\Phi})=\mathbb{E}\left(\frac{1}{d}\sum_{s=1}^{d}W_{s}\otimes\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{s}\right)=\frac{1}{d}\sum_{s=1}^{d}\mathbb{E}\left(W_{s}\otimes\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{s}\right)=\sum_{i,j=1}^{n}\eta_{ij}E_{ij}\otimes E_{ij}.$

So clearly, the spectrum of $\mathbb{E}(M_{\Phi})$ coincides with that of
$\eta$. As a consequence, we have $|\lambda_{1}(\mathbb{E}(M_{\Phi}))|=1$.
Moreover, it follows from Perron-Frobenius theorem that
$\|\mathbb{E}(M_{\Phi})\|_{\infty}=1$.

Next note that

(6)
$|\lambda_{1}(\mathbb{E}(M_{\Phi}))|\leq\mathbb{E}|\lambda_{1}(M_{\Phi})|\leq\mathbb{E}\|M_{\Phi}\|_{\infty}\leq\|\mathbb{E}(M_{\Phi})\|_{\infty}+\mathbb{E}\|M_{\Phi}-\mathbb{E}(M_{\Phi})\|_{\infty},$

where the left-most inequality follows using Jensen’s inequality while the
right-most one makes use of the triangle inequality. Now, we know by Theorem 2
that

$\mathbb{E}\|M_{\Phi}-\mathbb{E}(M_{\Phi})\|_{\infty}\leq\frac{C}{\sqrt{d}},$

for some universal constant $C$. So we deduce from equation (6) that

$1\leq\mathbb{E}|\lambda_{1}(M_{\Phi})|\leq\mathbb{E}s_{1}(M_{\Phi})\leq
1+\frac{C}{\sqrt{d}},$

which proves the statement about first eigenvalue and singular value in
Theorem 4.

To upper bound the second largest singular value, we observe that, by Weyl
inequalities (which are a consequence of the minimax principle), we have

$s_{2}(M_{\Phi})\leq
s_{2}(\mathbb{E}(M_{\Phi}))+s_{1}(M_{\Phi}-\mathbb{E}(M_{\Phi})).$

Hence, making use of Assumption 5 and of Theorem 2 again,

$\mathbb{E}s_{2}(M_{\Phi})\leq
s_{2}(\mathbb{E}(M_{\Phi}))+\mathbb{E}\|M_{\Phi}-\mathbb{E}(M_{\Phi})\|_{\infty}\leq\frac{\mathbf{C}^{\prime\prime}+C}{\sqrt{d}}.$

Finally, we know by Weyl’s majorant theorem [Bha97, Theorem II.3.6] that

$|\lambda_{1}(M_{\Phi})|+|\lambda_{2}(M_{\Phi})|\leq
s_{1}(M_{\Phi})+s_{2}(M_{\Phi}).$

We can thus upper bound the second largest eigenvalue as

$\mathbb{E}|\lambda_{2}(M_{\Phi})|\leq\mathbb{E}\|M_{\Phi}\|_{\infty}+\mathbb{E}s_{2}(M_{\Phi})-\mathbb{E}|\lambda_{1}(M_{\Phi})|\leq\frac{\mathbf{C}^{\prime\prime}+2C}{\sqrt{d}},$

where we have used all previously proven estimates. And this finishes the
proof. ∎

Let us note that all estimates in this paper are in expectation. However, it
is a standard procedure to turn these into bounds holding with high
probability using standard concentration inequalities. If doing so, it would
additionally be possible to modify the construction in Theorem 4 to get a
random CP map $\tilde{\Phi}$ which is exactly TP (not just on average), but
still has similar spectral properties as $\Phi$. Indeed, setting

$\Sigma:=\frac{1}{d}\sum_{s=1}^{d}W_{s}^{*}W_{s},$

one would have that, not only $\mathbb{E}(\Sigma)=I$, but also
$\|\Sigma-I\|_{\infty}$ is small with high probability. One could thus set
$\tilde{W}_{s}:=W_{s}\Sigma^{-1/2}$, $1\leq s\leq d$, and define the random CP
map $\tilde{\Phi}$, which is TP by construction, as

$\tilde{\Phi}:X\in\mathcal{M}_{n}(\mathbb{C})\mapsto\frac{1}{d}\sum_{s=1}^{d}\tilde{W}_{s}X\tilde{W}_{s}^{*}\in\mathcal{M}_{n}(\mathbb{C}).$

The latter is TP by construction and such that, with high probability, its
eigenvalues do not differ by much from those of $\Phi$.

We have however opted not to follow this path in order to keep the
presentation more synthetic. We aimed instead at shedding light on how recent
results from random matrix theory can be readily used to exhibit quantum
expanders from their classical counterparts. Let us in fact emphasize again on
this point, which was already mentioned in the introduction. Our result
provides a recipe for constructing a random optimal quantum expander from any
optimal classical expander (either random or deterministic). Indeed, let
$A\in\mathcal{M}_{n}(\mathbb{R})$ be the adjacency matrix of a $d$-regular
graph on $n$ vertices satisfying $d\geq(\log n)^{4}$ and $s_{2}(A)\leq
C\sqrt{d}$, for some universal constant $C>0$. Let
$W\in\mathcal{M}_{n}(\mathbb{C})$ be a random matrix with independent centered
entries, such that $\mathbb{E}|W_{ij}|^{2}=A_{ij}/d$, $1\leq i,j\leq n$.
Suppose additionally that the moments of the $W_{ij}$’s satisfy Assumption 3.
Next, sample $W_{1},\ldots,W_{d}$ independent copies of $W$, set
$K_{s}=W_{s}/\sqrt{d}$, $1\leq s\leq d$, and let $\Phi$ be the random CP map
on $\mathcal{M}_{n}(\mathbb{C})$ that has the $K_{s}$’s as Kraus operators.
Then $\Phi$ is on average TP and such that $\mathbb{E}|\lambda_{2}(\Phi)|\leq
C^{\prime}/\sqrt{d}$.

Finally, one might wonder why we have not said anything about the fact that
the random quantum channel $\Phi$ that we construct should have a fixed point
$\hat{\rho}$ which has on average a large entropy. This is because our result
actually remains interesting whether the entropy of $\hat{\rho}$ is large or
small. Indeed, it provides examples of quantum channels that have a spectral
gap that is as large as it can be as soon as their number $d$ of Kraus
operators is larger than $(\log n)^{4}$, hence in particular for $(\log
n)^{4}\leq d\ll n$. And the latter regime is one where the construction is
non-trivial whatever the entropy of $\hat{\rho}$ is, as explained in Section
1.2. If we wanted to guarantee that $\hat{\rho}$ has on average a large
entropy, we could add to Assumption 5 that the variance matrix $\eta$ is
doubly stochastic. That way, we would have that our random CP map $\Phi$ is on
average not only TP but also unital (because $\mathbb{E}(WW^{*})=I$). We would
thus have that $I/n$, which has maximal entropy, is on average left invariant
by $\Phi$. And we would deduce from this that $\hat{\rho}$ is on average close
to $I/n$, and hence has close to maximal entropy.

##  4\. Summary and perspectives

We have shown in this note that a wide class of random quantum channels are on
average optimal quantum expanders. Prior to this work, only three specific
models were known to have this property, all of them requiring a large amount
of randomness to be implemented, as they relied on the sampling of either Haar
unitary or Gaussian matrices. Here we prove that sparse matrices whose entries
have a much simpler distribution (e.g. Bernoulli random variables) actually do
the job as well. This is a first step towards derandomization, which could be
of great interest in practice. Quantum expanders indeed find applications in
many sub-fields of quantum information. The seminal ones were inspired by
applications of classical expanders, and therefore more computer science
orientated (quantum encryption [AS04], quantum interactive proof systems
[BASTS08], etc). But they also turned out to be crucial objects in quantum
condensed matter physics, in particular to design many-body quantum systems
where subsystems have large entanglement entropy but correlations between them
that decay fast [Has07, GGJN18, LPG22].

One open question at this point is: how to generalize the results we have
obtained here for random matrices $W_{s}$ with independent entries to the case
of correlated entries? Indeed, the operator norm estimate from [BBvH21, BvH22]
that we use does not require independent entries. We only add this assumption
to be able to get an optimal estimate without technical considerations. But
the trade-off between correlation and moment control would be interesting to
study. For instance, the same spectral gap scaling as the one we get is known
to hold when the $W_{s}$’s are independent uniformly distributed unitaries
[Has07, Pis14]. One can wonder whether this setting (where all moments are
tightly controlled) could be treated with our approach, and whether the result
could be extended to the case of independent unitaries distributed according
to more general measures, which are known to somehow resemble the uniform
measure. Examples include approximate $t$-design measures (which are by
definition such that their moments up to order $t$ are close to those of the
uniform measure), the uniform measure on sub-groups of the unitary group
(which have been shown to have moments that can be compared to those of the
uniform measure in a systematic way [BC20]), etc.

Finally, as mentioned in the introduction, we believe that the main
mathematical result our analysis relies on (which is taken from [BBvH21,
BvH22] and stated here as Theorem 3) could find several other applications in
quantum information. It could potentially be applied to any situation where
one needs to estimate the deviation from average of a sum of independent
random operators, and thus be useful to study all kinds of typical properties
of quantum systems.

### Acknowledgments

The authors are thankful to Ramon van Handel for bringing to their attention a
bug in a first version of this work, and for the suggested corrections. Part
of this work was conducted when the second named author visited the first
named author in Institut Fourier at Université Grenoble Alpes. The first named
author was supported by the ANR projects ESQuisses (grant number
ANR-20-CE47-0014-01), STARS (grant number ANR-20-CE40-0008) and QTraj (grant
number ANR-20-CE40-0024-01).

## References

  * [Alo86] N. Alon.  Eigenvalues and expanders.  Combinatorica, 6(2):83–96, 1986.
  * [AS04] A. Ambainis and A. Smith.  Small pseudo-random families of matrices: Derandomizing approximate quantum encryption.  RANDOM APPROX, LNCS, 3122:249–260, 2004.
  * [AS17] G. Aubrun and S. J. Szarek.  Alice and Bob meet Banach: The interface of asymptotic geometric analysis and quantum information theory, volume 223 of Mathematical Surveys and Monographs.  American Mathematical Society, 2017.
  * [BASTS08] A. Ben-Aroya, O. Schwartz, and A. Ta-Shma.  Quantum expanders: motivation and constructions.  23rd Annual IEEE Conference on Computational Complexity, pages 292–303, 2008.
  * [BBLM20] T. Bannink, J. Briët, F. Labib, and H. Maassen.  Quasirandom quantum channels.  Quantum, 4:298, 2020.
  * [BBvH21] A. Bandeira, M. Boedihardjo, and R. van Handel.  Matrix concentration inequalities and free probability.  arXiv:2108.06312, 2021.
  * [BC20] C. Bordenave and C. Collins.  Strong asymptotic freeness for independent uniform variables on compact groups associated to non-trivial representations.  arXiv:2012.08759, 2020.
  * [BFSU99] A. Z. Broder, A. M. Frieze, S. Suen, and E. Upfal.  Optimal construction of edge-disjoint paths in random graphs.  SIAM J. Comput., 28(2):541–573, 1999.
  * [BGBK19] F. Benaych-Georges, C. Bordenave, and A. Knowles.  Largest eigenvalues of sparse inhomogeneous Erdos-Rényi graphs.  Ann. Probab., 47(3):1653–1676, 2019.
  * [Bha97] R. Bhatia.  Matrix analysis, volume 169 of Graduate Texts in Mathematics.  Springer, New York, 1997.
  * [BHKY20] R. Bauerschmidt, J. Huang, A. Knowles, and H.-T. Yau.  Edge rigidity and universality of random regular graphs of intermediate degree.  Geom. Funct. Anal., 30(3):693–769, 2020.
  * [Bor20] C. Bordenave.  A new proof of Friedman’s second eigenvalue theorem and its extension to random lifts.  Ann. Sci. Éc. Norm. Supér. (4), 53(6):1393–1439, 2020.
  * [BvH16] A. S. Bandeira and R. van Handel.  Sharp nonasymptotic bounds on the norm of random matrices with independent entries.  Ann. Probab., 44(4):2479–2506, 2016.
  * [BvH22] T. Brailovskaya and R. van Handel.  Universality and sharp matrix concentration inequalities.  arXiv:2201.05142, 2022.
  * [CGJ18] N. Cook, L. Goldstein, and T. Johnson.  Size biased couplings and the spectral gap for random regular graphs.  Ann. Probab., 46(1):72–125, 2018.
  * [dlPnG99] V. H. de la Peña and E. Giné.  Decoupling: From dependence to independence.  Probability and Its Applications. Springer, New-York, 1999.
  * [EG08] J. Eisert and D. Gross.  Quantum Margulis expanders.  Quantum Inf. Comput., 8(8/9):722–733, 2008.
  * [Fri08] J. Friedman.  A proof of Alon’s second eigenvalue conjecture and related problems.  Mem. Amer. Math. Soc., 195(910), 2008.
  * [GGJN18] C. E. González-Guillén, M. Junge, and I. Nechita.  On the spectral gap of random quantum channels.  arXiv:1811.08847, 2018.
  * [Har08] A. W. Harrow.  Quantum expanders from any classical Cayley graph expander.  Quantum Inf. Comput., 8(8/9):715–721, 2008.
  * [Has07] M. B. Hastings.  Random unitaries give quantum expanders.  Phys. Rev. A, 76:032315, 2007.
  * [HLW06] S. Hoory, N. Linial, and A. Wigderson.  Expander graphs and their applications.  Bull. Am. Math. Soc., 43(4):439–561, 2006.
  * [LPG22] C Lancien and D. Pérez-García.  Correlation length in random MPS and PEPS.  Ann. Henri Poincaré, 23:141–222, 2022.
  * [LPS88] A. Lubotzky, R. Phillips, and P. Sarnak.  Ramanujan graphs.  Combinatorica, 8(3):261–277, 1988.
  * [LvHY18] R. Latała, R. van Handel, and P. Youssef.  The dimension-free structure of nonhomogeneous random matrices.  Invent. Math., 214(3):1031–1080, 2018.
  * [Mar88] G. A. Margulis.  Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators.  Problemy Peredachi Informatsii, 24(1):51–60, 1988.
  * [MSS15] A. W. Marcus, D. A. Spielman, and N. Srivastava.  Interlacing families I: Bipartite Ramanujan graphs of all degrees.  Ann. of Math. (2), 182(1):307–325, 2015.
  * [Nil91] A. Nilli.  On the second eigenvalue of a graph.  Discrete Math., 91(2):207–210, 1991.
  * [Pis14] G. Pisier.  Quantum expanders and geometry of operator spaces.  J. Eur. Math. Soc., 16(6):1183–1219, 2014.
  * [Sar22] A. Sarid.  The spectral gap of random regular graphs.  arXiv:2201.02015, 2022.
  * [TY19] K. Tikhomirov and P. Youssef.  The spectral gap of dense random regular graphs.  Ann. Probab., 47(1):362–419, 2019.
  * [TY21] K. Tikhomirov and P. Youssef.  Outliers in spectrum of sparse Wigner matrices.  Random Struct. Algorithms, 58(3):517–605, 2021.
  * [Wol12] M. M. Wolf.  Quantum chanels & operations: Guided tour.  Lecture notes available at https://www-m5.ma.tum.de/foswiki/pub/M5/Allgemeines/MichaelWolf/QChannelLecture.pdf, 2012\.