Skip to content

qubosolver.transforms

qubosolver.transforms

Transforms for QUBO instances.

Provides preprocessing transforms such as variable fixing to reduce problem size before solving.

Modules:

  • negative_bitflip –

    Bit-flip preprocessing transforms for QUBO instances with negative interactions.

  • variable_fixing –

    Variable-fixing transforms for QUBO problem reduction.

  • zeroing –

    Zeroing fallback for QUBO negative off-diagonal coefficients.

qubosolver.transforms.negative_bitflip

Bit-flip preprocessing transforms for QUBO instances with negative interactions.

Quantum (Rydberg) solvers cannot encode attractive interactions, so a QUBO must have non-negative off-diagonal coefficients to be embeddable. A change of variable x_i -> 1 - y_i on a subset of variables flips the sign of the interactions incident to it; choosing the subset that removes as much negative weight as possible is itself a QUBO, f^T Q_f f with Q_f = diag(C 1) - C, solved here by local search or tabu search.

apply finds the bit flips (by default with a local search on Q_f) and applies them to the matrix, returning a wrapper Instance that records the flip vector so the solution can later be mapped back with lift. When bit flips cannot remove every negative off-diagonal coefficient, the remaining ones can be dropped with transforms.zeroing.apply.

Typical usage:

from qubosolver.transforms import negative_bitflip
from qubosolver.solving import brute_force

flipped_instance = negative_bitflip.apply(instance, time_limit_s=60.0)
flipped_solution = brute_force.solve(flipped_instance)
solution = negative_bitflip.lift(flipped_solution, flipped_instance)

Classes:

  • Instance –

    A QUBO instance carrying bit-flip preprocessing history.

Functions:

  • apply –

    Find the bit flips minimizing negative weight and apply them to the QUBO matrix.

  • lift –

    Map a solution of the bit-flipped QUBO instance back onto the original variables.

Instance

Instance(parent_instance: qubosolver.Instance)

A QUBO instance carrying bit-flip preprocessing history.

Wraps a parent qubosolver.Instance whose off-diagonal coefficients may contain negative interactions. Applying apply solves the bit-flip problem, stores the flip vector here, and exposes the transformed matrix so it can be embedded and solved. lift uses the stored state to map a solution back onto the original variables.

Parameters:

  • parent_instance (qubosolver.Instance) –

    The original QUBO instance (before bit flips). A deep copy is kept internally for later reconstruction.

Methods:

  • __init_subclass__ –

    Register cls under its _tag so load can dispatch to it.

  • __len__ –

    Number of binary variables in the QUBO problem (same as size).

  • cost –

    Compute the QUBO objective \(x^T Q x\) for a candidate solution \(x\).

  • load –

    Deserialize an Instance previously saved with save.

  • save –

    Serialize this instance to file_like, tagged with its type.

Attributes:

Source code in qubosolver/transforms/negative_bitflip.py
def __init__(self, parent_instance: qubosolver.Instance) -> None:
    """Initialize from a parent QUBO instance.

    Args:
        parent_instance: The original QUBO instance (before bit flips).
            A deep copy is kept internally for later reconstruction.
    """
    super().__init__(parent_instance.matrix.detach().clone())
    self._parent_instance = copy.deepcopy(parent_instance)

    self.flips: Bitstring = bitstring.zeros(parent_instance.size)
    """Flip vector applied to the parent matrix, all-zero until [`apply`][] populates it."""

    self._metrics: dict[str, Any] = {}
    """Negative off-diagonal count and weight before/after the flips, as computed
    by [`apply`][]."""

    self._offset: float = 0.0
    """Constant term relating the flipped and original QUBO costs,
    $x^T Q x = y^T Q_{flipped} y + offset$."""

flips instance-attribute

flips: Bitstring = bitstring.zeros(parent_instance.size)

Flip vector applied to the parent matrix, all-zero until apply populates it.

matrix property

matrix: Matrix

The QUBO symmetric matrix.

Returns:

  • Matrix –

    QUBO symmetric matrix of shape (size, size).

Raises:

  • AssertionError –

    If the internal tensor is not 2-D or not square.

negative_bitflip property

negative_bitflip: negative_bitflip.Instance

View of this instance as a negative-bitflip instance.

Convenience property to avoid the boilerplate of assert isinstance(instance, negative_bitflip.Instance) before calling a method specific to that subclass. It exists purely to satisfy static type checkers (mypy) and enable IDE code completion — the runtime isinstance check and the TypeError below just mirror the guarantee that the assert would otherwise provide.

Returns:

  • negative_bitflip.Instance –

    This instance, narrowed to the negative-bitflip subclass.

Raises:

size property

size: int

Number of binary variables in the QUBO problem.

variable_fixing property

variable_fixing: variable_fixing.Instance

View of this instance as a variable-fixing instance.

Convenience property to avoid the boilerplate of assert isinstance(instance, variable_fixing.Instance) before calling a method specific to that subclass. It exists purely to satisfy static type checkers (mypy) and enable IDE code completion — the runtime isinstance check and the TypeError below just mirror the guarantee that the assert would otherwise provide.

Returns:

  • variable_fixing.Instance –

    This instance, narrowed to the variable-fixing subclass.

Raises:

zeroing property

zeroing: zeroing.Instance

View of this instance as a zeroing instance.

Convenience property to avoid the boilerplate of assert isinstance(instance, zeroing.Instance) before calling a method specific to that subclass. It exists purely to satisfy static type checkers (mypy) and enable IDE code completion — the runtime isinstance check and the TypeError below just mirror the guarantee that the assert would otherwise provide.

Returns:

  • zeroing.Instance –

    This instance, narrowed to the zeroing subclass.

Raises:

__init_subclass__

__init_subclass__(**kwargs: object) -> None

Register cls under its _tag so load can dispatch to it.

Automatic, so a new Instance subclass never needs to be added to a separate registry by hand.

Source code in qubosolver/types/instance.py
def __init_subclass__(cls, **kwargs: object) -> None:
    """Register `cls` under its `_tag` so [`load`][] can dispatch to it.

    Automatic, so a new `Instance` subclass never needs to be added to a
    separate registry by hand.
    """
    super().__init_subclass__(**kwargs)
    Instance._registry[cls._tag()] = cls

__len__

