qReduMIS: A Quantum-Informed Reduction Algorithm for the Maximum Independent Set Problem
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915200314114048 |
|---|---|
| author | Schuetz, Martin J. A. Yalovetzky, Romina Andrist, Ruben S. Salton, Grant Sun, Yue Raymond, Rudy Chakrabarti, Shouvanik Acharya, Atithi Shaydulin, Ruslan Pistoia, Marco Katzgraber, Helmut G. |
| author_facet | Schuetz, Martin J. A. Yalovetzky, Romina Andrist, Ruben S. Salton, Grant Sun, Yue Raymond, Rudy Chakrabarti, Shouvanik Acharya, Atithi Shaydulin, Ruslan Pistoia, Marco Katzgraber, Helmut G. |
| contents | We propose and implement a quantum-informed reduction algorithm for the maximum independent set problem that integrates classical kernelization techniques with information extracted from quantum devices. Our larger framework consists of dedicated application, algorithm, and hardware layers, and easily generalizes to the maximum weight independent set problem. In this hybrid quantum-classical framework, which we call qReduMIS, the quantum computer is used as a co-processor to inform classical reduction logic about frozen vertices that are likely (or unlikely) to be in large independent sets, thereby opening up the reduction space after removal of targeted subgraphs. We systematically assess the performance of qReduMIS based on experiments with up to 231 qubits run on Rydberg quantum hardware available through Amazon Braket. Our experiments show that qReduMIS can help address fundamental performance limitations faced by a broad set of (quantum) solvers including Rydberg quantum devices. We outline implementations of qReduMIS with alternative platforms, such as superconducting qubits or trapped ions, and we discuss potential future extensions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_12551 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | qReduMIS: A Quantum-Informed Reduction Algorithm for the Maximum Independent Set Problem Schuetz, Martin J. A. Yalovetzky, Romina Andrist, Ruben S. Salton, Grant Sun, Yue Raymond, Rudy Chakrabarti, Shouvanik Acharya, Atithi Shaydulin, Ruslan Pistoia, Marco Katzgraber, Helmut G. Quantum Physics Disordered Systems and Neural Networks Quantum Gases Optimization and Control We propose and implement a quantum-informed reduction algorithm for the maximum independent set problem that integrates classical kernelization techniques with information extracted from quantum devices. Our larger framework consists of dedicated application, algorithm, and hardware layers, and easily generalizes to the maximum weight independent set problem. In this hybrid quantum-classical framework, which we call qReduMIS, the quantum computer is used as a co-processor to inform classical reduction logic about frozen vertices that are likely (or unlikely) to be in large independent sets, thereby opening up the reduction space after removal of targeted subgraphs. We systematically assess the performance of qReduMIS based on experiments with up to 231 qubits run on Rydberg quantum hardware available through Amazon Braket. Our experiments show that qReduMIS can help address fundamental performance limitations faced by a broad set of (quantum) solvers including Rydberg quantum devices. We outline implementations of qReduMIS with alternative platforms, such as superconducting qubits or trapped ions, and we discuss potential future extensions. |
| title | qReduMIS: A Quantum-Informed Reduction Algorithm for the Maximum Independent Set Problem |
| topic | Quantum Physics Disordered Systems and Neural Networks Quantum Gases Optimization and Control |
| url | https://arxiv.org/abs/2503.12551 |