Struct QUBO 

pub struct QUBO<W = f64> { /* 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.

Example

use problemreductions::models::optimization::QUBO;
use problemreductions::{Problem, Solver, BruteForce};

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

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

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

Implementations

impl<W: Clone + Default> QUBO<W>

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

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)>) -> Self

where W: Zero,

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

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].

impl<W> QUBO<W>

where W: Clone + Zero + AddAssign + Mul<Output = W>,

pub fn evaluate(&self, config: &[usize]) -> W

Evaluate the QUBO objective for a configuration.

Trait Implementations

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<'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: Clone + Default + PartialOrd + Num + Zero + AddAssign + Mul<Output = W> + 'static,

const NAME: &'static str = "QUBO"

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

type GraphType = SimpleGraph

The graph type this problem operates on.

type Weight = W

The weight type for this problem.

type Size = W

The type used for objective/size values.

fn num_variables(&self) -> usize

Returns the number of variables in the problem.

fn num_flavors(&self) -> usize

Returns the number of possible values (flavors) for each variable. For binary problems, this is 2.

fn problem_size(&self) -> ProblemSize

Returns metadata about the problem size.

fn energy_mode(&self) -> EnergyMode

Returns whether larger or smaller objective values are better.

fn solution_size(&self, config: &[usize]) -> SolutionSize<Self::Size>

Evaluate the solution size for a given configuration.

fn variables(&self) -> Range<usize>

Returns the range of variable indices.

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

Returns the possible flavors as a vector.

fn is_valid_config(&self, config: &[usize]) -> bool

Check if a configuration is valid for this problem.

fn solution_size_multiple( &self, configs: &[Vec<usize>], ) -> Vec<SolutionSize<Self::Size>>

Evaluate multiple configurations at once (batch evaluation).

impl ReduceTo<QUBO> for SpinGlass<f64>

type Result = ReductionSGToQUBO

The reduction result type.

fn reduce_to(&self) -> Self::Result

Reduce this problem to the target problem type.

impl ReduceTo<SpinGlass> for QUBO<f64>

type Result = ReductionQUBOToSG

The reduction result type.

fn reduce_to(&self) -> Self::Result

Reduce this problem to the target problem type.

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.