__len__() -> int

Number of binary variables in the QUBO problem (same as size).

Source code in qubosolver/types/instance.py
def __len__(self) -> int:
    """Number of binary variables in the QUBO problem (same as [`size`][])."""
    return self.size

cost

cost(solution: Bitstring) -> float

Compute the QUBO objective \(x^T Q x\) for a candidate solution \(x\).

Parameters:

  • solution (Bitstring) –

    Binary vector \(x\) of shape (size,).

Returns:

  • float –

    Scalar cost value.

Source code in qubosolver/types/instance.py
def cost(self, solution: Bitstring) -> float:
    """Compute the QUBO objective $x^T Q x$ for a candidate solution $x$.

    Args:
        solution: Binary vector $x$ of shape ``(size,)``.

    Returns:
        Scalar cost value.
    """
    # Import here to avoid circular imports
    from qubosolver.utils import _costs  # noqa: PLC0415 (import cycle)

    cost = _costs.quadratic_cost(solution, self.matrix)
    assert type(cost) is float  # nosec B101
    return cost

load classmethod

load(file_like: FileLike[bytes]) -> Self

Deserialize an Instance previously saved with save.

Called on the base class qubosolver.Instance, it loads any instance with automatic dispatch.

Called on a subclass (e.g. variable_fixing.Instance.load(f)), it additionally requires the loaded Instance to be an instance of that subclass (raising TypeError otherwise).

Parameters:

  • file_like (FileLike[bytes]) –

    Source file path or readable binary file object, as produced by save.

Returns:

  • Self –

    A new instance of whichever concrete type wrote the tag.

Raises:

  • ValueError –

    If the stream is not a qubosolver file, or if its type tag is missing or unrecognized.

  • TypeError –

    If the loaded instance's type is not cls or a subclass thereof.

Example
from pathlib import Path
from qubosolver import Instance
from qubosolver.transforms import variable_fixing

file = Path("instance.bin")
instance = variable_fixing.Instance(Instance())

with file.open("wb") as f:
    instance.save(f)

# Three ways to load it back, from least to most strict:
with file.open("rb") as f:
    loaded = Instance.load(f)                  # accepts any Instance subtype
    # loads, then narrows (fails after loading)
    loaded = Instance.load(f).variable_fixing
    loaded = variable_fixing.Instance.load(f)  # narrows first (fails before loading)
Source code in qubosolver/types/instance.py
@classmethod
def load(cls, file_like: FileLike[bytes]) -> Self:
    """Deserialize an [`Instance`][] previously saved with [`save`][].

    Called on the base class [`qubosolver.Instance`][], it loads any instance with
    automatic dispatch.

    Called on a subclass (e.g.
    [`variable_fixing.Instance.load(f)`][qubosolver.transforms.variable_fixing.Instance.load]),
    it additionally requires the loaded `Instance` to be an instance of that subclass
    (raising [`TypeError`][] otherwise).

    Args:
        file_like: Source file path or readable binary file object,
            as produced by [`save`][].

    Returns:
        A new instance of whichever concrete type wrote the tag.

    Raises:
        ValueError: If the stream is not a qubosolver file, or if its type
            tag is missing or unrecognized.
        TypeError: If the loaded instance's type is not `cls` or a subclass thereof.

    Example:
        ```python
        from pathlib import Path
        from qubosolver import Instance
        from qubosolver.transforms import variable_fixing

        file = Path("instance.bin")
        instance = variable_fixing.Instance(Instance())

        with file.open("wb") as f:
            instance.save(f)

        # Three ways to load it back, from least to most strict:
        with file.open("rb") as f:
            loaded = Instance.load(f)                  # accepts any Instance subtype
            # loads, then narrows (fails after loading)
            loaded = Instance.load(f).variable_fixing
            loaded = variable_fixing.Instance.load(f)  # narrows first (fails before loading)
        ```
    """
    with io_utils.open(file_like, "rb") as f:
        io_utils.load_header(f)
        tag = io_utils.load_string(f)
        target_cls = Instance._registry.get(tag)
        if target_cls is None:
            msg = f"Cannot load Instance: unrecognized type tag {tag!r}."
            raise ValueError(msg)
        instance = target_cls._read_body(f)
    if not isinstance(instance, cls):
        msg = (
            f"Cannot load {cls.__module__}.{cls.__qualname__}: "
            f"stream contains a {type(instance).__module__}.{type(instance).__qualname__}."
        )
        raise TypeError(msg)
    return instance

save

save(file_like: FileLike[bytes]) -> None

Serialize this instance to file_like, tagged with its type.

Parameters:

Example
from pathlib import Path

with Path("instance.bin").open("wb") as f:
    instance.save(f)
Source code in qubosolver/types/instance.py
def save(self, file_like: FileLike[bytes]) -> None:
    """Serialize this instance to ``file_like``, tagged with its type.

    Args:
        file_like: Destination — a file path ([`str`][] or [`os.PathLike`][]),
            or a binary-writable [`typing.IO`][] stream.

    Example:
        ```python
        from pathlib import Path

        with Path("instance.bin").open("wb") as f:
            instance.save(f)
        ```
    """
    with io_utils.open(file_like, "wb") as f:
        io_utils.save_header(f)
        io_utils.save_string(f, self._tag())
        self._write_body(f)

apply

apply(instance: qubosolver.Instance, *, method: Literal['local_search', 'tabu_search'] = 'local_search', time_limit_s: float = 60.0, eps: float = 0.0, rng: torch.Generator | None = None) -> Instance

Find the bit flips minimizing negative weight and apply them to the QUBO matrix.

Wraps instance in a bit-flip Instance, finds the flips with method, and replaces the matrix with its flipped counterpart. When instance has no negative off-diagonal coefficient, the wrapper is returned unchanged (flips stays all-zero).

Parameters:

  • instance (qubosolver.Instance) –

    The QUBO instance to preprocess.

  • method (Literal['local_search', 'tabu_search'], default: 'local_search' ) –

    "local_search" (solving.iterative_bitflip_local_search.solve on Q_f, from random starts plus the no-flip start), "tabu_search" (the same local search, refined with solving.tabu_search.solve).

  • time_limit_s (float, default: 60.0 ) –

    Time limit in seconds. For "tabu_search", it is shared by the local search and the tabu search.

  • eps (float, default: 0.0 ) –

    Tolerance below which a coefficient is treated as zero.

  • rng (torch.Generator | None, default: None ) –

    PyTorch random number generator controlling the random starts of the local search.

