Identifying hard native instances for the maximum independent set problem on neutral atoms quantum processors
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_ | 1866916601163415552 |
|---|---|
| author | Cazals, Pierre François, Aymeric Henriet, Loïc Leclerc, Lucas Marin, Malory Naghmouchi, Yassine Coelho, Wesley da Silva Sikora, Florian Vitale, Vittorio Watrigant, Rémi Garzillo, Monique Witt Dalyac, Constantin |
| author_facet | Cazals, Pierre François, Aymeric Henriet, Loïc Leclerc, Lucas Marin, Malory Naghmouchi, Yassine Coelho, Wesley da Silva Sikora, Florian Vitale, Vittorio Watrigant, Rémi Garzillo, Monique Witt Dalyac, Constantin |
| contents | The Maximum Independent Set (MIS) problem is a fundamental combinatorial optimization task that can be naturally mapped onto the Ising Hamiltonian of neutral atom quantum processors. Given its connection to NP-hard problems and real-world applications, there has been significant experimental interest in exploring quantum advantage for MIS. Pioneering experiments on King's Lattice graphs suggested a quadratic speed-up over simulated annealing, but recent benchmarks using state-of-the-art methods found no clear advantage, likely due to the structured nature of the tested instances. In this work, we generate hard instances of unit-disk graphs by leveraging complexity theory results and varying key hardness parameters such as density and treewidth. For a fixed graph size, we show that increasing these parameters can lead to prohibitive classical runtime increases of several orders of magnitude. We then compare classical and quantum approaches on small instances and find that, at this scale, quantum solutions are slower than classical ones for finding exact solutions. Based on extended classical benchmarks at larger problem sizes, we estimate that scaling up to a thousand atoms with a 1 kHz repetition rate is a necessary step toward demonstrating a computational advantage with quantum methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_04291 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Identifying hard native instances for the maximum independent set problem on neutral atoms quantum processors Cazals, Pierre François, Aymeric Henriet, Loïc Leclerc, Lucas Marin, Malory Naghmouchi, Yassine Coelho, Wesley da Silva Sikora, Florian Vitale, Vittorio Watrigant, Rémi Garzillo, Monique Witt Dalyac, Constantin Quantum Physics The Maximum Independent Set (MIS) problem is a fundamental combinatorial optimization task that can be naturally mapped onto the Ising Hamiltonian of neutral atom quantum processors. Given its connection to NP-hard problems and real-world applications, there has been significant experimental interest in exploring quantum advantage for MIS. Pioneering experiments on King's Lattice graphs suggested a quadratic speed-up over simulated annealing, but recent benchmarks using state-of-the-art methods found no clear advantage, likely due to the structured nature of the tested instances. In this work, we generate hard instances of unit-disk graphs by leveraging complexity theory results and varying key hardness parameters such as density and treewidth. For a fixed graph size, we show that increasing these parameters can lead to prohibitive classical runtime increases of several orders of magnitude. We then compare classical and quantum approaches on small instances and find that, at this scale, quantum solutions are slower than classical ones for finding exact solutions. Based on extended classical benchmarks at larger problem sizes, we estimate that scaling up to a thousand atoms with a 1 kHz repetition rate is a necessary step toward demonstrating a computational advantage with quantum methods. |
| title | Identifying hard native instances for the maximum independent set problem on neutral atoms quantum processors |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2502.04291 |