Skip to content

mis

source package mis

Maximum Independent Set is a Python library that provides quantum solvers for the Maximum Independent Set problem.

The Maximum Independent Set problem (or MIS) is a graph optimization problem with applications to numerous fields, e.g. scheduling, constraint solving, etc. The input of this problem is a set of nodes and a set of conflicts between these nodes. Solving MIS is finding the largest set of nodes that do not have conflicts. This problem is well-known for being NP-hard -- in other words, there are no known exact, non-exponential algorithms that can reliably solve the problem, forcing entire industries to rely upon heuristics. Quantum computers offer alternative approaches to solving a number of problems, including MIS, in reasonable time.

The core of the library is a set of MIS solvers developed to be used on quantum devices, including quantum computers, for users who have access to one, or quantum emulators, for users who do not. We also provide non-quantum MIS solvers for benchmarking purposes.

Classes

  • Execution — A task being sent to a quantum device and which may need some time before it is completed.

  • MISInstance

  • SolverConfig — Configuration class for setting up solver parameters.

source class Execution()

Bases : abc.ABC, Generic[Result]

A task being sent to a quantum device and which may need some time before it is completed.

Methods

  • result

  • wait

  • status

  • map — Apply a transformation to the result once it is complete.

  • success — Shortcut to return a result that has already succeeded.

source method Execution.result() → Result

source async method Execution.wait(self) → Result

source method Execution.status() → Status

source method Execution.map(transform: Callable[[Result], Transformed]) → Execution[Transformed]

Apply a transformation to the result once it is complete.

source classmethod Execution.success(result: Result) → Execution[Result]

Shortcut to return a result that has already succeeded.

Failure

'MISSolver' not found in 'mis'.

Failure

'MISSolver.solve' not found in 'mis'.

source class MISInstance(graph: networkx.Graph)

Methods

  • draw — Draw instance graph with highlighted nodes.

source method MISInstance.draw(nodes: list[int] | None = None, node_size: int = 600, highlight_color: str = 'darkgreen', font_family: str = 'Century Gothic') → None

Draw instance graph with highlighted nodes.

Parameters

  • ```

  • nodes : list[int] — List of nodes to highlight.

  • node_size : int — Size of drawn nodes in drawn graph. (default: 600)

  • highlight_color : str — Color to highlight nodes with. (default: "darkgreen")

  • ```

Raises

  • Exception

source dataclass SolverConfig(use_quantum: bool = False, backend: BaseBackend | None = None, method: MethodType = MethodType.EAGER, max_iterations: int = 1, max_number_of_solutions: int = 1, device: Device | None = None, embedder: BaseEmbedder | None = None, pulse_shaper: BasePulseShaper | None = None, preprocessor: Callable[[nx.Graph], BasePreprocessor] | None = field(default_factory=default_preprocessor), postprocessor: Callable[[], BasePostprocessor] | None = default_postprocessor, greedy: GreedyConfig = field(default_factory=GreedyConfig))

Configuration class for setting up solver parameters.

Attributes

  • use_quantum : bool — Whether to use quantum hardware or simulation for solving.

  • backend : BaseBackend | None — Backend configuration to use. If None, use a non-quantum heuristic solver.

  • method : MethodType — The method used to solve this instance of MIS.

  • max_iterations : int — Maximum number of iterations allowed for solving.

  • max_number_of_solutions : int — A maximal number of solutions to return.

  • device : Device | None — Quantum device to execute the code in. If unspecified, use a reasonable default device.

  • embedder : BaseEmbedder | None — If specified, an embedder, i.e. a mechanism used to customize the layout of neutral atoms on the quantum device. Ignored for non-quantum backends.

  • pulse_shaper : BasePulseShaper | None — If specified, a pulse shaper, i.e. a mechanism used to customize the laser pulse to which the neutral atoms are subjected during the execution of the quantum algorithm. Ignored for non-quantum backends.

  • preprocessor : Callable[[nx.Graph], BasePreprocessor] | None — A graph preprocessor, used to decrease the size of the graph (hence the duration of actual resolution) by applying heuristics prior to embedding on a quantum device.

  • postprocessor : Callable[[], BasePostprocessor] | None — A postprocessor used to sort out and improve results.

  • greedy : GreedyConfig — If specified, use this for solving the GreedyMIS. Needs to be specified when method is GreedyMIS