qec_code/

distance.rs

use crate::Pauli;
use crate::binary::try_in_row_span;
use crate::code::StabilizerCode;
#[cfg(any(feature = "distance-ilp-highs", feature = "distance-ilp-gurobi"))]
use crate::distance_exact::ExactCssDistanceSolverStatus;
use crate::distance_exact::{
    ExactCssDistanceBackend, ExactCssDistanceSolverOptions, ExactCssDistanceSolverReport,
};
use crate::error::{QecError, Result};
use serde::{Deserialize, Serialize};

#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum LogicalClass {
    XLike,
    ZLike,
    Mixed,
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct DistanceResult {
    pub distance: usize,
    pub witness: Pauli,
    pub logical_class: LogicalClass,
}

#[derive(Debug, Clone, PartialEq)]
pub struct ExactCssDistanceComputation {
    pub distance: DistanceResult,
    pub solver_report: Option<ExactCssDistanceSolverReport>,
}

pub fn compute_distance(code: &StabilizerCode) -> Result<DistanceResult> {
    Ok(
        compute_distance_with_solver_options(code, ExactCssDistanceSolverOptions::default())?
            .distance,
    )
}

pub fn compute_distance_with_solver_options(
    code: &StabilizerCode,
    solver: ExactCssDistanceSolverOptions,
) -> Result<ExactCssDistanceComputation> {
    if code.num_logical_qubits() == 0 {
        return Err(QecError::DistanceWitnessNotFound);
    }

    #[cfg(any(feature = "distance-ilp-highs", feature = "distance-ilp-gurobi"))]
    {
        compute_distance_via_ilp(code, solver)
    }

    #[cfg(not(any(feature = "distance-ilp-highs", feature = "distance-ilp-gurobi")))]
    {
        compute_distance_without_ilp(code, solver)
    }
}

#[cfg(any(feature = "distance-ilp-highs", feature = "distance-ilp-gurobi"))]
fn compute_distance_via_ilp(
    code: &StabilizerCode,
    solver: ExactCssDistanceSolverOptions,
) -> Result<ExactCssDistanceComputation> {
    let lowered = crate::distance_ilp::lower_distance_problem(code)?;
    let config = qec_ilp_core::BinaryIlpConfig {
        backend: qec_ilp_core::BackendConfig {
            kind: backend_kind_to_ilp(solver.backend),
            time_limit_seconds: solver.time_limit_seconds,
            mip_gap: solver.mip_gap,
            threads: solver.threads,
            verbose: solver.verbose_solver,
        },
    };
    let mut backend = qec_ilp_core::backend::build_binary_backend(&lowered.model, &config)?;
    let backend_kind = backend.kind();
    let solution = backend.solve()?;
    let solver_status = solver_status_from_ilp(solution.status)?;
    let start = lowered.symplectic_var_offset;
    let end = start + code.n() * 2;
    let row = solution.binary_values[start..end]
        .iter()
        .map(|&bit| u8::from(bit))
        .collect::<Vec<_>>();
    let witness = Pauli::from_symplectic_row(row)?;
    post_validate_distance_witness(code, &witness)?;

    Ok(ExactCssDistanceComputation {
        distance: DistanceResult {
            distance: witness.weight(),
            logical_class: classify_logical(&witness),
            witness,
        },
        solver_report: Some(ExactCssDistanceSolverReport {
            backend: backend_kind_from_ilp(backend_kind),
            status: solver_status,
        }),
    })
}

#[cfg(not(any(feature = "distance-ilp-highs", feature = "distance-ilp-gurobi")))]
fn compute_distance_without_ilp(
    code: &StabilizerCode,
    solver: ExactCssDistanceSolverOptions,
) -> Result<ExactCssDistanceComputation> {
    if solver != ExactCssDistanceSolverOptions::default() {
        if solver.backend == ExactCssDistanceBackend::Gurobi {
            return Err(QecError::IlpBackendUnavailable("Gurobi".into()));
        }
        return Err(QecError::DistanceComputationUnsupported {
            n: code.n(),
            reason: "solver options require an ILP-enabled build".into(),
        });
    }
    Ok(ExactCssDistanceComputation {
        distance: compute_distance_via_exhaustive_search(code)?,
        solver_report: None,
    })
}

#[cfg(not(any(feature = "distance-ilp-highs", feature = "distance-ilp-gurobi")))]
fn compute_distance_via_exhaustive_search(code: &StabilizerCode) -> Result<DistanceResult> {
    validate_exhaustive_search_width(code.n())?;
    for weight in 1..=code.n() {
        if let Some(witness) = find_normalizer_witness_of_weight(code, weight)? {
            return Ok(DistanceResult {
                distance: weight,
                logical_class: classify_logical(&witness),
                witness,
            });
        }
    }
    Err(QecError::DistanceWitnessNotFound)
}

