Graphs are ubiquitous objects, useful for modeling all kinds of structures, both concrete and abstract. One structural feature of graphs which seems to be almost universally important is expansion. Informally, a graph is expanding if it is simultaneously sparse (hence “economical”) and highly connected (hence modeling a network which is robust against perturbations, where convergence to equilibrium occurs fast etc).

Hence, given a regular graph, a natural question to ask is: even if it is sparse, how “close” is it to the complete graph from an “operational” point of view? Such closeness can thus be measured in many different ways, depending on the application one has in mind. Examples of obvious properties of the complete graph include: (1) fast mixing of a random walk supported on it, (2) uniformity of edge density between subsets of vertices. One could therefore wonder which graphs satisfy either property (1) or (2) as well, and whether being similar to the complete graph in one sense or the other are actually two equivalent notions.

Random regular graphs can be shown to exhibit both properties (1) and (2) with high probability. What is more, it is known that, for any graph, property (1) implies property (2) [9], while the opposite implication holds only for dense graphs [4] or vertex-transitive sparse graphs [5]. This means that for the latter categories of graphs, the two notions of “quasi-randomness” defined by properties (1) and (2) are actually equivalent.

As we will see, similar questions can be asked in the quantum context. Studying the behavior of a walk on a regular graph there translates into studying the evolution of an input quantum state under iterative
applications of a unital quantum channel. And the idea that the graph has a uniform edge density translates into the idea that the quantum channel has outputs which are uniformly spread across all directions.
One can thus wonder, exactly as in the classical case, if these two “random looking” properties of unital quantum channels (i.e. fast convergence to their fixed point and uniformity of their output
directions) are in fact equivalent to one another.

Spectral expansion and uniformity for regular graphs

Let us first look at the classical situation, and start by defining more rigorously the two properties of regular graphs that we have been talking about.

For this, we need to introduce a bit of notation. Let $G=(V,E)$ be a $d$-regular graph, with vertex set $V$ and edge set $E$ (which means that the number of edges at each vertex is equal to $d$). Denote by $A$ its normalized adjacency matrix, i.e. the matrix of size $|V|\times|V|$ defined by $A_{uv}=e(u,v)/d$ for each $u,v\in V$, where $e(u,v)$ denotes the number of edges between vertices $u$ and $v$. The first property is related to so-called spectral expansion, which is defined as follows: Let $\lambda_1(A),\lambda_2(A),\ldots$ be the eigenvalues of $A$, ordered so that $|\lambda_1(A)|\geq|\lambda_2(A)|\geq\cdots$. Since $G$ is regular, $\lambda_1(A)=1$ (with associated eigenvector the all-one vector). The spectral expansion parameter of $G$ is then defined as
$$\lambda(G):=|\lambda_2(A)|; $$
the smallest $\lambda(G)$, the most spectrally expanding $G$. The second property is called uniformity, and can be seen as an edge expansion property. The uniformity parameter $\varepsilon(G)$ of $G$ is defined as the smallest $\varepsilon$ such that, for all $S,T\subset V$,
$$\left|\sum_{u\in S,v\in T} A_{uv}-\frac{|S||T|}{|V|}\right| \leq \varepsilon |V|;$$
the smallest $\varepsilon(G)$, the most uniform $G$.

With these definitions at hand, we can now make more rigorous what we informally explained before. Basically, we have two ways of defining and quantifying expansion of a given regular graph $G$: the first one is from a spectral perspective, through a parameter denoted $\lambda(G)$, the second one is from a more geometrical perspective, through a parameter denoted $\varepsilon(G)$. And we know the following: On the one hand, if a graph $G$ is expanding from the spectral point of view (i.e. if $\lambda(G)$ is small), then it is necessarily expanding from the geometrical point of view (i.e. $\varepsilon(G)$ is small as well). On the other hand, the converse (i.e. $\varepsilon(G)$ small implies $\lambda(G)$ small) is known to hold only for some classes of graphs, which we will define later, as we will explain how these results are proved.

What about quantum analogues?

How do these notions translate to the quantum setting? The adjacency matrix $A$ of a graph is nothing else than a transition matrix, mapping probability vectors to probability vectors. The quantum analogue of $A$ is thus a quantum channel, i.e. a completely positive and trace-preserving map $\Phi$, mapping density operators to density operators. The regularity condition on $G$ means that $A$ leaves the all-one vector invariant. In the quantum case, this translates into $\Phi$ leaving the identity matrix invariant, i.e. $\Phi$ being unital.

