quantrs2_core/quantum_walk/
search.rs

1//! Quantum walk search algorithm.
2
3use super::discrete::DiscreteQuantumWalk;
4use super::graph::{CoinOperator, Graph, SearchOracle};
5use scirs2_core::Complex64;
6
7/// Search algorithm using quantum walks
8pub struct QuantumWalkSearch {
9    #[allow(dead_code)]
10    graph: Graph,
11    oracle: SearchOracle,
12    walk: DiscreteQuantumWalk,
13}
14
15impl QuantumWalkSearch {
16    /// Create a new quantum walk search
17    pub fn new(graph: Graph, oracle: SearchOracle) -> Self {
18        let walk = DiscreteQuantumWalk::new(graph.clone(), CoinOperator::Grover);
19        Self {
20            graph,
21            oracle,
22            walk,
23        }
24    }
25
26    /// Apply the oracle that marks vertices
27    fn apply_oracle(&mut self) {
28        for &vertex in &self.oracle.marked {
29            for coin in 0..self.walk.coin_dimension {
30                let idx = self.walk.state_index(vertex, coin);
31                if idx < self.walk.state.len() {
32                    self.walk.state[idx] = -self.walk.state[idx]; // Phase flip
33                }
34            }
35        }
36    }
37
38    /// Run the search algorithm
39    pub fn run(&mut self, max_steps: usize) -> (usize, f64, usize) {
40        // Start in uniform superposition
41        let amplitude = Complex64::new(1.0 / (self.walk.hilbert_dim as f64).sqrt(), 0.0);
42        self.walk.state.fill(amplitude);
43
44        let mut best_vertex = 0;
45        let mut best_prob = 0.0;
46        let mut best_step = 0;
47
48        // Alternate between walk and oracle
49        for step in 1..=max_steps {
50            self.walk.step();
51            self.apply_oracle();
52
53            // Check probabilities at marked vertices
54            let probs = self.walk.position_probabilities();
55            for &marked in &self.oracle.marked {
56                if probs[marked] > best_prob {
57                    best_prob = probs[marked];
58                    best_vertex = marked;
59                    best_step = step;
60                }
61            }
62
63            // Early stopping if we have high probability
64            if best_prob > 0.5 {
65                break;
66            }
67        }
68
69        (best_vertex, best_prob, best_step)
70    }
71
72    /// Get vertex probabilities
73    pub fn vertex_probabilities(&self) -> Vec<f64> {
74        self.walk.position_probabilities()
75    }
76}
quantrs2_core/quantum_walk/search.rs

quantrs2_core/quantum_walk/
search.rs
