Expansion and local testability

CodingTheory provides exact finite-size computations for binary Tanner-graph expansion and reduced syndrome profiles, together with spectral graph estimates. The exact routines are exponential in the requested subset or error weight and are intended for small instances and bounded-weight checks.

Tanner-graph expansion

For a binary matrix H, columns are left vertices and rows are right vertices. The exact predicate

is_expander(H, γ, A)

checks

\[|N(S)| \geq A |S|\]

for every nonempty column set of size at most $\lfloor \gamma n\rfloor$. Use expansion_witness to obtain a failing subset and bipartite_expansion_profile to compute the exact minimum at each subset size. estimated_bipartite_vertex_expansion uses a Fiedler sweep and returns only an upper bound on the exact minimum.

is_left_right_expander checks both orientations. Code-object methods accept :X, :Z, or :both for CSS codes. Non-CSS codes support :both, where an X or Z entry connects the stabilizer to that qubit.

Reduced syndrome profiles

confinement_profile(H; max_error_weight=t) performs breadth-first search in the syndrome space. Consequently, the reported error weight is $\operatorname{dist}(e,\ker H)$, not the weight of an arbitrary error representative.

deterministic_QLTC_soundness computes

\[\min \frac{|He|}{\operatorname{dist}(e,\ker H)}\]

over syndrome cosets with a leader of weight at most max_error_weight. evaluate_single_shot_soundness restricts the resulting profile by syndrome weight.

Spectral estimates

algebraic_connectivity, fiedler_vector, estimated_edge_expansion, and estimated_vertex_expansion operate on ordinary Graphs.jl graphs. edge_expansion_bounds returns the combinatorial Cheeger interval. These graph quantities should not be confused with one-sided qubit-to-check expansion; use the matrix routines above for that purpose.

Restricted cosystolic expansion

cosystolic_expansion(boundary, incoming_boundary; max_weight=t) computes

\[\frac{|\partial_k x|} {\operatorname{dist}(x,\operatorname{im}\partial_{k+1})}\]

exactly for binary vectors of weight at most t. It verifies $\partial_k\partial_{k+1}=0$ and enumerates the incoming image, so max_boundary_rank limits the permitted image rank.

Group-ring and module-relative expansion are not currently exposed. Those require a canonical group-algebra lifting API and block-metric coset solver; treating physical Hamming distance as block distance would not be correct.

API

CodingTheory.algebraic_connectivity — Method
algebraic_connectivity(
    G::Graphs.AbstractGraph;
    normalized
) -> Any

Return the second-smallest eigenvalue of the combinatorial (or normalized) Laplacian. It is zero for a disconnected graph and for graphs with fewer than two vertices.

source
CodingTheory.confinement_profile — Method
confinement_profile(
    H;
    max_error_weight
) -> Dict{Int64, Int64}

Return, for every observed syndrome weight, the largest minimum error weight among syndrome cosets reached through max_error_weight. This computes reduced error weight, not the weight of an arbitrary representative.

source
CodingTheory.cosystolic_expansion — Method
cosystolic_expansion(
    boundary,
    incoming_boundary;
    max_weight,
    max_boundary_rank
) -> Any

Return the exact restricted ratio |boundary*x| / dist(x, image(incoming_boundary)) over binary vectors x of Hamming weight at most max_weight. The matrices represent Cₖ → Cₖ₋₁ and Cₖ₊₁ → Cₖ, respectively. A nontrivial cocycle therefore correctly gives ratio zero.

source
CodingTheory.deterministic_QLTC_soundness — Method
deterministic_QLTC_soundness(H; max_error_weight) -> Float64

Return the exact minimum of |syndrome(e)|/dist(e, ker(H)) over nontrivial syndrome cosets whose leader has weight at most max_error_weight.

source
CodingTheory.edge_expansion_bounds — Method
edge_expansion_bounds(
    G::Graphs.AbstractGraph
) -> Tuple{Any, Any}

Return Cheeger lower and upper bounds for edge expansion: λ₂/2 ≤ h(G) ≤ sqrt(2Δλ₂).

source
CodingTheory.estimated_bipartite_vertex_expansion — Method
estimated_bipartite_vertex_expansion(
    H;
    max_subset_size
) -> Any

