quantrs2_anneal/advanced_quantum_algorithms/

mod.rs

//! Advanced Quantum Algorithms for Annealing Optimization
//!
//! This module provides sophisticated quantum algorithms for optimization including:
//! - Infinite-depth QAOA with adaptive parameter optimization
//! - Quantum Zeno Effect-based annealing protocols
//! - Adiabatic shortcuts to adiabaticity optimization
//! - Counterdiabatic driving protocols
//!
//! Each algorithm is implemented in its own focused module for maintainability
//! and can be used independently or combined for hybrid approaches.

pub mod adiabatic_shortcuts;
pub mod counterdiabatic;
pub mod error;
pub mod infinite_qaoa;
pub mod utils;
pub mod zeno_annealing;

// Re-export all types for backward compatibility
pub use adiabatic_shortcuts::*;
pub use counterdiabatic::*;
pub use error::*;
pub use infinite_qaoa::*;
pub use utils::*;
pub use zeno_annealing::*;

use scirs2_core::ndarray::{Array1, Array2};
use scirs2_core::Complex64;
use std::collections::HashMap;
use std::sync::Arc;

use crate::{
    ising::{IsingModel, QuboModel},
    AnnealingResult, EmbeddingConfig,
};

/// Advanced quantum algorithms coordinator
///
/// This struct provides a unified interface for accessing all advanced quantum
/// algorithms and managing their configurations and execution.
#[derive(Debug, Clone)]
pub struct AdvancedQuantumAlgorithms {
    /// Default configuration for algorithms
    pub default_config: AdvancedAlgorithmConfig,
}

/// Configuration for advanced algorithm selection and execution
#[derive(Debug, Clone)]
pub struct AdvancedAlgorithmConfig {
    /// Enable infinite-depth QAOA
    pub enable_infinite_qaoa: bool,
    /// Enable Quantum Zeno annealing
    pub enable_zeno_annealing: bool,
    /// Enable adiabatic shortcuts
    pub enable_adiabatic_shortcuts: bool,
    /// Enable counterdiabatic driving
    pub enable_counterdiabatic: bool,
    /// Algorithm selection strategy
    pub selection_strategy: AlgorithmSelectionStrategy,
    /// Performance tracking
    pub track_performance: bool,
}

/// Strategy for selecting which algorithm to use
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum AlgorithmSelectionStrategy {
    /// Use the first available algorithm
    FirstAvailable,
    /// Use the algorithm with best historical performance
    BestPerformance,
    /// Use problem-specific algorithm selection
    ProblemSpecific,
    /// Use ensemble of multiple algorithms
    Ensemble,
    /// Manual algorithm selection
    Manual(String),
}

impl AdvancedQuantumAlgorithms {
    /// Create new advanced algorithms coordinator
    #[must_use]
    pub fn new() -> Self {
        Self {
            default_config: AdvancedAlgorithmConfig::default(),
        }
    }

    /// Create with custom configuration
    #[must_use]
    pub const fn with_config(config: AdvancedAlgorithmConfig) -> Self {
        Self {
            default_config: config,
        }
    }

    /// Solve problem using selected advanced algorithm
    pub fn solve<P>(
        &self,
        problem: &P,
        config: Option<AdvancedAlgorithmConfig>,
    ) -> AdvancedQuantumResult<AnnealingResult<Vec<i32>>>
    where
        P: Clone + 'static,
    {
        let config = config.unwrap_or_else(|| self.default_config.clone());

        match config.selection_strategy {
            AlgorithmSelectionStrategy::FirstAvailable => {
                self.solve_with_first_available(problem, &config)
            }
            AlgorithmSelectionStrategy::BestPerformance => {
                self.solve_with_best_performance(problem, &config)
            }
            AlgorithmSelectionStrategy::ProblemSpecific => {
                self.solve_with_problem_specific(problem, &config)
            }
            AlgorithmSelectionStrategy::Ensemble => self.solve_with_ensemble(problem, &config),
            AlgorithmSelectionStrategy::Manual(ref algorithm_name) => {
                self.solve_with_manual_selection(problem, &config, algorithm_name)
            }
        }
    }

