API

Construct a generalized Quantum Tanner code.

Returns (𝒞ˣ, 𝒞ᶻ) where 𝒞ˣ is the X-stabilizer matrix and 𝒞ᶻ is the Z-stabilizer matrix.

Arguments

• rate::Real: Rate parameter for local codes (CA has rate ρ, CB has rate 1-ρ)
• group: The group G for the left-right Cayley complex
• A: Symmetric generating set A for the left Cayley graph
• B: Symmetric generating set B for the right Cayley graph
• bipartite::Bool: Whether to use bipartite vertex partitioning (V₀, V₁)

The quantum Tanner code $\mathcal{Q} = (\mathcal{C}_0, \mathcal{C}_1)$ is defined by two classical Tanner codes, where

\[\begin{aligned} \text{Z-stabilizers:} \quad &\mathcal{C}_0 = T\!\left(\Gamma_0^{\square},\, (C_A \otimes C_B)^{\perp}\right), \\ \text{X-stabilizers:} \quad &\mathcal{C}_1 = T\!\left(\Gamma_1^{\square},\, (C_A^{\perp} \otimes C_B^{\perp})^{\perp}\right). \end{aligned}\]

Left-Right Cayley Complex

A Cayley graph $\Gamma(V,E)$ provides a graph-theoretic representation of a group $G$ via a fixed generating set $S$ that excludes the identity element. The vertex set $V$ corresponds to elements of $G$, with an edge connecting vertices $g$ and $g'$ if and only if there exists $s \in S$ such that $g \cdot s = g'$, where $\cdot$ denotes the group operation. Edges are undirected if S is symmetric, i.e., $S = S^{-1}$.

A left-right Cayley complex extends this construction by incorporating both left and right group actions. Specifically, we consider two symmetric generating sets $A$ and $B$ and define a bipartite structure on the vertices.

Consider $G$ be a finite group with symmetric generating sets $A, B \subseteq G$ such that $\langle A, B \rangle = G$ and $A = A^{-1}$, $B = B^{-1}$. The left-right Cayley complex $\Gamma(G,A,B)$ is defined as:

• Vertex set: $V = V_0 \cup V_1 = \{g_i \mid g \in G, i \in \{0,1\}\}$
• Edge sets:
  • $E_A = \{(g_i, (ag)_j) \mid a \in A, g \in G, i \neq j\}$
  • $E_B = \{(g_i, (gb)_j) \mid b \in B, g \in G, i \neq j\}$

This construction yields a 2-dimensional complex whose faces are 4-cycles of the form:

\[\begin{aligned} \{g_i, (ag)_j, (gb)_j, (agb)_i \mid i,j \in \{0,1\}, i \neq j\} \end{aligned}\]

To ensure distinct opposite vertices in each face, we require that elements of $A$ and $B$ are not conjugates:

\[\begin{aligned} \forall a \in A, b \in B, g \in G, \quad ag \neq gb \end{aligned}\]

Satisfying Total Non-Conjugacy (TNC) guarantees a proper 2D complex structure where each vertex has degree $\Delta_A + \Delta_B$, with $\Delta_A = |A|$ and $\Delta_B = |B|$. We typically take $\Delta_A = \Delta_B = \Delta$ (Radebold et al., 2025).

Tensor codes

Classical linear block codes employ redundancy to encode information and detect/correct errors. An [n,k]-code encodes k information bits into n > k bits, described by either:

• A $k \times n$ generator matrix G whose rows span the code space
• An $(n-k) \times n$ parity check matrix H representing parity constraints

These satisfy $GH^T = 0$.

For quantum Tanner codes, (Radebold et al., 2025) utilize a pair of binary linear codes $(C_A, C_B)$ where:

• $C_A$ encodes $\rho\Delta_A$ bits into $\Delta_A$ bits ($0 < \rho < 1$)
• $C_B$ encodes $(1-\rho)\Delta_B$ bits into $\Delta_B$ bits

We construct tensor codes:

\[\begin{aligned} C_0 = C_A \otimes C_B, \quad C_1 = C_A^\perp \otimes C_B^\perp \end{aligned}\]

where $\dim(C_i \otimes C_j) = \dim(C_i)\dim(C_j)$ and $d(C_i \otimes C_j) = d(C_i)d(C_j)$ for minimum distances.

Quantum Tanner codes

To construct a quantum Tanner code, we begin with a left-right Cayley complex $\Gamma(G,A,B)$ built from a finite non-abelian group $G$. Let $Q$ denote the complete set of faces of the complex, and for each vertex $v \in V$, let $Q(v)$ be the set of faces incident to $v$ (Radebold et al., 2025). We note that $Q(v)$ is uniquely determined by pairs $(a,b) \in A \times B$ for every vertex $v$. The physical qubits of the quantum code are placed on the faces of the complex, so the code length is $n = |Q|$.

We select two classical binary linear codes $C_A$ and $C_B$, where $C_A$ encodes $\rho\Delta_A$ logical bits into $\Delta_A$ bits for some $0 < \rho < 1$, and $C_B$ encodes $(1-\rho)\Delta_B$ logical bits into $\Delta_B$ bits. From these, we form the tensor codes $C_0 = C_A \otimes C_B$ and $C_1 = C_A^\perp \otimes C_B^\perp$. Since the number of columns of $C_A$ is $\Delta_A$, we can label these columns with elements of $A$. Having fixed this association, we use the notation that codewords of $C_A$ are binary vectors $\beta_A \in \mathbb{F}_2^A$. Similarly, we associate the columns of $C_B$ with elements of $B$, so that codewords of $C_B$ are binary vectors $\beta_B \subset \mathbb{F}_2^B$. This correspondence between the bits of the classical codes and group elements yields a natural labeling of the columns of the tensor codes $C_0$ and $C_1$ by pairs $(a,b) \in A \times B$ (Radebold et al., 2025).

To construct stabilizer generators on $\Gamma(G,A,B)$ using the classical codes $C_0$ and $C_1$, (Radebold et al., 2025) define a function

\[\begin{aligned} \phi_v: A \times B \to Q(v) \end{aligned}\]

for each vertex v by $\phi_v(a,b) = {v, av, vb, avb}$, which maps a pair of group generators to the unique face in $Q(v)$ that it defines. One can verify that $\phi_v$ is bijective (Radebold et al., 2025). For each basis element $\beta$ of $C_0$, we associate a set of pairs of group generators

\[\begin{aligned} Z(\beta) = \{(a,b) \mid \beta_{(a,b)} = 1\} \end{aligned}\]

corresponding to the nonzero entries of $\beta$. Each Z-stabilizer generator of the quantum Tanner code is then specified by a choice of vertex $v \in V_0$ and classical codeword $\beta$ such that the $Z$-stabilizer generator has support equal to the set of faces $\phi_v(Z(\beta))$. We can characterize this stabilizer generator by a binary vector $x \in \mathbb{F}2^Q$, where the |Q| qubits are labelled by faces of the complex. For a given Z-stabilizer generator, the restriction $x|{Q(v)}$ equals a basis element $\beta$ of $C_0$ (based on a fixed ordering of the faces), and is zero elsewhere. This yields $\dim(C_0)|V_0|$ Z-type stabilizer generators, which correspond to codewords of C_0 placed locally at each vertex (Radebold et al., 2025).

