Ramanujan quantum expanders from the Weil representation
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
- Quantum expanders from any classical Cayley graph expander
- Efficient quantum circuits for high-dimensional representations of SU(n) and Ramanujan quantum expanders
- Breaking the cubic barrier in the Solovay-Kitaev algorithm
Related papers
- Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
- Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
- Polynomial-time classical and quantum simulation of quantum impurity models
- A quasiparticle-protected superconducting qubit
- Theory of quantum-enhanced interferometry with general Markovian light sources
- A convergent hierarchy of spectral gap certificates for qubit Hamiltonians