BinaryOptimizationProblem

class BinaryOptimizationProblem(problem, *, hamiltonian_builder='native', quadratization_strength=None, decomposer=None, composer=None)

Bases: QAOAProblem

Generic QUBO or HUBO problem for QAOA.

Wraps a binary optimization problem expressed as either a quadratic form (QUBO) or higher-order polynomial (HUBO), normalizes it to a canonical BinaryPolynomialProblem, and exposes the QAOA building blocks: cost Hamiltonian (via Ising conversion), standard X-mixer, and ground-state initial superposition.

Accepted inputs (anything dimod.BinaryQuadraticModel or dimod.BinaryPolynomial accepts, plus matrices):

• np.ndarray / scipy.sparse.spmatrix — square QUBO matrix.

• dimod.BinaryQuadraticModel — quadratic form with named variables.

• dict with tuple keys — HUBO terms, e.g. {(0,): -1.0, (0, 1, 2): 2.0}.

• dimod.BinaryPolynomial — polynomial of arbitrary degree.

Ising-conversion strategies selected via hamiltonian_builder:

• "native" (default): translates each polynomial term into a Pauli-Z product. Exact, but high-degree terms produce many-body interactions that some simulators handle slowly.

• "quadratized": introduces auxiliary qubits and penalty terms so every interaction becomes two-body. Penalty magnitude is quadratization_strength; None picks 2 * max(|hubo coeff|).

Optionally accepts a dimod.hybrid decomposer/composer pair to enable partitioned solving via decompose(). Without one, the decomposition-related methods raise RuntimeError.

Parameters:

• problem (list | ndarray | spmatrix | BinaryQuadraticModel | Mapping[tuple[Hashable, ...], float] | BinaryPolynomial) – QUBO matrix, BQM, HUBO dict, or BinaryPolynomial.

• hamiltonian_builder (Literal['native', 'quadratized']) – "native" (default) or "quadratized".

• quadratization_strength (float | None) – Penalty strength for the quadratized builder. None (default) auto-picks 2 * max(|hubo coeff|). Ignored when hamiltonian_builder="native". The auto default is sized against a single worst-case term and may under-penalise dense HUBOs where many constraints can be violated simultaneously; pass an explicit value (or raise the multiplier on QuadratizedIsingConverter) for such instances.

• decomposer (ProblemDecomposer | None) – Optional hybrid.traits.ProblemDecomposer that enables decompose().

• composer (SubsamplesComposer | None) – Optional hybrid.traits.SubsamplesComposer for recombining sub-solutions; defaults to hybrid.SplatComposer.

Examples

>>> import numpy as np
>>> from divi.qprog.problems import BinaryOptimizationProblem
>>> Q = np.array([[-1.0, 2.0], [0.0, -1.0]])
>>> problem = BinaryOptimizationProblem(Q)
>>> problem.cost_hamiltonian  # ready for QAOA

Attributes Summary

canonical_problem	The normalized BinaryPolynomialProblem.
cost_hamiltonian	Cost Hamiltonian derived from the Ising conversion of the QUBO/HUBO.
decode_fn	Decode a measurement bitstring to the original variable assignment.
loss_constant	Constant offset from Ising conversion, added back to expectation values.
metadata	Encoding metadata from the Ising conversion (e.g. quadratization aux info).
mixer_hamiltonian	Standard X-mixer over all qubits in the Ising encoding.
raw_problem	The original QUBO/HUBO input passed at construction time.

Methods Summary

decompose()	Partition the problem using the configured hybrid decomposer.
evaluate_global_solution(solution)	Energy of a global bit assignment under the underlying BQM.
extend_solution(current_solution, prog_id, ...)	Splice a sub-problem's decoded bits into the global solution.
initial_solution_size()	Number of variables in the global solution vector.
postprocess_candidates(candidates, *[, strict])	Run global candidate solutions through the configured composer.

Attributes Documentation

canonical_problem

The normalized BinaryPolynomialProblem.

cost_hamiltonian

Cost Hamiltonian derived from the Ising conversion of the QUBO/HUBO.

decode_fn

Decode a measurement bitstring to the original variable assignment.

For problems built from named variables (e.g. a BQM with non-integer keys), the result is a dict mapping the original variable names to their bit values. For integer-indexed problems, returns the encoding’s raw bitstring projection.

loss_constant

Constant offset from Ising conversion, added back to expectation values.

metadata

Encoding metadata from the Ising conversion (e.g. quadratization aux info).

mixer_hamiltonian

Standard X-mixer over all qubits in the Ising encoding.

raw_problem

The original QUBO/HUBO input passed at construction time.

Methods Documentation

decompose()

Partition the problem using the configured hybrid decomposer.

Each non-trivial partition becomes its own BinaryOptimizationProblem keyed by (name, size). Partitions with no interactions are tracked internally and skipped during composition.

Raises:

ValueError – If no decomposer was provided at construction.

Return type:

dict[Hashable, QAOAProblem]

evaluate_global_solution(solution)

Energy of a global bit assignment under the underlying BQM.

Raises:

RuntimeError – If no decomposer was provided at construction.

Return type:

float

extend_solution(current_solution, prog_id, candidate_decoded)

Splice a sub-problem’s decoded bits into the global solution.

Returns a new list with values at positions corresponding to prog_id’s variables overwritten by candidate_decoded.

Return type:

list[int]

initial_solution_size()

Number of variables in the global solution vector.

Equals the number of variables in the underlying BQM. Only defined when a decomposer was provided at construction.

Raises:

RuntimeError – If no decomposer was provided.

Return type:

int

postprocess_candidates(candidates, *, strict=False)

Run global candidate solutions through the configured composer.

Return type:

list[tuple[ndarray, float]]

Returns:

Tuples (composed_solution, energy) where composed_solution is an int32 ndarray of bits and energy is the objective value computed by the composer.