cqlib_core/compile/sabre/heuristic.rs
1// This code is part of Cqlib.
2//
3// (C) Copyright China Telecom Quantum Group 2025-2026
4//
5// This code is licensed under the Apache License, Version 2.0. You may
6// obtain a copy of this license in the LICENSE.txt file in the root directory
7// of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.
8//
9// Any modifications or derivative works of this code must retain this
10// copyright notice, and modified files need to carry a notice indicating
11// that they have been altered from the originals.
12
13//! SABRE trial and SWAP-selection configuration.
14//!
15//! The router first evaluates candidate SWAPs with a structural distance score:
16//!
17//! ```text
18//! score = basic_weight * sum(front_layer_distance)
19//! + sum_i lookahead_weights[i] * mean(lookahead_layer_i_distance)
20//! score *= max(congestion[swap_left], congestion[swap_right])
21//! ```
22//!
23//! Lower scores are preferred. Active-layer scaling keeps a broad lookahead
24//! layer from overwhelming nearer routing requirements. Candidates in
25//! a narrow structural window are compared by exact-lowerability-aware
26//! predicted native two-qubit cost when the target provides native plans.
27//! Exact score ties are sampled from the seeded trial generator.
28//!
29//! The front layer contains unary and two-qubit routing requirements blocked by
30//! their current placement. Lookahead layers bias decisions toward requirements
31//! that become relevant soon. Repeated interactions remain represented in their
32//! dependency layers because they express future placement locality. Keeping
33//! the front as a sum preserves its weight as the front grows.
34//!
35//! Congestion control is optional. Reusing either endpoint of a candidate SWAP
36//! multiplies its entire structural score, discouraging serial movement through
37//! the same physical region and allowing independent movement to proceed in
38//! parallel.
39//!
40use crate::compile::CompilerError;
41
42/// Bounded VF2 prepass used to seed SABRE layout candidates.
43#[derive(Debug, Clone, Copy, PartialEq, Eq)]
44pub struct SabreVf2PrepassConfig {
45 /// Maximum number of complete perfect mappings scored by VF2.
46 pub candidate_limit: usize,
47 /// Maximum number of partial mapping extensions attempted by VF2.
48 pub call_limit: usize,
49}
50
51/// Configuration shared by SABRE layout refinement and routing.
52#[derive(Debug, Clone, PartialEq)]
53pub struct SabreConfig {
54 /// Number of randomized starting layouts added to deterministic and
55 /// interaction-aware layout candidates.
56 pub layout_trials: usize,
57 /// Maximum component-assignment states explored before layout reports
58 /// budget exhaustion. Exhaustion is distinct from proven infeasibility.
59 pub layout_assignment_budget: usize,
60 /// Optional bounded VF2 prepass used to add a topology-perfect candidate.
61 /// `None` disables the prepass.
62 pub vf2_prepass: Option<SabreVf2PrepassConfig>,
63 /// Number of forward/backward refinement iterations per layout trial.
64 pub refinement_iterations: usize,
65 /// Number of complete routing trials run for each fully refined layout.
66 ///
67 /// The search directly returns the best route and does not route
68 /// intermediate refinement states or run a separate layout-scoring phase.
69 pub routing_trials: usize,
70 /// Optional deterministic seed. Equal seeds produce equal cqlib results.
71 pub seed: Option<u64>,
72 /// Swap-selection heuristic configuration.
73 pub heuristic: SabreHeuristicConfig,
74}
75
76/// Swap-selection heuristic used by SABRE.
77///
78/// The primary score combines the current front-layer sum, active-layer-scaled
79/// lookahead, and multiplicative congestion. Exact native 2Q cost resolves
80/// candidates in a narrow structural window when native plans are available.
81#[derive(Debug, Clone, PartialEq)]
82pub struct SabreHeuristicConfig {
83 /// Weight of the current front-layer total distance.
84 pub basic_weight: f64,
85 /// Weights of each active-layer-scaled lookahead-layer total.
86 pub lookahead_weights: Vec<f64>,
87 /// Amount added to a physical qubit's congestion multiplier after using it
88 /// in a heuristic SWAP. `None` disables congestion control.
89 pub decay_increment: Option<f64>,
90 /// Number of heuristic SWAP attempts before decay values reset.
91 pub decay_reset: usize,
92 /// Number of heuristic SWAPs allowed without routing a front-layer node
93 /// before SABRE falls back to a shortest-path escape.
94 pub attempt_limit: usize,
95 /// Floating-point tolerance for treating candidate SWAP scores as tied.
96 pub best_epsilon: f64,
97}
98
99impl Default for SabreHeuristicConfig {
100 fn default() -> Self {
101 Self {
102 basic_weight: 1.0,
103 lookahead_weights: vec![0.5, 0.25, 0.125, 0.0625, 0.03125],
104 decay_increment: Some(0.002),
105 decay_reset: 10,
106 attempt_limit: 1000,
107 best_epsilon: 1e-10,
108 }
109 }
110}
111
112impl Default for SabreConfig {
113 fn default() -> Self {
114 Self {
115 layout_trials: 10,
116 layout_assignment_budget: 1_000_000,
117 vf2_prepass: Some(SabreVf2PrepassConfig {
118 candidate_limit: 10,
119 call_limit: 1_000_000,
120 }),
121 refinement_iterations: 1,
122 routing_trials: 1,
123 seed: None,
124 heuristic: SabreHeuristicConfig::default(),
125 }
126 }
127}
128
129impl SabreConfig {
130 /// Returns a compact deterministic SABRE configuration for reproducible tests and examples.
131 ///
132 /// This keeps all trial counts small, fixes the random seed, and uses a
133 /// bounded swap-attempt limit so small fixtures run quickly while still
134 /// exercising the SABRE routing path.
135 pub fn deterministic_seeded(seed: u64) -> Self {
136 Self {
137 layout_trials: 2,
138 layout_assignment_budget: 100_000,
139 vf2_prepass: Some(SabreVf2PrepassConfig {
140 candidate_limit: 10,
141 call_limit: 100_000,
142 }),
143 refinement_iterations: 1,
144 routing_trials: 1,
145 seed: Some(seed),
146 heuristic: SabreHeuristicConfig {
147 lookahead_weights: vec![0.5, 0.25, 0.125, 0.0625, 0.03125],
148 attempt_limit: 20,
149 ..SabreHeuristicConfig::default()
150 },
151 }
152 }
153
154 /// Validates the routing fields used by SABRE.
155 ///
156 /// This check intentionally ignores layout-refinement fields such as
157 /// [`SabreConfig::layout_trials`].
158 /// Routing starts from a concrete initial layout and does not depend on
159 /// those layout-only knobs.
160 pub fn validate(&self) -> Result<(), CompilerError> {
161 if self.routing_trials == 0 {
162 return Err(CompilerError::InvalidInput(
163 "sabre routing_trials must be greater than zero".to_string(),
164 ));
165 }
166 self.heuristic.validate()
167 }
168}
169
170impl SabreHeuristicConfig {
171 pub(crate) fn validate(&self) -> Result<(), CompilerError> {
172 validate_weight(self.basic_weight, "sabre basic_weight")?;
173 for (index, weight) in self.lookahead_weights.iter().copied().enumerate() {
174 validate_weight(weight, &format!("sabre lookahead_weights[{index}]"))?;
175 }
176 if let Some(increment) = self.decay_increment {
177 validate_weight(increment, "sabre decay_increment")?;
178 if self.decay_reset == 0 {
179 return Err(CompilerError::InvalidInput(
180 "sabre decay_reset must be greater than zero when decay is enabled".to_string(),
181 ));
182 }
183 }
184 if !(self.best_epsilon.is_finite() && self.best_epsilon >= 0.0) {
185 return Err(CompilerError::InvalidInput(
186 "sabre best_epsilon must be finite and non-negative".to_string(),
187 ));
188 }
189 Ok(())
190 }
191}
192
193fn validate_weight(value: f64, name: &str) -> Result<(), CompilerError> {
194 if value.is_finite() && value >= 0.0 {
195 Ok(())
196 } else {
197 Err(CompilerError::InvalidInput(format!(
198 "{name} must be finite and non-negative"
199 )))
200 }
201}
202
203#[cfg(test)]
204#[path = "heuristic_test.rs"]
205mod heuristic_test;