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.
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.
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.
Sipser and Spielman constructed LDPC codes from either bipartite \emph{spectral} expanders or one-sided \emph{lossless} expanders. In higher dimensions, \emph{spectral} expansion similarly played a central role in the constructions of asymptotically good classical LTCs and qLDPC codes by Dinur, Evra, Livne, Lubotzky, and Mozes and by Panteleev and Kalachev. Alternatively, Lin and Hsieh constructed classical LTCs and qLDPC codes from two-dimensional \emph{lossless} cubical complexes.
In this work we develop the higher-dimensional \emph{lossless} approach. We do not construct the required high-dimensional lossless cubical complexes; rather, we investigate what their existence would imply. We associate with a high-dimensional cubical complex a \emph{level chain complex}, whose chain groups are supported on the level sets of the Boolean cube rather than on its cells. Our main technical contribution is a clean local-to-global theorem for this structure: suitable one-dimensional lossless expansion in the directional graphs implies small-set coboundary expansion of the global level complex. As a consequence, sufficiently imbalanced, two-sided lossless four-dimensional cubical complexes give rise to asymptotically good quantum locally testable codes. We expect the local-to-global principle developed here to have further applications.
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].
We introduce a high-dimensional cubical complex, for any dimensiont∈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=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,…,htas 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=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.
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,
For an abelian group H acting on the set [𝓁], an (H,𝓁)-lift of a graph G₀ is a graph obtained by replacing each vertex by 𝓁 copies, and each edge by a matching corresponding to the action of an element of H. Expanding graphs obtained via abelian lifts, form a key ingredient in the recent breakthrough constructions of quantum LDPC codes, (implicitly) in the fiber bundle codes by Hastings, Haah and O'Donnell [STOC 2021] achieving distance Ω̃(N^{3/5}), and in those by Panteleev and Kalachev [IEEE Trans. Inf. Theory 2021] of distance Ω(N/log(N)). However, both these constructions are non-explicit. In particular, the latter relies on a randomized construction of expander graphs via abelian lifts by Agarwal et al. [SIAM J. Discrete Math 2019]. In this work, we show the following explicit constructions of expanders obtained via abelian lifts. For every (transitive) abelian group H ⩽ Sym(𝓁), constant degree d ≥ 3 and ε > 0, we construct explicit d-regular expander graphs G obtained from an (H,𝓁)-lift of a (suitable) base n-vertex expander G₀ with the following parameters: ii) λ(G) ≤ 2√{d-1} + ε, for any lift size 𝓁 ≤ 2^{n^{δ}} where δ = δ(d,ε), iii) λ(G) ≤ ε ⋅ d, for any lift size 𝓁 ≤ 2^{n^{δ₀}} for a fixed δ₀ > 0, when d ≥ d₀(ε), or iv) λ(G) ≤ Õ(√d), for lift size "exactly" 𝓁 = 2^{Θ(n)}. As corollaries, we obtain explicit quantum lifted product codes of Panteleev and Kalachev of almost linear distance (and also in a wide range of parameters) and explicit classical quasi-cyclic LDPC codes with wide range of circulant sizes. Items (i) and (ii) above are obtained by extending the techniques of Mohanty, O'Donnell and Paredes [STOC 2020] for 2-lifts to much larger abelian lift sizes (as a byproduct simplifying their construction). This is done by providing a new encoding of special walks arising in the trace power method, carefully "compressing" depth-first search traversals. Result (iii) is via a simpler proof of Agarwal et al. [SIAM J. Discrete Math 2019] at the expense of polylog factors in the expansion.