Returns:

  • Instance –

    A bit-flip instance carrying the flip vector and metrics.

Raises:

Source code in qubosolver/transforms/negative_bitflip.py
def apply(
    instance: qubosolver.Instance,
    *,
    method: Literal["local_search", "tabu_search"] = "local_search",
    time_limit_s: float = 60.0,
    eps: float = 0.0,
    rng: torch.Generator | None = None,
) -> Instance:
    """Find the bit flips minimizing negative weight and apply them to the QUBO matrix.

    Wraps `instance` in a bit-flip [`Instance`][], finds the flips with `method`,
    and replaces the matrix with its flipped counterpart.  When
    `instance` has no negative off-diagonal coefficient, the wrapper is returned
    unchanged (``flips`` stays all-zero).

    Args:
        instance: The QUBO instance to preprocess.
        method: ``"local_search"``
            ([`solving.iterative_bitflip_local_search.solve`][qubosolver.solving.classical.iterative_bitflip_local_search.solve]
            on ``Q_f``, from random starts plus the no-flip start),
            ``"tabu_search"`` (the same local search, refined with
            [`solving.tabu_search.solve`][qubosolver.solving.classical.tabu_search.solve]).
        time_limit_s: Time limit in seconds. For ``"tabu_search"``, it is shared
            by the local search and the tabu search.
        eps: Tolerance below which a coefficient is treated as zero.
        rng: PyTorch random number generator controlling the random starts of
            the local search.

    Returns:
        A bit-flip instance carrying the flip vector and metrics.

    Raises:
        ValueError: If `method` is unknown.
    """
    if not _has_negative_offdiagonal(instance.matrix, eps=eps):
        return Instance(instance)

    bitflip_solution = _solve_bitflip(
        instance, method=method, time_limit=time_limit_s, eps=eps, rng=rng
    )

    flips = bitflip_solution[0].bitstring
    objective_value = bitflip_solution[0].cost
    metrics = _compute_negative_weight_metrics(instance.matrix, flips, eps)

    Q_flipped, offset = _transform_qubo_with_bitflips(instance.matrix, flips)

    flipped_instance = Instance(instance)
    flipped_instance._matrix = Q_flipped
    flipped_instance.flips = flips
    flipped_instance._metrics = metrics
    flipped_instance._metrics["objective_value"] = objective_value
    flipped_instance._offset = offset

    return flipped_instance

lift

lift(flipped_solution: Solution, flipped_instance: Instance) -> Solution

Map a solution of the bit-flipped QUBO instance back onto the original variables.

Undoes the flips recorded on flipped_instance (y_i -> x_i) and recomputes costs against the original (unflipped) matrix. When no bit flip was applied, returns a deep copy of flipped_solution unchanged.

Parameters:

  • flipped_solution (Solution) –

    Solution obtained on the bit-flipped instance.

  • flipped_instance (Instance) –

    The bit-flipped instance produced by apply.

Returns:

  • Solution –

    A new solution over the original variables.

Source code in qubosolver/transforms/negative_bitflip.py
def lift(flipped_solution: Solution, flipped_instance: Instance) -> Solution:
    """Map a solution of the bit-flipped QUBO instance back onto the original variables.

    Undoes the flips recorded on `flipped_instance` (``y_i -> x_i``) and recomputes
    costs against the original (unflipped) matrix.  When no bit flip was applied,
    returns a deep copy of `flipped_solution` unchanged.

    Args:
        flipped_solution: Solution obtained on the bit-flipped instance.
        flipped_instance: The bit-flipped instance produced by [`apply`][].

    Returns:
        A new solution over the original variables.
    """
    flipped = torch.any(flipped_instance.flips != 0)
    if not flipped:
        return copy.deepcopy(flipped_solution)

    solution = Solution()
    solution.bitstrings = _apply_bitflips(flipped_solution.bitstrings, flipped_instance.flips)
    solution.costs = vector.tensor(
        [flipped_instance._parent_instance.cost(b) for b in solution.bitstrings]
    )
    solution.counts = flipped_solution.counts
    solution.probabilities = flipped_solution.probabilities

    return solution

qubosolver.transforms.variable_fixing

Variable-fixing transforms for QUBO problem reduction.

Variable fixing eliminates variables from a QUBO instance before solving by proving, from the structure of the objective matrix alone, that certain variables must be 0 or 1 in any optimal solution. Reducing the problem size this way can significantly cut the resources required by the solver.

Typical usage:

from qubosolver.transforms import variable_fixing
from qubosolver.solving import brute_force

reduced_instance = variable_fixing.apply_recursively(instance)
reduced_solution = brute_force.solve(reduced_instance)
solution = variable_fixing.lift(reduced_solution, reduced_instance)

Classes:

  • Instance –

    A QUBO instance with variable-fixing history.

Functions:

  • apply –

    Apply each fixation rule once and reduce the QUBO matrix accordingly.

  • apply_recursively –

    Apply fixation rules repeatedly until no further variables can be fixed.

  • hansen_fixing –

    Identify variables that can be fixed using Hansen's bounding criterion.

  • lift –

    Reconstruct the full solution by reinserting fixed variables.

Attributes:

  • Rule –

    A function that inspects a QUBO instance and returns the variables it can fix,

Rule module-attribute

A function that inspects a QUBO instance and returns the variables it can fix, as a mapping from variable index to the value (0 or 1) it is fixed to.

Instance

Instance(parent_instance: qubosolver.Instance)

A QUBO instance with variable-fixing history.

Wraps a parent qubosolver.Instance and tracks which variables were fixed (and to which value) so the original solution can be reconstructed via lift.

Parameters:

  • parent_instance (qubosolver.Instance) –

    The original (unreduced) QUBO instance. A deep copy is kept internally for later reconstruction.

Methods:

  • __init_subclass__ –

    Register cls under its _tag so load can dispatch to it.

  • __len__ –

    Number of binary variables in the QUBO problem (same as size).

  • cost –

    Compute the QUBO objective \(x^T Q x\) for a candidate solution \(x\).

  • load –

    Deserialize an Instance previously saved with save.

  • save –

    Serialize this instance to file_like, tagged with its type.