(Radebold et al., 2025) repeat the same process for vertices $v \in V_1$ and basis elements of $C_1$ to produce $\dim(C_1)|V_1|$ X-type stabilizers at each vertex of that partition.

Stabilizer Matrices

For each vertex $v \in V_0$ and basis element $\beta \in C_0$, we define the support set (Radebold et al., 2025):

\[\begin{aligned} Z(\beta) = \{(a,b) \in A \times B \mid \beta_{(a,b)} = 1\}. \end{aligned}\]

The corresponding $Z$-stabilizer generator has support $\varphi_v(Z(\beta))$, where $\varphi_v \colon A \times B \to Q(v)$ is the bijective mapping from generator pairs to incident faces (Radebold et al., 2025).

Similarly, for each vertex $v \in V_1$ and basis element $\beta \in C_1$, we define $X$-stabilizer generators with support $\varphi_v(Z(\beta))$ (Radebold et al., 2025).

This yields $\dim(C_0) \times |V_0|$ $Z$-type stabilizer generators and $\dim(C_1) \times |V_1|$ $X$-type stabilizer generators.

The resulting quantum code exhibits the low-density parity-check (LDPC) property because each stabilizer generator acts on at most $\Delta^2$ qubits (where $\Delta = |A| = |B|$) and each qubit is involved in at most $4\rho(1-\rho)\Delta^2$ stabilizer generators. These bounds remain constant as $|G| \to \infty$, ensuring the LDPC property (Radebold et al., 2025).

CSS Commutativity

All stabilizer generators of opposite type commute pairwise. The CSS orthogonality constraint $C_X \subset C_Z^{\perp}$ is fulfilled because when a $C_0$-generator (from $V_0$) and a $C_1$-generator (from $V_1$) have intersecting supports, their anchor vertices must be neighbors in the bipartite graph. If connected by a $B$-edge, their local views share an $A$-set where $C_A \perp C_A^{\perp}$ ensures orthogonality. Note that the $A$-edge case is analogous, with $C_B \perp C_B^{\perp}$.

Quantum Tanner code parameters

For component codes $C_A[\Delta, \rho\Delta, \delta\Delta]$ and $C_B[\Delta, (1-\rho)\Delta, \delta\Delta]$, the number of physical qubits is $n = \Delta^2 |G| / 2$, the number of $X$-stabilizers is $\dim(C_1) \times |V_1| \approx 2\rho(1-\rho)\Delta^2 |G|$, and the number of $Z$-stabilizers is $\dim(C_0) \times |V_0| \approx 2\rho(1-\rho)\Delta^2 |G|$. The resulting quantum code rate is at least $(2\rho - 1)^2$. For other properties, see (Radebold et al., 2025).

Dihedral Ramanujan Graphs

The quantum Tanner code construction of (Radebold et al., 2025) utilizes a specific class of Frobenius groups.

A finite group G is a Frobenius group if it can be expressed as a semidirect product

\[\begin{aligned} G = N \rtimes H \end{aligned}\]

where N (the Frobenius kernel) and H (the Frobenius complement) satisfy the condition that the ratio $r = \frac{|N|-1}{|H|}$ is a positive integer. A canonical example, and the one primarily utilized in ((Radebold et al., 2025), (Hirano et al., 2016)), is the dihedral group of order 2p for an odd prime p:

\[\begin{aligned} D_{2p} = \langle x, y \mid x^p = y^2 = 1, yxy^{-1} = x^{-1} \rangle. \end{aligned}\]

For $D_{2p}$, the kernel is the cyclic subgroup $N = \langle x \rangle \cong \mathbb{Z}_p$ and the complement is $H = \langle y \rangle \cong \mathbb{Z}_2$, yielding $r = \frac{p-1}{2}$.

(Hirano et al., 2016) provides a method to construct Ramanujan graphs from these groups. A Cayley graph $\text{Cay}(G, S)$ is Ramanujan if its non-trivial eigenvalues $\lambda$ satisfy $|\lambda| \leq 2\sqrt{|S|-1}$. For a Frobenius group $G = N \rtimes H$ with $r \geq 4$, the Theorem 3.3 of (Hirano et al., 2016) states that the maximum "covalency" $\hat{l}_{G, \mathcal{S}_0}$ for which all corresponding normal Cayley graphs remain Ramanujan is given by the trivial bound:

\[\begin{aligned} \hat{l}_{G, \mathcal{S}_0} = l_0 = \max \{ l \in \mathcal{L} \mid l \le 2(\sqrt{|G|}-1) \}. \end{aligned}\]

For the dihedral group $D_{2p}$ with $p \geq 11$, this bound specializes to Corollary 3.4 of (Hirano et al., 2016):

\[\begin{aligned} \hat{l} = 2 \left\lfloor \sqrt{2p} - \frac{1}{2} \right\rfloor - 1. \end{aligned}\]

Thus, (Radebold et al., 2025) uses such dihedral groups $\D_{2p}$ and their symmetric generating sets to construct the underlying expander graphs for the quantum Tanner code.

Examples

Here is new [[36, 8, (3,3)]] code found via random search:

julia> F = free_group([:s, :r]);

julia> s, r = gens(F);

julia> rels = [s^2, r^4, s*r*s*r];

julia> G, epimorphism = quo(F, rels);

julia> s, r = epimorphism(s), epimorphism(r);

julia> A = [s, r, r^3];

julia> B = [s*r, s*r^3, r^2];

julia> H_A = [1  0  1; 0  1  1];

julia> G_A = [1  1  1];

julia> H_B = [1  1  1];

julia> G_B = [1  1  0; 1  0  1];

julia> classical_code_pair = ((H_A, G_A), (H_B, G_B));

julia> c = QuantumTannerCode(G, A, B, classical_code_pair);

julia> import JuMP; import HiGHS;

julia> code_n(c), code_k(c), distance(c, DistanceMIPAlgorithm(solver=HiGHS, logical_operator_type=:Z)), distance(c, DistanceMIPAlgorithm(solver=HiGHS, logical_operator_type=:X))
(36, 8, 3, 3)

Here is an example of a new [[360, 8, 10]] quantum Tanner code using Morgenstern generating sets

julia> using QuantumExpanders; using Oscar; using QuantumClifford.ECC;

julia> l, i = 1, 2;

julia> q = 2^l;

julia> Δ = q+1;

