Quantum circuits achieve exact Ramanujan expansion with few resources
Ramanujan quantum expanders from the Weil representation
Computational Complexity
Summary
Building efficient quantum networks requires special structures called quantum expanders. This paper shows how to create particularly good quantum expanders, called Ramanujan quantum expanders, using a mathematical construction based on the Weil representation. The authors’ method uses relatively few quantum resources and matches an important quality bound exactly, which was not achieved in previous work. This advancement could help design better quantum communication and computing systems.
What this means in practice
- •For quantum hardware engineers: Create quantum circuits that implement high-quality quantum expanders with fewer gates and qudits, enabling better quantum network designs.
- •For quantum algorithm developers: Use exact Ramanujan quantum expanders to design algorithms with improved spectral properties for quantum information processing.
A theory result. No direct application yet.
Authors
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.