Attributes:

Source code in qubosolver/transforms/variable_fixing.py
def __init__(self, parent_instance: qubosolver.Instance) -> None:
    """Initialize from a parent QUBO instance.

    Args:
        parent_instance: The original (unreduced) QUBO instance.
            A deep copy is kept internally for later reconstruction.
    """
    super().__init__(
        parent_instance.matrix.detach().clone(),
    )
    self._parent_instance = copy.deepcopy(parent_instance)
    self._fixed_indices: list[dict[int, int]] = []

fixed_indices property

fixed_indices: list[dict[int, int]]

Fixation history: one dict per apply call, mapping index → fixed value.

matrix property

matrix: Matrix

The QUBO symmetric matrix.

Returns:

  • Matrix –

    QUBO symmetric matrix of shape (size, size).

Raises:

  • AssertionError –

    If the internal tensor is not 2-D or not square.

n_fixed_indices property

n_fixed_indices: int

Total number of variables fixed across all fixation rounds.

negative_bitflip property

negative_bitflip: negative_bitflip.Instance

View of this instance as a negative-bitflip instance.

Convenience property to avoid the boilerplate of assert isinstance(instance, negative_bitflip.Instance) before calling a method specific to that subclass. It exists purely to satisfy static type checkers (mypy) and enable IDE code completion — the runtime isinstance check and the TypeError below just mirror the guarantee that the assert would otherwise provide.

Returns:

  • negative_bitflip.Instance –

    This instance, narrowed to the negative-bitflip subclass.

Raises:

size property

size: int

Number of binary variables in the QUBO problem.

variable_fixing property

variable_fixing: variable_fixing.Instance

View of this instance as a variable-fixing instance.

Convenience property to avoid the boilerplate of assert isinstance(instance, variable_fixing.Instance) before calling a method specific to that subclass. It exists purely to satisfy static type checkers (mypy) and enable IDE code completion — the runtime isinstance check and the TypeError below just mirror the guarantee that the assert would otherwise provide.

Returns:

  • variable_fixing.Instance –

    This instance, narrowed to the variable-fixing subclass.

Raises:

zeroing property

zeroing: zeroing.Instance

View of this instance as a zeroing instance.

Convenience property to avoid the boilerplate of assert isinstance(instance, zeroing.Instance) before calling a method specific to that subclass. It exists purely to satisfy static type checkers (mypy) and enable IDE code completion — the runtime isinstance check and the TypeError below just mirror the guarantee that the assert would otherwise provide.

Returns:

  • zeroing.Instance –

    This instance, narrowed to the zeroing subclass.

Raises:

__init_subclass__

__init_subclass__(**kwargs: object) -> None

Register cls under its _tag so load can dispatch to it.

Automatic, so a new Instance subclass never needs to be added to a separate registry by hand.

Source code in qubosolver/types/instance.py
def __init_subclass__(cls, **kwargs: object) -> None:
    """Register `cls` under its `_tag` so [`load`][] can dispatch to it.

    Automatic, so a new `Instance` subclass never needs to be added to a
    separate registry by hand.
    """
    super().__init_subclass__(**kwargs)
    Instance._registry[cls._tag()] = cls

__len__

__len__() -> int

Number of binary variables in the QUBO problem (same as size).

Source code in qubosolver/types/instance.py
def __len__(self) -> int:
    """Number of binary variables in the QUBO problem (same as [`size`][])."""
    return self.size

cost

cost(solution: Bitstring) -> float

Compute the QUBO objective \(x^T Q x\) for a candidate solution \(x\).

Parameters:

  • solution (Bitstring) –

    Binary vector \(x\) of shape (size,).

Returns:

  • float –

    Scalar cost value.

Source code in qubosolver/types/instance.py
def cost(self, solution: Bitstring) -> float:
    """Compute the QUBO objective $x^T Q x$ for a candidate solution $x$.

    Args:
        solution: Binary vector $x$ of shape ``(size,)``.

    Returns:
        Scalar cost value.
    """
    # Import here to avoid circular imports
    from qubosolver.utils import _costs  # noqa: PLC0415 (import cycle)

    cost = _costs.quadratic_cost(solution, self.matrix)
    assert type(cost) is float  # nosec B101
    return cost

load classmethod

load(file_like: FileLike[bytes]) -> Self

Deserialize an Instance previously saved with save.

Called on the base class qubosolver.Instance, it loads any instance with automatic dispatch.

Called on a subclass (e.g. variable_fixing.Instance.load(f)), it additionally requires the loaded Instance to be an instance of that subclass (raising TypeError otherwise).

Parameters:

  • file_like (FileLike[bytes]) –

    Source file path or readable binary file object, as produced by save.

Returns:

  • Self –

    A new instance of whichever concrete type wrote the tag.

Raises:

  • ValueError –

    If the stream is not a qubosolver file, or if its type tag is missing or unrecognized.

  • TypeError –

    If the loaded instance's type is not cls or a subclass thereof.

Example
from pathlib import Path
from qubosolver import Instance
from qubosolver.transforms import variable_fixing

file = Path("instance.bin")
instance = variable_fixing.Instance(Instance())

with file.open("wb") as f:
    instance.save(f)

# Three ways to load it back, from least to most strict:
with file.open("rb") as f:
    loaded = Instance.load(f)                  # accepts any Instance subtype
    # loads, then narrows (fails after loading)
    loaded = Instance.load(f).variable_fixing
    loaded = variable_fixing.Instance.load(f)  # narrows first (fails before loading)