We can now naturally extend the definitions of spectral expansion and uniformity: Let $\Phi$ be a unital quantum channel, acting on operators on $\mathbb C^n$. $\Phi$ has spectral expansion parameter
$$\lambda(\Phi):=|\lambda_2(\Phi)|,$$
and uniformity parameter $\varepsilon(\Phi)$, the smallest $\varepsilon$ such that, for all subspaces $V,W\subset\mathbb C^n$,
$$ \left| \mathrm{Tr}(P_V\Phi(P_W)) – \frac{\mathrm{Tr}(P_V)\mathrm{Tr}(P_W)}{n} \right| \leq \varepsilon n .$$
Spectral expansion in the quantum case was first introduced in [8] (to study entanglement entropy in quantum many-body 1D systems) and in [2] (to characterize the complexity of comparing and estimating quantum entropies). Since then, the construction of quantum expanders, i.e. of unital quantum channels $\Phi$ such that $\lambda(\Phi)$ is small, has attracted a lot of interest, as it has applications in many different fields of quantum information: randomness reduction, quantum cryptography, quantum error-correction, quantum many-body physics etc. The notion of uniformity in the quantum case, on the contrary, was formalized only recently [3]. Proving that equivalence statements hold between these two notions of expansion, in the quantum case as in the classical one, would thus potentially open the way to new ways of understanding and constructing such central objects as quantum expanders.

Characterizing spectral expansion and uniformity through tensor norms

In order to understand relationships between the parameters $\lambda$ and $\varepsilon$, both in the classical and quantum settings, a crucial observation is that they can be re-expressed in terms of tensor norms, both on commutative $\ell_p$ spaces and non-commutative $S_p$ spaces. Before we do this, we need to introduce a few concepts.

Given a vector $x\in\mathbb C^n$, its (normalized) $\ell_p$-norm is defined as
$$ \|x\|_{\ell_p}:=\left( \frac{1}{n} \sum_{i=1}^n |x_i|^p \right)^{1/p} .$$
Then, given a linear operator $M:\mathbb C^n\to\mathbb C^n$, its $\ell_p$-to-$\ell_q$ norm is defined as
$$ \|M\|_{\ell_p\to\ell_q}:=\max\left\{ \langle y| M |x \rangle, \ x,y\in\mathbb C^n,\ \|x\|_{\ell_p}=1,\|y\|_{\ell_{q’}}=1 \right\}, $$
where $q’$ is such that $1/q+1/q’=1$. And the cut-norm of $M$ is defined as
$$ \|M\|_{cut} := \max\left\{ \langle y| M |x \rangle, \ x,y\in\{0,1\}^n \right\}. $$

Similarly, given a matrix $X\in\mathcal M_n(\mathbb C)$, its (normalized) $S_p$-norm is defined as
$$ \|X\|_{S_p} := \left( \frac{1}{n} \mathrm{Tr}(|X|^p) \right)^{1/p} .$$
Then, given a linear operator $\Psi:\mathcal M_n(\mathbb C)\to\mathcal M_n(\mathbb C)$, its $S_p$-to-$S_q$ norm is defined as
$$ \|\Psi\|_{S_p\to S_q} := \max\left\{ \mathrm{Tr}(Y^*\Psi(X)), \ X,Y\in\mathcal M_n(\mathbb C),\ \|X\|_{S_p}=1,\|Y\|_{S_{q’}}=1 \right\} .$$
And the cut-norm of $\Psi$ is defined as
$$ \|\Psi\|_{cut} := \left\{ \mathrm{Tr}(Y^*\Psi(X)), \ X,Y \text{ projectors on } \mathbb C^n \right\} .$$

It is not very complicated to see that spectral expansion and uniformity can actually be characterized in terms of some of the various norms defined above. Indeed, for any regular graph $G$ on $n$ vertices, with adjacency matrix $A$,
$$ \lambda(G)=\left\| A-J \right\|_{\ell_2\to\ell_2} \text{ and } \varepsilon(G)=\left\| A-J \right\|_{cut} , $$
where $J$ is the matrix with all coefficients equal to $1/n$ (i.e. the adjacency matrix of the complete graph on $n$ vertices). And analogously, for any unital quantum channel $\Phi$ on $n\times n$ matrices,
$$ \lambda(\Phi)= \left\| \Phi-\Pi \right\|_{S_2\to S_2} \text{ and } \varepsilon(\Phi)= \left\| \Phi-\Pi \right\|_{cut}, $$
where $\Pi$ is the so-called completely randomizing quantum channel, defined as $\Pi:X\mapsto\mathrm{Tr}(X)I/n$, with $I$ the identity matrix.

