One application of near-term quantum computing devices1,2,3,4 is to solve combinatorial optimization problems such as non-deterministic polynomial-time hard problems5,6,7,8. Here we present an experimental protocol with Rydberg atoms to determine the maximum independent set of graphs9, defined as an independent set of vertices of maximal size. Our proposal is based on a Rydberg quantum wire scheme, which exploits auxiliary atoms to engineer long-ranged networks of qubits. We experimentally test the protocol on three-dimensional Rydberg atom arrays, overcoming the intrinsic limitations of two-dimensional arrays for tackling combinatorial problems and encode high-degree vertices. We find the maximum independent set solutions with our programmable quantum-wired Rydberg simulator for Kuratowski subgraphs10 and a six-degree graph, which are paradigmatic examples of non-planar and high-degree graphs, respectively. Our protocol provides a way to engineer the complex connections of high-degree graphs through many-body entanglement, taking a step towards the demonstration of quantum advantage in combinatorial optimization.
Your institute does not have access to this article
Subscription info for Chinese customers
We have a dedicated website for our Chinese customers. Please go to naturechina.com to subscribe to this journal.
Get time limited or full article access on ReadCube.
All prices are NET prices.
The computer codes used to analyse the data of this study are available from Figshare, the public data repository at https://doi.org/10.6084/m9.figshare.19306640.v3.
Ebadi, S. et al. Quantum phases of matter on a 256-atom programmable quantum simulator. Nature 595, 227–232 (2021).
Arute, F. et al. Quantum supremacy using a programmable superconducting processor. Nature 574, 505–510 (2019).
Monroe, C. et al. Programmable quantum simulations of spin systems with trapped Ions. Rev. Mod. Phys. 93, 025001 (2021).
Scholl, P. et al. Quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms. Nature 595, 233–238 (2021).
Chen, H. et al. Experimental demonstration of a quantum annealing algorithm for the traveling salesman problem in a nuclear-magnetic-resonance quantum simulator. Phys. Rev. A 83, 032314 (2011).
Yarkoni, S., Plaat, A. & Back, T. First results solving arbitrarily structured maximum independent set problems using quantum annealing. In IEEE Congress on Evolutionary Computation (CEC) 1–6 (IEEE, 2018).
Centrone, F. et al. Experimental demonstration of quantum advantage for NP verification with limited information. Nat. Commun. 12, 850 (2021).
Lucas, A. Ising formulations of many NP problems. Front. Phys 2, 5–15 (2014).
Korte, B. & Vygen, J. Combinatorial Optimization (Springer, 2017).
Kuratowski, K. Sur le probléme des courbes gauches en topologie. Fund. Math. 15, 271–283 (1930).
Barahona, F. On the computational complexity of Ising spin glass models. J. Phys. A 15, 3241–3253 (1982).
Arora, S. & Barak, B. Computational Complexity: A Modern Approach (Cambridge Univ. Press, 2009)..
Farhi, E. et al. A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science 292, 472–475 (2001).
Dickson, N. G. & Amin, M. H. S. Does adiabatic quantum optimization fail for NP-complete problems? Phys. Rev. Lett. 106, 050502 (2011).
Pichler, H., Wang, S.-T., Zhou, L., Choi, S. & Lukin, M. D. Quantum optimization for maximum independent set using Rydberg atom arrays. Preprint at https://arxiv.org/abs/1808.10816 (2018).
Ebadi, S. et al. Quantum optimization of maximum independent set using Rydberg atom arrays. Science https://doi.org/10.1126/science.abo6587 (2022).
Labuhn, H. et al. Tunable two-dimensional arrays of single Rydberg atoms for realizing quantum Ising models. Nature 534, 667–670 (2016).
Bernien, H. et al. Probing many-body dynamics on a 51-atom quantum simulator. Nature 551, 579–584 (2017).
Weber, S. et al. Hardware considerations for high-connectivity quantum annealers. In APS March Meeting Abstracts 2018, A33-008 (2018).
Kerman, A. Design and simulation of complex superconducting circuits for advanced quantum annealing hardware. In APS March Meeting Abstracts 2018, C26−001 (2018).
Kerman, A. Paramagnetic tree coupling of spin qubits. US patent 10,719,775 (2020).
Qiu, X., Zoller, P. & Li, X. Programmable quantum annealing architectures with Ising quantum wires. PRX Quantum 1, 020311 (2020).
Song, Y., Kim, M., Hwang, H., Lee, W. & Ahn, J. Quantum simulation of Cayley-tree Ising Hamiltonians with three-dimensional Rydberg atoms. Phys. Rev. Res. 3, 013286 (2021).
Kim, M., Song, Y., Kim, J. & Ahn, J. Quantum–Ising Hamiltonian programming in trio, quartet, and sextet qubit systems. PRX Quantum 1, 020323 (2020).
Lee, W., Kim, H. & Ahn, J. Defect-free atomic array formation using the Hungarian matching algorithm. Phys. Rev. A 95, 053424 (2017).
Kim, H., Kim, M., Lee, W. & Ahn, J. Gerchberg–Saxton algorithm for tweezer-trap atom arrangements. Opt. Express 27, 2184 (2019).
de Léséleuc, S., Barredo, D., Lienhard, V., Browaeys, A. & Lahaye, T. Analysis of imperfections in the coherent optical excitation of single atoms to Rydberg states. Phys. Rev. A 97, 053803 (2018).
Lee, W., Kim, M., Jo, H., Song, Y. & Ahn, J. Coherent and dissipative dynamics of entangled few-body systems of Rydberg atoms. Phys. Rev. A 99, 043404 (2019).
Jo, H., Song, Y., Kim, M. & Ahn, J. Rydberg atom entanglements in the weak coupling regime. Phys. Rev. Lett. 124, 033603 (2020).
Barredo, D., Lienhard, V., Léséleuc, S., Lahaye, T. & Browaeys, A. Synthetic three-dimensional atomic structures assembled atom by atom. Nature 561, 79–82 (2018).
Lee, W., Kim, H. & Ahn, J. Three-dimensional rearrangement of single atoms using actively controlled optical microtraps. Opt. Express 24, 9816 (2016).
Garey, M. & Johnson, D. The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32, 826–834 (1977).
Choi, V. Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design. Quantum Inf. Process. 10, 343–353 (2011).
Preskill, J. Quantum computing in the NISQ era and beyond. Quantum 2, 79 (2018).
Denchev, V. S. et al. What is the computational value of finite-range tunneling? Phys. Rev. X 6, 031015 (2016).
This research was supported by the Samsung Science and Technology Foundation (SSTF-BA1301-52) and the National Research Foundation of Korea (NRF) (2017R1E1A1A01074307, 2019M3E4A1080411, 2020R1A4A3079707 and 2021R1A2C4001847).
The authors declare no competing interests.
Peer review information
Nature Physics thanks Davide Venturelli and the other, anonymous, reviewer(s) for their contribution to the peer review of this work.
Publisher’s note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
About this article
Cite this article
Kim, M., Kim, K., Hwang, J. et al. Rydberg quantum wires for maximum independent set problems. Nat. Phys. 18, 755–759 (2022). https://doi.org/10.1038/s41567-022-01629-5