Quantum Minimum Distance

The minimum distance of a quantum code is the lowest weight of a logical operator, that is, of an element of the normalizer that is not in the stabilizer group. Degeneracy is what makes this harder than the classical problem: many distinct operators represent the same logical action, so the search is over cosets rather than over codewords.

For a CSS code the problem splits, and X_minimum_distance and Z_minimum_distance may be computed independently; the code distance is the smaller of the two. For a subsystem code there are two different answers and they must not be conflated. The bare distance minimizes over operators that commute with the whole gauge group, while the dressed distance allows multiplication by gauge operators and so can be smaller. The bare and dressed functions below are separate for exactly this reason.

As in the classical case, the exact solvers return certified values, while the probabilistic and heuristic searches return upper bounds witnessed by an operator they found. The setter functions record externally supplied bounds and do not verify them. Distance computations are the most expensive operation in this library; see the minimum distance tutorial for how to choose a solver and how to supply known bounds to prune the search.

Bounds and bookkeeping

CodingTheory.distance_automorphisms — Method
distance_automorphisms(S::AbstractStabilizerCodeCSS) -> Any

Return user-supplied physical-qubit permutation generators available to distance preprocessors. Quantum code families do not generate these automatically yet.

source
CodingTheory.set_X_minimum_distance_lower_bound! — Method
set_X_minimum_distance_lower_bound!(
    S::AbstractStabilizerCodeCSS,
    lower::Int64
)

Return nothing after tightening the certified lower bound on the X-distance. The bound records that no nontrivial X logical has smaller weight.

source
CodingTheory.set_X_minimum_distance_upper_bound! — Method
set_X_minimum_distance_upper_bound!(
    S::AbstractStabilizerCodeCSS,
    upper::Int64,
    witness::Union{Nemo.FqMatrix, Nemo.fpMatrix, Hecke.SMat, SparseArrays.SparseMatrixCSC}
)

Return nothing after tightening the X-distance upper bound using witness, which is validated as an X logical operator of weight upper.

source
CodingTheory.set_Z_minimum_distance_lower_bound! — Method
set_Z_minimum_distance_lower_bound!(
    S::AbstractStabilizerCodeCSS,
    lower::Int64
)

Return nothing after tightening the certified lower bound on the Z-distance. The bound records that no nontrivial Z logical has smaller weight.

source
CodingTheory.set_Z_minimum_distance_upper_bound! — Method
set_Z_minimum_distance_upper_bound!(
    S::AbstractStabilizerCodeCSS,
    upper::Int64,
    witness::Union{Nemo.FqMatrix, Nemo.fpMatrix, Hecke.SMat, SparseArrays.SparseMatrixCSC}
)

Return nothing after tightening the Z-distance upper bound using witness, which is validated as a Z logical operator of weight upper.

source
CodingTheory.set_distance_automorphisms! — Method
set_distance_automorphisms!(
    S::AbstractStabilizerCodeCSS,
    permutations::Vector{<:AbstractVector{<:Integer}};
    validate
)

Return nothing after registering physical-qubit permutations for distance searches. Validation checks that each permutation preserves both CSS stabilizer row spaces.

source
CodingTheory.set_minimum_distance_lower_bound! — Method
set_minimum_distance_lower_bound!(
    S::AbstractStabilizerCodeCSS,
    lower::Int64;
    which
)

Return nothing after tightening a certified lower bound. A full-distance lower bound also applies to both CSS sectors because d = min(d_X, d_Z).

source
CodingTheory.set_minimum_distance_upper_bound! — Method
set_minimum_distance_upper_bound!(
    S::AbstractStabilizerCodeCSS,
    upper::Int64,
    witness::Union{Nemo.FqMatrix, Nemo.fpMatrix, Hecke.SMat, SparseArrays.SparseMatrixCSC};
    which
)

Return nothing after tightening a CSS distance upper bound using a validated logical witness.

source

Exact algorithms

CodingTheory.XZ_minimum_distance — Method
XZ_minimum_distance(
    S::AbstractStabilizerCodeCSS;
    kwargs...
) -> Tuple{Any, Any}

Return a tuple containing the exact X- and Z-distances of a binary CSS code. Either entry may be -1 when that sector was not certified within the requested limits; any nonnegative entry is exact. These computations can be expensive.

source
CodingTheory.X_minimum_distance — Method
X_minimum_distance(
    S::AbstractStabilizerCodeCSS;
    kwargs...
) -> Tuple{Any, Any}

Return the exact X-distance and a witnessing logical operator in symplectic $[X \mid Z]$ form for a binary CSS code. A nonnegative returned distance is exact; -1 means no exact value was certified within the requested limits. A found witness may still tighten the stored upper bound after a time limit. This computation can be expensive.

source
CodingTheory.Z_minimum_distance — Method
Z_minimum_distance(
    S::AbstractStabilizerCodeCSS;
    kwargs...
) -> Tuple{Any, Any}

Return the exact Z-distance and a witnessing logical operator in symplectic $[X \mid Z]$ form for a binary CSS code. A nonnegative returned distance is exact; -1 means no exact value was certified within the requested limits. A found witness may still tighten the stored upper bound after a time limit. This computation can be expensive.

source
CodingTheory.minimum_distance — Method
minimum_distance(
    S::AbstractStabilizerCodeCSS;
    which,
    alg,
    max_d,
    verbose,
    time_limit_sec,
    ilp_parity_cut_max_degree,
    ilp_optimizer,
    ilp_threads,
    ilp_cyclic_period
) -> Tuple{Any, Any}

Return the X, Z, or full minimum distance of a binary CSS stabilizer code. The witness is returned in symplectic [X | Z] form.

source

Probabilistic algorithms

CodingTheory.probabilistic_minimum_distance — Method
probabilistic_minimum_distance(
    S::AbstractStabilizerCodeCSS;
    which,
    alg,
    max_weight,
    max_iters,
    p,
    l,
    info_set_alg,
    automorphisms,
    seed,
    verbose
) -> Tuple{Any, Any}

Return an X, Z, or full-distance upper bound found using quotient-aware binary ISD. Returned witnesses are symplectic [X | Z] rows.

source

Heuristic algorithms

CodingTheory.heuristic_minimum_distance — Method
heuristic_minimum_distance(
    S::AbstractStabilizerCodeCSS;
    which,
    alg,
    max_iters,
    pop_size,
    mutation_rate,
    automorphisms,
    seed,
    verbose
) -> Tuple{Any, Any}

Return a CSS distance upper bound found using a quotient-aware metaheuristic. These algorithms never certify a lower bound.

source