Source code in qubosolver/types/instance.py
@classmethod
def load(cls, file_like: FileLike[bytes]) -> Self:
    """Deserialize an [`Instance`][] previously saved with [`save`][].

    Called on the base class [`qubosolver.Instance`][], it loads any instance with
    automatic dispatch.

    Called on a subclass (e.g.
    [`variable_fixing.Instance.load(f)`][qubosolver.transforms.variable_fixing.Instance.load]),
    it additionally requires the loaded `Instance` to be an instance of that subclass
    (raising [`TypeError`][] otherwise).

    Args:
        file_like: Source file path or readable binary file object,
            as produced by [`save`][].

    Returns:
        A new instance of whichever concrete type wrote the tag.

    Raises:
        ValueError: If the stream is not a qubosolver file, or if its type
            tag is missing or unrecognized.
        TypeError: If the loaded instance's type is not `cls` or a subclass thereof.

    Example:
        ```python
        from pathlib import Path
        from qubosolver import Instance
        from qubosolver.transforms import variable_fixing

        file = Path("instance.bin")
        instance = variable_fixing.Instance(Instance())

        with file.open("wb") as f:
            instance.save(f)

        # Three ways to load it back, from least to most strict:
        with file.open("rb") as f:
            loaded = Instance.load(f)                  # accepts any Instance subtype
            # loads, then narrows (fails after loading)
            loaded = Instance.load(f).variable_fixing
            loaded = variable_fixing.Instance.load(f)  # narrows first (fails before loading)
        ```
    """
    with io_utils.open(file_like, "rb") as f:
        io_utils.load_header(f)
        tag = io_utils.load_string(f)
        target_cls = Instance._registry.get(tag)
        if target_cls is None:
            msg = f"Cannot load Instance: unrecognized type tag {tag!r}."
            raise ValueError(msg)
        instance = target_cls._read_body(f)
    if not isinstance(instance, cls):
        msg = (
            f"Cannot load {cls.__module__}.{cls.__qualname__}: "
            f"stream contains a {type(instance).__module__}.{type(instance).__qualname__}."
        )
        raise TypeError(msg)
    return instance

save

save(file_like: FileLike[bytes]) -> None

Serialize this instance to file_like, tagged with its type.

Parameters:

Example
from pathlib import Path

with Path("instance.bin").open("wb") as f:
    instance.save(f)
Source code in qubosolver/types/instance.py
def save(self, file_like: FileLike[bytes]) -> None:
    """Serialize this instance to ``file_like``, tagged with its type.

    Args:
        file_like: Destination — a file path ([`str`][] or [`os.PathLike`][]),
            or a binary-writable [`typing.IO`][] stream.

    Example:
        ```python
        from pathlib import Path

        with Path("instance.bin").open("wb") as f:
            instance.save(f)
        ```
    """
    with io_utils.open(file_like, "wb") as f:
        io_utils.save_header(f)
        io_utils.save_string(f, self._tag())
        self._write_body(f)

apply

apply(instance: qubosolver.Instance, fixation_rules: Sequence[Rule] = (hansen_fixing,), *, inplace: bool = False) -> Instance

Apply each fixation rule once and reduce the QUBO matrix accordingly.

Each rule in fixation_rules is called in order; variables it identifies are immediately fixed and the matrix is reduced before the next rule runs.

Parameters:

  • instance (qubosolver.Instance) –

    The QUBO instance to reduce.

  • fixation_rules (Sequence[Rule], default: (hansen_fixing,) ) –

    Ordered sequence of Rule callables.

  • inplace (bool, default: False ) –

    If False (default), wraps instance in a new variable-fixing Instance before modifying it.

Returns:

  • Instance –

    The reduced instance with updated fixation history.

Source code in qubosolver/transforms/variable_fixing.py
def apply(
    instance: qubosolver.Instance,
    fixation_rules: Sequence[Rule] = (hansen_fixing,),
    *,
    inplace: bool = False,
) -> Instance:
    """Apply each fixation rule once and reduce the QUBO matrix accordingly.

    Each rule in `fixation_rules` is called in order; variables it identifies
    are immediately fixed and the matrix is reduced before the next rule runs.

    Args:
        instance: The QUBO instance to reduce.
        fixation_rules: Ordered sequence of [`Rule`][] callables.
        inplace: If ``False`` (default), wraps `instance` in a new
            variable-fixing [`Instance`][] before modifying it.

    Returns:
        The reduced instance with updated fixation history.
    """
    if not inplace:
        instance = Instance(instance)

    instance = instance.variable_fixing

    for rule in fixation_rules:
        fixed = rule(instance)
        _reduce_qubo(instance, fixed, inplace=True)

    if instance.size == 0:
        logger.info("Variable fixing reduced the instance to zero variables.")

    return instance

apply_recursively

apply_recursively(instance: qubosolver.Instance, fixation_rules: Sequence[Rule] = (hansen_fixing,), *, inplace: bool = False) -> Instance

Apply fixation rules repeatedly until no further variables can be fixed.

Calls apply in a loop; stops when a full pass over all rules fixes no additional variables.

Parameters:

  • instance (qubosolver.Instance) –

    The QUBO instance to reduce.

  • fixation_rules (Sequence[Rule], default: (hansen_fixing,) ) –

    Ordered sequence of [Rule] callables.

  • inplace (bool, default: False ) –

    If False (default), wraps instance in a new variable-fixing Instance before modifying it.

Returns:

  • Instance –

    The fully reduced instance.

Source code in qubosolver/transforms/variable_fixing.py
def apply_recursively(
    instance: qubosolver.Instance,
    fixation_rules: Sequence[Rule] = (hansen_fixing,),
    *,
    inplace: bool = False,
) -> Instance:
    """Apply fixation rules repeatedly until no further variables can be fixed.

    Calls [`apply`][] in a loop; stops when a full pass over all rules
    fixes no additional variables.

    Args:
        instance: The QUBO instance to reduce.
        fixation_rules: Ordered sequence of [`Rule`] callables.
        inplace: If ``False`` (default), wraps `instance` in a new
            variable-fixing [`Instance`][] before modifying it.

    Returns:
        The fully reduced instance.
    """
    if not inplace:
        instance = Instance(instance)

    instance = instance.variable_fixing

    while True:
        prev_n_fixations = len(instance._fixed_indices)
        apply(instance, fixation_rules, inplace=True)
        n_fixations = len(instance._fixed_indices)
        assert n_fixations >= prev_n_fixations  # nosec B101
        if n_fixations == prev_n_fixations:
            return instance

hansen_fixing

hansen_fixing(instance: qubosolver.Instance) -> dict[int, int]

Identify variables that can be fixed using Hansen's bounding criterion.

For each variable i, computes a lower bound c_i + 2 * sum(min(0, Q_ij)) and an upper bound c_i + 2 * sum(max(0, Q_ij)) from the diagonal and off-diagonal elements of the QUBO matrix. A variable is fixed to 0 when its lower bound is non-negative (it cannot improve the objective by being 1) and to 1 when its upper bound is non-positive (it can only improve it).

