Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929204348583936 |
|---|---|
| author | Andrist, Ruben S. Schuetz, Martin J. A. Minssen, Pierre Yalovetzky, Romina Chakrabarti, Shouvanik Herman, Dylan Kumar, Niraj Salton, Grant Shaydulin, Ruslan Sun, Yue Pistoia, Marco Katzgraber, Helmut G. |
| author_facet | Andrist, Ruben S. Schuetz, Martin J. A. Minssen, Pierre Yalovetzky, Romina Chakrabarti, Shouvanik Herman, Dylan Kumar, Niraj Salton, Grant Shaydulin, Ruslan Sun, Yue Pistoia, Marco Katzgraber, Helmut G. |
| contents | Rydberg atom arrays are among the leading contenders for the demonstration of quantum speedups. Motivated by recent experiments with up to 289 qubits [Ebadi et al., Science 376, 1209 (2022)] we study the maximum independent set problem on unit-disk graphs with a broader range of classical solvers beyond the scope of the original paper. We carry out extensive numerical studies and assess problem hardness, using both exact and heuristic algorithms. We find that quasi-planar instances with Union-Jack-like connectivity can be solved to optimality for up to thousands of nodes within minutes, with both custom and generic commercial solvers on commodity hardware, without any instance-specific fine-tuning. We also perform a scaling analysis, showing that by relaxing the constraints on the classical simulated annealing algorithms considered in Ebadi et al., our implementation is competitive with the quantum algorithms. Conversely, instances with larger connectivity or less structure are shown to display a time-to-solution potentially orders of magnitudes larger. Based on these results we propose protocols to systematically tune problem hardness, motivating experiments with Rydberg atom arrays on instances orders of magnitude harder (for established classical solvers) than previously studied. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_09442 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups Andrist, Ruben S. Schuetz, Martin J. A. Minssen, Pierre Yalovetzky, Romina Chakrabarti, Shouvanik Herman, Dylan Kumar, Niraj Salton, Grant Shaydulin, Ruslan Sun, Yue Pistoia, Marco Katzgraber, Helmut G. Quantum Physics Disordered Systems and Neural Networks Optimization and Control Rydberg atom arrays are among the leading contenders for the demonstration of quantum speedups. Motivated by recent experiments with up to 289 qubits [Ebadi et al., Science 376, 1209 (2022)] we study the maximum independent set problem on unit-disk graphs with a broader range of classical solvers beyond the scope of the original paper. We carry out extensive numerical studies and assess problem hardness, using both exact and heuristic algorithms. We find that quasi-planar instances with Union-Jack-like connectivity can be solved to optimality for up to thousands of nodes within minutes, with both custom and generic commercial solvers on commodity hardware, without any instance-specific fine-tuning. We also perform a scaling analysis, showing that by relaxing the constraints on the classical simulated annealing algorithms considered in Ebadi et al., our implementation is competitive with the quantum algorithms. Conversely, instances with larger connectivity or less structure are shown to display a time-to-solution potentially orders of magnitudes larger. Based on these results we propose protocols to systematically tune problem hardness, motivating experiments with Rydberg atom arrays on instances orders of magnitude harder (for established classical solvers) than previously studied. |
| title | Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups |
| topic | Quantum Physics Disordered Systems and Neural Networks Optimization and Control |
| url | https://arxiv.org/abs/2307.09442 |