Name | maximum-independent-set JSON |
Version |
0.2.0
JSON |
| download |
home_page | None |
Summary | A Python library designed to help users design classical- and quantum-driven solutions for the Maximum Independent Set (MIS) problem. |
upload_time | 2025-07-16 11:17:00 |
maintainer | None |
docs_url | None |
author | None |
requires_python | <3.13,>=3.10 |
license | MIT-derived |
keywords |
quantum
|
VCS |
 |
bugtrack_url |
|
requirements |
No requirements were recorded.
|
Travis-CI |
No Travis.
|
coveralls test coverage |
No coveralls.
|
[](https://pypi.org/project/maximum-independent-set/)
[](https://github.com/pasqal-io/maximum-independent-set/actions/workflows/test.yml)

# Maximum independent set
The [Maximum Independent Set](https://en.wikipedia.org/wiki/Independent_set_(graph_theory)) problem (MIS) is a standard and widespread graph problem in scheduling, network theory, error correction, and even in the quantum sector as part of more general optimization algorithms (e.g., QUBO formulations) or as a benchmark on quantum annealers or neutral atom devices.
There is currently no known polynomial-time algorithm for general graphs running on classical (non-quantum) devices, which means that, in practice, finding an exact solution for large graphs is generally not possible due to time and hardware limitations. For this reason, most applications of MIS must satisfy themselves with finding approximate solutions. As it turns out, in some cases, even finding approximate solutions is considered hard. For these reasons, there is high interest in solving MIS on quantum devices.
The maximum-independent-set library provides the means to achieve this: it compiles an MIS into a form suited for execution on existing analog quantum hardware, such as the commercial QPUs produced by Pasqal. It is designed for **scientists and engineers** working on optimization problems—**no quantum computing knowledge required** and **no quantum computer needed** for testing.
This library lets users treat the solver as a **black box**: feed in a graph of interest, get back an optimal (or near-optimal) independent set. For more advanced users, it offers tools to **fine-tune algorithmic strategies**, leverage **quantum hardware** via the Pasqal cloud, or even **experiment with custom quantum sequences** and processing pipelines.
Users setting their first steps into quantum computing will learn how to implement the core algorithm in a few simple steps and run it using the Pasqal Neutral Atom QPU. More experienced users will find this library to provide the right environment to explore new ideas - both in terms of methodologies and data domain - while always interacting with a simple and intuitive QPU interface.
This library is actively used to solve real-world projects. We have applied it to optimize the layout and costs of [5G network deployments](https://www.pasqal.com/blog/reducing-the-costs-of-deploying-a-5g-network-with-a-hybrid-classical-quantum-approach/), [schedule satellite missions with Thales](https://www.pasqal.com/success-story/thales/), and [improve charging network planning for electric vehicles with EDF](https://www.pasqal.com/success-story/edf/). These case studies highlight how quantum-based MIS solutions can tackle complex challenges across telecom, aerospace and energy sectors.
## Installation
### Using `hatch`, `uv` or any pyproject-compatible Python manager
Edit file `pyproject.toml` to add the line
```
"maximum-independent-set"
```
to the list of `dependencies`.
### Using `pip` or `pipx`
To install the `pipy` package using `pip` or `pipx`
1. Create a `venv` if that's not done yet
```sh
$ python -m venv venv
```
2. Enter the venv
```sh
$ . venv/bin/activate
```
3. Install the package
```sh
$ pip install maximum-independent-set
# or
$ pipx install maximum-independent-set
```
## QuickStart
```python
from mis import MISSolver, MISInstance, BackendConfig, SolverConfig
import networkx as nx
# Generate a simple graph (here, a triangle)
graph = nx.Graph()
graph.add_edges_from([(0, 1), (0, 2)])
instance = MISInstance(graph)
# Use a default quantum backend.
config = SolverConfig(backend=BackendConfig())
solver = MISSolver(instance, config)
# Solve the MIS problem.
results = solver.solve()
# Show the results.
print("MIS solutions:", results)
results[0].draw()
```
## Documentation
[Documentation](https://pasqal-io.github.io/maximum-independent-set/latest/)
[Tutorials](https://pasqal-io.github.io/maximum-independent-set/latest/tutorial%201a%20-%20Using%20a%20Quantum%20Device%20to%20solve%20MIS/).
[Full API documentation](https://pasqal-io.github.io/maximum-independent-set/latest/api/mis/).
## Getting in touch
- [Pasqal Community Portal](https://community.pasqal.com/) (forums, chat, tutorials, examples, code library).
- [GitHub Repository](https://github.com/pasqal-io/maximum-independent-set) (source code, issue tracker).
- [Professional Support](https://www.pasqal.com/contact-us/) (if you need tech support, custom licenses, a variant of this library optimized for your workload, your own QPU, remote access to a QPU, ...)
Raw data
{
"_id": null,
"home_page": null,
"name": "maximum-independent-set",
"maintainer": null,
"docs_url": null,
"requires_python": "<3.13,>=3.10",
"maintainer_email": null,
"keywords": "quantum",
"author": null,
"author_email": "Manu Lahariya <manu.lahariya@pasqal.com>, David Teller <david.teller@pasqal.com>, Roland Guichard <roland.guichard@pasqal.com>",
"download_url": "https://files.pythonhosted.org/packages/a2/b7/184090731f8980333c9a48534f7ad761648323d7f22898f2213f0a86c1c0/maximum_independent_set-0.2.0.tar.gz",
"platform": null,
"description": "[](https://pypi.org/project/maximum-independent-set/)\n[](https://github.com/pasqal-io/maximum-independent-set/actions/workflows/test.yml)\n\n\n\n# Maximum independent set\n\nThe [Maximum Independent Set](https://en.wikipedia.org/wiki/Independent_set_(graph_theory)) problem (MIS) is a standard and widespread graph problem in scheduling, network theory, error correction, and even in the quantum sector as part of more general optimization algorithms (e.g., QUBO formulations) or as a benchmark on quantum annealers or neutral atom devices.\n\nThere is currently no known polynomial-time algorithm for general graphs running on classical (non-quantum) devices, which means that, in practice, finding an exact solution for large graphs is generally not possible due to time and hardware limitations. For this reason, most applications of MIS must satisfy themselves with finding approximate solutions. As it turns out, in some cases, even finding approximate solutions is considered hard. For these reasons, there is high interest in solving MIS on quantum devices.\n\nThe maximum-independent-set library provides the means to achieve this: it compiles an MIS into a form suited for execution on existing analog quantum hardware, such as the commercial QPUs produced by Pasqal. It is designed for **scientists and engineers** working on optimization problems\u2014**no quantum computing knowledge required** and **no quantum computer needed** for testing.\n\nThis library lets users treat the solver as a **black box**: feed in a graph of interest, get back an optimal (or near-optimal) independent set. For more advanced users, it offers tools to **fine-tune algorithmic strategies**, leverage **quantum hardware** via the Pasqal cloud, or even **experiment with custom quantum sequences** and processing pipelines.\n\nUsers setting their first steps into quantum computing will learn how to implement the core algorithm in a few simple steps and run it using the Pasqal Neutral Atom QPU. More experienced users will find this library to provide the right environment to explore new ideas - both in terms of methodologies and data domain - while always interacting with a simple and intuitive QPU interface.\n\nThis library is actively used to solve real-world projects. We have applied it to optimize the layout and costs of [5G network deployments](https://www.pasqal.com/blog/reducing-the-costs-of-deploying-a-5g-network-with-a-hybrid-classical-quantum-approach/), [schedule satellite missions with Thales](https://www.pasqal.com/success-story/thales/), and [improve charging network planning for electric vehicles with EDF](https://www.pasqal.com/success-story/edf/). These case studies highlight how quantum-based MIS solutions can tackle complex challenges across telecom, aerospace and energy sectors.\n\n## Installation\n\n### Using `hatch`, `uv` or any pyproject-compatible Python manager\n\nEdit file `pyproject.toml` to add the line\n\n```\n \"maximum-independent-set\"\n```\n\nto the list of `dependencies`.\n\n### Using `pip` or `pipx`\nTo install the `pipy` package using `pip` or `pipx`\n\n1. Create a `venv` if that's not done yet\n\n```sh\n$ python -m venv venv\n\n```\n\n2. Enter the venv\n\n```sh\n$ . venv/bin/activate\n```\n\n3. Install the package\n\n```sh\n$ pip install maximum-independent-set\n# or\n$ pipx install maximum-independent-set\n```\n\n## QuickStart\n\n```python\nfrom mis import MISSolver, MISInstance, BackendConfig, SolverConfig\nimport networkx as nx\n\n# Generate a simple graph (here, a triangle)\ngraph = nx.Graph()\ngraph.add_edges_from([(0, 1), (0, 2)])\ninstance = MISInstance(graph)\n\n# Use a default quantum backend.\nconfig = SolverConfig(backend=BackendConfig())\nsolver = MISSolver(instance, config)\n\n# Solve the MIS problem.\nresults = solver.solve()\n\n# Show the results.\nprint(\"MIS solutions:\", results)\nresults[0].draw()\n```\n\n## Documentation\n\n[Documentation](https://pasqal-io.github.io/maximum-independent-set/latest/)\n\n[Tutorials](https://pasqal-io.github.io/maximum-independent-set/latest/tutorial%201a%20-%20Using%20a%20Quantum%20Device%20to%20solve%20MIS/).\n\n[Full API documentation](https://pasqal-io.github.io/maximum-independent-set/latest/api/mis/).\n\n## Getting in touch\n\n- [Pasqal Community Portal](https://community.pasqal.com/) (forums, chat, tutorials, examples, code library).\n- [GitHub Repository](https://github.com/pasqal-io/maximum-independent-set) (source code, issue tracker).\n- [Professional Support](https://www.pasqal.com/contact-us/) (if you need tech support, custom licenses, a variant of this library optimized for your workload, your own QPU, remote access to a QPU, ...)\n",
"bugtrack_url": null,
"license": "MIT-derived",
"summary": "A Python library designed to help users design classical- and quantum-driven solutions for the Maximum Independent Set (MIS) problem.",
"version": "0.2.0",
"project_urls": {
"Issues": "https://github.com/pasqal-io/maximum-independent-set/issues",
"Source": "https://github.com/pasqal-io/maximum-independent-set"
},
"split_keywords": [
"quantum"
],
"urls": [
{
"comment_text": null,
"digests": {
"blake2b_256": "55e8903290bb551de849b2aa6d84a376a2ee07a2586082143149a8b9d5e0432b",
"md5": "a5eb8d8a100dffb4da40dfe97fb398cf",
"sha256": "ced9425e73bf798195373e71e807be0e238ea12b9d65adccea03e221f282524d"
},
"downloads": -1,
"filename": "maximum_independent_set-0.2.0-py3-none-any.whl",
"has_sig": false,
"md5_digest": "a5eb8d8a100dffb4da40dfe97fb398cf",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": "<3.13,>=3.10",
"size": 38391,
"upload_time": "2025-07-16T11:16:58",
"upload_time_iso_8601": "2025-07-16T11:16:58.814658Z",
"url": "https://files.pythonhosted.org/packages/55/e8/903290bb551de849b2aa6d84a376a2ee07a2586082143149a8b9d5e0432b/maximum_independent_set-0.2.0-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": null,
"digests": {
"blake2b_256": "a2b7184090731f8980333c9a48534f7ad761648323d7f22898f2213f0a86c1c0",
"md5": "25aa6d3d1c8d101b5f7d9ba59527219c",
"sha256": "49084e979847090578d8befce9a2d3b3508c9623cddbd7ffe3b952d574c36ab7"
},
"downloads": -1,
"filename": "maximum_independent_set-0.2.0.tar.gz",
"has_sig": false,
"md5_digest": "25aa6d3d1c8d101b5f7d9ba59527219c",
"packagetype": "sdist",
"python_version": "source",
"requires_python": "<3.13,>=3.10",
"size": 34099,
"upload_time": "2025-07-16T11:17:00",
"upload_time_iso_8601": "2025-07-16T11:17:00.573606Z",
"url": "https://files.pythonhosted.org/packages/a2/b7/184090731f8980333c9a48534f7ad761648323d7f22898f2213f0a86c1c0/maximum_independent_set-0.2.0.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2025-07-16 11:17:00",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "pasqal-io",
"github_project": "maximum-independent-set",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"lcname": "maximum-independent-set"
}