    /// Solve using first available algorithm
    fn solve_with_first_available<P>(
        &self,
        problem: &P,
        config: &AdvancedAlgorithmConfig,
    ) -> AdvancedQuantumResult<AnnealingResult<Vec<i32>>>
    where
        P: Clone + 'static,
    {
        if config.enable_infinite_qaoa {
            let qaoa_config = InfiniteQAOAConfig::default();
            let mut qaoa = InfiniteDepthQAOA::new(qaoa_config);
            return qaoa.solve(problem);
        }

        if config.enable_zeno_annealing {
            let zeno_config = ZenoConfig::default();
            let mut annealer = QuantumZenoAnnealer::new(zeno_config);
            return annealer.solve(problem);
        }

        if config.enable_adiabatic_shortcuts {
            let shortcuts_config = ShortcutsConfig::default();
            let mut optimizer = AdiabaticShortcutsOptimizer::new(shortcuts_config);
            return optimizer.solve(problem);
        }

        if config.enable_counterdiabatic {
            let cd_config = CounterdiabaticConfig::default();
            let mut optimizer = CounterdiabaticDrivingOptimizer::new(cd_config);
            return optimizer.solve(problem);
        }

        Err(AdvancedQuantumError::NoAlgorithmAvailable)
    }

    /// Optimize a problem using the advanced quantum algorithms
    pub fn optimize_problem(
        &self,
        problem: &crate::ising::QuboModel,
    ) -> AdvancedQuantumResult<crate::simulator::AnnealingResult<crate::simulator::AnnealingSolution>>
    {
        use crate::simulator::AnnealingSolution;
        use std::time::Instant;

        let start_time = Instant::now();

        // Convert QUBO to Ising for algorithm application
        let ising = IsingModel::from_qubo(problem);

        // Select and apply algorithm based on strategy
        let best_solution = match self.default_config.selection_strategy {
            AlgorithmSelectionStrategy::FirstAvailable => {
                self.optimize_with_first_available(&ising)?
            }
            AlgorithmSelectionStrategy::BestPerformance => {
                self.optimize_with_best_performance(&ising)?
            }
            AlgorithmSelectionStrategy::ProblemSpecific => {
                self.optimize_with_problem_specific(&ising)?
            }
            AlgorithmSelectionStrategy::Ensemble => self.optimize_with_ensemble(&ising)?,
            AlgorithmSelectionStrategy::Manual(ref algo_name) => {
                self.optimize_with_manual_selection(&ising, algo_name)?
            }
        };

        let runtime = start_time.elapsed();

        // Convert solution back to QUBO format (0/1 instead of -1/+1)
        let qubo_solution: Vec<i8> = best_solution.iter().map(|&s| i8::from(s == 1)).collect();

        // Calculate energy in QUBO formulation
        let mut energy = 0.0;
        for (var, coeff) in problem.linear_terms() {
            if qubo_solution[var] == 1 {
                energy += coeff;
            }
        }
        for (var1, var2, coeff) in problem.quadratic_terms() {
            if qubo_solution[var1] == 1 && qubo_solution[var2] == 1 {
                energy += coeff;
            }
        }

        let solution = AnnealingSolution {
            best_spins: qubo_solution,
            best_energy: energy,
            repetitions: 1,
            total_sweeps: 1000,
            runtime,
            info: format!(
                "Optimized using advanced quantum algorithms (strategy: {:?})",
                self.default_config.selection_strategy
            ),
        };

        Ok(Ok(solution))
    }

    /// Optimize using the first available algorithm
    fn optimize_with_first_available(&self, ising: &IsingModel) -> AdvancedQuantumResult<Vec<i32>> {
        if self.default_config.enable_infinite_qaoa {
            return self.optimize_with_infinite_qaoa(ising);
        }
        if self.default_config.enable_zeno_annealing {
            return self.optimize_with_zeno(ising);
        }
        if self.default_config.enable_adiabatic_shortcuts {
            return self.optimize_with_adiabatic_shortcuts(ising);
        }
        if self.default_config.enable_counterdiabatic {
            return self.optimize_with_counterdiabatic(ising);
        }
        Err(AdvancedQuantumError::NoAlgorithmAvailable)
    }

    /// Optimize using algorithm with best historical performance
    fn optimize_with_best_performance(
        &self,
        ising: &IsingModel,
    ) -> AdvancedQuantumResult<Vec<i32>> {
        // For simplicity, use infinite QAOA as it generally performs well
        // In production, would track performance metrics and select accordingly
        if self.default_config.enable_infinite_qaoa {
            self.optimize_with_infinite_qaoa(ising)
        } else {
            self.optimize_with_first_available(ising)
        }
    }