Return a one-sided column-to-row vertex-expansion estimate from forward and reverse Fiedler sweeps. The result is an upper bound on the exact minimum.

source
CodingTheory.estimated_edge_expansion — Method
estimated_edge_expansion(G::Graphs.AbstractGraph) -> Any

Return the smallest edge-boundary ratio found by sweeping prefixes of a Fiedler ordering. This is an upper bound on the graph's edge expansion.

source
CodingTheory.estimated_vertex_expansion — Method
estimated_vertex_expansion(G::Graphs.AbstractGraph) -> Any

Return the smallest external-vertex-boundary ratio found by a Fiedler sweep. This is an upper bound on vertex expansion.

source
CodingTheory.evaluate_single_shot_soundness — Method
evaluate_single_shot_soundness(
    H,
    cutoff::Integer;
    max_error_weight
) -> Dict

Return the confinement profile restricted to syndrome weights below cutoff. The profile is exact for syndrome cosets with leaders through max_error_weight.

source
CodingTheory.expansion_witness — Method
expansion_witness(H, γ::Real, A::Real) -> Any

Return a subset of columns violating |N(S)| ≥ A|S| for 1 ≤ |S| ≤ floor(γ*ncols(H)), or nothing if every subset passes. This is an exact, exponential-time computation over the support graph.

source
CodingTheory.fiedler_vector — Method
fiedler_vector(G::Graphs.AbstractGraph) -> Any

Return a unit Fiedler vector of the combinatorial Laplacian. For a graph with fewer than two vertices, return a zero vector.

source
CodingTheory.is_bipartite_expander — Method
is_bipartite_expander(
    G::Graphs.AbstractGraph,
    left::AbstractVector{<:Integer},
    right::AbstractVector{<:Integer},
    γ::Real,
    A::Real
) -> Bool

Return whether the selected left-to-right bipartite adjacency satisfies the specified one-sided expansion inequality.

source
CodingTheory.is_expander — Method
is_expander(H, γ::Real, A::Real) -> Bool

Return whether one-sided vertex expansion from columns to rows holds exactly.

source
CodingTheory.is_left_right_expander — Method
is_left_right_expander(
    H,
    γ_left::Real,
    A_left::Real,
    γ_right::Real,
    A_right::Real
) -> Bool

Return whether both orientations of a binary bipartite adjacency matrix satisfy their respective one-sided expansion inequalities.

source
CodingTheory.is_topologically_connected — Function
is_topologically_connected(S::AbstractSubsystemCode) -> Bool
is_topologically_connected(
    S::AbstractSubsystemCode,
    check_type::Symbol
) -> Bool

Return whether the selected Tanner graph is connected.

source
CodingTheory.nontrivial_adjacency_spectral_radius — Method
nontrivial_adjacency_spectral_radius(
    G::Graphs.AbstractGraph
) -> Float64

Return the largest absolute adjacency eigenvalue after removing the trivial spectral-radius eigenvalues. For a connected d-regular bipartite graph this removes both d and -d.

source
CodingTheory.normalized_laplacian_matrix — Method
normalized_laplacian_matrix(G::Graphs.AbstractGraph) -> Any

Return the symmetric normalized Laplacian. Isolated vertices have zero diagonal, following the convention used by Graphs.jl.

source
CodingTheory.sipser_spielman_guarantees — Method
sipser_spielman_guarantees(
    H,
    γ::Real,
    A::Real;
    verify
) -> NamedTuple{(:epsilon, :degree, :has_linear_distance, :guaranteed_distance, :has_guaranteed_decoding, :bit_flip_radius), <:NTuple{6, Any}}

Return the standard consequences of a certified (γ,A) one-sided expansion bound for a binary left-regular parity-check matrix. By default the claim is checked exactly; use verify=false only when it was certified elsewhere.

source
CodingTheory.verify_QLTC_soundness — Method
verify_QLTC_soundness(
    H,
    threshold::Real;
    max_error_weight
) -> Any

Return whether the exact restricted deterministic QLTC soundness is at least threshold.

source
CodingTheory.verify_confinement — Method
verify_confinement(
    H,
    target_syndrome_weight::Integer;
    max_error_weight
) -> Union{Missing, Bool}

Return whether every nontrivial syndrome coset with leader weight at most max_error_weight has syndrome weight strictly above the target.

source