#[cfg(not(any(feature = "distance-ilp-highs", feature = "distance-ilp-gurobi")))]
fn validate_exhaustive_search_width(n: usize) -> Result<()> {
    let symplectic_bits = n
        .checked_mul(2)
        .ok_or(QecError::DistanceComputationUnsupported {
            n,
            reason: "enable a distance ILP feature or use a smaller code".into(),
        })?;
    let _ = 1usize.checked_shl(symplectic_bits as u32).ok_or(
        QecError::DistanceComputationUnsupported {
            n,
            reason: "enable a distance ILP feature or use a smaller code".into(),
        },
    )?;
    Ok(())
}

#[cfg(not(any(feature = "distance-ilp-highs", feature = "distance-ilp-gurobi")))]
fn find_normalizer_witness_of_weight(
    code: &StabilizerCode,
    weight: usize,
) -> Result<Option<Pauli>> {
    let stabilizer_rows = code.stabilizer_rows();
    let mut support = Vec::with_capacity(weight);
    search_supports(code, &stabilizer_rows, weight, 0, &mut support)
}

#[cfg(not(any(feature = "distance-ilp-highs", feature = "distance-ilp-gurobi")))]
fn search_supports(
    code: &StabilizerCode,
    stabilizer_rows: &[Vec<u8>],
    target_weight: usize,
    next_qubit: usize,
    support: &mut Vec<usize>,
) -> Result<Option<Pauli>> {
    if support.len() == target_weight {
        let mut x = vec![0; code.n()];
        let mut z = vec![0; code.n()];
        return search_pauli_assignments(code, stabilizer_rows, support, 0, &mut x, &mut z);
    }

    let remaining = target_weight - support.len();
    let max_qubit = code.n() - remaining;
    for qubit in next_qubit..=max_qubit {
        support.push(qubit);
        if let Some(witness) =
            search_supports(code, stabilizer_rows, target_weight, qubit + 1, support)?
        {
            return Ok(Some(witness));
        }
        support.pop();
    }
    Ok(None)
}

#[cfg(not(any(feature = "distance-ilp-highs", feature = "distance-ilp-gurobi")))]
fn search_pauli_assignments(
    code: &StabilizerCode,
    stabilizer_rows: &[Vec<u8>],
    support: &[usize],
    support_index: usize,
    x: &mut [u8],
    z: &mut [u8],
) -> Result<Option<Pauli>> {
    if support_index == support.len() {
        let candidate = Pauli::from_xz_bits(x.to_vec(), z.to_vec())?;
        return if is_nontrivial_normalizer_witness(code, stabilizer_rows, &candidate)? {
            Ok(Some(candidate))
        } else {
            Ok(None)
        };
    }

    let qubit = support[support_index];
    for (x_bit, z_bit) in [(1, 0), (0, 1), (1, 1)] {
        x[qubit] = x_bit;
        z[qubit] = z_bit;
        if let Some(witness) =
            search_pauli_assignments(code, stabilizer_rows, support, support_index + 1, x, z)?
        {
            return Ok(Some(witness));
        }
    }
    x[qubit] = 0;
    z[qubit] = 0;
    Ok(None)
}

#[cfg(not(any(feature = "distance-ilp-highs", feature = "distance-ilp-gurobi")))]
fn is_nontrivial_normalizer_witness(
    code: &StabilizerCode,
    stabilizer_rows: &[Vec<u8>],
    candidate: &Pauli,
) -> Result<bool> {
    Ok(code
        .stabilizers()
        .iter()
        .all(|stabilizer| candidate.commutes_with(stabilizer))
        && !try_in_row_span(stabilizer_rows, &candidate.to_symplectic_row())?)
}

fn classify_logical(pauli: &Pauli) -> LogicalClass {
    let has_x = pauli.x_bits().contains(&1);
    let has_z = pauli.z_bits().contains(&1);

    match (has_x, has_z) {
        (true, false) => LogicalClass::XLike,
        (false, true) => LogicalClass::ZLike,
        (true, true) => LogicalClass::Mixed,
        (false, false) => unreachable!("logical witnesses are non-identity"),
    }
}

#[cfg(any(feature = "distance-ilp-highs", feature = "distance-ilp-gurobi"))]
fn backend_kind_to_ilp(kind: ExactCssDistanceBackend) -> qec_ilp_core::BackendKind {
    match kind {
        ExactCssDistanceBackend::Auto => qec_ilp_core::BackendKind::Auto,
        ExactCssDistanceBackend::Highs => qec_ilp_core::BackendKind::Highs,
        ExactCssDistanceBackend::Gurobi => qec_ilp_core::BackendKind::Gurobi,
    }
}

#[cfg(any(feature = "distance-ilp-highs", feature = "distance-ilp-gurobi"))]
fn backend_kind_from_ilp(kind: qec_ilp_core::BackendKind) -> ExactCssDistanceBackend {
    match kind {
        qec_ilp_core::BackendKind::Auto => ExactCssDistanceBackend::Auto,
        qec_ilp_core::BackendKind::Highs => ExactCssDistanceBackend::Highs,
        qec_ilp_core::BackendKind::Gurobi => ExactCssDistanceBackend::Gurobi,
    }
}