Parameters:

Returns:

  • dict[int, int] –

    Mapping of variable index to fixed value (0 or 1). Variables that cannot be fixed are omitted.

Source code in qubosolver/transforms/variable_fixing.py
def hansen_fixing(instance: qubosolver.Instance) -> dict[int, int]:
    """Identify variables that can be fixed using Hansen's bounding criterion.

    For each variable *i*, computes a lower bound
    ``c_i + 2 * sum(min(0, Q_ij))`` and an upper bound
    ``c_i + 2 * sum(max(0, Q_ij))`` from the diagonal and off-diagonal
    elements of the QUBO matrix.  A variable is fixed to 0 when its lower
    bound is non-negative (it cannot improve the objective by being 1) and
    to 1 when its upper bound is non-positive (it can only improve it).

    Args:
        instance: The QUBO instance to analyze.

    Returns:
        Mapping of variable index to fixed value (``0`` or ``1``).
            Variables that cannot be fixed are omitted.
    """
    fixed_dict: dict[int, int] = {}
    size: int = cast("int", instance.size)
    epsilon: float = 1e-8  # Tolerance to avoid floating-point precision issues

    for i in range(size):
        ci = instance.matrix[i, i].item()  # Diagonal element

        q_minus = sum(min(0, instance.matrix[i, j].item()) for j in range(size) if j != i)
        q_plus = sum(max(0, instance.matrix[i, j].item()) for j in range(size) if j != i)

        if ci + q_minus * 2 >= -epsilon:
            fixed_dict[i] = 0
        elif ci + q_plus * 2 <= epsilon:
            fixed_dict[i] = 1

    return fixed_dict

lift

lift(reduced_solution: Solution, reduced_instance: Instance) -> Solution

Reconstruct the full solution by reinserting fixed variables.

Reverses the fixation history stored in reduced_instance: fixed variables are reinserted at their original positions in each bitstring, and costs are recomputed against the original (unreduced) QUBO matrix.

If no variables were fixed, returns a deep copy of reduced_solution unchanged.

Parameters:

  • reduced_solution (Solution) –

    Solution obtained from solving the reduced QUBO.

  • reduced_instance (Instance) –

    The reduced instance carrying the fixation history and a reference to the original instance.

Returns:

  • Solution –

    A new solution with full-length bitstrings and costs evaluated against the original QUBO matrix. Counts and probabilities are carried over from reduced_solution.

Source code in qubosolver/transforms/variable_fixing.py
def lift(reduced_solution: Solution, reduced_instance: Instance) -> Solution:
    """Reconstruct the full solution by reinserting fixed variables.

    Reverses the fixation history stored in `reduced_instance`: fixed variables
    are reinserted at their original positions in each bitstring, and costs
    are recomputed against the original (unreduced) QUBO matrix.

    If no variables were fixed, returns a deep copy of `reduced_solution`
    unchanged.

    Args:
        reduced_solution: Solution obtained from solving the reduced QUBO.
        reduced_instance: The reduced instance carrying the fixation
            history and a reference to the original instance.

    Returns:
        A new solution with full-length
            bitstrings and costs evaluated against the original QUBO matrix.
            Counts and probabilities are carried over from `reduced_solution`.
    """
    if not reduced_solution:
        return Solution()

    bitstrings_list = reduced_solution.bitstrings.tolist()

    def reinsert_fixed_variables(bitstring: list[int]) -> list[int]:
        for fixation_dict in reversed(reduced_instance._fixed_indices):
            for position, bit_value in sorted(fixation_dict.items()):
                bitstring.insert(position, bit_value)
        return bitstring

    bits_to_reinsert = sum(len(fixation_dict) for fixation_dict in reduced_instance._fixed_indices)
    assert (bits_to_reinsert + len(bitstrings_list[0])) == reduced_instance._parent_instance.size  # nosec B101

    if bits_to_reinsert == 0:
        return copy.deepcopy(reduced_solution)

    solution = Solution()

    solution.bitstrings = bitstrings.tensor(
        [reinsert_fixed_variables(bitstring) for bitstring in bitstrings_list]
    )
    solution.costs = vector.tensor(
        [reduced_instance._parent_instance.cost(b) for b in solution.bitstrings]
    )
    solution.counts = reduced_solution.counts
    solution.probabilities = reduced_solution.probabilities

    return solution

qubosolver.transforms.zeroing

Zeroing fallback for QUBO negative off-diagonal coefficients.

Bit-flip preprocessing (see transforms.negative_bitflip) removes as much negative off-diagonal weight as possible, but some negative coefficients may remain when the problem is not fully bipartisable. Quantum (Rydberg) solvers cannot embed such coefficients, so this module offers a last-resort approximation: apply sets every remaining negative off-diagonal coefficient to zero and records which positions were zeroed in a zeroing Instance.

from qubosolver.transforms import negative_bitflip, zeroing

reduced_instance = negative_bitflip.apply(instance, time_limit_s=60.0)
# drop any negative coefficient bit flips could not remove
zeroed_instance = zeroing.apply(reduced_instance)
print(zeroed_instance.zeroed_edges)       # (N, 2) tensor of zeroed (i, j) index pairs

Classes:

Functions:

  • apply –

    Set remaining negative off-diagonal coefficients to zero.

  • lift –

    Map a solution of the zeroed QUBO back onto the pre-zeroing problem.

Instance

Instance(parent_instance: qubosolver.Instance)

A QUBO Instance recording zeroing history.

Records which off-diagonal coefficients were set to zero by apply by keeping the matrix of the removed negative coefficients (negative_matrix) rather than a single flag. Because the QUBO matrix is symmetric, each zeroed interaction appears twice in negative_matrix but once in zeroed_edges.

Parameters:

  • parent_instance (qubosolver.Instance) –

    The QUBO instance to extend with zeroing state.

Methods:

  • __init_subclass__ –

    Register cls under its _tag so load can dispatch to it.

  • __len__ –

    Number of binary variables in the QUBO problem (same as size).

  • cost –

    Compute the QUBO objective \(x^T Q x\) for a candidate solution \(x\).

  • load –

    Deserialize an Instance previously saved with save.

  • save –

    Serialize this instance to file_like, tagged with its type.

