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:1907.01259

New Elementary High Dimensional Edge Expanders using Strong Symmetry

Tali Kaufman, Izhar Oppenheim

Published Jul 2, 2019• 2 citations
arXivHTMLPDF

Abstract

Coboundary and cosystolic expansion are notions of expansion that generalize the Cheeger constant or edge expansion of a graph to higher dimensions. The classical Cheeger inequality implies that for graphs edge expansion is equivalent to spectral expansion. In higher dimensions this is not the case: a simplicial complex can be spectrally expanding but not high dimensional edge-expanding. The phenomenon of high dimensional edge expansion in higher dimensions is much more involved than spectral expansion, and is far from being understood. In particular, the only known bounded degree cosystolic expanders are derived from deep mathematical tools that are far from being elementary! In this work we study high dimensional complexes which are {\em strongly symmetric}. Namely, there is a group that acts transitively on top dimensional cells of the simplicial complex [e.g., for graphs it corresponds to a group that acts transitively on the edges]. Using the strong symmetry, we develop a new machinery to prove high dimensional edge expansion. We then use this machinery to construct a new {\em elementary} family of bounded degree two-dimensional cosystolic expanders. Bounded degree cosystolic expanders play a major role in a recent breakthrough construction of quantum error correcting codes that break the state of the art constructions. Thus, any advancement in their construction, and in particular, an elementary construction of such objects is of a major importance.

Related papers

New Cosystolic Expanders from Tensors Imply Explicit Quantum LDPC Codes with $Ω(\sqrt{n}\log^kn)$ Distance

Tali Kaufman, Ran J. Tessler

In this work we introduce a new notion of expansion in higher dimensions that is stronger than the well studied cosystolic expansion notion, and is termed {\em Collective-cosystolic expansion}. We show that tensoring two cosystolic expanders yields a new cosystolic expander, assuming one of the complexes in the product, is not only cosystolic expander, but rather a collective cosystolic expander. We then show that the well known bounded degree cosystolic expanders, the Ramanujan complexes are, in fact, collective cosystolic expanders. This enables us to construct new bounded degree cosystolic expanders, by tensoring of Ramanujan complexes. Using our new constructed bounded degree cosystolic expanders we construct {\em explicit} quantum LDPC codes of distance $\sqrt{n} \log^k n$ for any $k$, improving a recent result of Evra et. al. \cite{EKZ}, and setting a new record for distance of explicit quantum LDPC codes. The work of \cite{EKZ} took advantage of the high dimensional expansion notion known as cosystolic expansion, that occurs in Ramanujan complexes. Our improvement is achieved by considering tensor product of Ramanujan complexes, and using their newly derived property, the collective cosystolic expansion.

arXiv:2008.09495•Aug 21, 2020•13 citations

Symmetric Self-Dual Quantum Codes on High Dimensional Expanders

Kyle Gulshen, Tali Kaufman

We construct a family of constant-rate highly-symmetric self-dual qLDPC codes on high dimensional expanders. This is the first self-dual code constructed on high dimensional expanders and also the first such code with a rich (e.g. transitive) symmetry group, whose order exceeds the number of qubits. From this symmetry, we identify an extensive set of logical generators that act as permutations or diagonal gates, as well as a handful of other interesting gates (including the logical swap-Hadamard from self-duality). These advantages over prior constructions are in large part due to the fact that our codes are the first to be explicitly defined on expanding (non-product) simplicial complexes. Indeed, our work develops a broader framework toward utilizing high dimensional expanders to construct highly performant quantum codes with fault tolerant gates. While asymptotically good qLDPC codes have been constructed on 2D HDX built from products of graphs, these product constructions have a number of limitations, such as a lack of structure useful for fault-tolerant logic. Our framework for (fold-)transversal logical gates naturally utilizes symmetric non-product simplicial high dimensional expanders, and we demonstrate concretely through our 2D code family how this framework gives a rich set of fault-tolerant logical generators.

arXiv:2510.07864•Oct 9, 2025•10 citations

Improved Small Set Expansion in High Dimensional Expanders

Tali Kaufman, David Mass

Small set high dimensional expansion over general sheaves has recently became central to several major breakthroughs. These include the construction of classical locally testable and quantum LDPC codes with constant rate and linear distance, $Ω(n)$-levels lower bounds for the Sum-of-Squares hierarchy, and the proof of the NLTS conjecture. In this work, we improve upon the state-of-the-art results for small set expansion in simplicial complexes, for both constant and general sheaves. Compared to one line of work (e.g., [KM22, DD24]), we improve upon their result by obtaining \emph{strong expansion} for small sets. Compared to another line of work (e.g., [KKL14, EK16, KM21, FK22]), we get an \emph{exponential improvement} in the size of sets for which expansion is guaranteed. Our result is based on a novel technique that bridges these two lines of work via a ``local vs. global'' case analysis: for ``local'' sets, which are concentrated within small links, we adapt ideas from the ``fat machinery'' of [KKL14, EK16]; for ``global'' sets, which are spread across the complex, we exploit global averaging operators in the spirit of [KM22, DD24].