#[cfg(any(feature = "distance-ilp-highs", feature = "distance-ilp-gurobi"))]
fn solver_status_from_ilp(
    status: qec_ilp_core::model::ModelSolutionStatus,
) -> Result<ExactCssDistanceSolverStatus> {
    Ok(match status {
        qec_ilp_core::model::ModelSolutionStatus::Optimal => ExactCssDistanceSolverStatus::Optimal,
        qec_ilp_core::model::ModelSolutionStatus::Infeasible => {
            return Err(QecError::IlpInfeasible);
        }
        qec_ilp_core::model::ModelSolutionStatus::TimeLimit => {
            ExactCssDistanceSolverStatus::TimeLimit
        }
        qec_ilp_core::model::ModelSolutionStatus::SolutionLimit => {
            ExactCssDistanceSolverStatus::SolutionLimit
        }
        qec_ilp_core::model::ModelSolutionStatus::SubOptimal => {
            ExactCssDistanceSolverStatus::SubOptimal
        }
    })
}

#[cfg(any(feature = "distance-ilp-highs", feature = "distance-ilp-gurobi"))]
fn post_validate_distance_witness(code: &StabilizerCode, witness: &Pauli) -> Result<()> {
    if !code
        .stabilizers()
        .iter()
        .all(|stabilizer| witness.commutes_with(stabilizer))
    {
        return Err(QecError::IlpSolveFailed(
            "returned witness does not commute with stabilizers".into(),
        ));
    }

    if witness.weight() == 0 {
        return Err(QecError::IlpInfeasible);
    }

    if try_in_row_span(&code.stabilizer_rows(), &witness.to_symplectic_row())? {
        return Err(QecError::IlpSolveFailed(
            "returned witness lies in stabilizer span".into(),
        ));
    }

    Ok(())
}

#[cfg(test)]
mod tests {
    use super::{LogicalClass, classify_logical};
    use crate::Pauli;
    #[cfg(any(feature = "distance-ilp-highs", feature = "distance-ilp-gurobi"))]
    use crate::{QecError, StabilizerCode};

    #[cfg(any(feature = "distance-ilp-highs", feature = "distance-ilp-gurobi"))]
    fn single_qubit_z_stabilizer_code() -> StabilizerCode {
        StabilizerCode::from_stabilizers(1, vec![Pauli::from_xz_bits(vec![0], vec![1]).unwrap()])
            .unwrap()
    }

    #[test]
    fn classify_logical_distinguishes_x_z_and_mixed_supports() {
        let x_like = Pauli::from_xz_bits(vec![1, 0], vec![0, 0]).unwrap();
        let z_like = Pauli::from_xz_bits(vec![0, 0], vec![0, 1]).unwrap();
        let mixed = Pauli::from_xz_bits(vec![0, 1], vec![0, 1]).unwrap();

        assert_eq!(classify_logical(&x_like), LogicalClass::XLike);
        assert_eq!(classify_logical(&z_like), LogicalClass::ZLike);
        assert_eq!(classify_logical(&mixed), LogicalClass::Mixed);
    }

    #[cfg(any(feature = "distance-ilp-highs", feature = "distance-ilp-gurobi"))]
    #[test]
    fn post_validate_distance_witness_rejects_non_commuting_witnesses() {
        let code = single_qubit_z_stabilizer_code();
        let witness = Pauli::from_xz_bits(vec![1], vec![0]).unwrap();

        assert_eq!(
            super::post_validate_distance_witness(&code, &witness),
            Err(QecError::IlpSolveFailed(
                "returned witness does not commute with stabilizers".into(),
            ))
        );
    }

    #[cfg(any(feature = "distance-ilp-highs", feature = "distance-ilp-gurobi"))]
    #[test]
    fn post_validate_distance_witness_rejects_stabilizer_span_elements() {
        let code = single_qubit_z_stabilizer_code();
        let witness = Pauli::from_xz_bits(vec![0], vec![1]).unwrap();

        assert_eq!(
            super::post_validate_distance_witness(&code, &witness),
            Err(QecError::IlpSolveFailed(
                "returned witness lies in stabilizer span".into(),
            ))
        );
    }

    #[cfg(any(feature = "distance-ilp-highs", feature = "distance-ilp-gurobi"))]
    #[test]
    fn post_validate_distance_witness_rejects_zero_weight_witnesses() {
        let code = StabilizerCode::from_stabilizers(1, vec![]).unwrap();
        let witness = Pauli::from_xz_bits(vec![0], vec![0]).unwrap();

        assert_eq!(
            super::post_validate_distance_witness(&code, &witness),
            Err(QecError::IlpInfeasible)
        );
    }

    #[cfg(any(feature = "distance-ilp-highs", feature = "distance-ilp-gurobi"))]
    #[test]
    fn infeasible_solver_status_is_rejected_before_reading_solution_values() {
        assert_eq!(
            super::solver_status_from_ilp(qec_ilp_core::ModelSolutionStatus::Infeasible),
            Err(QecError::IlpInfeasible),
        );
    }
}