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

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.

  • node_index — Return the index for a node in the original graph.

  • node_indices — Return the indices for nodes in the original graph.

source method MISInstance.draw(nodes: list[int] | None = None, node_size: int = 600, highlight_color: str = 'darkgreen', font_family: str = 'serif') → 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 method MISInstance.node_index(node: Any) → int

Return the index for a node in the original graph.

source method MISInstance.node_indices(nodes: list[Any]) → list[int]

Return the indices for nodes in the original graph.

source class MISSolution(instance: MISInstance, nodes: list[int], frequency: float)

A solution to a MIS problem.

Attributes

  • instance : MISInstance — The MIS instance to which this class represents a solution.

  • size : int — The number of nodes in this solution.

  • node_indices : list[int] — The indices of the nodes of instance picked in this solution.

  • nodes : list[Any] — The nodes of instance picked in this solution.

  • frequency : float — How often this solution showed up in the measures, where 0. represents a solution that never showed up in the meaures and 1. a solution that showed up in all measures.

Methods

  • draw — Draw instance graph with solution nodes highlighted.

source method MISSolution.draw(node_size: int = 600, highlight_color: str = 'darkgreen', font_family: str = 'serif') → None

Draw instance graph with solution nodes highlighted.

Parameters

  • ```

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

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

  • font : str — Font type

  • ```

source dataclass SolverConfig(backend: BaseBackend | BackendConfig | None = None, weighting: Weighting = Weighting.UNWEIGHTED, 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[[SolverConfig, nx.Graph], BasePreprocessor] | None = field(default_factory=default_preprocessor), postprocessor: Callable[[SolverConfig], BasePostprocessor] | None = field(default_factory=default_postprocessor), greedy: GreedyConfig = field(default_factory=GreedyConfig), runs: int = 500)

Configuration class for setting up solver parameters.

Attributes

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

  • weighting : Weighting — The weighting policy for this solver, i.e. should it attempt to maximize size of the solution (by number of nodes, ignoring weights) or maximizing the total weight of the solution (the sum of weights of individual nodes, ignoring the number of nodes).

  • 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[[SolverConfig, 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[[SolverConfig], 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

  • runs : int — When using a quantum backend, how many times we repeat each quantum run. Since quantum executions are non-deterministic, higher numbers increases the reliability of the result, but also the duration until the results are available.

class BackendConfig(**data: Any)

Bases : pydantic.BaseModel

Generic configuration for backends.

Create a new model by parsing and validating input data from keyword arguments.

Raises [ValidationError][pydantic_core.ValidationError] if the input data cannot be validated to form a valid model.

self is explicitly positional-only to allow self as a field name.

Attributes

  • model_config : ClassVar[ConfigDict] — Configuration for the model, should be a dictionary conforming to [ConfigDict][pydantic.config.ConfigDict].

  • model_extra : dict[str, Any] | None — Get extra fields set during validation.

  • model_fields_set : set[str] — Returns the set of fields that have been explicitly set on this model instance.

  • backend : BackendType — The type of backend to use.

  • username : str | None — For a backend that requires authentication, such as Pasqal Cloud,.

  • password : str | None — For a backend that requires authentication, such as Pasqal Cloud,.

  • project_id : str | None — For a backend that associates jobs to projects, such as Pasqal Cloud,.

  • device : NamedDevice | DeviceType | None

  • dt : int — For a backend that supports customizing the duration of steps, the.

  • wait : bool — For a remote backend where we submit a batch of jobs,.

enum BackendType()

Bases : StrEnum

Type of backend to use for solving the QUBO.

Attributes

  • QUTIP

  • REMOTE_QPU

  • REMOTE_EMUMPS

  • REMOTE_EMUTN

  • REMOTE_EMUFREE

  • EMU_MPS

  • EMU_SV

source dataclass GreedyConfig(default_solving_threshold: int = 2, subgraph_quantity: int = 5, mis_sample_quantity: int = 1)

Configuration for greedy solving strategies.

Attributes

  • default_solving_threshold : int — Size threshold (number of nodes) for using MIS solving when greedy method is used.

  • subgraph_quantity : int — Number of candidate subgraphs to generate during greedy mapping.

  • mis_sample_quantity : int — Number of MIS solutions to sample per iteration (if applicable).

source enum MethodType()

Bases : str, Enum

The method used to extract the MIS.

Attributes

  • EAGER — An eager solver that attempts to extract a MIS in a single shot.

  • GREEDY — A greedy solver that decomposes the graph into smaller subgraphs that can benefit from device-specific physical layouts.

source enum Weighting()

Bases : str, Enum

The algorithm used by the solver.

Attributes

  • UNWEIGHTED — Unweighted Maximum Independent Set

  • WEIGHTED — Weighted Maximum Independent Set