An important fact about the cut-norm, in the classical and quantum cases, is that it is equivalent to the $\ell_{\infty}\to\ell_1$ and $S_{\infty}\to S_1$ norms, respectively, with constants of domination that do not depend on the dimension. Specifically, we have
$$ \forall\ M:\mathbb C^n\to\mathbb C^n,\ \|M\|_{cut} \leq \|M\|_{\ell_{\infty}\to\ell_1} \leq \pi^2\|M\|_{cut} , $$
$$ \forall\ \Psi:\mathcal M_n(\mathbb C)\to\mathcal M_n(\mathbb C),\ \|\Psi\|_{cut} \leq \|\Psi\|_{S_{\infty}\to S_1} \leq \pi^2\|\Psi\|_{cut} . $$
This means that comparing parameters $\lambda$ and $\varepsilon$, for graphs or quantum channels, actually boils down to comparing $\ell_2\to\ell_2$ and $\ell_{\infty}\to\ell_1$ norms or $S_2\to S_2$ and $S_{\infty}\to S_1$ norms.

Because of the inherently crucial tensor product structure of quantum information theory, there are plenty of other contexts where such tensor norms show up. Just to mention a few examples: to quantify the amount of entanglement in multipartite quantum states [1], to quantify non-locality or communication complexity in cooperative multi-player scenarios [11] etc.

How to prove equivalence between spectral expansion and uniformity?

By the way these $\ell_p$ and $S_p$ norms are ordered, it always holds that $\|\cdot\|_{\ell_2\to\ell_2}\geq\|\cdot\|_{\ell_{\infty}\to\ell_1}$ and $\|\cdot\|_{S_2\to S_2}\geq\|\cdot\|_{S_{\infty}\to S_1}$. This proves the claim that, for any regular graph $G$ and any unital quantum channel $\Phi$, a small spectral expansion parameter implies a small uniformity parameter, since
$$ \lambda(G)= \left\| A-J \right\|_{\ell_2\to\ell_2} \geq \left\| A-J \right\|_{\ell_{\infty}\to\ell_1} \geq \left\| A-J \right\|_{cut} = \varepsilon(G) ,$$
$$ \lambda(\Phi)= \left\| \Phi-\Pi \right\|_{S_2\to S_2} \geq \left\| \Phi-\Pi \right\|_{S_{\infty}\to S_1} \geq \left\| \Phi-\Pi \right\|_{cut} = \varepsilon(\Phi) .$$

But what about the converse? For which classes of graphs and quantum channels does a small uniformity parameter imply a small spectral expansion parameter? As we explained earlier, in the classical case, there are basically two categories of graphs for which this reverse implication holds: those that are sufficiently dense and those that are sparse but with enough symmetries. As we will see, the same is actually true in the quantum case.

Let us start with the case of dense graphs, which was studied in the seminal work [4]. For any $d$-regular graph $G$ on $n$ vertices, define its edge density as $\delta:=d/n$. Then,
$$ \lambda(G) \leq \left( \frac{2\varepsilon(G)}{\delta^2} \right)^{1/4} . $$
This proves that, whenever $\delta=\Omega(1)$, $\lambda(G)\leq C\varepsilon(G)^{1/4}$.

The analogue of this result in the quantum case is treated in [3] and reads as follows: For any unital quantum channel $\Phi$, define its randomizing parameter as $\eta:=\|\Phi-\Pi\|_{S_1\to S_{\infty}}$. Then,
$$ \lambda(\Phi) \leq \left( \pi^2\eta^3\varepsilon(G) \right)^{1/4} . $$
This proves that, whenever $\eta=O(1)$, $\lambda(G)\leq C\varepsilon(G)^{1/4}$. Now, observe that, in the classical case, $\eta=\|A-J\|_{\ell_1\to\ell_{\infty}}=1/\delta-1$, so that the condition $\delta=\Omega(1)$ is actually equivalent to the condition $\eta=O(1)$. The quantum statement can thus really be seen as similar to the classical one. In fact, such inequality involving $\eta$ rather than $\delta$, holds in the exact same way in the classical setting, and is better than the original one in the regime where $\eta$ is small enough (i.e. $\delta$ is large enough). Indeed, the proof only relies on a clever use of Cauchy-Schwartz inequality and is thus valid for $\ell_p$ norms as for $S_p$ norms.

