Ramanujan quantum expanders from the Weil representation

arXiv:2609.38075 · quant-ph, cs.CC · Submitted 2026-09-29 · Read on arXiv

quant-ph, cs.CC

Submitted: 2026-09-29

Updated: 2026-09-29

License: http://creativecommons.org/licenses/by/4.0/

The gist: For every odd prime power q and D=q+1, we construct an infinite family of Ramanujan quantum expanders of degree D.

Terminology

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 PSL 2(F p) for p which is an even power of q, through the odd irreducible subrepresentation of the Weil representation of SL 2(F p). For a quantum expander of dimension N, our implementation uses O(squared N) elementary gates, and O(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.

Sources

Related papers