Struct QUBO 

pub struct QUBO<W = i64> { /* private fields */ }

The QUBO (Quadratic Unconstrained Binary Optimization) problem.

Given n binary variables x_i ∈ {0, 1} and a matrix Q, minimize the quadratic form:

f(x) = Σ_i Σ_j Q_ij * x_i * x_j = x^T Q x

The matrix Q is typically upper triangular, with diagonal elements representing linear terms and off-diagonal elements representing quadratic interactions.

QUBO<i64> is the default exact-integer variant. QUBO<f64> stores finite floating-point coefficients. An explicit variant reduction converts exactly representable integer coefficients to f64.

Example

use problemreductions::models::algebraic::QUBO;
use problemreductions::{Problem, BruteForce};

// Q matrix: minimize x0 - 2*x1 + x0*x1
// Q = [[1, 1], [0, -2]]
let problem = QUBO::from_matrix(vec![
    vec![1, 1],
    vec![0, -2],
]).unwrap();

let solver = BruteForce::new();
let solutions = solver.find_all_witnesses(&problem).unwrap();

// Optimal is x = [0, 1] with value -2
assert!(solutions.contains(&vec![false, true]));

Implementations

impl<W: WeightElement> QUBO<W>

pub fn from_matrix(matrix: Vec<Vec<W>>) -> Result<Self, ConstructionError>

Create a QUBO problem from a full matrix.

The matrix should be square. Only the upper triangular part (including diagonal) is used.

pub fn new( linear: Vec<W>, quadratic: Vec<((usize, usize), W)>, ) -> Result<Self, ConstructionError>

Create a QUBO from linear and quadratic terms.

Arguments

• linear - Linear coefficients (diagonal of Q)
• quadratic - Quadratic coefficients as ((i, j), value) for i < j

impl<W> QUBO<W>

pub fn num_vars(&self) -> usize

Get the number of variables.

pub fn matrix(&self) -> &[Vec<W>]

Get the Q matrix.

pub fn get(&self, i: usize, j: usize) -> Option<&W>

Get a specific matrix element Q[i][j].

Trait Implementations

impl<W> BruteForceProblem for QUBO<W>

where W: WeightElement + VariantParam,

fn dimensions(&self) -> Vec<usize>

Cardinality of each coordinate in the brute-force search space.

fn num_variables(&self) -> usize

Number of coordinates in the brute-force search space.

impl<W: Clone> Clone for QUBO<W>

fn clone(&self) -> QUBO<W>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<W: Debug> Debug for QUBO<W>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl DeclaredVariant for QUBO<i64>

impl DeclaredVariant for QUBO<f64>

impl<'de, W> Deserialize<'de> for QUBO<W>

where W: Deserialize<'de>,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<W> Problem for QUBO<W>

where W: WeightElement + VariantParam,

const NAME: &'static str = "QUBO"

Base name of this problem type (e.g., “MaximumIndependentSet”).

type Solution = Vec<bool>

Mathematical witness type for this problem.

type Value = Min<<W as WeightElement>::Sum>

The evaluation value type.

fn parameter_names() -> &'static [&'static str]

Canonical parameter names for this problem model.

fn parameters(&self) -> ProblemParameters

Measure the complete canonical parameters of this concrete instance.

fn evaluate( &self, solution: &Self::Solution, ) -> Result<Min<W::Sum>, EvaluationError>

Evaluate the problem on a solution.

fn variant() -> Vec<(&'static str, &'static str)>

Returns variant attributes derived from type parameters.

fn problem_type() -> ProblemType

Look up this problem’s catalog entry.

impl ReduceTo<ILP<bool, f64>> for QUBO<f64>

type Result = ReductionQUBOToILP<f64>

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl ReduceTo<ILP> for QUBO<i64>

type Result = ReductionQUBOToILP

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl ReduceTo<QUBO<f64>> for MaximumSetPacking<f64>

type Result = ReductionSPToQUBO

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl ReduceTo<QUBO<f64>> for MinimumDiscretePlanarInverseKinematics

type Result = ReductionMinimumDiscretePlanarInverseKinematicsToQUBO

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl ReduceTo<QUBO<f64>> for QUBO<i64>

type Result = VariantReductionResult<QUBO, QUBO<f64>>

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl ReduceTo<QUBO<f64>> for SpinGlass<SimpleGraph, f64>

type Result = ReductionSGToQUBO

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl ReduceTo<QUBO> for ClosestVectorProblem<i64>

type Result = ReductionCVPToQUBO

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl ReduceTo<QUBO> for KColoring<KN, SimpleGraph>

type Result = ReductionKColoringToQUBO<KN>

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl ReduceTo<QUBO> for KColoring<K2, SimpleGraph>

type Result = ReductionKColoringToQUBO<K2>

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl ReduceTo<QUBO> for KColoring<K3, SimpleGraph>

type Result = ReductionKColoringToQUBO<K3>

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl ReduceTo<QUBO> for GraphPartitioning<SimpleGraph>

type Result = ReductionGraphPartitioningToQUBO

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl ReduceTo<QUBO> for Knapsack

type Result = ReductionKnapsackToQUBO

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl ReduceTo<QUBO> for KSatisfiability<K2>

type Result = ReductionKSatToQUBO

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl ReduceTo<QUBO> for KSatisfiability<K3>

type Result = Reduction3SATToQUBO

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl ReduceTo<QUBO> for MinimumMultiwayCut<SimpleGraph, i64>

type Result = ReductionMinimumMultiwayCutToQUBO

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl ReduceTo<QUBO> for PaintShop

type Result = ReductionPaintShopToQUBO

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl ReduceTo<QUBO> for SpinGlass<SimpleGraph, i64>

type Result = ReductionSGToQUBO<i64>

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl ReduceTo<QUBO> for TravelingSalesman<SimpleGraph, i64>

type Result = ReductionTravelingSalesmanToQUBO

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl ReduceTo<QUBO> for ILP<bool>

type Result = ReductionILPToQUBO

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl ReduceTo<SpinGlass<SimpleGraph, f64>> for QUBO<f64>

type Result = ReductionQUBOToSG

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl<W> Serialize for QUBO<W>

where W: Serialize,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.