Quantum optimization of maximum independent set using Rydberg atom arrays

Creators: Ebadi, S.; Keesling, A.; Cain, M.; Wang, T. T.; Levine, H.; Bluvstein, D.; Semeghini, G.; Omran, A.; Liu, J.-G.; Samajdar, R.; Luo, X.-Z.; Nash, B.; Gao, X.; Barak, B.; Farhi, E.; Sachdev, S.; Gemelke, N.; Zhou, L.; Choi, S.; Pichler, H.; Wang, S.-T.; Greiner, M.; Vuletić, V.; Lukin, M. D.

Abstract

Realizing quantum speedup for practically relevant, computationally hard problems is a central challenge in quantum information science. Using Rydberg atom arrays with up to 289 qubits in two spatial dimensions, we experimentally investigate quantum algorithms for solving the maximum independent set problem. We use a hardware-efficient encoding associated with Rydberg blockade, realize closed-loop optimization to test several variational algorithms, and subsequently apply them to systematically explore a class of graphs with programmable connectivity. We find that the problem hardness is controlled by the solution degeneracy and number of local minima, and we experimentally benchmark the quantum algorithm's performance against classical simulated annealing. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions in the deep circuit regime and analyze its origins.

Additional Information

© 2022 the authors, some rights reserved; exclusive licensee American Association for the Advancement of Science. No claim to original US government works. Submitted 17 February 2022; accepted 22 April 2022; Published online 5 May 2022. We thank I. Cirac, J. Cong, S. Evered, M. Kalinowski, M. Lin, T. Manovitz, M. Murphy, B. Schiffer, J. Singh, A. Sohrabizadeh, J. Tura, and D. Wild for illuminating discussions and feedback on the manuscript. We acknowledge financial support from the DARPA ONISQ program (grant no. W911NF2010021), the Center for Ultracold Atoms, the National Science Foundation, the Vannevar Bush Faculty Fellowship, the US Department of Energy [DE-SC0021013 and DOE Quantum Systems Accelerator Center (contract no. 7568717)], the Army Research Office MURI, QuEra Computing, and Amazon Web Services. M.C. acknowledges support from DOE CSG award fellowship (DE-SC0020347). H.L. acknowledges support from the National Defense Science and Engineering Graduate (NDSEG) fellowship. D.B. acknowledges support from the NSF Graduate Research Fellowship Program (grant DGE1745303) and The Fannie and John Hertz Foundation. G.S. acknowledges support from a fellowship from the Max Planck/Harvard Research Center for Quantum Optics. R.S. and S.S. were supported by the U.S. Department of Energy under grant DE-SC0019030. X.G. acknowledges support from a fellowship from the Max Planck/Harvard Research Center for Quantum Optics. B.B. acknowledges support from DARPA grant W911NF2010021, a Simons investigator fellowships, NSF grants CCF 1565264 and DMS-2134157, and DOE grant DE-SC0022199. H.P. acknowledges support by the Army Research Office (grant no. W911NF-21-1-0367). The DMRG calculations in this paper were performed using the ITensor package (54) and were run on the FASRC Odyssey cluster supported by the FAS Division of Science Research Computing Group at Harvard University. Author contributions: S.E., A.K., M.C., T.T.W., H.L., D.B., G.S., A.O., and J.-G. L. contributed to building the experimental setup, performing the measurements, and data analysis. M.C., J.-G. L., R. S., X.-Z. L., B. N., X. G., L. Z., S. C., H. P., and S.-T. W. contributed to theoretical analysis and interpretation. B. B., E. F., S. S., and N. G. contributed to interpretation of the observations and benchmarking studies. All authors discussed the results and contributed to the manuscript. All work was supervised by M.G., V.V., and M.D.L. Competing interests: N.G., M.G., V.V., and M.D.L. are cofounders and shareholders of QuEra Computing. A.K. is a shareholder and an executive at QuEra Computing. A.O. and S.-T.W. are shareholders of QuEra Computing. Some of the techniques and methods used in this work are included in pending patent applications filed by Harvard University (Patent application nos. PCT/US2018/042080 and PCT/US2019/049115). Data and materials availability: Code for classical tensor network algorithms for graph characterization is available at (35). Data and code are available on Zenodo (56).

Attached Files

Submitted - 2202.09372.pdf

Supplemental Material - science.abo6587_sm.pdf

Files

2202.09372.pdf

Files (31.2 MB)

Name	Size	Download all
2202.09372.pdf md5:6b523cb592aa5c43e516589dbcc45d26	26.8 MB	Preview Download
science.abo6587_sm.pdf md5:5edf6f617c4a724803b2026f53742cab	4.4 MB	Preview Download

Additional details

	All versions	This version
Views	0	0
Downloads	0	0
Data volume	0 Bytes	0 Bytes