julia> SL₂, B = morgenstern_generators(l, i);
[ Info: |SL₂(𝔽(4))| = 60

julia> A = alternative_morgenstern_generators(B, FirstOnly());

julia> H_A = [1 1 1 0];

julia> G_A = [1 1 0 0;
              1 0 1 0;
              0 0 0 1];

julia> H_B = [0 1 1;
              1 1 0];

julia> G_B = [1 1 1];

julia> classical_code_pair = ((H_A, G_A), (H_B, G_B));

julia> c = QuantumTannerCode(SL₂, A, B, classical_code_pair);

julia> import HiGHS; import JuMP;

julia> code_n(c), code_k(c), distance(c, DistanceMIPAlgorithm(solver=HiGHS, logical_operator_type=:Z)), distance(c, DistanceMIPAlgorithm(solver=HiGHS, logical_operator_type=:X))
(360, 8, 10, 3)

Fields

• group::Group: The order of the underlying finite group

• A::Vector{<:GroupElem}: Symmetric generating set (closed under inverses) not containing the identity

• B::Vector{<:GroupElem}: Symmetric generating set (closed under inverses) not containing the identity

• classical_codes::Tuple{Tuple{Matrix{Int64}, Matrix{Int64}}, Tuple{Matrix{Int64}, Matrix{Int64}}}: Tuple $((H_A, G_A), (H_B, G_B))$ where $(H_A, H_B)$ and $(G_A, G_B)$ are parity-check and generator matrices, respectively.

Constructs the Lubotzky–Phillips–Sarnak Ramanujan graph $X^(p,q)$ as described in (Lubotzky et al., 1988).

Returns the $(p+1)$-regular LPS Ramanujan graph $X^{p,q}$.

LPS Ramanujan graph $X^(p,q)$

Let $p$ and $q$ be distinct primes congruent to $1 \pmod{4}$. The LPS Ramanujan graphs $X^{p,q}$ are $p+1$-regular Cayley graphs of the projective linear group $\mathrm{PSL}(2,\mathbb{Z}/q\mathbb{Z})$ when the Legendre symbol satisfies $\left( \tfrac{p}{q} \right) = 1$, and of $\mathrm{PGL}(2,\mathbb{Z}/q\mathbb{Z})$ when $\left( \tfrac{p}{q} \right) = -1$.

The construction of these graphs relies on representing the prime p as a sum of four squares. Specifically, the p+1 generators for the Cayley graph are derived from the distinct integer solutions to

\[\begin{aligned} p = a_0^2 + a_1^2 + a_2^2 + a_3^2 \end{aligned}\]

where $a_0 > 0$ is odd and $a_1, a_2, a_3$ are even. That there are exactly p+1 such representations is a consequence of Jacobi’s theorem on the number of representations $r_4(n)$:

\[\begin{aligned} r_4(n) = 8 \sum_{\substack{d \mid n \\ 4 \nmid d}} d \end{aligned}\]

To generalize this construction, (Lubotzky et al., 1988) used representations by certain quaternary quadratic forms ((Dickson, 1927), (Sarnak, 1990)). Define the form

\[\begin{aligned} \mathcal{Q}_q(x_1, x_2, x_3, x_4) = x_1^2 + 4q^2x_2^2 + 4q^2x_3^2 + 4q^2x_4^2, \end{aligned}\]

and let $r_Q(n)$ denote the number of integer solutions $v \in \mathbb{Z}^4$ to $\mathcal{Q}_q(v) = n$. Unlike the explicit formula for $r_4(n)$, no simple closed form exists for $r_Q(n)$. However, the Ramanujan conjecture (Ramanujan, 1916) proved in this context by Eichler (Eichler, 1954) and Igusa (Igusa, 1956) provides a asymptotic approximation which establishes LPS graphs $X^{p,q}$ as Ramanujan graphs. For n = p^k with $vk \ge 0$v, we have

\[\begin{aligned} r_Q(p^k) = C(p^k) + O_\varepsilon\!\left( p^{k(1/2 + \varepsilon)} \right) \quad \text{as } k \to \infty, \quad \forall \varepsilon > 0, \end{aligned}\]

where the main term C(p^k) is given by

\[\begin{aligned} C(p^k) = \begin{cases} c_1 \displaystyle\sum_{d \mid p^k} d & ext{if } \left( \tfrac{p}{q} \right) = 1 \\ c_2 \displaystyle\sum_{d \mid p^k} d & ext{if } \left( \tfrac{p}{q} \right) = -1 \text{ and } k ext{ is even} \\ 0 & \text{if } \left( \tfrac{p}{q} \right) = -1 \text{ and } k \text{ is odd} \end{cases} \end{aligned}\]

The constants $c_1$ and $c_2$ are determined in Section 4 of (Lubotzky et al., 1988).

Here, $d\mu_{p+1}$ denotes the limiting spectral distribution given in Proposition 4.3 of (Lubotzky et al., 1988) where $k = p + 1$ is the degree of the graph.

\[\begin{aligned} d\mu_{p+1}(t) = \begin{cases} \dfrac{\sqrt{p - t^2/4}}{\pi(p+1)(1-(t/(p+1))^2)} \, dt & \text{if } |t| \leq 2\sqrt{p} \\ 0 & \text{otherwise} \end{cases} \end{aligned}\]

Cayley graphs of Free Groups via Geometric Group Theory

As detailed in (Lubotzky et al., 1988), for a prime $p \equiv 1 \pmod{4}$, there exists a set S of p + 1 integral quaternions of norm p, unique up to units and satisfying $\alpha \equiv 1 \pmod{2}$. (Lubotzky et al., 1988) establishes that every quaternion $\alpha \in H(\mathbb{Z})$ with $N(\alpha) = p^k$ can be expressed uniquely in the form $\alpha = \varepsilon p^r R_m(\alpha_1, \ldots, \bar{lpha}_s)$ where $\varepsilon$ is a unit, $2r + m = k$, and $R_m$ is a reduced word in the elements of $S$ and their conjugates, where "reduced" means no generator is adjacent to its inverse (see Definition 2.3.4 of (Löh, 2017)). This unique factorization property shows that the multiplicative group $A(2)$ formed by these quaternion classes (modulo the identification $\pm p^{v_1}\alpha \sim p^{v_2}\beta$ is freely generated by the classes $[\alpha_1], [\alpha_2], \ldots, [\alpha_s]$ (see Proposition 2.3.5 of (Löh, 2017)), with every element represented by exactly one reduced word (see Corollary 2.3.6 of (Löh, 2017)). Consequently, the Cayley graph $\text{Cay}(A(2), S)$ is an infinite (p + 1)-regular tree (see Theorem 2.3.1 of (Löh, 2017)). The finite Ramanujan graphs $X^{p,q}$ are then constructed as explicit quotients of this tree by taking the congruence subgroup $A(2q)$, defined as the kernel of reduction modulo $2q$. The quotient $A(2)/A(2q)$ is shown to be isomorphic to either $\PGL(2, \mathbb{Z}/q\mathbb{Z})$ or $\PSL(2, \mathbb{Z}/q\mathbb{Z})$, and the resulting Cayley graph is the LPS graph $X^{p,q}$.

Arguments

• p: A prime number congruent to $1 \pmod{4}$.
• q: A prime number, distinct from p, also congruent to $1 \pmod{4}$.

Create alternative Morgenstern generators using all pairwise products (i≠j).

Morgenstern showed that for every prime q, there exist infinitely many groups $\G_i = \mathrm{PGL}_2(q^i)$ or $G_i = \mathrm{PSL}_2(q^i)$, each with a symmetric generating set $B_i$ of size $q+1$, such that the Cayley graphs $\mathrm{Cay}(G_i, B_i)$ are Ramanujan graphs ((Morgenstern, 1994), (Dinur et al., 2022)). That is, the second largest eigenvalue satisfies $\lambda(\mathrm{Cay}(G_i, B_i)) \leq 2\sqrt{q}/(q+1)$.

The construction uses an explicit arithmetic lattice $\Gamma$ in $\mathrm{PSL}_2(\mathbb{F}_q)$ that is isomorphic to the free product of $q+1$ copies of the cyclic group of order 2, where $B = {b_0, b_1, \ldots, b_q}$ consists of elements of order $2$ (Dinur et al., 2022). The Cayley graphs are obtained as images $B_i = \phi(B)$ under epimorphisms $\phi: \Gamma \to G_i$.

Dinur provided an alternative construction of symmetric generating sets $A_i$ for $G_i = \mathrm{PGL}_2(q^i)$ such that the pairs $(A_i, B_i)$ satisfy the total non-congruency condition (Dinur et al., 2022) for Morgenstern construction of Ramanujan graphs using even prime q.

Generator Constructions

All Pairs Construction

The subgroup $\Lambda$ is generated by the symmetric set

\[\begin{aligned} A = {b_t b_s \mid b_t, b_s \in B, t \neq s} \end{aligned}\]

which has size $k_1 = q^2 + q$. For a finite group $G$ with symmetric generating set $B$ where each element has order 2, the all pairs construction generates the alternative generating set:

\[\begin{aligned} A = {b_i b_j \mid b_i, b_j \in B, i \neq j} \end{aligned}\]

This construction yields Cayley graphs $\text{Cay}(G_i, A_i)$ with spectral expansion satisfying:

\[\begin{aligned} \lambda(\text{Cay}(G_i, A_i)) < \frac{3q-1}{q^2+q} < \frac{3\sqrt{k_1-1}}{k_1} \end{aligned}\]

Create alternative Morgenstern generators using products with first element only.

Generator Constructions

First Element Construction

A more efficient construction recognizes that $\Lambda$ is actually a free group on the q generators $\b_0 b_j : j = 1, \ldots, q$. Since $(b_0 b_j)^{-1} = b_j b_0$, we obtain the symmetric generating set:

\[\begin{aligned} A' = {b_0 b_j, b_j b_0 \mid j = 1, \ldots, q} \end{aligned}\]

This construction produces Cayley graphs with improved spectral properties:

\[\begin{aligned} \lambda(\text{Cay}(G_i, A'_i)) < \frac{3\sqrt{2q-1}}{2q} \end{aligned}\]

The default constructor uses the more efficient FirstOnly algorithm, providing better spectral expansion with smaller generating sets of size $k_1 = 2q$ compared to $k_1 = q^2 + q$ for the all pairs construction.

Construct the Cayley complex square graphs 𝒢₀□ and 𝒢₁□ as presented in (Gu et al., Jun 2022).

It is more convenient to count the edges as directional (i.e. double counting them), as that makes it much easier to track how edge indices correspond to indices in A×B.

Returns (𝒢₀□, 𝒢₁□, edge₀_q_idx, edge₁_q_idx, edge₀_ab_idx, edge₁_ab_idx) where:

• 𝒢₀□: Square graph on $V_0 = G × {0}$ with edges between vertices connected via squares
• 𝒢₁□: Square graph on $V_1 = G × {1}$ with edges between vertices connected via squares
• `edge₀_q_idx: Dictionary mapping edges (src,dst,multiplicity) in 𝒢₀□ to their corresponding square index in Q
• edge₁_q_idx: Dictionary mapping edges (src,dst,multiplicity) in 𝒢₁□ to their corresponding square index in Q
• edge₀_ab_idx: Dictionary mapping edges (src,dst,multiplicity) in 𝒢₀□ to their corresponding position in A×B grid for 𝒢₀□
• edge₁_ab_idx: Dictionary mapping edges (src,dst,multiplicity) in 𝒢₁□ to their corresponding position in A×B grid for 𝒢₁□

Bipartite Left-Right Cayley Complex

The bipartite left-right Cayley complex a 2-dimensional complex from a finite group G and symmetric generating sets $A = A^-1$, $B = B^-1$.

The vertex set V is bipartite and partitioned as V = V₀ ∪ V₁, with $V_0 = G × {0}$ and $V_1 = G × {1}$ representing two copies of the group G. The edge sets consist of A-edges $E_A$ and B-edges $E_B$, where $E_A$ contains pairs $\{(g,0), (ag,1)\}$ for all g ∈ G and a ∈ A, and $E_B$ contains pairs $\{(g,0), (gb,1)\}$ for all g ∈ G and b ∈ B. The graph $G_A = (V, E_A)$ is the double cover of the left Cayley graph Cay(G, A), while $G_B = (V, E_B)$ is the double cover of the right Cayley graph Cay(G, B) (Leverrier and Zémor, Apr 2022).

The set Q of squares is defined as the collection of 4-subsets of vertices of the form

\[\begin{aligned} {(g,0), (ag,1), (gb,1), (agb,0)} \end{aligned}\]

for all g ∈ G, a ∈ A, and b ∈ B. Each square contains two vertices from V₀ and two from V₁, forming the two-dimensional cells of the complex.

The Total No-Conjugacy (TNC) condition ag ≠ gb for all a ∈ A, b ∈ B, g ∈ G ensures that every square consists of four distinct vertices and that the local view Q(v) of squares incident to any vertex v naturally identifies with the product set A × B (Leverrier and Zémor, Apr 2022).

By restricting to vertices in V₀, the set of squares Q defines a graph 𝒢₀□ = (V₀, Q) where edges connect pairs (g,0) and (agb,0) that appear as opposite corners of squares. Similarly, restricting to V₁ defines the graph 𝒢₁□ = (V₁, Q) where edges connect pairs (ag,1) and (gb,1). Both 𝒢₀□ and 𝒢₁□ are Δ²-regular multigraphs on |G| vertices, with the total number of squares given by |Q| = Δ²|G|/2.

Construct the Cayley complex square graphs 𝒢₀□ and 𝒢₁□ using the quadripartite construction as presented in (Leverrier and Zémor, Apr 2022).

Returns (𝒢₀□, 𝒢₁□, edge₀_q_idx, edge₁_q_idx, edge₀_ab_idx, edge₁_ab_idx) where:

• 𝒢₀□: Square graph on `V₀₀ ∪ V₁₁ with edges
• 𝒢₁□: Square graph on `V₀₁ ∪ V₁₀ with edges
• edge₀_q_idx: Dictionary mapping (src,dst,multiplicity) to their corresponding square index in 𝒢₀□
• edge₁_q_idx: Dictionary mapping (src,dst,multiplicity) to their corresponding square index in 𝒢₁□
• edge₀_ab_idx: Dictionary mapping (src,dst,multiplicity) to their corresponding position in A×B grid for 𝒢₀□
• edge₁_ab_idx: Dictionary mapping (src,dst,multiplicity) to their corresponding position in A×B grid for 𝒢₁□

It is more convenient to count the edges as directional (i.e. double counting them), as that makes it much easier to track how edge indices correspond to indices in A×B.

Quadripartite Left-Right Cayley Complex

The quadripartite left-right Cayley complex is built from a finite group G with two generating sets A and B. The vertex set V is partitioned into four disjoint copies of the group:

\[\begin{aligned} V = V_{00} \cup V_{01} \cup V_{10} \cup V_{11} \end{aligned}\]

where $V_{ij} = G \times \{i,j\} for i,j \in \{0,1\}$

The squares Q of the complex are defined as the set of 4-tuples

\[\begin{aligned} {(g,00), (ag,01), (gb,10), (agb,11) : g \in G, a \in A, b \in B\} \end{aligned}\]

with total cardinality $|Q| = |G||A||B|$.

Two square graphs are derived from this complex structure. The graph

\[\begin{aligned} \mathcal{G}_0^\square = (V_{00} \cup V_{11}, Q) \end{aligned}\]

connects vertices (g,00) to (agb,11) for each square, while

\[\begin{aligned} \mathcal{G}_1^\square = (V_{01} \cup V_{10}, Q) \end{aligned}\]

connects vertices (gb,10) to (ag,01). Both graphs are ($|A| \times |B|$)-regular directed multigraphs, with each vertex having exactly $\Delta_A \Delta_B$ incident edges, where $\Delta_A = |A|$ and $\Delta_B = |B|$. The local view Q(v) at any vertex v identifies with $A \times B$, where the squares incident to v are in bijection with pairs $(a,b) \in A \times B$ (Leverrier and Zémor, Apr 2022).

Construct the Cayleyˡᵉᶠᵗ graph for a given group and set of generators.

Construct the Cayleyʳⁱᵍʰᵗ graph for a given group and set of generators.

Convert redundant face list to matrix format for stabilizer matrix generation.

Compute the generator matrix of the dual code for classical component codes in quantum Tanner construction (Leverrier and Zémor, Apr 2022). We work with pairs of classical codes and their duals to construct quantum CSS codes. The dual code relationship is crucial because quantum Tanner codes are defined through the pair $(\mathcal{C}_0, \mathcal{C}_1)$ where

\[\begin{aligned} \mathcal{C}_0 = T(\mathcal{G}_0^{\square}, C_0^{\perp}), \quad C_0 = C_A \otimes C_B \end{aligned}\]

and

\[\begin{aligned} \mathcal{C}_1 = T(\mathcal{G}_1^{\square}, C_1^{\perp}), \quad C_1 = C_A^{\perp} \otimes C_B^{\perp} \end{aligned}\]

Theorem 18 of (Leverrier and Zémor, Apr 2022) requires that both the component codes and their duals have sufficiently large minimum distances, which is achieved with high probability when the codes are randomly generated as specified.

Example

julia> using QuantumExpanders: dual_code # hide

julia> H = uniformly_random_code_checkmatrix(0.5, 10);

julia> G = dual_code(H)
[0   1   1   1   1   1   0   0   0   0]
[0   1   1   0   1   0   1   0   0   0]
[0   0   1   1   1   0   0   1   0   0]
[1   0   1   1   0   0   0   0   1   0]
[0   0   0   0   1   0   0   0   0   1]

julia> G * transpose(H) == zero_matrix(base_ring(G), size(G, 1), size(H, 1))
true

Arguments

• H::zzModMatrix: Parity check matrix of a classical linear code, typically one of the component codes $C_A$ or $C_B$.

Enumerate all square incidences in the Left-Right Cayley Complex following introduction by (Dinur et al., 2022).

The left-right Cayley complex $X$ is an incidence structure between:

• Vertices $V = V_0 \cup V_1$ where $V_0 = G \times \{0\}$, $V_1 = G \times \{1\}$
• $A$-edges $E_A = \{(g,0), (ag,1)\}$ for $g \in G$, $a \in A$ (double cover of the left Cayley graph $\mathrm{Cay}(G,A)$)
• $B$-edges $E_B = \{(g,0), (gb,1)\}$ for $g \in G$, $b \in B$ (double cover of the right Cayley graph $\mathrm{Cay}(G,B)$)
• Squares $Q = \{(g,0), (ag,1), (gb,1), (agb,0)\}$ for $g \in G$, $a \in A$, $b \in B$

Each square $q \in Q$ corresponds to one physical qubit in the quantum Tanner code. Each square appears in two natural local views (Radebold et al., 2025):

• From $V_0$ vertices: defines the graph $\Gamma_0^{\square} = (V_0, Q)$ used for $Z$-stabilizers
• From $V_1$ vertices: defines the graph $\Gamma_1^{\square} = (V_1, Q)$ used for $X$-stabilizers

We explicitly enumerate both incidences of each square to facilitate the Tanner code construction.

Construction Framework

For each vertex $v \in V$, the set of incident faces $Q(v)$ is uniquely determined by pairs $(a,b) \in A \times B$.

The bijective mapping $\varphi_v \colon A \times B \to Q(v)$ is defined as (Radebold et al., 2025):

\[\varphi_v(a,b) = \{v,\, av,\, vb,\, avb\}\]

This establishes a natural labeling of qubits (faces) by generator pairs, allowing classical tensor codes to be applied locally at each vertex (Radebold et al., 2025).

Arguments

• G: A finite group
• A: Symmetric generating set (closed under inverses) not containing the identity
• B: Symmetric generating set (closed under inverses) not containing the identity

Generate a pair of symmetric generating sets for group G of sizes δA and δB.

Returns a pair of symmetric generating sets (A, B) that generate G and satisfy the non-conjugacy condition.

Both A and B are symmetric, A and B are disjoint, and the pair (A, B) satisfies the total non-conjugacy condition: for all a ∈ A, b ∈ B, g ∈ G, a ≠ gbg⁻¹.

julia> using QuantumExpanders; using Oscar; using Random;

julia> G = dihedral_group(8);

julia> rng = MersenneTwister(23);

julia> A, B = find_random_generating_sets(G, 3, 3; rng=deepcopy(rng))
2-element Vector{Vector{PcGroupElem}}:
 [f1*f2, f1*f2*f3, f1*f3]
 [f3, f2, f2*f3]

julia> A, B = find_random_generating_sets(G, 3; rng=deepcopy(rng))
2-element Vector{Vector{PcGroupElem}}:
 [f1*f2, f1*f2*f3, f1*f3]
 [f3, f2, f2*f3]

Here is a new [[36, 1, 3]] quantum Tanner code generated using these symmetric generating sets, A and B, as follows:

julia> H_A = [1 0 1; 1 1 0];

julia> G_A = [1 1 1];

julia> H_B = [1 1 1; 1 1 0];

julia> G_B = [1 1 0];

julia> classical_code_pair = ((H_A, G_A), (H_B, G_B));

julia> c = QuantumTannerCode(G, A, B, classical_code_pair);

julia> code_n(c), code_k(c)
(36, 1)

julia> import JuMP; import HiGHS;

julia> distance(c, DistanceMIPAlgorithm(solver=HiGHS))
3

Arguments

• G: A finite group
• δ_A: The size of the first symmetric generating set
• δ_B: The size of the second symmetric generating set (defaults to δ_A)

Generate a good Quantum Tanner code meeting minimum weight requirements.

Arguments

• ρ: Rate parameter for local codes
• group, A, B: Expander graph components
• minweight_x: Minimum weight for X-stabilizers
• minweight_z: Minimum weight for Z-stabilizers
• max_iterations: Maximum attempts to find a good code

Check that two binary parity check matrices X and Z result in a good CSS code (i.e., commutation constraints are fulfilled)

Check whether the symmetric generating sets A and B satisfy the Total Non-Conjugacy (TNC) condition for the given group G, as defined in (Dinur et al., 2022).

Given a finite group with symmetric generating sets A and B (i.e., $A = A^-1$ and $B = B^-1$), the TNC condition requires:

\[\begin{aligned} \forall a \in A, \forall b \in B, \forall g \in G, \quad g^{-1} a g \neq b \end{aligned}\]

Arguments

• group: The finite group G
• genA: Symmetric generating set A for G ($A = A^-1$)
• genB: Symmetric generating set B for G ($B = B^-1$)

Check the Ramanujan property:

• For a (p+1)-regular graph, the trivial eigenvalue is p+1.
• All other eigenvalues should have absolute value ≤ 2√p.

Arguments

• g::SimpleGraph: A connected (p+1)-regular graph to test for the Ramanujan property
• p::Int: The prime parameter used to compute the eigenvalue bound $2\sqrt{p}$

Check the generating set is symmetric.

Computes the Legendre symbol $\frac{a}{p}$ for an odd prime p.

Returns an integer in ${-1, 0, 1}$ where $1$ indicates a is a quadratic residue modulo p with $a \not\equiv 0 \pmod{p}$, -1 indicates a is a quadratic non-residue modulo p, and 0 indicates $a \equiv 0 \pmod{p}$ (i.e., p divides a).

julia> using QuantumExpanders;

julia> legendre_symbol(2, 7)
1

julia> legendre_symbol(3, 7)
-1

julia> legendre_symbol(14, 7)
0

The Legendre symbol determines whether $a$ is a quadratic residue modulo $p$, and specifically controls which group $\mathrm{PGL}$ or $\mathrm{PSL}$ is used in the LPS construction of the Ramanujan graph (Lubotzky et al., 1988).

• When $\frac{p}{q} = -1$, the graph $X^{p,q}$ is constructed as a Cayley graph of $\mathrm{PGL}(2, \mathbb{Z}/q\mathbb{Z})$

and is bipartite of order $q(q^2-1)$.

• When $\frac{p}{q} = 1$, the graph is constructed as a Cayley graph of $\mathrm{PSL}(2, \mathbb{Z}/q\mathbb{Z})$, is

non-bipartite, and has order $q(q^2-1)/2$.

Arguments

• a::Int: The integer for which to compute the Legendre symbol.
• p::Int: An odd prime number

Constructs the generator matrices from the filtered four-square solutions. For each solution (a, b, c, d), creates a matrix:

\[\begin{aligned} \begin{bmatrix} a + i b & c + i d \\ -c + i d & a - i b \end{bmatrix} \end{aligned}\]

where $i$ satisfies $i^2 \equiv -1 \pmod{q}$. These matrices have determinant $a^2 + b^2 + c^2 + d^2 = p$ and will serve as the $p+1$ generators for the Cayley graph.

Arguments

• solutions::AbstractVector: The filtered set of p+1 integer tuples (a, b, c, d) satisfying $p = a^2 + b^2 + c^2 + d^2$ with a > 0 odd and b, c, d even
• F::FqField: The finite field $\mathbb{F}_q$ over which the matrices are constructed
• p::Int: The prime number used in the four-square decomposition

Construct the LPS Ramanujan graph for the case where the Legendre symbol $\left(\frac{p}{q}\right) = -1$ as described in (Lubotzky et al., 1988).

Returns a Cayley graph of the projective general linear group $\mathrm{PGL}(2, \mathbb{F}_q)$ that is (p+1)-regular and has order $q(q^2 - 1)$. The graph is bipartite.

Arguments

• ::Val{-1}: Dispatch parameter indicating $\left(\frac{p}{q}\right) = -1$
• p::Int: Prime number congruent to $1 \pmod{4}$ used in the four-square decomposition
• q::Int: Prime number congruent to $1 \pmod{4}$ defining the finite field $\mathbb{F}_q$

Construct the LPS Ramanujan graph for the case where the Legendre symbol $\left(\frac{p}{q}\right) = 1$ as described in (Lubotzky et al., 1988).

Returns a Cayley graph of the projective special linear group $\mathrm{PSL}(2, \mathbb{F}_q)$ that is (p+1)-regular and has order $q(q^2 - 1)/2$. The graph is non-bipartite.

Arguments

• ::Val{1}: Dispatch parameter indicating $\left(\frac{p}{q}\right) = 1$
• p::Int: Prime number congruent to $1 \pmod{4}$ used in the four-square decomposition
• q::Int: Prime number congruent to $1 \pmod{4}$ defining the finite field $\mathbb{F}_q$

Give all Morgenstern generators over $PSL_2(q^i)$, where i is even, $q=2^l$, and p is prime.

The theorem 5.13 of (Morgenstern, 1994) provides a method to construct families of (q+1)-regular Ramanujan graphs for even prime powers q. This explicit construction produces Cayley graphs of the projective special linear group $\mathrm{PSL}_2(\mathbb{F}_{q^d})$ with respect to a specific set of $q+1$ generators. These generators are $2 \times 2$ matrices of the form:

\[\begin{aligned} \begin{pmatrix} 1 & \gamma_k + \delta_k\mathbb{i} \\ (\gamma_k + \delta_k\mathbb{i} + \delta_k)x & 1 \end{pmatrix}, \quad k=1,\ldots,q+1 \end{aligned}\]

where q = 2^l is an even prime power, and d is an even integer extension degree. The field $\mathbb{F}_{q^d}$ is constructed as $\mathbb{F}_q[x]/g(x)\mathbb{F}_q[x]$ where g(x) is an irreducible polynomial of degree d. Within this field, $\mathbb{i}$ denotes a root of the irreducible polynomial $x^2 + x + \varepsilon = 0$. The pairs $(\gamma_k, \delta_k)$ are the q+1 solutions in \mathbb{F}_q^2to the\gamma_k^2 + \gamma_k\delta_k + \delta_k^2\varepsilon = 1. And x is the polynomial variable that represents an element of\mathbb{F}_{q^d}` in the construction.

The same theorem states that the resulting Cayley graph $\Gamma_g$ has the following properties: it is a (q+1)-regular Ramanujan graph of order $|\Gamma_g| = q^{3d} - q^d$ and is non-bipartite. The graph has girth at least $\frac{2}{3}\log_q|\Gamma_g|$ and diameter at most $2\log_q|\Gamma_g| + 2$. Furthermore, as per Theorem 5.11, all eigenvalues $\mu$ of the adjacency matrix satisfy $|\mu| \leq 2\sqrt{q}$ for $\mu \neq$\pm(q+1)``.

Returns $(SL_2(q^i), B)$, where $B$ is the list of generators. As $PSL_2(q^i) = SL_2(q^i)$, we work in $SL_2(q^i)$.

Arguments

• l: A positive integer specifying that q = 2^l, where q is the size of the base field $\mathbb{F}_q$.
• i: An even positive integer specifying the extension degree for the field $\mathbb{F}_{q^i}$.

Internally call the morgenstern_f sampler to find an irreducible $x^2 + x + \varepsilon \in \mathbb{F}_q[x]$.

Find all $q + 1$ solutions $(\gamma, \delta) \in \mathbb{F}_q^2$ to the $\gamma^2 + \gamma\delta + \delta^2\varepsilon = 1$.

Quaternion Algebra

A quaternion algebra over $k = \mathbb{F}_q(x)$ is a skewfield $\mathcal{A}$ with center $k$ that has degree four as a vector space over $k$. In Morgenstern's explicit construction of Ramanujan graphs for even prime power $q$ (Morgenstern, 1994), a specific quaternion algebra is defined as

\[\begin{aligned} \mathscr{A} = k\mathbf{1} + k\mathbf{i} + k\mathbf{j} + k\mathbf{ij} \end{aligned}\]

with relations

\[\begin{aligned} \mathbf{i}^2 = \mathbf{i} + \varepsilon, \mathbf{j}^2 = x, \mathbf{ij} = \mathbf{ji} + \mathbf{j} \end{aligned}\]

The parameter $\varepsilon \in \mathbb{F}_q$ is chosen so that the polynomial $f(x) = x^2 + x + \varepsilon$ is irreducible over $\mathbb{F}_q$. This ensures $\mathcal{A}$ is a skewfield. The algebra is ramified at the finite place $x$ and at $1/x$.

The connection to graph theory arises from studying elements in the integral set

\[\begin{aligned} \mathscr{S} = \mathbb{F}_q[x]\mathbf{1} + \mathbb{F}_q[x]\mathbf{i} + \mathbb{F}_q[x]\mathbf{j} + \mathbb{F}_q[x]\mathbf{ij} \end{aligned}\]

The "basic norm x+1" elements are defined as

\[\begin{aligned} \xi = 1 + \gamma\mathbf{j} + \delta\mathbf{ij}, \quad \text{with} \gamma, \delta \in \mathbb{F}_q, \end{aligned}\]

satisfying the norm equation $N(\xi) = \gamma^2 + \gamma\delta + \delta^2arepsilon = 1$. This equation has exactly $q+1$ solutions in $\mathbb{F}_q$, parameterizing generators $\xi_1, \dots, \xi_{q+1}$. These generators define a free product group

\[\begin{aligned} A(x) = \langle \xi_1 \rangle * \langle \xi_2 \rangle * \cdots * \langle \xi_{q+1} \rangle \end{aligned}\]

which acts simply transitively on the $q+1$-regular tree $T_{x+1} = G'_{x+1}/G'_{O_{x+1}}$. Taking the quotient by a congruence subgroup $A(g)$, where $g(x)$ is irreducible of even degree, yields a finite $(q+1)$-regular graph $\Gamma_g = A(g) \backslash T_{x+1}$. This graph is the Cayley graph of $PSL_2(\mathbb{F}_{q^d})$ with respect to the images of the $q+1$ generators.

Arguments

• R: Polynomial ring $\mathbb{F}_q[x]$ where q is a power of 2.

Generate a normal Cayley subset of a finite group G. A Cayley subset S is called normal if it is a union of conjugacy classes of G. (Hirano et al., 2016) studies the spectral properties of Cayley graphs built from such subsets.

We take all conjugacy classes of G and excluding the trivial conjugacy class containing only the identity element. The resulting set S automatically satisfies several important properties: it is symmetric ($S = S^{-1}$) because conjugacy classes are closed under inverses, and it is normal ($g^{-1}Sg = S$ for all $g \in G$) by construction.

In the context of (Hirano et al., 2016), normal Cayley subsets are particularly valuable because they allow for explicit computation of graph eigenvalues using character theory.For any normal Cayley subset S, the eigenvalues of the Cayley graph X(S) can be expressed as:

\[\begin{aligned} \lambda_{\chi} = \frac{1}{\chi(1)} \sum_{s \in S} \chi(s) \end{aligned}\]

where $\chi$ ranges over the irreducible characters of G.

The work by (Hirano et al., 2016) establishes that for Frobenius groups $G = N \rtimes H$ with sufficiently large kernel-complement ratio ($r = (|N|-1)/|H| \geq 4$), there exists a well-defined bound $l_0$ such that all normal Cayley subsets with covalency $l \leq l_0$ produce Ramanujan graphs. For dihedral groups $D_{2p}$ in particular, this bound takes the explicit form

\[\begin{aligned} l_0 = 2\lfloor \sqrt{2p} - \frac{1}{2} \rfloor - 1 \end{aligned}\]

when $p \geq 11$.

Examples

julia> using Oscar

julia> G = dihedral_group(10);

julia> S = normal_cayley_subset(G)
9-element Vector{PcGroupElem}:
 f1
 f1*f2^2
 f1*f2^4
 f1*f2
 f1*f2^3
 f2
 f2^4
 f2^2
 f2^3

julia> length(S)
9

julia> all(s^-1 in S for s in S)
true

julia> all(g^-1 * s * g in S for s in S, g in G)
true

The properties of normal Cayley subsets find direct application in the construction of Ramanujan graphs for specific group families, as demonstrated in the following results:

(Mehry, 2023) investigates the construction of Ramanujan Cayley graphs for sporadic groups and linear groups, with a particular focus on the Mathieu groups M(9), M(10), and M(11), as well as the Suzuki groups $\text{Sz}(q)$. Additionally, they examines the special linear group SL(2, q). By leveraging the character tables of these groups and identifying appropriate normal symmetric generating subsets, the (Mehry, 2023) derive conditions under which the corresponding Cayley graphs satisfy the Ramanujan property.

(Droll, 2010) classifies all unitary Cayley graphs $X_n$ that are Ramanujan. The unitary Cayley graph $X_n$ is constructed on the additive group $\mathbb{Z}/n\mathbb{Z}$, where vertices represent integers modulo n, and edges connect two vertices if their difference is a multiplicative unit modulo n (i.e., $\gcd(a-b, n) = 1$). (Droll, 2010) provides a complete characterization: $X_n$ is Ramanujan—meaning it satisfies the optimal spectral gap condition $\lambda(X_n) \leq 2\sqrt{k-1}$ for k-regular graphs—if and only if n belongs to one of six explicit families based on its prime factorization, such as powers of 2, primes, or products of two primes under specific constraints.

(Wang et al., 1998) prove that every finite group admits a normal Cayley graph, except for $\mathbb{Z}_4 \times \mathbb{Z}_2$ and $Q_8 \times \mathbb{Z}_2^r$, and that every finite group has a normal Cayley digraph.

Arguments

• G::Group: A finite group

Construct X and Z stabilizer generators for the Quantum Tanner Code introduced in (Leverrier and Zémor, Apr 2022).

Returns the matrix for X-type stabilizer generators (dim(C₁) × |V₁| rows) and matrix for Z-type stabilizer generators (dim(C₀) × |V₀| rows).

Filters the solutions from solve_four_squares to select exactly $p+1` solutions with$a > 0$and$b, c, d`` even.

Returns an array of exactly p+1 tuples $(a, b, c, d)$ satisfying $p = a^2 + b^2 + c^2 + d^2$ with a > 0 odd and b, c, d even, representing the filtered solution set $S$ used in LPS Ramanujan graph construction (Lubotzky et al., 1988).

Arguments

• solutions::AbstractVector: The complete set of integer solutions to $p = a^2 + b^2 + c^2 + d^2$.
• p::Int: The prime number congruent to $1 \pmod{4}$ for which the solutions were generated

Puncturing is a standard technique for constructing new linear codes from existing ones ((Liu et al., 2020), (Gundersen et al., 2025)).

Let C be an [n, k, d] linear code over Galois field with characteristic 2 with parity-check matrix $H_B$, and let t be a set of coordinates given by cols. The punctured code $C_t$ is obtained by deleting the coordinates in t from every codeword of C. The resulting code is linear and has length n − |t|.

Returns a parity-check matrix for the punctured code $C_t$. The construction proceeds by computing a generator matrix G of C from $H_B$, deleting the columns indexed by t, and then computing a parity-check matrix for the resulting punctured code.

Here is an example of puncturing the classical [6,3,3] code:

julia> using QuantumExpanders; using Nemo

julia> H = [1 0 0 0 1 1;
            0 1 0 1 0 1;
            0 0 1 1 1 0];

julia> H_new = puncture(H, [6])
2×5 Matrix{Int64}:
 1  1  1  0  0
 1  1  0  1  1

julia> rank(matrix(GF(2), H_new))
2

Now, it is a [5,2,2] code. This distance is verified from dist-m4ri program.

Generate a pair of random classical codes (CA, CB) for quantum Tanner code construction (Radebold et al., 2025)

Returns a tuple (CA, CB) where each code is represented as a tuple (parity check matrix, generator matrix). Both codes have block length Δ, with CA having dimension ⌊ρΔ⌋ and CB having dimension Δ - ⌊ρΔ⌋.

Arguments

• ρ::Real: Target rate parameter, must satisfy 0 < ρ < 1/2
• Δ::Integer: Block length of the component codes

Generates the center of the general linear group $\mathrm{GL}(2, F)$ over a finite field $F$, consisting of all scalar matrices

\[\begin{aligned} \begin{bmatrix} x & 0 \\ 0 & x \end{bmatrix} \end{aligned}\]

where $x$ is any nonzero element of $F$. These matrices form the center $Z(GL(2, F))$ and are used in the LPS construction to form the projective general linear group $PGL(2, F) = GL(2, F)/Z(GL(2, F))$.

Arguments

• GL2::MatrixGroup: The general linear group $\mathrm{GL}(2, F)$ over a finite field F.

Generates the center of the special linear group $\mathrm{SL}(2, F)$ over a finite field $F$, consisting of scalar matrices

\[\begin{aligned} \begin{bmatrix} x & 0 \\ 0 & x \end{bmatrix} \end{aligned}\]

with $x^2 = 1$. These matrices form the center $Z(SL(2, F))$ and are used in the LPS construction to form the projective special linear group $PSL(2, F) = SL(2, F)/Z(SL(2, F))$.

Arguments

• GL2::MatrixGroup: The general linear group $\mathrm{GL}(2, F)$ over a finite field F.

Finds all integer solutions to the equation $p = a^2 + b^2 + c^2 + d^2$ for a prime $p \equiv 1 \pmod{4}$. according to the Jacobi's theorem.

Returns an array of tuples $(a, b, c, d)$ where each tuple represents an integer solution to the equation $p = a^2 + b^2 + c^2 + d^2$, with exactly $8(p+1)$ distinct solutions according to Jacobi's four-square theorem.

Arguments

• p::Int: A prime number congruent to $1 \pmod{4}$ for which to find four-square representations.

Construct the Tanner code for a given multigraph, edge numbering and local code.

The edge numbering is a map from (vertex, vertex, multiplicity) to index. Most convenient when used with cayley_complex_square_graphs.

Returns a binary matrix of size (r*V) × E representing the parity check matrix of the Tanner code, where r is the number of checks in the local code, V is the number of vertices, and E is the number of edges.

Tanner Code

Tanner code is a classical code where bits are placed on edges of a graph and constraints are imposed by local codes at each vertex.

The Tanner code construction is defined as:

\[\begin{aligned} T(\mathcal{G}, C_0) = \{ x \in \mathbb{F}_2^E : \operatorname{res}_{E(v)}(x) \in C_0 \forall v \in V(\mathcal{G})) \} \end{aligned}\]

the set of vectors $\mathbb{F_2}^E$ such that the restriction of x to edges incident to each vertex v belongs to the local code C₀. The qubits are placed on squares of the left-right Cayley complex, with Z-stabilizers defined by T(𝒢₀□, CA ⊗ CB) and X-stabilizers defined by T(𝒢₁□, CA⊥ ⊗ CB⊥). The commuting condition H_X H_Zᵀ = 0 essential for CSS codes follows naturally from the incidence structure of the complex.

As depicted in (Dinur et al., 2022), (Leverrier and Zémor, Apr 2022), and (Gu et al., Jun 2022).

Arguments

• mgraph: A multigraph representing the underlying graph structure. For quantum Tanner codes, this is 𝒢₀□ or 𝒢₁□ from the left-right Cayley complex.
• edge_q_index: A dictionary mapping (vertex, vertex, multiplicity) tuples to qubit indices. This identifies which physical qubit (placed on squares/faces) corresponds to each edge in the multigraph.
• edge_ab_index: A dictionary mapping (vertex, vertex, multiplicity) tuples to local coordinate indices. This provides the identification of each edge with an element of A×B in the local view.
• local_code: A binary matrix representing the parity check matrix of the local code. For quantum Tanner codes, this is C₀ = CA ⊗ CB for Z-stabilizers or C₁ = CA⊥ ⊗ CB⊥ for X-stabilizers.

Construct the Tanner code for a given multigraph, edge numbering and local code.

The edge numbering is a map from (vertex, vertex, multiplicity) to index. Most convenient when used with cayley_complex_square_graphs_quadripartite.

As depicted in (Dinur et al., 2022), (Leverrier and Zémor, Apr 2022), and (Gu et al., Jun 2022).

Generate a random binary parity check matrix for classical component codes used in quantum Tanner code construction (Leverrier and Zémor, Apr 2022).

Local Component Codes

The random classical code generation is essential for building quantum Tanner codes as described in (Leverrier and Zémor, Apr 2022). Theorem 18 of (Leverrier and Zémor, Apr 2022) establishes that for sufficiently large $\Delta$, random codes with specific rates yield asymptotically good quantum Tanner codes with high probability. Specifically, this theorem requires choosing $C_A$ via a random uniform $r \times \Delta$ generator matrix and $C_B$ via a random uniform $r \times \Delta$ parity-check matrix, where$r = \lfloor \rho \Delta \rfloor$.

The randomness is fundamental to obtaining codes with the robustness properties established in Theorem 9 of (Leverrier and Zémor, Apr 2022), which guarantees that with probability tending to 1 as $\Delta \to \infty$, the dual tensor code

\[\begin{aligned} C_A \otimes \mathbb{F}_2^B + \mathbb{F}_2^A \otimes C_B \end{aligned}\]

is $\Delta^{3/2-\varepsilon}$-robust with $\Delta^{\gamma}$-resistance to puncturing.

Example

julia> using QuantumExpanders: uniformly_random_code_checkmatrix;

julia> H = uniformly_random_code_checkmatrix(0.5, 10)
[0   0   1   1   0   0   1   1   0   1]
[1   1   0   0   1   0   0   0   1   0]
[1   1   1   0   0   0   0   1   1   1]
[1   1   1   0   0   1   0   1   1   1]
[0   0   0   1   1   1   0   0   1   0]

Arguments

• ρ::Real: Target rate of the classical component code, determining the code's dimension relative to its block length.
• Δ::Integer: Block length of the classical component code, corresponding to the size of the generating sets in the underlying Cayley graph structure.