<p>[This answer was copied from my answer on the now-defunct theoreticalphysics stackexchange site.]
For classical expanders, the spectral definition can be expressed in terms of the second-smallest eigenvalue of the graph Laplacian, which can be thought of as the minimum of a quadratic form over all unit vectors orthogonal to the all-ones vector.  If we restrict this minimization to vectors of the form (a,a,...,a, b,b, ..b), then this yields the edge expansion of the graph.  <a href="https://lucatrevisan.wordpress.com/2011/01/19/cs359g-lecture-3-cheegers-inequality/">here</a> is a discussion.  The rough equivalence of these two definitions is known as <a href="https://en.wikipedia.org/wiki/Expander_graph#Relationships_between_different_expansion_properties">Cheeger's inequality</a>.</p>

<p>This suggests that for the quantum case we should consider the action of the channel (formed by applying a random unitary from the expander) on projectors.  A result analogous to Cheeger's inequality is derived in Appendix A of <a href="http://arxiv.org/abs/0706.0556">arXiv:0706.0556</a>.</p>

<p>On the other hand, while this is mathematically analogous, we do still know of many fewer applications of quantum expanders than are known for classical expanders.</p>

CC BY-SA 3.0
2018-04-04T02:07:19.463Z
Please accept my invitation to: https://quantumcomputing.stackexchange.com/ .
Rob
CC BY-SA 3.0
2015-11-23T16:43:24.470Z
2015-11-23T16:43:24.470Z
Aram Harrow
<p>(also asked <a href="http://theoreticalphysics.stackexchange.com/questions/1099/geometric-picture-behind-quantum-expanders">here</a>, no replies)</p>

<p>A $(d,\lambda)$-quantum expander is a distribution $\nu$ over the unitary group $\mathcal{U}(d)$ with the property that: a) $|\mathrm{supp} \ \nu| =d$, b) $\Vert \mathbb{E}_{U \sim \nu} U \otimes U^{\dagger} - \mathbb{E}_{U \sim \mu_H} U \otimes U^{\dagger}\Vert_{\infty} \leq \lambda$, where $\mu_H$ is the Haar measure. If instead of distributions over unitaries we consider distributions over permutation matrices, it's not difficult to see that we recover the usual definition of a $d$-regular expander graph. For more background, see e.g.: <a href="http://arxiv.org/abs/0811.2597">Efficient Quantum Tensor Product Expanders and k-designs</a> by Harrow and Low.</p>

<p>My question is - do quantum expanders admit any kind of geometric interpretation similar to classical expanders (where spectral gap $\sim$ isoperimetry/expansion of the underlying graph)? I don't define "geometric realization" formally, but conceptually, one could hope that purely spectral criterion can be translated to some geometric picture (which, in the classical case, is the source of mathematical richness enjoyed by expanders; mathematical structure of quantum expanders seem to be much more limited).</p>

CC BY-SA 3.0
2012-04-08T23:02:31.147Z
Maybe there's a simpler question lurking beneath ? There's a natural random walk associated with the Laplacian of a graph, and the eigenvalues of the latter tell you about the mixing of the former. It's this "geometric" view of random walks (in terms of heat diffusion) that helps us interpret expanders in the classical case. Is there a similar link between quantum random walks and properties of associated Hadamard matrices ?
Suresh Venkat
<quantum-computing><spectral-graph-theory>
Geometric picture behind quantum expanders
Marcin Kotowski
# Geometric picture behind quantum expanders

(Asked by: username_0 on 2012-04-07)

(also asked [here](http://theoreticalphysics.stackexchange.com/questions/1099/geometric-picture-behind-quantum-expanders), no replies)

A $(d,\lambda)$-quantum expander is a distribution $\nu$ over the unitary group $\mathcal{U}(d)$ with the property that: a) $|\mathrm{supp} \ \nu| =d$, b) $\Vert \mathbb{E}\_{U \sim \nu} U \otimes U^{\dagger} - \mathbb{E}\_{U \sim \mu\_H} U \otimes U^{\dagger}\Vert\_{\infty} \leq \lambda$, where $\mu\_H$ is the Haar measure. If instead of distributions over unitaries we consider distributions over permutation matrices, it's not difficult to see that we recover the usual definition of a $d$-regular expander graph. For more background, see e.g.: [Efficient Quantum Tensor Product Expanders and k-designs](http://arxiv.org/abs/0811.2597) by Harrow and Low.

My question is - do quantum expanders admit any kind of geometric interpretation similar to classical expanders (where spectral gap $\sim$ isoperimetry/expansion of the underlying graph)? I don't define "geometric realization" formally, but conceptually, one could hope that purely spectral criterion can be translated to some geometric picture (which, in the classical case, is the source of mathematical richness enjoyed by expanders; mathematical structure of quantum expanders seem to be much more limited).

**Tags:** quantum-computing, spectral-graph-theory

> **Comments:**
> **username_1**: Maybe there's a simpler question lurking beneath ? There's a natural random walk associated with the Laplacian of a graph, and the eigenvalues of the latter tell you about the mixing of the former. It's this "geometric" view of random walks (in terms of heat diffusion) that helps us interpret expanders in the classical case. Is there a similar link between quantum random walks and properties of associated Hadamard matrices ?  

---

## 1 answers

### Answer by username_2 on 2015-11-23. Score: 7

[This answer was copied from my answer on the now-defunct theoreticalphysics stackexchange site.]
For classical expanders, the spectral definition can be expressed in terms of the second-smallest eigenvalue of the graph Laplacian, which can be thought of as the minimum of a quadratic form over all unit vectors orthogonal to the all-ones vector. If we restrict this minimization to vectors of the form (a,a,...,a, b,b, ..b), then this yields the edge expansion of the graph. [here](https://lucatrevisan.wordpress.com/2011/01/19/cs359g-lecture-3-cheegers-inequality/) is a discussion. The rough equivalence of these two definitions is known as [Cheeger's inequality](https://en.wikipedia.org/wiki/Expander_graph#Relationships_between_different_expansion_properties).

This suggests that for the quantum case we should consider the action of the channel (formed by applying a random unitary from the expander) on projectors. A result analogous to Cheeger's inequality is derived in Appendix A of [arXiv:0706.0556](http://arxiv.org/abs/0706.0556).

On the other hand, while this is mathematically analogous, we do still know of many fewer applications of quantum expanders than are known for classical expanders.

> **Comments:**
> **username_3**: Please accept my invitation to: https://quantumcomputing.stackexchange.com/ .  

---

