mis.pipeline.maximization

Classes

Maximization — A postprocessor dedicated to improving MIS results provided by a quantum algorithm.

source class Maximization(frequency_threshold: float = 1e-07, augment_rounds: int = 10, seed: int = 0)

A postprocessor dedicated to improving MIS results provided by a quantum algorithm.

This postprocessor expects that a result could be vulnerable to bitflips, so it will attempt to fix any result provided by the quantum algorithm, to make it independent (if it's not independent) and maximal (if it's not maximal).

frequency_threshold: Minimal frequency to check. Discard any solution which show up with a frequency <= frequency_threshold. Set 0 to never discard any solution. augment_rounds: The number of attempts to augment an independent set to add possibly missing nodes. seed: A random seed.

Methods

postprocess — The main entry point: attempt to improve a solution.
is_independent_solution — Check whether a solution is independent.
is_independent_list — Check whether a list of nodes within a graph is independent.
augment_to_maximal — Augment a given set up to a maximal IS using a greedy algorithm running k times.
reduce_to_independence — Reduce the given candidate solution to an independent state of graph g.

source method Maximization.postprocess(solution: MISSolution) → MISSolution | None

The main entry point: attempt to improve a solution.

source method Maximization.is_independent_solution(solution: MISSolution) → bool

Check whether a solution is independent.

source method Maximization.is_independent_list(graph: nx.Graph, nodes: list[int]) → bool

Check whether a list of nodes within a graph is independent.

source method Maximization.augment_to_maximal(solution: MISSolution) → MISSolution

Augment a given set up to a maximal IS using a greedy algorithm running k times.

See https://doi.org/10.48550/arXiv.2202.09372 section 2.3 of supplementary material for reference.

source method Maximization.reduce_to_independence(solution: MISSolution) → MISSolution

Reduce the given candidate solution to an independent state of graph g.

We progressively remove the nodes with highest number of neighbours.

See https://doi.org/10.48550/arXiv.2202.09372 section 2.3 of supplementary material for reference.