    /// Optimize using problem-specific algorithm selection
    fn optimize_with_problem_specific(
        &self,
        ising: &IsingModel,
    ) -> AdvancedQuantumResult<Vec<i32>> {
        // Analyze problem characteristics
        let num_qubits = ising.num_qubits;
        let num_couplings = ising.couplings().len();
        let coupling_density = num_couplings as f64 / (num_qubits * num_qubits) as f64;

        // Select algorithm based on problem characteristics
        if num_qubits < 20 && coupling_density > 0.5 {
            // Densely coupled small problems: use infinite QAOA
            if self.default_config.enable_infinite_qaoa {
                return self.optimize_with_infinite_qaoa(ising);
            }
        }

        if coupling_density < 0.1 {
            // Sparse problems: use Zeno annealing
            if self.default_config.enable_zeno_annealing {
                return self.optimize_with_zeno(ising);
            }
        }

        // Default fallback
        self.optimize_with_first_available(ising)
    }

    /// Optimize using ensemble of multiple algorithms
    fn optimize_with_ensemble(&self, ising: &IsingModel) -> AdvancedQuantumResult<Vec<i32>> {
        let mut results = Vec::new();
        let mut energies = Vec::new();

        // Run all enabled algorithms
        if self.default_config.enable_infinite_qaoa {
            if let Ok(sol) = self.optimize_with_infinite_qaoa(ising) {
                let energy = self.calculate_ising_energy(ising, &sol);
                results.push(sol);
                energies.push(energy);
            }
        }

        if self.default_config.enable_zeno_annealing {
            if let Ok(sol) = self.optimize_with_zeno(ising) {
                let energy = self.calculate_ising_energy(ising, &sol);
                results.push(sol);
                energies.push(energy);
            }
        }

        if self.default_config.enable_adiabatic_shortcuts {
            if let Ok(sol) = self.optimize_with_adiabatic_shortcuts(ising) {
                let energy = self.calculate_ising_energy(ising, &sol);
                results.push(sol);
                energies.push(energy);
            }
        }

        if self.default_config.enable_counterdiabatic {
            if let Ok(sol) = self.optimize_with_counterdiabatic(ising) {
                let energy = self.calculate_ising_energy(ising, &sol);
                results.push(sol);
                energies.push(energy);
            }
        }

        // Return the best solution
        if let Some(best_idx) = energies
            .iter()
            .enumerate()
            .min_by(|(_, a), (_, b)| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal))
            .map(|(idx, _)| idx)
        {
            Ok(results[best_idx].clone())
        } else {
            Err(AdvancedQuantumError::NoAlgorithmAvailable)
        }
    }

    /// Optimize with manual algorithm selection
    fn optimize_with_manual_selection(
        &self,
        ising: &IsingModel,
        algo_name: &str,
    ) -> AdvancedQuantumResult<Vec<i32>> {
        match algo_name {
            "infinite_qaoa" | "qaoa" => self.optimize_with_infinite_qaoa(ising),
            "zeno" | "quantum_zeno" => self.optimize_with_zeno(ising),
            "adiabatic_shortcuts" | "shortcuts" => self.optimize_with_adiabatic_shortcuts(ising),
            "counterdiabatic" | "cd" => self.optimize_with_counterdiabatic(ising),
            _ => Err(AdvancedQuantumError::InvalidAlgorithm(
                algo_name.to_string(),
            )),
        }
    }

    /// Helper: optimize using infinite QAOA
    fn optimize_with_infinite_qaoa(&self, ising: &IsingModel) -> AdvancedQuantumResult<Vec<i32>> {
        let config = InfiniteQAOAConfig::default();
        let mut qaoa = InfiniteDepthQAOA::new(config);
        let result = qaoa.solve(ising)?;
        result.map_err(|e| AdvancedQuantumError::ConvergenceError(format!("QAOA failed: {e:?}")))
    }

    /// Helper: optimize using Quantum Zeno annealing
    fn optimize_with_zeno(&self, ising: &IsingModel) -> AdvancedQuantumResult<Vec<i32>> {
        let config = ZenoConfig::default();
        let mut zeno = QuantumZenoAnnealer::new(config);
        let result = zeno.solve(ising)?;
        result.map_err(|e| AdvancedQuantumError::ZenoError(format!("Zeno annealing failed: {e:?}")))
    }

    /// Helper: optimize using adiabatic shortcuts
    fn optimize_with_adiabatic_shortcuts(
        &self,
        ising: &IsingModel,
    ) -> AdvancedQuantumResult<Vec<i32>> {
        let config = ShortcutsConfig::default();
        let mut shortcuts = AdiabaticShortcutsOptimizer::new(config);
        let result = shortcuts.solve(ising)?;
        result.map_err(|e| {
            AdvancedQuantumError::ConvergenceError(format!("Adiabatic shortcuts failed: {e:?}"))
        })
    }

    /// Helper: optimize using counterdiabatic driving
    fn optimize_with_counterdiabatic(&self, ising: &IsingModel) -> AdvancedQuantumResult<Vec<i32>> {
        // Counterdiabatic driving is a specific method within adiabatic shortcuts
        let mut config = ShortcutsConfig::default();
        config.shortcut_method = ShortcutMethod::CounterdiabaticDriving;
        let mut optimizer = AdiabaticShortcutsOptimizer::new(config);
        let result = optimizer.solve(ising)?;
        result.map_err(|e| {
            AdvancedQuantumError::ConvergenceError(format!("Counterdiabatic driving failed: {e:?}"))
        })
    }

    /// Helper: calculate Ising energy for a solution
    fn calculate_ising_energy(&self, ising: &IsingModel, solution: &[i32]) -> f64 {
        let mut energy = 0.0;

        // Linear terms
        for (i, bias) in ising.biases() {
            energy += bias * f64::from(solution[i]);
        }

        // Quadratic terms
        for coupling in ising.couplings() {
            energy += coupling.strength
                * f64::from(solution[coupling.i])
                * f64::from(solution[coupling.j]);
        }

        energy
    }

    /// Solve using algorithm with best historical performance
    fn solve_with_best_performance<P>(
        &self,
        problem: &P,
        config: &AdvancedAlgorithmConfig,
    ) -> AdvancedQuantumResult<AnnealingResult<Vec<i32>>>
    where
        P: Clone + 'static,
    {
        // For now, delegate to first available
        // In practice, would analyze performance history
        self.solve_with_first_available(problem, config)
    }

    /// Solve using problem-specific algorithm selection
    fn solve_with_problem_specific<P>(
        &self,
        problem: &P,
        config: &AdvancedAlgorithmConfig,
    ) -> AdvancedQuantumResult<AnnealingResult<Vec<i32>>>
    where
        P: Clone + 'static,
    {
        // Analyze problem characteristics to select best algorithm
        // Since we can't call num_variables() on generic P, estimate size from conversion
        let problem_size = if let Ok(ising_problem) = self.convert_to_ising(problem) {
            ising_problem.num_qubits
        } else {
            100 // Default size for unknown problems
        };
        let density = self.estimate_problem_density(problem, problem_size);

        if problem_size <= 50 && density > 0.7 {
            // Dense small problems: use infinite QAOA
            if config.enable_infinite_qaoa {
                let qaoa_config = InfiniteQAOAConfig::default();
                let mut qaoa = InfiniteDepthQAOA::new(qaoa_config);
                return qaoa.solve(problem);
            }
        } else if problem_size > 100 {
            // Large problems: use Zeno annealing
            if config.enable_zeno_annealing {
                let zeno_config = ZenoConfig::default();
                let mut annealer = QuantumZenoAnnealer::new(zeno_config);
                return annealer.solve(problem);
            }
        }

        // Fallback to first available
        self.solve_with_first_available(problem, config)
    }

    /// Solve using ensemble of algorithms
    fn solve_with_ensemble<P>(
        &self,
        problem: &P,
        config: &AdvancedAlgorithmConfig,
    ) -> AdvancedQuantumResult<AnnealingResult<Vec<i32>>>
    where
        P: Clone + 'static,
    {
        let mut results = Vec::new();

        // Run available algorithms
        if config.enable_infinite_qaoa {
            let qaoa_config = InfiniteQAOAConfig::default();
            let mut qaoa = InfiniteDepthQAOA::new(qaoa_config);
            if let Ok(result) = qaoa.solve(problem) {
                results.push(result);
            }
        }

        if config.enable_zeno_annealing {
            let zeno_config = ZenoConfig::default();
            let mut annealer = QuantumZenoAnnealer::new(zeno_config);
            if let Ok(result) = annealer.solve(problem) {
                results.push(result);
            }
        }

        // Select first successful result (could be improved with energy comparison)
        if let Some(best_result) = results.into_iter().next() {
            Ok(best_result)
        } else {
            Err(AdvancedQuantumError::EnsembleFailed)
        }
    }

    /// Solve using manually selected algorithm
    fn solve_with_manual_selection<P>(
        &self,
        problem: &P,
        config: &AdvancedAlgorithmConfig,
        algorithm_name: &str,
    ) -> AdvancedQuantumResult<AnnealingResult<Vec<i32>>>
    where
        P: Clone + 'static,
    {
        match algorithm_name {
            "infinite_qaoa" if config.enable_infinite_qaoa => {
                let qaoa_config = InfiniteQAOAConfig::default();
                let mut qaoa = InfiniteDepthQAOA::new(qaoa_config);
                qaoa.solve(problem)
            }
            "zeno_annealing" if config.enable_zeno_annealing => {
                let zeno_config = ZenoConfig::default();
                let mut annealer = QuantumZenoAnnealer::new(zeno_config);
                annealer.solve(problem)
            }
            "adiabatic_shortcuts" if config.enable_adiabatic_shortcuts => {
                let shortcuts_config = ShortcutsConfig::default();
                let mut optimizer = AdiabaticShortcutsOptimizer::new(shortcuts_config);
                optimizer.solve(problem)
            }
            "counterdiabatic" if config.enable_counterdiabatic => {
                let cd_config = CounterdiabaticConfig::default();
                let mut optimizer = CounterdiabaticDrivingOptimizer::new(cd_config);
                optimizer.solve(problem)
            }
            _ => Err(AdvancedQuantumError::AlgorithmNotFound(
                algorithm_name.to_string(),
            )),
        }
    }

    /// Estimate problem density (fraction of realized couplings) for algorithm
    /// selection.
    ///
    /// When the problem is convertible to an Ising model the true number of
    /// non-zero couplings is used; otherwise a coarse heuristic is applied.
    fn estimate_problem_density<P>(&self, problem: &P, num_vars: usize) -> f64
    where
        P: Clone + 'static,
    {
        let max_interactions = num_vars * num_vars.saturating_sub(1) / 2;

        if max_interactions == 0 {
            return 0.0;
        }

        // Use the actual coupling count whenever the problem can be converted.
        if let Ok(ising) = self.convert_to_ising(problem) {
            let actual_interactions = ising
                .couplings()
                .iter()
                .filter(|coupling| coupling.strength.abs() > 1e-12)
                .count();
            return actual_interactions as f64 / max_interactions as f64;
        }

        // Fallback heuristic for non-convertible problem types.
        let estimated_interactions = num_vars * 2;
        estimated_interactions as f64 / max_interactions as f64
    }

    /// Convert a supported problem type into an [`IsingModel`].
    ///
    /// Accepts `IsingModel` (owned or by reference) and `QuboModel` (converted via
    /// `QuboModel::to_ising`), and returns an honest error for any other type
    /// rather than fabricating a fixed-size empty model.
    fn convert_to_ising<P>(&self, problem: &P) -> Result<IsingModel, String>
    where
        P: Clone + 'static,
    {
        use std::any::Any;
        let any_problem = problem as &dyn Any;

        if let Some(ising) = any_problem.downcast_ref::<IsingModel>() {
            return Ok(ising.clone());
        }
        if let Some(ising_ref) = any_problem.downcast_ref::<&IsingModel>() {
            return Ok((*ising_ref).clone());
        }
        if let Some(qubo) = any_problem.downcast_ref::<QuboModel>() {
            return Ok(qubo.to_ising().0);
        }
        if let Some(qubo_ref) = any_problem.downcast_ref::<&QuboModel>() {
            return Ok((*qubo_ref).to_ising().0);
        }

        Err("Unsupported problem type: expected IsingModel or QuboModel".to_string())
    }
}