Attributes:

Source code in qubosolver/transforms/zeroing.py
def __init__(self, parent_instance: qubosolver.Instance) -> None:
    """Initialize from a QUBO instance, before any zeroing.

    Args:
        parent_instance: The QUBO instance to extend with zeroing state.
    """
    super().__init__(parent_instance.matrix.detach().clone())
    self._parent_instance = copy.deepcopy(parent_instance)
    self.negative_matrix: Matrix = torch.zeros_like(self._matrix)
    """Matrix of removed negative coefficients: same (symmetric) shape as the
    QUBO matrix, holding the original values at zeroed positions and 0 elsewhere."""

matrix property

matrix: Matrix

The QUBO symmetric matrix.

Returns:

  • Matrix –

    QUBO symmetric matrix of shape (size, size).

Raises:

  • AssertionError –

    If the internal tensor is not 2-D or not square.

negative_bitflip property

negative_bitflip: negative_bitflip.Instance

View of this instance as a negative-bitflip instance.

Convenience property to avoid the boilerplate of assert isinstance(instance, negative_bitflip.Instance) before calling a method specific to that subclass. It exists purely to satisfy static type checkers (mypy) and enable IDE code completion — the runtime isinstance check and the TypeError below just mirror the guarantee that the assert would otherwise provide.

Returns:

  • negative_bitflip.Instance –

    This instance, narrowed to the negative-bitflip subclass.

Raises:

negative_matrix instance-attribute

negative_matrix: Matrix = torch.zeros_like(self._matrix)

Matrix of removed negative coefficients: same (symmetric) shape as the QUBO matrix, holding the original values at zeroed positions and 0 elsewhere.

size property

size: int

Number of binary variables in the QUBO problem.

variable_fixing property

variable_fixing: variable_fixing.Instance

View of this instance as a variable-fixing instance.

Convenience property to avoid the boilerplate of assert isinstance(instance, variable_fixing.Instance) before calling a method specific to that subclass. It exists purely to satisfy static type checkers (mypy) and enable IDE code completion — the runtime isinstance check and the TypeError below just mirror the guarantee that the assert would otherwise provide.

Returns:

  • variable_fixing.Instance –

    This instance, narrowed to the variable-fixing subclass.

Raises:

zeroed_edges property

zeroed_edges: torch.Tensor

The zeroed interactions as an (N, 2) tensor of (i, j) index pairs.

Each symmetric pair is reported once (i < j); N is the number of zeroed off-diagonal interactions.

zeroing property

zeroing: zeroing.Instance

View of this instance as a zeroing instance.

Convenience property to avoid the boilerplate of assert isinstance(instance, zeroing.Instance) before calling a method specific to that subclass. It exists purely to satisfy static type checkers (mypy) and enable IDE code completion — the runtime isinstance check and the TypeError below just mirror the guarantee that the assert would otherwise provide.

Returns:

  • zeroing.Instance –

    This instance, narrowed to the zeroing subclass.

Raises:

__init_subclass__

__init_subclass__(**kwargs: object) -> None

Register cls under its _tag so load can dispatch to it.

Automatic, so a new Instance subclass never needs to be added to a separate registry by hand.

Source code in qubosolver/types/instance.py
def __init_subclass__(cls, **kwargs: object) -> None:
    """Register `cls` under its `_tag` so [`load`][] can dispatch to it.

    Automatic, so a new `Instance` subclass never needs to be added to a
    separate registry by hand.
    """
    super().__init_subclass__(**kwargs)
    Instance._registry[cls._tag()] = cls

__len__

__len__() -> int

Number of binary variables in the QUBO problem (same as size).

Source code in qubosolver/types/instance.py
def __len__(self) -> int:
    """Number of binary variables in the QUBO problem (same as [`size`][])."""
    return self.size

cost

cost(solution: Bitstring) -> float

Compute the QUBO objective \(x^T Q x\) for a candidate solution \(x\).

Parameters:

  • solution (Bitstring) –

    Binary vector \(x\) of shape (size,).

Returns:

  • float –

    Scalar cost value.

Source code in qubosolver/types/instance.py
def cost(self, solution: Bitstring) -> float:
    """Compute the QUBO objective $x^T Q x$ for a candidate solution $x$.

    Args:
        solution: Binary vector $x$ of shape ``(size,)``.

    Returns:
        Scalar cost value.
    """
    # Import here to avoid circular imports
    from qubosolver.utils import _costs  # noqa: PLC0415 (import cycle)

    cost = _costs.quadratic_cost(solution, self.matrix)
    assert type(cost) is float  # nosec B101
    return cost

load classmethod

load(file_like: FileLike[bytes]) -> Self

Deserialize an Instance previously saved with save.

Called on the base class qubosolver.Instance, it loads any instance with automatic dispatch.

Called on a subclass (e.g. variable_fixing.Instance.load(f)), it additionally requires the loaded Instance to be an instance of that subclass (raising TypeError otherwise).

Parameters:

  • file_like (FileLike[bytes]) –

    Source file path or readable binary file object, as produced by save.

Returns:

  • Self –

    A new instance of whichever concrete type wrote the tag.

Raises:

  • ValueError –

    If the stream is not a qubosolver file, or if its type tag is missing or unrecognized.

  • TypeError –

    If the loaded instance's type is not cls or a subclass thereof.

Example
from pathlib import Path
from qubosolver import Instance
from qubosolver.transforms import variable_fixing

file = Path("instance.bin")
instance = variable_fixing.Instance(Instance())

with file.open("wb") as f:
    instance.save(f)

# Three ways to load it back, from least to most strict:
with file.open("rb") as f:
    loaded = Instance.load(f)                  # accepts any Instance subtype
    # loads, then narrows (fails after loading)
    loaded = Instance.load(f).variable_fixing
    loaded = variable_fixing.Instance.load(f)  # narrows first (fails before loading)
