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.

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•0 citations

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•11 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•0 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•30 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. Background. Classical expanders can be defined in either combinatorial or spectral terms, while quantum expanders usually have only a spectral definition. Quantum expanders were introduced in [2] for their application to quantum spin chains and in [5] for applications to quantum statistical zero knowledge. Here we (following [2] and [4]) define a (N, D, λ) quantum expander to be a quantum operation E that • Has N-dimensional input and output. • Has D Kraus operators. • Has second-largest singular value ≤ λ. Equivalently, if E(ρ) = ρ and tr ρσ = 0 then ‖E(σ)‖2 ≤ λ‖σ‖2,

Quantum Information and Computation•Sep 1, 2008•23 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•Sep 7, 2007•0 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.
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 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 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 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. Background. Classical expanders can be defined in either combinatorial or spectral terms, while quantum expanders usually have only a spectral definition. Quantum expanders were introduced in [2] for their application to quantum spin chains and in [5] for applications to quantum statistical zero knowledge. Here we (following [2] and [4]) define a (N, D, λ) quantum expander to be a quantum operation E that • Has N-dimensional input and output. • Has D Kraus operators. • Has second-largest singular value ≤ λ. Equivalently, if E(ρ) = ρ and tr ρσ = 0 then ‖E(σ)‖2 ≤ λ‖σ‖2,
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.