Skip to main content

Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

Rydberg quantum wires for maximum independent set problems

Abstract

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

Access options

Buy article

Get time limited or full article access on ReadCube.

$32.00

All prices are NET prices.

Fig. 1: The graph representation of a Rydberg atom array.
Fig. 2: Experimental tests of Rydberg quantum wires.
Fig. 3: Experimental construction of Kuratowski subgraphs.
Fig. 4: Vertex-splitting demonstration.

Data availability

The data that support the findings of this study are available from Figshare, the public data repository at https://doi.org/10.6084/m9.figshare.19306640.v3. Source data are provided with this paper.

Code availability

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.

References

  1. Ebadi, S. et al. Quantum phases of matter on a 256-atom programmable quantum simulator. Nature 595, 227–232 (2021).

    ADS  Article  Google Scholar 

  2. Arute, F. et al. Quantum supremacy using a programmable superconducting processor. Nature 574, 505–510 (2019).

    ADS  Article  Google Scholar 

  3. Monroe, C. et al. Programmable quantum simulations of spin systems with trapped Ions. Rev. Mod. Phys. 93, 025001 (2021).

    ADS  MathSciNet  Article  Google Scholar 

  4. Scholl, P. et al. Quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms. Nature 595, 233–238 (2021).

    ADS  Article  Google Scholar 

  5. 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).

    ADS  Article  Google Scholar 

  6. 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).

  7. Centrone, F. et al. Experimental demonstration of quantum advantage for NP verification with limited information. Nat. Commun. 12, 850 (2021).

    ADS  Article  Google Scholar 

  8. Lucas, A. Ising formulations of many NP problems. Front. Phys 2, 5–15 (2014).

    Article  Google Scholar 

  9. Korte, B. & Vygen, J. Combinatorial Optimization (Springer, 2017).

  10. Kuratowski, K. Sur le probléme des courbes gauches en topologie. Fund. Math. 15, 271–283 (1930).

    Article  Google Scholar 

  11. Barahona, F. On the computational complexity of Ising spin glass models. J. Phys. A 15, 3241–3253 (1982).

    ADS  MathSciNet  Article  Google Scholar 

  12. Arora, S. & Barak, B. Computational Complexity: A Modern Approach (Cambridge Univ. Press, 2009)..

  13. Farhi, E. et al. A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science 292, 472–475 (2001).

    ADS  MathSciNet  Article  Google Scholar 

  14. Dickson, N. G. & Amin, M. H. S. Does adiabatic quantum optimization fail for NP-complete problems? Phys. Rev. Lett. 106, 050502 (2011).

    ADS  Article  Google Scholar 

  15. 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).

  16. Ebadi, S. et al. Quantum optimization of maximum independent set using Rydberg atom arrays. Science https://doi.org/10.1126/science.abo6587 (2022).

  17. Labuhn, H. et al. Tunable two-dimensional arrays of single Rydberg atoms for realizing quantum Ising models. Nature 534, 667–670 (2016).

    ADS  Article  Google Scholar 

  18. Bernien, H. et al. Probing many-body dynamics on a 51-atom quantum simulator. Nature 551, 579–584 (2017).

    ADS  Article  Google Scholar 

  19. Weber, S. et al. Hardware considerations for high-connectivity quantum annealers. In APS March Meeting Abstracts 2018, A33-008 (2018).

  20. Kerman, A. Design and simulation of complex superconducting circuits for advanced quantum annealing hardware. In APS March Meeting Abstracts 2018, C26−001 (2018).

  21. Kerman, A. Paramagnetic tree coupling of spin qubits. US patent 10,719,775 (2020).

  22. Qiu, X., Zoller, P. & Li, X. Programmable quantum annealing architectures with Ising quantum wires. PRX Quantum 1, 020311 (2020).

    Article  Google Scholar 

  23. 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).

    Article  Google Scholar 

  24. Kim, M., Song, Y., Kim, J. & Ahn, J. Quantum–Ising Hamiltonian programming in trio, quartet, and sextet qubit systems. PRX Quantum 1, 020323 (2020).

    Article  Google Scholar 

  25. Lee, W., Kim, H. & Ahn, J. Defect-free atomic array formation using the Hungarian matching algorithm. Phys. Rev. A 95, 053424 (2017).

    ADS  Article  Google Scholar 

  26. Kim, H., Kim, M., Lee, W. & Ahn, J. Gerchberg–Saxton algorithm for tweezer-trap atom arrangements. Opt. Express 27, 2184 (2019).

    ADS  Article  Google Scholar 

  27. 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).

    ADS  Article  Google Scholar 

  28. 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).

    ADS  Article  Google Scholar 

  29. Jo, H., Song, Y., Kim, M. & Ahn, J. Rydberg atom entanglements in the weak coupling regime. Phys. Rev. Lett. 124, 033603 (2020).

    ADS  Article  Google Scholar 

  30. 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).

    ADS  Article  Google Scholar 

  31. Lee, W., Kim, H. & Ahn, J. Three-dimensional rearrangement of single atoms using actively controlled optical microtraps. Opt. Express 24, 9816 (2016).

    ADS  Article  Google Scholar 

  32. Garey, M. & Johnson, D. The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32, 826–834 (1977).

    MathSciNet  Article  Google Scholar 

  33. Choi, V. Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design. Quantum Inf. Process. 10, 343–353 (2011).

    MathSciNet  Article  Google Scholar 

  34. Preskill, J. Quantum computing in the NISQ era and beyond. Quantum 2, 79 (2018).

    Article  Google Scholar 

  35. Denchev, V. S. et al. What is the computational value of finite-range tunneling? Phys. Rev. X 6, 031015 (2016).

    Google Scholar 

Download references

Acknowledgements

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).

Author information

Authors and Affiliations

Authors

Contributions

J.A. designed the project. M.K. and K.K. performed most of the experiments. M.K., K.K., J.H. and J.A. analysed and validated the data. E.-G.M. and J.A. wrote the manuscript. All authors have read, discussed and contributed to the manuscript.

Corresponding author

Correspondence to Jaewook Ahn.

Ethics declarations

Competing interests

The authors declare no competing interests.

Peer review

Peer review information

Nature Physics thanks Davide Venturelli and the other, anonymous, reviewer(s) for their contribution to the peer review of this work.

Additional information

Publisher’s note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Supplementary information

Supplementary Information

Supplementary Discussion, Figs. 1 and 2, and Tables 1 and 2.

Supplementary Video 1

Visualization of a 3D atom array of the quantum-wired K5 graph.

Supplementary Video 2

Visualization of a 3D atom array of the quantum-wired K3,3 graph.

Source data

Source Data Fig. 2

Experimental data of Fig. 2.

Source Data Fig. 3

Experimental data of Fig. 3.

Source Data Fig. 4

Experimental data of Fig. 4.

Rights and permissions

Reprints and Permissions

About this article

Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1038/s41567-022-01629-5

Search

Quick links

Nature Briefing

Sign up for the Nature Briefing newsletter — what matters in science, free to your inbox daily.

Get the most important science stories of the day, free in your inbox. Sign up for Nature Briefing