arXiv:2512.10385•Dec 11, 2025•0 citations

Connectivity Bounds for GHZ Graphs

L. Sunil Chandran, Rishikesh Gajjala

Greenberger-Horne-Zeilinger (GHZ) states are multipartite entangled quantum states that play a central role in quantum information theory, with applications in quantum communication, cryptography, and distributed quantum computing. A major experimental goal is to create high-dimensional GHZ states using multiple entangled parties. Krenn, Gu and Zeilinger discovered a surprising bridge between these quantum-optical experiments and graph theory: certain photonic experiments can be represented by edge-coloured, edge-weighted graphs, and the dimension of the produced GHZ state equals the number of feasible monochromatic inherited vertex colourings. This led Krenn and Gu to conjecture that every GHZ graph with more than four vertices has dimension at most $2$. A counterexample would give a new high-dimensional multipartite GHZ construction, while a proof would clarify fundamental resource limitations in quantum optics. It is known that the conjecture holds for graphs of vertex connectivity at most $2$ [MFCS 2024], and that simple GHZ graphs with $n>4$ vertices have dimension less than $n/\sqrt{2}$ [Quantum 2024]. However, no general upper bound depending only on vertex connectivity was known. We prove that every simple connected GHZ graph $G$ with at least four vertices has dimension at most $2^{κ(G)-1}+\binom{κ(G)}{2}$, where $κ(G)$ is the vertex connectivity of $G$. We also prove new bounds in terms of edge connectivity and maximum degree.

quant-pharXiv:2610.22190•Oct 16, 2026•0 citations

New cosystolic expanders from tensors imply explicit Quantum LDPC codes with Ω(√ n log k n ) distance

Tali Kaufman, Ran J. Tessler

In this work we introduce a new notion of expansion in higher dimensions that is stronger than the well studied cosystolic expansion notion, and is termed Collective-cosystolic expansion.

ACM Symposium on Theory of Computing (STOC)•Jun 15, 2021•27 citations

Expansion of High-Dimensional Cubical Complexes: with Application to Quantum Locally Testable Codes

Irit Dinur, Ting-Chun Lin, Thomas Vidick

We introduce a high-dimensional cubical complex, for any dimension$t \in \mathbb{N}$, and apply it to the design of quantum locally testable codes. Our complex is a natural generalization of the constructions by Panteleev and Kalachev and by Dinur et. al of a square complex (case$t=2$), which have been applied to the design of classical locally testable codes (LTC) and quantum low-density parity check codes (qLDPC) respectively. We turn the geometric (cubical) complex into a chain complex by relying on constant-sized local codes$h_{1}, \ldots,h_{t}$as gadgets. A recent result of Panteleev and Kalachev on existence of tuples of codes that are product expanding enables us to prove lower bounds on the cycle and co-cycle expansion of our chain complex. For$t=4$our construction gives a new family of “almost-good” quantum LTCs - with constant relative rate, inverse-polylogarithmic relative distance and soundness, and constant-size parity checks. Both the distance of the quantum code and its local testability are proven directly from the cycle and co-cycle expansion of our chain complex.

