Hardness of the maximum-independent-set problem on unit-disk graphs and prospects for quantum speedups

Hardness of the maximum-independent-set problem on unit-disk graphs and prospects for quantum speedups

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)0036-807510.1126/science.abo6587], we study the maximum-independent-set problem on unit-disk graphs with a broa...

Full description

Bibliographic Details
Main Authors: Ruben S. Andrist, Martin J. A. Schuetz, Pierre Minssen, Romina Yalovetzky, Shouvanik Chakrabarti, Dylan Herman, Niraj Kumar, Grant Salton, Ruslan Shaydulin, Yue Sun, Marco Pistoia, Helmut G. Katzgraber
Format: Article
Language:English
Published: American Physical Society 2023-12-01
Series:Physical Review Research
Online Access:http://doi.org/10.1103/PhysRevResearch.5.043277

Internet

http://doi.org/10.1103/PhysRevResearch.5.043277

Similar Items