mis.pipeline.maximization
source module 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)
Bases : BasePostprocessor
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.