Skip to main content

qualia_core_db/solvers/qpu/
pre_solver.rs

1//! QPU Pre-Solver — converts high-level problem descriptions into provider-ready
2//! QUBO matrices or gate-model quantum circuits.
3//!
4//! Ported from `qpu/src/pre_solver.rs`.
5
6use super::{JobParameters, ProblemType, QpuError};
7use serde::{Deserialize, Serialize};
8use std::collections::HashMap;
9
10// ── Problem description ───────────────────────────────────────────────────────
11
12#[derive(Debug, Clone, Serialize, Deserialize)]
13pub struct ProblemDescription {
14    pub problem_type: ProblemType,
15    pub variables: Vec<Variable>,
16    pub constraints: Vec<Constraint>,
17    pub objective: Objective,
18}
19
20#[derive(Debug, Clone, Serialize, Deserialize)]
21pub struct Variable {
22    pub name: String,
23    pub domain: VariableDomain,
24    pub index: u32,
25}
26
27#[derive(Debug, Clone, Serialize, Deserialize)]
28pub enum VariableDomain {
29    Binary,
30    Spin,
31    Integer { min: i32, max: i32 },
32    Continuous { min: f64, max: f64 },
33}
34
35#[derive(Debug, Clone, Serialize, Deserialize)]
36pub struct Constraint {
37    pub constraint_type: ConstraintType,
38    pub variables: Vec<String>,
39    pub parameters: serde_json::Value,
40}
41
42#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
43pub enum ConstraintType {
44    Linear,
45    Quadratic,
46    Equality,
47    Inequality,
48    Logical,
49}
50
51#[derive(Debug, Clone, Serialize, Deserialize)]
52pub struct Objective {
53    pub objective_type: ObjectiveType,
54    pub expression: String,
55    pub minimize: bool,
56}
57
58#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
59pub enum ObjectiveType {
60    Linear,
61    Quadratic,
62    Polynomial,
63    Custom,
64}
65
66// ── QUBO formulation ──────────────────────────────────────────────────────────
67
68#[derive(Debug, Clone, Serialize, Deserialize)]
69pub struct QuboFormulation {
70    pub num_variables: u32,
71    /// (variable_index, coefficient)
72    pub linear_terms: Vec<(u32, f64)>,
73    /// (var_a, var_b, coefficient)
74    pub quadratic_terms: Vec<(u32, u32, f64)>,
75    pub offset: f64,
76}
77
78impl QuboFormulation {
79    /// Creates an empty QUBO formulation with `num_variables`.
80    pub fn new(num_variables: u32) -> Self {
81        Self {
82            num_variables,
83            linear_terms: Vec::new(),
84            quadratic_terms: Vec::new(),
85            offset: 0.0,
86        }
87    }
88
89    /// Adds a linear coefficient for `variable`.
90    pub fn add_linear_term(&mut self, variable: u32, coefficient: f64) {
91        self.linear_terms.push((variable, coefficient));
92    }
93
94    /// Adds a quadratic coupler `(var_a, var_b)`.
95    pub fn add_quadratic_term(&mut self, var_a: u32, var_b: u32, coefficient: f64) {
96        self.quadratic_terms.push((var_a, var_b, coefficient));
97    }
98
99    /// Evaluate the QUBO energy `E(x)` at a binary assignment `bits` (`0` or `1` per variable).
100    pub fn evaluate_binary(&self, bits: &[u8]) -> f64 {
101        let mut energy = self.offset;
102        for &(v, c) in &self.linear_terms {
103            let x = if bits.get(v as usize).copied().unwrap_or(0) != 0 {
104                1.0
105            } else {
106                0.0
107            };
108            energy += c * x;
109        }
110        for &(a, b, c) in &self.quadratic_terms {
111            let xa = if bits.get(a as usize).copied().unwrap_or(0) != 0 {
112                1.0
113            } else {
114                0.0
115            };
116            let xb = if bits.get(b as usize).copied().unwrap_or(0) != 0 {
117                1.0
118            } else {
119                0.0
120            };
121            energy += c * xa * xb;
122        }
123        energy
124    }
125
126    /// Serializes the formulation into QPU `JobParameters`.
127    pub fn to_job_parameters(&self) -> JobParameters {
128        JobParameters {
129            num_qubits: self.num_variables,
130            hamiltonian: serde_json::to_string(self).ok(),
131            circuit: None,
132            circuit_depth: 1,
133            shots: 1000,
134            extra: serde_json::json!({"formulation": "qubo"}),
135        }
136    }
137}
138
139// ── Circuit formulation ───────────────────────────────────────────────────────
140
141#[derive(Debug, Clone, Serialize, Deserialize)]
142pub struct CircuitFormulation {
143    pub num_qubits: u32,
144    pub gates: Vec<Gate>,
145    pub measurements: Vec<Measurement>,
146}
147
148#[derive(Debug, Clone, Serialize, Deserialize)]
149pub struct Gate {
150    pub gate_type: GateType,
151    pub qubits: Vec<u32>,
152    pub parameters: Vec<f64>,
153}
154
155#[derive(Debug, Clone, Serialize, Deserialize)]
156pub enum GateType {
157    H,
158    X,
159    Y,
160    Z,
161    Rx,
162    Ry,
163    Rz,
164    CNOT,
165    CZ,
166    SWAP,
167    ZZ,
168    Custom(String),
169}
170
171#[derive(Debug, Clone, Serialize, Deserialize)]
172pub struct Measurement {
173    pub qubit: u32,
174    pub basis: MeasurementBasis,
175}
176
177#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
178pub enum MeasurementBasis {
179    Computational,
180    X,
181    Y,
182    Z,
183}
184
185impl CircuitFormulation {
186    /// Creates an empty gate-model formulation with `num_qubits`.
187    pub fn new(num_qubits: u32) -> Self {
188        Self {
189            num_qubits,
190            gates: Vec::new(),
191            measurements: Vec::new(),
192        }
193    }
194
195    /// Appends a gate to the circuit.
196    pub fn add_gate(&mut self, gate: Gate) {
197        self.gates.push(gate);
198    }
199
200    /// Appends a measurement.
201    pub fn add_measurement(&mut self, m: Measurement) {
202        self.measurements.push(m);
203    }
204
205    /// Serializes the circuit into QPU `JobParameters`.
206    pub fn to_job_parameters(&self) -> JobParameters {
207        JobParameters {
208            num_qubits: self.num_qubits,
209            hamiltonian: None,
210            circuit: serde_json::to_string(self).ok(),
211            circuit_depth: self.gates.len() as u32,
212            shots: 1000,
213            extra: serde_json::json!({"formulation": "circuit"}),
214        }
215    }
216}
217
218// ── QUBO Penalty Sufficiency Theorem (Q42-08 / §6.2.3) ────────────────────────
219
220/// Bounds for enforcing the QUBO Penalty Sufficiency Theorem (`P * delta > U - L`)
221/// on a penalized Hamiltonian `E(x) = f(x) + P * g(x)`.
222#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
223pub struct QuboPenaltyBounds {
224    /// Global lower bound `L <= min_x f(x)` over all binary states (including infeasible).
225    pub objective_lower_bound: f64,
226    /// Upper bound `U >= min_{x feasible} f(x)` on at least one known feasible state.
227    pub feasible_upper_bound: f64,
228    /// Minimum positive constraint violation gap `delta <= min_{x infeasible} g(x)`.
229    pub min_violation_delta: f64,
230    /// Penalty multiplier `P` applied to `g(x)`.
231    pub penalty_weight: f64,
232}
233
234/// Enforce the **QUBO Penalty Sufficiency Theorem**:
235/// For `E(x) = f(x) + P * g(x)` with `g(x) = 0` on feasible states and `g(x) >= delta > 0`
236/// on infeasible states, `P * delta > U - L` guarantees every global ground state of `E(x)`
237/// is feasible.
238pub fn verify_qubo_penalty_sufficiency(bounds: &QuboPenaltyBounds) -> Result<(), QpuError> {
239    if !bounds.objective_lower_bound.is_finite()
240        || !bounds.feasible_upper_bound.is_finite()
241        || !bounds.min_violation_delta.is_finite()
242        || !bounds.penalty_weight.is_finite()
243    {
244        return Err(QpuError::Api(
245            "QUBO penalty bounds must be finite real numbers".to_string(),
246        ));
247    }
248    if bounds.min_violation_delta <= 0.0 {
249        return Err(QpuError::Api(format!(
250            "QUBO minimum violation gap delta must be > 0, got {}",
251            bounds.min_violation_delta
252        )));
253    }
254    if bounds.feasible_upper_bound < bounds.objective_lower_bound {
255        return Err(QpuError::Api(format!(
256            "QUBO feasible upper bound U ({}) < objective lower bound L ({})",
257            bounds.feasible_upper_bound, bounds.objective_lower_bound
258        )));
259    }
260    let span = bounds.feasible_upper_bound - bounds.objective_lower_bound;
261    let penalty_gap = bounds.penalty_weight * bounds.min_violation_delta;
262    if !(penalty_gap > span) {
263        return Err(QpuError::Api(format!(
264            "QUBO Penalty Sufficiency Theorem violated: P * delta ({} * {} = {}) must be strictly > U - L ({})",
265            bounds.penalty_weight, bounds.min_violation_delta, penalty_gap, span
266        )));
267    }
268    Ok(())
269}
270
271/// Compute a sufficient penalty weight `P = (U - L) / delta + safety_margin` (`safety_margin > 0`).
272pub fn minimum_sufficient_penalty(
273    objective_lower_bound: f64,
274    feasible_upper_bound: f64,
275    min_violation_delta: f64,
276    safety_margin: f64,
277) -> Result<f64, QpuError> {
278    if !safety_margin.is_finite() || safety_margin <= 0.0 {
279        return Err(QpuError::Api(
280            "QUBO penalty safety_margin must be finite and > 0".to_string(),
281        ));
282    }
283    if !min_violation_delta.is_finite() || min_violation_delta <= 0.0 {
284        return Err(QpuError::Api(
285            "QUBO min_violation_delta must be finite and > 0".to_string(),
286        ));
287    }
288    if !objective_lower_bound.is_finite()
289        || !feasible_upper_bound.is_finite()
290        || feasible_upper_bound < objective_lower_bound
291    {
292        return Err(QpuError::Api(
293            "QUBO objective bounds must be finite with U >= L".to_string(),
294        ));
295    }
296    Ok((feasible_upper_bound - objective_lower_bound) / min_violation_delta + safety_margin)
297}
298
299// ── Pre-solver ────────────────────────────────────────────────────────────────
300
301pub struct PreSolver {
302    variable_map: HashMap<String, u32>,
303}
304
305impl PreSolver {
306    /// Creates a pre-solver with the default formulation strategy.
307    pub fn new() -> Self {
308        Self {
309            variable_map: HashMap::new(),
310        }
311    }
312
313    /// Formulates `problem` into executable `JobParameters`; `QpuError` on unsupported problem kinds.
314    pub fn formulate(&mut self, problem: &ProblemDescription) -> Result<JobParameters, QpuError> {
315        match problem.problem_type {
316            ProblemType::Annealing => self.formulate_qubo(problem),
317            ProblemType::GateModel => self.formulate_circuit(problem),
318            ProblemType::Vqe | ProblemType::Qaoa => self.formulate_circuit(problem),
319        }
320    }
321
322    /// Formulate a constrained QUBO only after verifying the QUBO Penalty Sufficiency Theorem
323    /// (`P * delta > U - L`).
324    pub fn formulate_penalized_qubo(
325        &mut self,
326        problem: &ProblemDescription,
327        bounds: &QuboPenaltyBounds,
328    ) -> Result<JobParameters, QpuError> {
329        verify_qubo_penalty_sufficiency(bounds)?;
330        self.formulate_qubo(problem)
331    }
332
333    fn formulate_qubo(&mut self, problem: &ProblemDescription) -> Result<JobParameters, QpuError> {
334        let mut qubo = QuboFormulation::new(problem.variables.len() as u32);
335        self.variable_map.clear();
336        for var in &problem.variables {
337            self.variable_map.insert(var.name.clone(), var.index);
338        }
339        for c in &problem.constraints {
340            self.apply_constraint_qubo(&mut qubo, c)?;
341        }
342        self.apply_objective_qubo(&mut qubo, &problem.objective)?;
343        Ok(qubo.to_job_parameters())
344    }
345
346    fn formulate_circuit(
347        &mut self,
348        problem: &ProblemDescription,
349    ) -> Result<JobParameters, QpuError> {
350        let mut circuit = CircuitFormulation::new(problem.variables.len() as u32);
351        self.variable_map.clear();
352        for var in &problem.variables {
353            self.variable_map.insert(var.name.clone(), var.index);
354            circuit.add_gate(Gate {
355                gate_type: GateType::H,
356                qubits: vec![var.index],
357                parameters: vec![],
358            });
359        }
360        for c in &problem.constraints {
361            self.apply_constraint_circuit(&mut circuit, c)?;
362        }
363        for var in &problem.variables {
364            circuit.add_measurement(Measurement {
365                qubit: var.index,
366                basis: MeasurementBasis::Computational,
367            });
368        }
369        Ok(circuit.to_job_parameters())
370    }
371
372    fn apply_constraint_qubo(
373        &self,
374        qubo: &mut QuboFormulation,
375        c: &Constraint,
376    ) -> Result<(), QpuError> {
377        match c.constraint_type {
378            ConstraintType::Linear => {
379                if let Some(coeffs) = c.parameters.as_array() {
380                    for (i, coeff) in coeffs.iter().enumerate() {
381                        if let (Some(val), Some(name)) = (coeff.as_f64(), c.variables.get(i)) {
382                            if let Some(&idx) = self.variable_map.get(name.as_str()) {
383                                qubo.add_linear_term(idx, val);
384                            }
385                        }
386                    }
387                }
388                Ok(())
389            }
390            ConstraintType::Quadratic => {
391                if let Some(params) = c.parameters.as_object() {
392                    for (key, value) in params {
393                        if let Some(coeff) = value.as_f64() {
394                            let parts: Vec<&str> = key.splitn(2, ',').collect();
395                            if parts.len() == 2 {
396                                if let (Some(&a), Some(&b)) = (
397                                    self.variable_map.get(parts[0]),
398                                    self.variable_map.get(parts[1]),
399                                ) {
400                                    qubo.add_quadratic_term(a, b, coeff);
401                                }
402                            }
403                        }
404                    }
405                }
406                Ok(())
407            }
408            ref t => Err(QpuError::Api(format!(
409                "Constraint type {:?} not supported for QUBO",
410                t
411            ))),
412        }
413    }
414
415    fn apply_constraint_circuit(
416        &self,
417        circuit: &mut CircuitFormulation,
418        c: &Constraint,
419    ) -> Result<(), QpuError> {
420        if c.constraint_type == ConstraintType::Logical && c.variables.len() == 2 {
421            let a = self
422                .variable_map
423                .get(c.variables[0].as_str())
424                .copied()
425                .unwrap_or(0);
426            let b = self
427                .variable_map
428                .get(c.variables[1].as_str())
429                .copied()
430                .unwrap_or(0);
431            circuit.add_gate(Gate {
432                gate_type: GateType::CNOT,
433                qubits: vec![a, b],
434                parameters: vec![],
435            });
436            Ok(())
437        } else {
438            Err(QpuError::Api(format!(
439                "Constraint type {:?} not supported for circuit",
440                c.constraint_type
441            )))
442        }
443    }
444
445    fn apply_objective_qubo(
446        &self,
447        qubo: &mut QuboFormulation,
448        obj: &Objective,
449    ) -> Result<(), QpuError> {
450        let sign = if obj.minimize { 1.0 } else { -1.0 };
451        match obj.objective_type {
452            ObjectiveType::Linear => {
453                for &idx in self.variable_map.values() {
454                    qubo.add_linear_term(idx, sign);
455                }
456                Ok(())
457            }
458            ObjectiveType::Quadratic => {
459                let vars: Vec<u32> = self.variable_map.values().cloned().collect();
460                for i in 0..vars.len() {
461                    for j in i..vars.len() {
462                        qubo.add_quadratic_term(vars[i], vars[j], sign);
463                    }
464                }
465                Ok(())
466            }
467            ref t => Err(QpuError::Api(format!(
468                "Objective type {:?} not supported",
469                t
470            ))),
471        }
472    }
473}
474
475impl Default for PreSolver {
476    fn default() -> Self {
477        Self::new()
478    }
479}
480
481#[cfg(test)]
482mod tests {
483    use super::*;
484
485    fn two_var_problem(pt: ProblemType) -> ProblemDescription {
486        ProblemDescription {
487            problem_type: pt,
488            variables: vec![
489                Variable {
490                    name: "x0".into(),
491                    domain: VariableDomain::Binary,
492                    index: 0,
493                },
494                Variable {
495                    name: "x1".into(),
496                    domain: VariableDomain::Binary,
497                    index: 1,
498                },
499            ],
500            constraints: vec![],
501            objective: Objective {
502                objective_type: ObjectiveType::Linear,
503                expression: "x0 + x1".into(),
504                minimize: true,
505            },
506        }
507    }
508
509    #[test]
510    fn qubo_formulation_roundtrip() {
511        let mut solver = PreSolver::new();
512        let params = solver
513            .formulate(&two_var_problem(ProblemType::Annealing))
514            .unwrap();
515        assert_eq!(params.num_qubits, 2);
516        assert!(params.hamiltonian.is_some());
517    }
518
519    #[test]
520    fn circuit_formulation_roundtrip() {
521        let mut solver = PreSolver::new();
522        let params = solver
523            .formulate(&two_var_problem(ProblemType::GateModel))
524            .unwrap();
525        assert_eq!(params.num_qubits, 2);
526        assert!(params.circuit.is_some());
527    }
528
529    #[test]
530    fn qubo_add_terms() {
531        let mut q = QuboFormulation::new(2);
532        q.add_linear_term(0, 1.0);
533        q.add_linear_term(1, -1.0);
534        q.add_quadratic_term(0, 1, 0.5);
535        assert_eq!(q.linear_terms.len(), 2);
536        assert_eq!(q.quadratic_terms.len(), 1);
537    }
538
539    #[test]
540    fn qubo_penalty_sufficiency_theorem_enforces_feasible_ground_state() {
541        // Minimize f(x0, x1) = -3*x0 - 3*x1 subject to x0 + x1 <= 1 (g(x0, x1) = x0 * x1, delta = 1).
542        // Feasible states: (0,0)->0, (1,0)->-3, (0,1)->-3 => U = -3.
543        // Infeasible state: (1,1) has f(1,1) = -6 => L = -6, so U - L = 3.
544        let insufficient = QuboPenaltyBounds {
545            objective_lower_bound: -6.0,
546            feasible_upper_bound: -3.0,
547            min_violation_delta: 1.0,
548            penalty_weight: 2.0, // P * delta = 2 <= U - L = 3 (under-penalized!)
549        };
550        assert!(verify_qubo_penalty_sufficiency(&insufficient).is_err());
551
552        let mut solver = PreSolver::new();
553        assert!(solver
554            .formulate_penalized_qubo(&two_var_problem(ProblemType::Annealing), &insufficient)
555            .is_err());
556
557        // Demonstrate that under P = 2.0, infeasible (1,1) has lower energy (-4) than feasible (1,0) (-3):
558        let mut bad_qubo = QuboFormulation::new(2);
559        bad_qubo.add_linear_term(0, -3.0);
560        bad_qubo.add_linear_term(1, -3.0);
561        bad_qubo.add_quadratic_term(0, 1, 2.0);
562        assert!(bad_qubo.evaluate_binary(&[1, 1]) < bad_qubo.evaluate_binary(&[1, 0]));
563
564        // Compute sufficient penalty P > (U - L) / delta = 3.0:
565        let p_suff = minimum_sufficient_penalty(-6.0, -3.0, 1.0, 1.0).unwrap();
566        assert!((p_suff - 4.0).abs() < 1e-12);
567        let sufficient = QuboPenaltyBounds {
568            objective_lower_bound: -6.0,
569            feasible_upper_bound: -3.0,
570            min_violation_delta: 1.0,
571            penalty_weight: p_suff,
572        };
573        assert!(verify_qubo_penalty_sufficiency(&sufficient).is_ok());
574        assert!(solver
575            .formulate_penalized_qubo(&two_var_problem(ProblemType::Annealing), &sufficient)
576            .is_ok());
577
578        // Under P = 4.0, infeasible (1,1) has energy -2 > feasible ground state energy -3:
579        let mut good_qubo = QuboFormulation::new(2);
580        good_qubo.add_linear_term(0, -3.0);
581        good_qubo.add_linear_term(1, -3.0);
582        good_qubo.add_quadratic_term(0, 1, p_suff);
583        assert_eq!(good_qubo.evaluate_binary(&[1, 0]), -3.0);
584        assert_eq!(good_qubo.evaluate_binary(&[0, 1]), -3.0);
585        assert_eq!(good_qubo.evaluate_binary(&[1, 1]), -2.0);
586        assert!(good_qubo.evaluate_binary(&[1, 1]) > good_qubo.evaluate_binary(&[1, 0]));
587    }
588}