Source code in qubosolver/types/instance.py
@classmethod
def load(cls, file_like: FileLike[bytes]) -> Self:
    """Deserialize an [`Instance`][] previously saved with [`save`][].

    Called on the base class [`qubosolver.Instance`][], it loads any instance with
    automatic dispatch.

    Called on a subclass (e.g.
    [`variable_fixing.Instance.load(f)`][qubosolver.transforms.variable_fixing.Instance.load]),
    it additionally requires the loaded `Instance` to be an instance of that subclass
    (raising [`TypeError`][] otherwise).

    Args:
        file_like: Source file path or readable binary file object,
            as produced by [`save`][].

    Returns:
        A new instance of whichever concrete type wrote the tag.

    Raises:
        ValueError: If the stream is not a qubosolver file, or if its type
            tag is missing or unrecognized.
        TypeError: If the loaded instance's type is not `cls` or a subclass thereof.

    Example:
        ```python
        from pathlib import Path
        from qubosolver import Instance
        from qubosolver.transforms import variable_fixing

        file = Path("instance.bin")
        instance = variable_fixing.Instance(Instance())

        with file.open("wb") as f:
            instance.save(f)

        # Three ways to load it back, from least to most strict:
        with file.open("rb") as f:
            loaded = Instance.load(f)                  # accepts any Instance subtype
            # loads, then narrows (fails after loading)
            loaded = Instance.load(f).variable_fixing
            loaded = variable_fixing.Instance.load(f)  # narrows first (fails before loading)
        ```
    """
    with io_utils.open(file_like, "rb") as f:
        io_utils.load_header(f)
        tag = io_utils.load_string(f)
        target_cls = Instance._registry.get(tag)
        if target_cls is None:
            msg = f"Cannot load Instance: unrecognized type tag {tag!r}."
            raise ValueError(msg)
        instance = target_cls._read_body(f)
    if not isinstance(instance, cls):
        msg = (
            f"Cannot load {cls.__module__}.{cls.__qualname__}: "
            f"stream contains a {type(instance).__module__}.{type(instance).__qualname__}."
        )
        raise TypeError(msg)
    return instance

save

save(file_like: FileLike[bytes]) -> None

Serialize this instance to file_like, tagged with its type.

Parameters:

Example
from pathlib import Path

with Path("instance.bin").open("wb") as f:
    instance.save(f)
Source code in qubosolver/types/instance.py
def save(self, file_like: FileLike[bytes]) -> None:
    """Serialize this instance to ``file_like``, tagged with its type.

    Args:
        file_like: Destination — a file path ([`str`][] or [`os.PathLike`][]),
            or a binary-writable [`typing.IO`][] stream.

    Example:
        ```python
        from pathlib import Path

        with Path("instance.bin").open("wb") as f:
            instance.save(f)
        ```
    """
    with io_utils.open(file_like, "wb") as f:
        io_utils.save_header(f)
        io_utils.save_string(f, self._tag())
        self._write_body(f)

apply

apply(instance: qubosolver.Instance) -> Instance

Set remaining negative off-diagonal coefficients to zero.

Approximates the QUBO by dropping any negative off-diagonal coefficient that bit flips could not remove, so a quantum solver can embed it. Returns a Instance whose negative_matrix holds the removed coefficients (an all-zero matrix when nothing was zeroed).

Parameters:

Returns:

Source code in qubosolver/transforms/zeroing.py
def apply(instance: qubosolver.Instance) -> Instance:
    """Set remaining negative off-diagonal coefficients to zero.

    Approximates the QUBO by dropping any negative off-diagonal coefficient that
    bit flips could not remove, so a quantum solver can embed it.  Returns a
    [`Instance`][qubosolver.transforms.zeroing.Instance] whose
    [`negative_matrix`][qubosolver.transforms.zeroing.Instance.negative_matrix]
    holds the removed coefficients (an all-zero matrix when nothing was zeroed).

    Args:
        instance: The QUBO instance to zero.

    Returns:
        A zeroing instance.
    """
    zeroed_instance = Instance(instance)

    Q = instance.matrix
    n = Q.shape[0]
    offdiag_mask = ~torch.eye(n, dtype=torch.bool, device=Q.device)
    negative_mask = offdiag_mask & (Q < 0)

    zeroed_instance.negative_matrix[negative_mask] = Q[negative_mask]
    zeroed_instance._matrix[negative_mask] = 0.0

    return zeroed_instance

lift

lift(zeroed_solution: Solution, zeroed_instance: Instance) -> Solution

Map a solution of the zeroed QUBO back onto the pre-zeroing problem.

Zeroing only drops coefficients; it does not rename or remove variables, so the bitstrings themselves are kept. Costs are recomputed against the pre-zeroing matrix (_parent_instance) so they reflect the true, non- approximated objective rather than the zeroed one, and the candidates are re-sorted by that cost, since the order on the zeroed matrix may differ. When nothing was zeroed, returns a deep copy of zeroed_solution unchanged.

Parameters:

  • zeroed_solution (Solution) –

    Solution obtained on the zeroed QUBO.

  • zeroed_instance (Instance) –

    The zeroed instance produced by apply.

Returns:

  • Solution –

    A new solution with costs evaluated against the pre-zeroing matrix, sorted by ascending cost.

Source code in qubosolver/transforms/zeroing.py
def lift(zeroed_solution: Solution, zeroed_instance: Instance) -> Solution:
    """Map a solution of the zeroed QUBO back onto the pre-zeroing problem.

    Zeroing only drops coefficients; it does not rename or remove variables, so
    the bitstrings themselves are kept.  Costs are recomputed against the
    pre-zeroing matrix (``_parent_instance``) so they reflect the true, non-
    approximated objective rather than the zeroed one, and the candidates are
    re-sorted by that cost, since the order on the zeroed matrix may differ.
    When nothing was zeroed, returns a deep copy of `zeroed_solution` unchanged.

    Args:
        zeroed_solution: Solution obtained on the zeroed QUBO.
        zeroed_instance: The zeroed instance produced by [`apply`][].

    Returns:
        A new solution with costs evaluated against the pre-zeroing matrix,
            sorted by ascending cost.
    """
    if not zeroed_instance.zeroed_edges.numel():
        return copy.deepcopy(zeroed_solution)

    solution = Solution()
    solution.bitstrings = zeroed_solution.bitstrings
    solution.counts = zeroed_solution.counts
    solution.probabilities = zeroed_solution.probabilities
    solution._compute_costs(zeroed_instance._parent_instance.matrix)._sort_by_cost()

    return solution