arXiv:2609.38075
Ramanujan quantum expanders from the Weil representation
Siddhartha Jain
Abstract
For every odd prime power $q$ and $D=q+1$, we construct an infinite family of Ramanujan quantum expanders of degree $D$. The construction transfers Morgenstern's Ramanujan Cayley graphs on $\operatorname{PSL}_2(\mathbb{F}_{p})$ for $p$ which is an even power of $q$, through the odd irreducible subrepresentation of the Weil representation of $\operatorname{SL}_2(\mathbb{F}_{p})$. For a quantum expander of dimension $N$, our implementation uses $O(\log^2 N)$ elementary gates, and $O(\log N)$ ancilla qudits, using a fixed finite gate set depending on $q$. An advantage compared to the previous work of Iyer, Jain, Jordan, and Somma (FOCS 2026) is that assuming the quantum circuit is implemented exactly, we satisfy the $2\sqrt{D-1}/D$ singular value bound exactly without any additive error.
AI Summary
The paper addresses explicit, efficiently implementable fixed-degree quantum expanders satisfying the Ramanujan contraction bound without additive error. For every fixed odd prime power $q$, it constructs a uniform infinite family of degree-$D=q+1$ mixed-unitary channels in dimensions $N_k=(q^{2k}-1)/2$, with second singular value on traceless operators at most $2\sqrt{D-1}/D$. Unlike the near-Ramanujan construction discussed in the paper, this bound is exact under exact circuit implementation. The construction combines Morgenstern’s non-bipartite Ramanujan Cayley graphs on $\operatorname{PSL}_2(\mathbb F_{q^{2k}})$ with Harrow’s spectral transfer principle. It uses the $(q^{2k}-1)/2$-dimensional odd irreducible subspace of the Weil representation. Projective phases cancel under conjugation. Each generator factors into at most four quadratic-phase, field-scaling, and additive-field Fourier operations, avoiding a nonabelian group Fourier transform. The paper supplies irreducibility and transfer proofs, explicit generator formulas, and deterministic preprocessing. Each channel use requires $O(\log^2 N)$ gates and depth and $O(\log N)$ ancilla qudits over a declared finite gate set depending on $q$; classical preprocessing takes $\widetilde O(\log^5 N)$ bit operations. Inputs must already occupy the odd subspace; encoding and decoding costs are excluded. Exactness is relative to that gate library. Synthesis over another universal gate set gives controlled encoded-channel error, but does not automatically preserve the odd subspace or establish the same logical spectral guarantee. Construction for all degrees and for every sufficiently large dimension remains open.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.