impl Default for AdvancedAlgorithmConfig {
    fn default() -> Self {
        Self {
            enable_infinite_qaoa: true,
            enable_zeno_annealing: true,
            enable_adiabatic_shortcuts: true,
            enable_counterdiabatic: true,
            selection_strategy: AlgorithmSelectionStrategy::ProblemSpecific,
            track_performance: true,
        }
    }
}

impl Default for AdvancedQuantumAlgorithms {
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_coordinator_convert_to_ising_real() {
        let algorithms = AdvancedQuantumAlgorithms::default();

        // Real Ising input is preserved.
        let mut ising = IsingModel::new(4);
        ising.set_bias(0, 0.5).expect("set bias");
        ising.set_coupling(0, 1, -1.0).expect("set coupling");
        ising.set_coupling(2, 3, 0.25).expect("set coupling");
        let converted = algorithms
            .convert_to_ising(&ising)
            .expect("Ising input should convert");
        assert_eq!(converted.num_qubits, 4);

        // The density estimate reflects the actual coupling count (2 of 6).
        let density = algorithms.estimate_problem_density(&ising, converted.num_qubits);
        let expected = 2.0 / 6.0;
        assert!(
            (density - expected).abs() < 1e-12,
            "density {density} != {expected}"
        );
    }

    #[test]
    fn test_coordinator_convert_to_ising_rejects_unsupported() {
        let algorithms = AdvancedQuantumAlgorithms::default();
        let bogus: Vec<f64> = vec![1.0, 2.0, 3.0];
        assert!(
            algorithms.convert_to_ising(&bogus).is_err(),
            "unsupported types must error rather than return a fabricated empty model"
        );
    }
}