arXiv:2402.07476•Annual Symposium on Foundations of Computer Science•Oct 27, 2024•34 citations
Coboundary and cosystolic expansion are notions of expansion that generalize the Cheeger constant or edge expansion of a graph to higher dimensions. The classical Cheeger inequality implies that for graphs edge expansion is equivalent to spectral expansion. In higher dimensions this is not the case: a simplicial complex can be spectrally expanding but not high dimensional edge-expanding.
The phenomenon of high dimensional edge expansion in higher dimensions is much more involved than spectral expansion, and is far from being understood. In particular, the only known bounded degree cosystolic expanders are derived from deep mathematical tools that are far from being elementary!
In this work we study high dimensional complexes which are {\em strongly symmetric}. Namely, there is a group that acts transitively on top dimensional cells of the simplicial complex [e.g., for graphs it corresponds to a group that acts transitively on the edges]. Using the strong symmetry, we develop a new machinery to prove high dimensional edge expansion. We then use this machinery to construct a new {\em elementary} family of bounded degree two-dimensional cosystolic expanders.
Bounded degree cosystolic expanders play a major role in a recent breakthrough construction of quantum error correcting codes that break the state of the art constructions. Thus, any advancement in their construction, and in particular, an elementary construction of such objects is of a major importance.
New Cosystolic Expanders from Tensors Imply Explicit Quantum LDPC Codes with Ω(nlog⁡kn)Ω(\sqrt{n}\log^kn)Ω(n​logkn) Distance
In this work we introduce a new notion of expansion in higher dimensions that is stronger than the well studied cosystolic expansion notion, and is termed {\em Collective-cosystolic expansion}. We show that tensoring two cosystolic expanders yields a new cosystolic expander, assuming one of the complexes in the product, is not only cosystolic expander, but rather a collective cosystolic expander. We then show that the well known bounded degree cosystolic expanders, the Ramanujan complexes are, in fact, collective cosystolic expanders. This enables us to construct new bounded degree cosystolic expanders, by tensoring of Ramanujan complexes. Using our new constructed bounded degree cosystolic expanders we construct {\em explicit} quantum LDPC codes of distance nlog⁡kn\sqrt{n} \log^k nn​logkn for any kkk, improving a recent result of Evra et. al. \cite{EKZ}, and setting a new record for distance of explicit quantum LDPC codes. The work of \cite{EKZ} took advantage of the high dimensional expansion notion known as cosystolic expansion, that occurs in Ramanujan complexes. Our improvement is achieved by considering tensor product of Ramanujan complexes, and using their newly derived property, the collective cosystolic expansion.
We construct a family of constant-rate highly-symmetric self-dual qLDPC codes on high dimensional expanders. This is the first self-dual code constructed on high dimensional expanders and also the first such code with a rich (e.g. transitive) symmetry group, whose order exceeds the number of qubits. From this symmetry, we identify an extensive set of logical generators that act as permutations or diagonal gates, as well as a handful of other interesting gates (including the logical swap-Hadamard from self-duality). These advantages over prior constructions are in large part due to the fact that our codes are the first to be explicitly defined on expanding (non-product) simplicial complexes. Indeed, our work develops a broader framework toward utilizing high dimensional expanders to construct highly performant quantum codes with fault tolerant gates. While asymptotically good qLDPC codes have been constructed on 2D HDX built from products of graphs, these product constructions have a number of limitations, such as a lack of structure useful for fault-tolerant logic. Our framework for (fold-)transversal logical gates naturally utilizes symmetric non-product simplicial high dimensional expanders, and we demonstrate concretely through our 2D code family how this framework gives a rich set of fault-tolerant logical generators.
Small set high dimensional expansion over general sheaves has recently became central to several major breakthroughs. These include the construction of classical locally testable and quantum LDPC codes with constant rate and linear distance, Ω(n)Ω(n)Ω(n)-levels lower bounds for the Sum-of-Squares hierarchy, and the proof of the NLTS conjecture. In this work, we improve upon the state-of-the-art results for small set expansion in simplicial complexes, for both constant and general sheaves. Compared to one line of work (e.g., [KM22, DD24]), we improve upon their result by obtaining \emph{strong expansion} for small sets. Compared to another line of work (e.g., [KKL14, EK16, KM21, FK22]), we get an \emph{exponential improvement} in the size of sets for which expansion is guaranteed. Our result is based on a novel technique that bridges these two lines of work via a ``local vs. global'' case analysis: for ``local'' sets, which are concentrated within small links, we adapt ideas from the ``fat machinery'' of [KKL14, EK16]; for ``global'' sets, which are spread across the complex, we exploit global averaging operators in the spirit of [KM22, DD24].
Greenberger-Horne-Zeilinger (GHZ) states are multipartite entangled quantum states that play a central role in quantum information theory, with applications in quantum communication, cryptography, and distributed quantum computing. A major experimental goal is to create high-dimensional GHZ states using multiple entangled parties. Krenn, Gu and Zeilinger discovered a surprising bridge between these quantum-optical experiments and graph theory: certain photonic experiments can be represented by edge-coloured, edge-weighted graphs, and the dimension of the produced GHZ state equals the number of feasible monochromatic inherited vertex colourings. This led Krenn and Gu to conjecture that every GHZ graph with more than four vertices has dimension at most 222. A counterexample would give a new high-dimensional multipartite GHZ construction, while a proof would clarify fundamental resource limitations in quantum optics. It is known that the conjecture holds for graphs of vertex connectivity at most 222 [MFCS 2024], and that simple GHZ graphs with n>4n>4n>4 vertices have dimension less than n/2n/\sqrt{2}n/2​ [Quantum 2024]. However, no general upper bound depending only on vertex connectivity was known. We prove that every simple connected GHZ graph GGG with at least four vertices has dimension at most 2κ(G)−1+(κ(G)2)2^{κ(G)-1}+\binom{κ(G)}{2}2κ(G)−1+(2κ(G)​), where κ(G)κ(G)κ(G) is the vertex connectivity of GGG. We also prove new bounds in terms of edge connectivity and maximum degree.
We introduce a high-dimensional cubical complex, for any dimensiont∈Nt \in \mathbb{N}t∈N, and apply it to the design of quantum locally testable codes. Our complex is a natural generalization of the constructions by Panteleev and Kalachev and by Dinur et. al of a square complex (caset=2t=2t=2), which have been applied to the design of classical locally testable codes (LTC) and quantum low-density parity check codes (qLDPC) respectively. We turn the geometric (cubical) complex into a chain complex by relying on constant-sized local codesh1,…,hth_{1}, \ldots,h_{t}h1​,…,ht​as gadgets. A recent result of Panteleev and Kalachev on existence of tuples of codes that are product expanding enables us to prove lower bounds on the cycle and co-cycle expansion of our chain complex. Fort=4t=4t=4our construction gives a new family of “almost-good” quantum LTCs - with constant relative rate, inverse-polylogarithmic relative distance and soundness, and constant-size parity checks. Both the distance of the quantum code and its local testability are proven directly from the cycle and co-cycle expansion of our chain complex.