Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.38075

Ramanujan quantum expanders from the Weil representation

Siddhartha Jain

quant-phcs.CCSubmitted Sep 29, 2026• Announced Sep 30, 2026• 0 citations
arXivHTMLPDF

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.

No sign of AI-generated text

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Efficient quantum circuits for high-dimensional representations of SU(n) and Ramanujan quantum expanders

Vishnu Iyer, Siddhartha Jain, Stephen Jordan +1 more

We present efficient quantum circuits that implement high-dimensional unitary irreducible representations (irreps) of $SU(n)$, where $n \ge 2$ is constant. For dimension $N$ and error $ε$, the number of quantum gates in our circuits is polynomial in $\log(N)$ and $\log(1/ε)$. Our construction relies on the Jordan-Schwinger representation, which allows us to realize irreps of $SU(n)$ in the Hilbert space of $n$ quantum harmonic oscillators. Together with a recent efficient quantum Hermite transform, which allows us to map the computational basis states to the eigenstates of the quantum harmonic oscillator, this allows us to implement these irreps efficiently. Our quantum circuits can be used to construct explicit Ramanujan quantum expanders, a longstanding open problem. They can also be used to fast-forward the evolution of certain quantum systems.

quant-pharXiv:2602.15180•Feb 18, 2026•5 citations

Depth-1 expanders on the unitary group and applications

Anurag Anshu, Shankar Balasubramanian, Jonas Haferkamp +2 more

We construct a constant-degree and constant-gap quantum expander on $n$ qubits where each unitary can be implemented by a depth-$1$ and 1D circuit of Pauli or CNOT gates. We provide two applications of this expander. First, we use it to construct a family of frustration-free 1D Hamiltonians whose ground states obey the entanglement-gap relation $S = Θ(Δ^{-1/2})$; this is believed to be optimal, but achieving it had been open. Second, we use it to provide a streaming protocol that tests for closeness to a class of 1D volume-law entangled states. Moreover, we extend our quantum expander to a constant-degree and constant-gap expander on the unitary group where each unitary is a single $T$ gate, a single $T^{\dagger}$ gate, or a depth-$1$ Clifford circuit. This implies that a random sequence of unitaries from the expander yields a gapped walk on a dense subgroup of the unitary group. This improves upon previous work by Bourgain and Gamburd which did not control the dependence of the gap on the dimension.

quant-pharXiv:2609.01605•Sep 2, 2026•1 citation

Quantum Expanders: Motivation and Constructions

Avraham Ben-Aroya, Oded Schwartz, Amnon Ta‐Shma

We define quantum expanders in a natural way. We give two constructions of quantum expanders, both based on classical expander constructions. The first construction is algebraic, and is based on the construction of Cayley Ramanujan graphs over the group PGL(2, q) given by Lubotzky et al. (1988). The second construction is combinatorial, and is based on a quantum variant of the Zig-Zag product introduced by Reingold et al. (2000). Both constructions are of constant degree, and the second one is explicit. Using quantum expanders, we characterize the complexity of comparing and estimating quantum entropies. Specifically, we consider the following task: given two mixed states, each given by a quantum circuit generating it, decide which mixed state has more entropy. We show that this problem is QSZK-complete (where QSZK is the class of languages having a zero-knowledge quantum interactive protocol). This problem is very well motivated from a physical point of view. Our proof resembles the classical proof that the entropy difference problem is SZK-complete, but crucially depends on the use of quantum expanders.

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2008•16 citations

Quantum expanders and the quantum entropy difference problem

Avraham Ben-Aroya, Amnon Ta‐Shma

We define quantum expanders in a natural way. We show that under certain conditions classical expander constructions generalize to the quantum setting, and in particular so does the Lubotzky, Philips and Sarnak construction of Ramanujan expanders from Cayley graphs of the group PGL. We show that this definition is exactly what is needed for characterizing the complexity of estimating quantum entropies.

arXiv:quant-ph/0702129•Feb 13, 2007•77 citations

Full-Rank Constructions of Explicit Lossless Expanders and Good Small-Set qLTCs

Yali Aharon-Holzman, Michael Ilan, Assaf Reiner +1 more

