Source-linked AI summary
Ramanujan quantum expanders from the Weil representation
Siddhartha Jain
TL;DR
Efficient explicit quantum expanders with the Ramanujan bound are difficult to construct. This paper transfers Morgenstern’s classical Ramanujan Cayley graphs through the odd Weil representation to construct an infinite family of fixed-degree quantum expanders. The circuits achieve the bound exactly when implemented exactly.
Problem
The challenge is to construct quantum channels with small second singular value explicitly and with efficient circuits.
Source: p. 1Method
The construction transfers Morgenstern’s Ramanujan Cayley graphs through the odd irreducible Weil representation, implementing the representation with elementary operations.
Source: p. 2Results
The construction gives Ramanujan quantum expanders with the exact spectral bound and O(log^2 N) circuit size; its channels form an infinite family in dimensions N_k → ∞.
Source: p. 2, §E.5 · p. 18Takeaways & Limitations
The odd Weil representation provides a directly implementable irreducible representation for transferring the classical Ramanujan bound without a group Fourier transform.
Source: pp. 1–2
Abstract
from arXiv · showhide
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.
1. Can we construct Ramanujan quantum expanders for all degrees?
The construction seeks fixed-degree Ramanujan quantum expanders across a sequence of dimensions, using a classical spectral bound transferred through an irreducible projective representation. The degree is fixed by q, while the even parameter n controls the dimension.
1. Can we construct Ramanujan quantum expanders for all degrees?
A Quantum expansion and the transfer lemma
- The transfer lemma carries a classical Cayley-walk spectral bound to an irreducible projective representation, without decomposing it into irreducible blocks.The appendix fixes odd prime power q and degree D = q + 1; p = q^n for positive even n, and q fixes the degree while n controls dimension.Source: A Quantum expansion and the transfer… · p. 3
A.1 The contraction we need
The appendix defines quantum expansion as contraction on density matrices and establishes an equivalent traceless-operator norm bound. It then transfers classical Cayley-walk contraction to an irreducible projective representation by analyzing conjugation as a mean-zero function.
A.1 The contraction we need
- A degree-D mixed-unitary channel is a uniform choice among D unitaries, and it is a quantum expander when it contracts every density matrix toward the maximally mixed state.The Ramanujan condition bounds the contraction parameter by λ_D; when the second singular value is below 1, the maximally mixed state is the unique fixed density matrix.Source: §A.1 · pp. 3–4
- The channel’s contraction parameter is equivalently its Hilbert–Schmidt contraction on traceless operators, which form the orthogonal complement of the identity.The density-matrix formulation first yields the bound for Hermitian traceless operators; splitting a general traceless operator into Hermitian and skew-Hermitian parts extends it.Source: §A.1 · pp. 3–4
A.2 Cayley walks and irreducibility
- A symmetric Cayley walk contracts mean-zero functions, and a unitary or projective representation is irreducible exactly when its commutant contains only scalars.The commutant criterion also applies when projective phases are present.Source: §A.2 · pp. 4–5
A.3 The transfer lemma
- For an irreducible projective representation, conjugating a traceless operator across the group produces a mean-zero operator-valued function to which the classical walk bound applies.The function is used only in the proof; the construction does not prepare it, enumerate the group, or compute a group Fourier transform.Source: §A.3 · pp. 5–6
B The classical graph family
Morgenstern’s finite-field PSL2 family supplies symmetric generating sets of degree D = q + 1 whose Cayley walks meet the spectral bound needed for transfer. The generators and their lifts can be computed deterministically over the fixed field.
B The classical graph family
- For every even n ≥ 2, with D = q + 1 and q = ℓr an odd prime power, a symmetric generating set of size D for PSL2(Fp), where p := qn, yields a connected, non-bipartite Cayley graph.Source: B The classical graph family · p. 6
- A field model for F_p, its generators, and lifts to SL2(F_p) are computable deterministically in O(n^5) operations over fixed F_q.Source: B The classical graph family · p. 6
- The finite-quotient choice matters: one quotient gives a bipartite graph, while the other gives the required norm bound.The construction defers the field-model algorithm to Section E.5.Source: B The classical graph family · p. 6
B.1 Which finite quotient?
The construction selects the square case of Morgenstern’s finite quotient to obtain a Ramanujan Cayley graph on the PSL2 quotient. This avoids the bipartite PGL2 case, whose eigenvalue −1 violates the absolute norm bound needed for transfer.
B.1 Which finite quotient?
- For odd prime-power fields, the multiplicative group is cyclic, and the square class of a records which quotient case holds.Source: §B.1 · p. 6
- The basic generators are projective quaternion classes built from a fixed nonsquare ν and satisfy the norm-t parameter relation.The passage specifies i^2 = ν, j^2 = t − 1, ij = −ji, and ξ_c,d = 1 + cj + dij for pairs satisfying νd^2 − c^2 = 1.Source: §B.1 · p. 7
- Reducing the q + 1 projective classes modulo an even-degree irreducible polynomial produces distinct, symmetric, nonidentity generators of a finite quotient.The polynomial is required to be relatively prime to t(t − 1).Source: §B.1 · p. 7
- The square choice yields a (q + 1)-regular Ramanujan Cayley graph on the finite quotient.The cited Morgenstern eigenvalue bound is 2√q in absolute value for eigenvalues other than ±(q + 1) [Mor91, Theorems 4.10–4.11].Source: §B.1 · p. 7
- Choosing t as a square selects the PSL2 quotient; the nonsquare choice gives a bipartite PGL2 graph with a mean-zero eigenfunction of eigenvalue −1.That eigenvalue prevents the absolute norm bound required by the transfer lemma.Source: §B.1 · p. 7
B.2 Selecting the non-bipartite family
The section constructs a connected, non-bipartite Ramanujan Cayley graph on PSL2(Fp) from a field model, then connects its generators to the odd Weil representation. The field construction also supports deterministic generation of the graph data.
B.2 Selecting the non-bipartite family
- Choosing t as a square selects the PSL2 quotient; a nonsquare instead yields a bipartite graph with an eigenvalue −1 that obstructs the required absolute norm bound.The field model requires known square roots of t and the fixed nonsquare ν so the generators can be written as matrices.Source: §B.2 · p. 8
- The image of B_gn gives D distinct, nonidentity symmetric generators and a connected Ramanujan Cayley graph on PSL2(Fp).The graph is non-bipartite, allowing the normalized classical bound to establish Eq. (6).Source: §B.2 · p. 8
- The field-model and generator-matrix steps use O(n^5) arithmetic operations over the fixed field Fq.The cited construction uses O(n^3) operations after the field construction.Source: §B.2 · p. 8
C The odd Weil representation
- The Weil representation begins with quadratic phases, field scaling, and Fourier transforms on basis states labeled by Fp, then restricts to the odd subspace and proves that restriction irreducible.This supplies a directly implementable irreducible representation for the transfer argument.Source: C The odd Weil representation · p. 8
C.1 Three explicit operations
Three elementary operations realize the Weil action on the finite-field basis, and a factorization expresses each group element using at most four such operators. Restriction to the odd subspace yields an irreducible representation whose projective phases do not affect the channel.
C.1 Three explicit operations
- Quadratic phase, scaling, and Fourier transform suffice to express each group element using at most four operators, up to a scalar phase.The associated operators give a projective unitary representation of SL2(Fp).Source: §C.1 · pp. 9–10
C.2 Why we restrict to the odd subspace
- The odd subspace is invariant and has an orthonormal basis indexed by one representative from each nonzero pair {x, −x}.Odd vectors have zero coefficient at 0 and opposite coefficients at x and −x.Source: §C.2 · p. 10
C.3 Irreducibility: first diagonal, then scalar
- Quadratic phases force commuting operators to be diagonal in the odd basis, and scalings force their diagonal entries to agree, proving irreducibility.The Fourier operator is not needed for this irreducibility argument.Source: §C.3 · p. 11
C.4 Why the choice of lift does not matter
- The two lifts of each PSL2(Fp) element differ by a scalar phase on the restricted representation, so neither lift nor phase choice affects the channel.Conjugation cancels the projective phases and gives an ordinary unitary representation on operator space.Source: §C.4 · p. 11
D Proof of the Ramanujan bound
The proof combines the classical generator family with the odd Weil representation to obtain the Ramanujan quantum-expander bound. The following section separates channel-use implementation from deterministic preparation of its circuit description.
D Proof of the Ramanujan bound
- The degree-D mixed-unitary channel on H− satisfies the claimed Ramanujan bound by transferring the classical walk norm bound through the irreducible projective representation.The proof also establishes the density-matrix statement from the traceless-operator bound.Source: D Proof of the Ramanujan bound · p. 12
E Exact circuits and classical preprocessing
- The implementation discussion separates supplying a generator, assembling the channel, and deterministically computing the field model, generator matrices, and circuit coefficients.This distinguishes the cost of a channel use from the cost of preparing its circuit description.Source: E Exact circuits and classical… · p. 12
E.1 The register, gate set, and input promise
The compiler implements the channel on the odd subspace using a register of logarithmic size and a fixed finite gate library. It builds generator operations from elementary Weil operators and realizes the channel by selecting a generator and discarding its control.
E.1 The register, gate set, and input promise
- The register uses m = Θ(log N) qudits and has physical dimension p, while the channel acts on its N-dimensional odd subspace.Inputs are assumed already supported on the odd subspace; encoding and decoding costs are excluded.Source: §E.1 · pp. 12–13
- The exact gate library is fixed independently of n, p, and N, and exactness is defined relative to that library.It includes controlled gates and a fixed-size preparation for the generator control register.Source: §E.1 · pp. 12–13
E.2 Implementing the three elementary operators
- Each elementary Weil operator is implemented with O(m^2) gates and depth and O(m) ancillas.The operators are quadratic phase, field scaling, and the finite-field Fourier transform; reversible field arithmetic supplies the stated bounds.Source: §E.2 · pp. 13–14
E.3 From a generator circuit to the channel
- Each lifted generator uses at most four elementary Weil operators, and the channel is realized by choosing a generator uniformly and discarding its control.Workspace is reused between factors, and scalar phases do not affect the resulting channel.Source: §E.3 · p. 14
E.4 Approximation over another gate set
The paper analyzes replacing its exact circuit with local gates from another gate set. The resulting channel approximation has a spectral guarantee when the approximating operators are unitaries on the same odd subspace.
E.4 Approximation over another gate set
- Approximation alone does not establish a spectral bound unless the approximating Kraus operators are unitaries on the same odd subspace.The physical full-register channel is not a substitute: it fixes parity and therefore has a nonzero traceless invariant operator.Source: §E.4 · pp. 15–16
- The synthesized circuit’s channel-distance guarantee allows inputs entangled with an arbitrary reference register.Discarding the environment cannot increase the distance.Source: §E.4 · p. 15
- Local gate synthesis uses O(L log1.441(L/ε)) gates and the same registers as the exact circuit.The exact Stinespring circuit has L = O(m^2) local gates.Source: §E.4 · p. 15
- σ2(eΦ) ≤ λD + 2δ when the approximating operators are unitaries on the odd subspace and are within δ of the original generators.In particular, unitary approximations of error ε/2 give additive spectral error ε.Source: §E.4 · p. 16
E.5 Deterministic classical preprocessing
A deterministic compiler constructs the field model, lifted generators, factorization data, and gate lists. Its output supports an infinite uniform family of degree-D Ramanujan quantum expanders with logarithmic-size channel circuits.
E.5 Deterministic classical preprocessing
- The field construction finds a square α = β^2 that lies in no proper subfield containing Fq, then constructs the required square roots and field data.The deterministic search takes O(n^5) field operations; the condition that t have a known square root is the extra condition on the field model.Source: §E.5 · pp. 16–17
- The compiler uses the field data to build explicit determinant-one generator matrices and then computes their circuit coefficients.The generator lifts are distinct projective matrices, and the remaining trace, pairing, and quadratic-form data are obtained by linear algebra.Source: §E.5 · pp. 17–18
- The uniform classical compiler outputs the field polynomial, lifted generators, factorization coefficients, trace-pairing matrix, quadratic-phase coefficients, and complete gate lists in O(m^5) fixed-field operations.Its bit complexity is eO(m^5), and hence at most O(m^6).Source: §E.5 · p. 17
- The resulting channels form an infinite uniform family of degree-D Ramanujan quantum expanders in dimensions N_k → ∞, with O(log^2 N_k) gates per channel use.The gate bound applies to inputs already supported on the odd subspace.Source: §E.5 · p. 18