Let us now turn to the case of symmetric graphs. More specifically, let $G$ be a so-called vertex-transitive regular graph. This means that there exists $\Gamma$ a transitive subgroup of the group of permutations of $n$ elements (with $n$ the number of vertices of $G$), such that the adjacency matrix $A$ of $G$ satisfies
$$ \forall\ \gamma\in\Gamma,\ M_{\gamma}AM_{\gamma}^{-1}=A ,$$
where $M_{\gamma}$ is the $n\times n$ permutation matrix associated to $\gamma$.

If $G$ is such a graph, the celebrated commutative Grothendieck inequality for tensor products [6] (more precisely a factorization version of it [10]) allows to show that
$$ \|A-J\|_{\ell_2\to\ell_2} \leq K\|A-J\|_{\ell_{\infty}\to\ell_1} , $$
where $1.338 < K < 1.405$ is the complex Grothendieck constant. As an immediate corollary, we get that, for any vertex-transitive regular graph $G$, $$ \lambda(G) = \|A-J\|_{\ell_2\to\ell_2} \leq K\|A-J\|_{\ell_{\infty}\to\ell_1} \leq K\pi^2\|A-J\|_{cut} = K\pi^2\varepsilon(G) . $$

The analogue of vertex-transitivity for a quantum channel is so-called irreducible covariance. Namely, a unital quantum channel $\Phi$ is irreducibly covariant if there exists a compact group $\Gamma$ with irreducible unitary representations $\gamma\in\Gamma\mapsto U_{\gamma}\in U(n)$ and $\gamma\in\Gamma\mapsto V_{\gamma}\in U(n)$ such that
$$ \forall\ \gamma\in\Gamma,\ \Phi(U_{\gamma}\cdot U_{\gamma}^{-1}) = V_{\gamma}\Phi(\cdot)V_{\gamma}^{-1} .$$

If $\Phi$ is such a quantum channel, it is now a factorization version of the non-commutative Grothendieck inequality [7] which allows to show that
$$ \|\Phi-\Pi\|_{S_2\to S_2} \leq 2 \|\Phi-\Pi\|_{S_{\infty}\to S_1} .$$
Again, we get as an immediate corollary that, for any irreducibly covariant unital quantum channel $\Phi$,
$$ \lambda(\Phi) = \|\Phi-\Pi\|_{S_2\to S_2} \leq 2\|\Phi-\Pi\|_{S_{\infty}\to S_1} \leq 2\pi^2\|\Phi-\Pi\|_{cut} = 2\pi^2\varepsilon(\Phi) . $$

Can the classical setting be seen as a special case of the quantum setting?

There are several ways to embed adjacency matrices of regular graphs into quantum channels. One possibility is to define, for any $A:\mathbb C^n\to\mathbb C^n$,
$$ \Phi_A:X\in\mathcal M_n(\mathbb C) \mapsto \sum_{i,j=1}^n A_{ij}X_{jj} |i\rangle\langle i| \in \mathcal M_n(\mathbb C) .$$
As a sanity check that this embedding makes sense, observe that the complete graph is embedded into the completely randomizing quantum channel, i.e. $\Phi_J=\Pi$. What is more, it is easy to see that $\|\Phi_A-\Pi\|_{S_p\to S_q}= \|A-J\|_{\ell_p\to\ell_q}$ and $\|\Phi_A-\Pi\|_{cut}= \|A-J\|_{cut}$, so that spectral expansion and uniformity parameters are preserved under the embedding. Finally, $\Phi_A$ is an irreducibly covariant quantum channel if and only if $A$ is the adjacency matrix of a vertex-transitive graph, and $\Phi_A$ is a $O(1)$-randomizing quantum channel if and only if $A$ is the adjacency matrix of an $\Omega(1)$-dense graph.

This means that all quasi-randomness properties of a given regular graph can be exported into quasi-randomness properties of its corresponding unital quantum channel. This is particularly useful in order to show that irreducible covariance is a necessary condition for a non-randomizing unital channel to be such that uniformity implies spectral expansion. Indeed, in [5] examples where provided of sparse regular graphs $G$ which are not vertex-transitive, and such that $\varepsilon(G)$ is small but $\lambda(G)$ is large. Through the embedding described above, such examples can be immediately turned into examples of non-randomizing unital channels $\Phi$ which are not irreducibly covariant, and such that $\varepsilon(\Phi)$ is small but $\lambda(\Phi)$ is large.

► BibTeX data

► References

Cited by

This View is published in Quantum Views under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.