We construct explicit two-sided lossless expanders whose binary adjacency matrices have full rank, and use them to obtain explicit asymptotically good quantum LDPC codes whose specified X- and Z-check matrices have full row rank and satisfy small-set soundness, or confinement, on a linear range. Our lossless expanders are a variant of those of Hsieh, Lubotzky, Mohanty, Reiner, and Zhang, with a free action of a finite 2-group. Under such an action, injectivity and surjectivity of the adjacency matrix are detected on a fixed-size matrix indexed by vertex orbits. Adding a sparse factor to the gadget at the middle vertices of a single type then enforces full rank, with a controlled loss in expansion. To obtain the 2-group action, we observe that reducing the generators of the Lubotzky-Phillips-Sarnak Ramanujan graphs modulo powers of 2, instead of modulo an odd prime, gives Ramanujan Cayley graphs on finite 2-groups. This construction may be of independent interest. Plugging two such expanders into the balanced product of Lin and Hsieh gives the quantum codes, since full rank of the input graphs is inherited by the check matrices. Our construction supplies the code family sought by Hong, Guo, and Lucas. Applying their analysis, within their framework and under their dynamical assumptions, gives quantum memories whose free-energy density is analytic at every positive temperature and whose guaranteed lifetime is $exp(Ω(N))$ at sufficiently low fixed positive temperature, where N is the blocklength. This improves the previously guaranteed stretched-exponential timescale.

quant-pharXiv:2611.02963•Nov 3, 2026•0 citations

Quantum expanders from any classical Cayley graph expander

Aram W. Harrow

We give a simple recipe for translating walks on Cayley graphs of a group G into a quantum operation on any irrep of G. Most properties of the classical walk carry over to the quantum operation: degree becomes the number of Kraus operators, the spectral gap becomes the gap of the quantum operation (viewed as a linear map on density matrices), and the quantum operation is efficient whenever the classical walk and the quantum Fourier transform on G are efficient. This means that using classical constant-degree constant-gap families of Cayley expander graphs on e.g. the symmetric group, we can construct efficient families of quantum expanders.

