Hardness of the maximum-independent-set problem on unit-disk graphs and prospects for quantum speedups
Abstract
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 quasiplanar 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.
Copyright and License
Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.
Acknowledgement
We thank Maddie Cain, Alex Keesling, Eric Kessler, Harry Levine, Mikhail Lukin, Hannes Pichler, and Shengtao Wang for fruitful discussions. We thank Peter Komar and Gili Rosenberg for detailed reviews of the manuscript, and Marjan Bagheri, Victor Bocking, Alexander Buts, Lou Romano, Peter Sceusa, and Tyler Takeshita for their support.
R.S.A., M.J.A.S., P.M., and R.Y. contributed equally to this work. M.P. and H.G.K. acted as co-equal principal investigators (co-PIs).
This paper was prepared for informational purposes with contributions from the Global Technology Applied Research center of JPMorgan Chase & Co. This paper is not a product of the Research Department of JPMorgan Chase & Co. or its affiliates. Neither JPMorgan Chase & Co. nor any of its affiliates makes any explicit or implied representation or warranty and none of them accept any liability in connection with this paper, including, without limitation, with respect to the completeness, accuracy, or reliability of the information contained herein and the potential legal, compliance, tax, or accounting effects thereof. This document is not intended as investment research or investment advice, or as a recommendation, offer, or solicitation for the purchase or sale of any security, financial instrument, financial product or service, or to be used in any way for evaluating the merits of participating in any transaction.
Files
| Name | Size | Download all |
|---|---|---|
|
md5:ff09b87495515b90d32a5e3c7c49f330
|
2.3 MB | Preview Download |
Additional details
- Caltech groups
- AWS Center for Quantum Computing