1use super::{JobParameters, ProblemType, QpuError};
7use serde::{Deserialize, Serialize};
8use std::collections::HashMap;
9
10#[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#[derive(Debug, Clone, Serialize, Deserialize)]
69pub struct QuboFormulation {
70 pub num_variables: u32,
71 pub linear_terms: Vec<(u32, f64)>,
73 pub quadratic_terms: Vec<(u32, u32, f64)>,
75 pub offset: f64,
76}
77
78impl QuboFormulation {
79 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 pub fn add_linear_term(&mut self, variable: u32, coefficient: f64) {
91 self.linear_terms.push((variable, coefficient));
92 }
93
94 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 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 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#[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 pub fn new(num_qubits: u32) -> Self {
188 Self {
189 num_qubits,
190 gates: Vec::new(),
191 measurements: Vec::new(),
192 }
193 }
194
195 pub fn add_gate(&mut self, gate: Gate) {
197 self.gates.push(gate);
198 }
199
200 pub fn add_measurement(&mut self, m: Measurement) {
202 self.measurements.push(m);
203 }
204
205 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#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
223pub struct QuboPenaltyBounds {
224 pub objective_lower_bound: f64,
226 pub feasible_upper_bound: f64,
228 pub min_violation_delta: f64,
230 pub penalty_weight: f64,
232}
233
234pub 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
271pub 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
299pub struct PreSolver {
302 variable_map: HashMap<String, u32>,
303}
304
305impl PreSolver {
306 pub fn new() -> Self {
308 Self {
309 variable_map: HashMap::new(),
310 }
311 }
312
313 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 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 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, };
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 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 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 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}