arXiv:0709.1142•Quantum Information and Computation•Sep 1, 2008•66 citations
For every odd prime power qqq and D=q+1D=q+1D=q+1, we construct an infinite family of Ramanujan quantum expanders of degree DDD. The construction transfers Morgenstern's Ramanujan Cayley graphs on PSL⁡2(Fp)\operatorname{PSL}_2(\mathbb{F}_{p})PSL2​(Fp​) for ppp which is an even power of qqq, through the odd irreducible subrepresentation of the Weil representation of SL⁡2(Fp)\operatorname{SL}_2(\mathbb{F}_{p})SL2​(Fp​). For a quantum expander of dimension NNN, our implementation uses O(log⁡2N)O(\log^2 N)O(log2N) elementary gates, and O(log⁡N)O(\log N)O(logN) ancilla qudits, using a fixed finite gate set depending on qqq. 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 2D−1/D2\sqrt{D-1}/D2D−1​/D singular value bound exactly without any additive error.
The paper addresses explicit, efficiently implementable fixed-degree quantum expanders satisfying the Ramanujan contraction bound without additive error. For every fixed odd prime power qqq, it constructs a uniform infinite family of degree-D=q+1D=q+1D=q+1 mixed-unitary channels in dimensions Nk=(q2k−1)/2N_k=(q^{2k}-1)/2Nk​=(q2k−1)/2, with second singular value on traceless operators at most 2D−1/D2\sqrt{D-1}/D2D−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 PSL⁡2(Fq2k)\operatorname{PSL}_2(\mathbb F_{q^{2k}})PSL2​(Fq2k​) with Harrow’s spectral transfer principle. It uses the (q2k−1)/2(q^{2k}-1)/2(q2k−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⁡2N)O(\log^2 N)O(log2N) gates and depth and O(log⁡N)O(\log N)O(logN) ancilla qudits over a declared finite gate set depending on qqq; classical preprocessing takes O~(log⁡5N)\widetilde O(\log^5 N)O(log5N) 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.
We present efficient quantum circuits that implement high-dimensional unitary irreducible representations (irreps) of SU(n)SU(n)SU(n), where n≥2n \ge 2n≥2 is constant. For dimension NNN and error εεε, the number of quantum gates in our circuits is polynomial in log⁡(N)\log(N)log(N) and log⁡(1/ε)\log(1/ε)log(1/ε). Our construction relies on the Jordan-Schwinger representation, which allows us to realize irreps of SU(n)SU(n)SU(n) in the Hilbert space of nnn quantum harmonic oscillators. Together with a recent efficient quantum Hermite transform, which allows us to map the computational basis states to the eigenstates of the quantum harmonic oscillator, this allows us to implement these irreps efficiently. Our quantum circuits can be used to construct explicit Ramanujan quantum expanders, a longstanding open problem. They can also be used to fast-forward the evolution of certain quantum systems.
We construct a constant-degree and constant-gap quantum expander on nnn qubits where each unitary can be implemented by a depth-111 and 1D circuit of Pauli or CNOT gates. We provide two applications of this expander. First, we use it to construct a family of frustration-free 1D Hamiltonians whose ground states obey the entanglement-gap relation S=Θ(Δ−1/2)S = Θ(Δ^{-1/2})S=Θ(Δ−1/2); this is believed to be optimal, but achieving it had been open. Second, we use it to provide a streaming protocol that tests for closeness to a class of 1D volume-law entangled states. Moreover, we extend our quantum expander to a constant-degree and constant-gap expander on the unitary group where each unitary is a single TTT gate, a single T†T^{\dagger}T† gate, or a depth-111 Clifford circuit. This implies that a random sequence of unitaries from the expander yields a gapped walk on a dense subgroup of the unitary group. This improves upon previous work by Bourgain and Gamburd which did not control the dependence of the gap on the dimension.
We define quantum expanders in a natural way. We give two constructions of quantum expanders, both based on classical expander constructions. The first construction is algebraic, and is based on the construction of Cayley Ramanujan graphs over the group PGL(2, q) given by Lubotzky et al. (1988). The second construction is combinatorial, and is based on a quantum variant of the Zig-Zag product introduced by Reingold et al. (2000). Both constructions are of constant degree, and the second one is explicit. Using quantum expanders, we characterize the complexity of comparing and estimating quantum entropies. Specifically, we consider the following task: given two mixed states, each given by a quantum circuit generating it, decide which mixed state has more entropy. We show that this problem is QSZK-complete (where QSZK is the class of languages having a zero-knowledge quantum interactive protocol). This problem is very well motivated from a physical point of view. Our proof resembles the classical proof that the entropy difference problem is SZK-complete, but crucially depends on the use of quantum expanders.
We construct explicit two-sided lossless expanders whose binary adjacency matrices have full rank, and use them to obtain explicit asymptotically good quantum LDPC codes whose specified X- and Z-check matrices have full row rank and satisfy small-set soundness, or confinement, on a linear range. Our lossless expanders are a variant of those of Hsieh, Lubotzky, Mohanty, Reiner, and Zhang, with a free action of a finite 2-group. Under such an action, injectivity and surjectivity of the adjacency matrix are detected on a fixed-size matrix indexed by vertex orbits. Adding a sparse factor to the gadget at the middle vertices of a single type then enforces full rank, with a controlled loss in expansion. To obtain the 2-group action, we observe that reducing the generators of the Lubotzky-Phillips-Sarnak Ramanujan graphs modulo powers of 2, instead of modulo an odd prime, gives Ramanujan Cayley graphs on finite 2-groups. This construction may be of independent interest. Plugging two such expanders into the balanced product of Lin and Hsieh gives the quantum codes, since full rank of the input graphs is inherited by the check matrices. Our construction supplies the code family sought by Hong, Guo, and Lucas. Applying their analysis, within their framework and under their dynamical assumptions, gives quantum memories whose free-energy density is analytic at every positive temperature and whose guaranteed lifetime is exp(Ω(N))exp(Ω(N))exp(Ω(N)) at sufficiently low fixed positive temperature, where N is the blocklength. This improves the previously guaranteed stretched-exponential timescale.
We give a simple recipe for translating walks on Cayley graphs of a group G into a quantum operation on any irrep of G. Most properties of the classical walk carry over to the quantum operation: degree becomes the number of Kraus operators, the spectral gap becomes the gap of the quantum operation (viewed as a linear map on density matrices), and the quantum operation is efficient whenever the classical walk and the quantum Fourier transform on G are efficient. This means that using classical constant-degree constant-gap families of Cayley expander graphs on e.g. the symmetric group, we can construct efficient families of quantum expanders.