Sign up ×
Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. It's 100% free.

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 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).

share|cite|improve this question
A quantum expander is a random choice of one of d unitaries, and a classical expander is a random choice of one of d permutations. The two are completely analogous. I don't know what intuition you have regarding one that you don't find in the other, maybe you don't like that the unitary can be arbitrarily close to the identity? –  Ron Maimon Jul 9 '12 at 8:06

2 Answers 2

In the same paper that was linked in the question, the authors mentioned the bounds of the TPEs, in Theorem 1.6: Let $v_C$ be a classical $(N, D, 1- l_C)$ TPE, and for $0<p<1$, define $v_Q = pv_C+ (1-p)\delta_F$. Suppose that $e_A$= $1-2(2k)^4k/\sqrt{N}>0$. Then $v_Q$ is a quantum $(N,D+1, 1-e_Q, k)$ TPE where $e_Q$ is greater than or equal to $e_A/12*\min (pe_C, 1-p)>0$. This bound is optimized when $p= 1/(1+l_C)$ in which case we have $e_Q$ is greater than or equal to $e_A e_C/24$. This means that any constant degree and gap $2k$ classical TPE gives a $k$ quantum TPE, with constant gap. If the classical TPE is efficient then the quantum one is too. From these results, I believe that there is a similar geometric interpretation, except that it is limited when $2k$>N, for the quantum expanders.

share|cite|improve this answer
I don't see how is this supposed to help. –  Marcin Kotowski Apr 8 '12 at 21:35

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 is a discussion. The rough equivalence of these two definitions is known as Cheeger's inequality.

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.

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.