Quantum Optimization on Rydberg Atom Arrays with Arbitrary Connectivity: Gadgets Limitations and a Heuristic Approach

• URL: http://arxiv.org/abs/2508.06130v1
• Date: Fri, 08 Aug 2025 08:50:29 GMT
• Title: Quantum Optimization on Rydberg Atom Arrays with Arbitrary Connectivity: Gadgets Limitations and a Heuristic Approach
• Authors: Pierre Cazals, Amalia Sorondo, Victor Onofre, Constantin Dalyac, Wesley da Silva Coelho, Vittorio Vitale,
• Abstract summary: We discuss the complexity-theoretic limits of reductions from arbitrary graphs to unit-disk instances.<n>We prove any such reduction incurs a blow-up in geometric count and degrades solution approximation guarantees.<n>As a practical alternative, we propose a divide-and-conquer with only linear overhead which leverages pred atomic layouts.
• Score: 0.5497663232622965
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Programmable quantum systems based on Rydberg atom arrays have recently emerged as a promising testbed for combinatorial optimization. Indeed, the Maximum Weighted Independent Set problem on unit-disk graphs can be efficiently mapped to such systems due to their geometric constraints. However, extending this capability to arbitrary graph instances typically necessitates the use of reduction gadgets, which introduce additional experimental overhead and complexity. Here, we analyze the complexity-theoretic limits of polynomial reductions from arbitrary graphs to unit-disk instances. We prove any such reduction incurs a quadratic blow-up in vertex count and degrades solution approximation guarantees. As a practical alternative, we propose a divide-and-conquer heuristic with only linear overhead which leverages precalibrated atomic layouts. We benchmark it on Erd\"os-R\'enyi graphs, and demonstrate feasibility on the Orion Alpha processor.

Related papers

• Lighter-X: An Efficient and Plug-and-play Strategy for Graph-based Recommendation through Decoupled Propagation [49.865020394064096]
  We propose textbfLighter-X, an efficient and modular framework that can be seamlessly integrated with existing GNN-based recommender architectures.<n>Our approach substantially reduces both parameter size and computational complexity while preserving the theoretical guarantees and empirical performance of the base models.<n>Experiments demonstrate that Lighter-X achieves comparable performance to baseline models with significantly fewer parameters.
  arXiv  Detail & Related papers  (2025-10-11T08:33:08Z)
• A quantum wire approach to weighted combinatorial graph optimisation problems [0.0]
  We present and experimentally demonstrate an efficient encoding scheme based on chains of Rydberg-blockaded atoms.<n>We embed maximum weighted independent set (MWIS) and quadratic unconstrained binary optimization (QUBO) problems on a neutral atom architecture.
  arXiv  Detail & Related papers  (2025-03-21T13:00:51Z)
• Quantum adiabatic optimization with Rydberg arrays: localization phenomena and encoding strategies [0.9500919522633157]
  Quantum adiabatic optimization seeks to solve problems using quantum dynamics.<n>Hamiltonians are often incompatible with native constraints of quantum hardware.<n>We show that encoded problems can exhibit an exponentially closing minimum gap.
  arXiv  Detail & Related papers  (2024-11-07T12:10:01Z)
• Demonstration of weighted graph optimization on a Rydberg atom array using local light-shifts [0.0]
  We present demonstrations of solving maximum weighted independent set problems on a Rydberg atom array.<n>We verify the ability to prepare weighted graphs in 1D and 2D arrays.
  arXiv  Detail & Related papers  (2024-04-03T11:42:38Z)
• Exploring the impact of graph locality for the resolution of MIS with neutral atom devices [0.755972004983746]
  We build upon recent progress made for using 3D arrangements to embed more complex classes of graphs. We report experimental and theoretical results which represent important steps towards tackling hard problems on quantum computers.
  arXiv  Detail & Related papers  (2023-06-23T08:53:16Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  We develop an adaptive inexact Newton method for equality-constrained nonlinear, nonIBS optimization problems. We demonstrate the superior performance of our method on benchmark nonlinear problems, constrained logistic regression with data from LVM, and a PDE-constrained problem.
  arXiv  Detail & Related papers  (2023-05-28T06:33:37Z)
• Efficient algorithms to solve atom reconfiguration problems. I. The redistribution-reconfiguration (red-rec) algorithm [35.300779480388705]
  Red-rec exploits simples and exact subroutines to solve atom reconfiguration problems on grids.<n>Red-rec enables assembling large configurations of atoms with high mean success probability.
  arXiv  Detail & Related papers  (2022-12-07T19:00:01Z)
• Embedding the MIS problem for non-local graphs with bounded degree using 3D arrays of atoms [0.0]
  The Maximum Independent Set (MIS) is a known NP-hard problem that can be naturally encoded in Rydberg atom arrays. We present a deterministic and efficient construction to embed a large family of non-local graphs in 3D atomic arrays. This construction is a first crucial step towards tackling tasks on quantum computers for which no classical efficient epsilon-approximation scheme exists.
  arXiv  Detail & Related papers  (2022-09-12T11:46:10Z)
• Quantum optimization with arbitrary connectivity using Rydberg atom arrays [0.0]
  We extend the classes of problems that can be efficiently encoded in Rydberg arrays by constructing explicit mappings from the original problems. We analyze several examples, including: maximum weighted independent set on graphs with arbitrary connectivity, quadratic unconstrained binary optimization problems with arbitrary or restricted connectivity, and integer factorization.
  arXiv  Detail & Related papers  (2022-09-08T18:00:00Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  We present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space. We generalize the "XY"-mixer designed to preserve the subspace of "one-hot" states to the general case of subspaces given by a number of computational basis states. Our analysis also leads to valid Trotterizations for "XY"-mixer with fewer CX gates than is known to date.
  arXiv  Detail & Related papers  (2022-03-11T17:19:26Z)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  Coherent control of quantum computations can be used to improve some quantum protocols and algorithms. We refine the PBS-calculus, a graphical language for coherent control inspired by quantum optics.
  arXiv  Detail & Related papers  (2022-02-10T18:59:52Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  In second-order optimization, a potential bottleneck can be computing the Hessian matrix of the optimized function at every iteration. We show that the Gaussian sketching matrix can be drastically sparsified, significantly reducing the computational cost of sketching. We prove that Newton-LESS enjoys nearly the same problem-independent local convergence rate as Gaussian embeddings.
  arXiv  Detail & Related papers  (2021-07-15T17:33:05Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
  arXiv  Detail & Related papers  (2021-06-22T11:07:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.