# Geometric picture behind quantum expanders

+ 12 like - 0 dislike
82 views

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

This post has been migrated from (A51.SE)

+ 0 like - 0 dislike

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.

This post has been migrated from (A51.SE)
answered Apr 8, 2012 by (40 points)
I don't see how is this supposed to help.

This post has been migrated from (A51.SE)

 Please use answers only to (at least partly) answer questions. To comment, discuss, or ask for clarification, leave a comment instead. To mask links under text, please type your text, highlight it, and click the "link" button. You can then enter your link URL. Please consult the FAQ for as to how to format your post. This is the answer box; if you want to write a comment instead, please use the 'add comment' button. Live preview (may slow down editor)   Preview Your name to display (optional): Email me at this address if my answer is selected or commented on: Privacy: Your email address will only be used for sending these notifications. Anti-spam verification: If you are a human please identify the position of the character covered by the symbol $\varnothing$ in the following word:p$\hbar$ysics$\varnothing$verflowThen drag the red bullet below over the corresponding character of our banner. When you drop it there, the bullet changes to green (on slow internet connections after a few seconds). To avoid this verification in future, please log in or register.