Approximate combinatorial optimization with Rydberg atoms: the barrier of interpretability

• URL: http://arxiv.org/abs/2507.22761v1
• Date: Wed, 30 Jul 2025 15:22:50 GMT
• Title: Approximate combinatorial optimization with Rydberg atoms: the barrier of interpretability
• Authors: Christian de Correc, Thomas Ayral, Corentin Bertrand,
• Abstract summary: We evaluate the ability of two interpretation strategies to correct errors in the recently introduced Crossing Lattice embedding.<n>It is unlikely that a scalable and generic improvement in quality can be achieved with Rydberg platforms.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Analog quantum computing with Rydberg atoms is seen as an avenue to solve hard graph optimization problems, because they naturally encode the Maximum Independent Set (MIS) problem on Unit-Disk (UD) graphs, a problem that admits rather efficient approximation schemes on classical computers. Going beyond UD-MIS to address generic graphs requires embedding schemes, typically with chains of ancilla atoms, and an interpretation algorithm to map results back to the original problem. However, interpreting approximate solutions obtained with realistic quantum computers proves to be a difficult problem. As a case study, we evaluate the ability of two interpretation strategies to correct errors in the recently introduced Crossing Lattice embedding. We find that one strategy, based on finding the closest embedding solution, leads to very high qualities, albeit at an exponential cost. The second strategy, based on ignoring defective regions of the embedding graph, is polynomial in the graph size, but it leads to a degradation of the solution quality which is prohibitive under realistic assumptions on the defect generation. Moreover, more favorable defect scalings lead to a contradiction with well-known approximability conjectures. Therefore, it is unlikely that a scalable and generic improvement in solution quality can be achieved with Rydberg platforms -- thus moving the focus to heuristic algorithms.

Related papers

• Minor Embedding for Quantum Annealing with Reinforcement Learning [10.787328610467801]
  Reinforcement Learning (RL) offers a promising alternative by treating minor embedding as a sequential decision-making problem.<n>We propose a RL-based approach to minor embedding using a Proximal Policy Optimization agent, testing its ability to embed both fully connected and randomly generated problem.<n>Our proposed approach is also able to scale to moderate problem sizes and adapts well to different graph structures, highlighting RL's potential as a flexible and general-purpose framework.
  arXiv  Detail & Related papers  (2025-07-21T18:54:15Z)
• Graph Coloring via Quantum Optimization on a Rydberg-Qudit Atom Array [0.0]
  We introduce a new approach to solving native-embedded graph coloring problems.<n>We demonstrate the ability to robustly find optimal graph colorings for chromatic numbers up to the number of distinct Rydberg states used.<n>We discuss the experimental feasibility of this approach and propose extensions to solve higher chromatic number problems.
  arXiv  Detail & Related papers  (2025-04-11T14:55:35Z)
• A Scalable and Robust Compilation Framework for Emitter-Photonic Graph State [1.3624495460189865]
  We study the GraphState-to-Circuit compilation problem in the context of the deterministic scheme.<n>We propose a novel compilation framework that partitions the target graph state into subgraphs, compiles them individually, and subsequently combines and schedules the circuits to maximize emitter resource utilization.
  arXiv  Detail & Related papers  (2025-03-20T17:01:33Z)
• A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
  The proposed method introduces a Quantum Genetic Algorithm (QGA) using a Grover-based evolutionary framework and divide-and-conquer principles.<n>On complete graphs, the proposed method consistently achieves the true optimal MaxCut values, outperforming the Semidefinite Programming (SDP) approach.<n>On ErdHos-R'enyi random graphs, the QGA demonstrates competitive performance, achieving median solutions within 92-96% of the SDP results.
  arXiv  Detail & Related papers  (2025-01-02T05:06:16Z)
• A Greedy Strategy for Graph Cut [95.2841574410968]
  We propose a greedy strategy to solve the problem of Graph Cut, called GGC.<n>It starts from the state where each data sample is regarded as a cluster and dynamically merges the two clusters.<n>GGC has a nearly linear computational complexity with respect to the number of samples.
  arXiv  Detail & Related papers  (2024-12-28T05:49:42Z)
• 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)
• Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
  We provide the first proof of convergence for normalized error feedback algorithms across a wide range of machine learning problems. We show that due to their larger allowable stepsizes, our new normalized error feedback algorithms outperform their non-normalized counterparts on various tasks.
  arXiv  Detail & Related papers  (2024-10-22T10:19:27Z)
• 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)
• Distributionally Robust Semi-Supervised Learning Over Graphs [68.29280230284712]
  Semi-supervised learning (SSL) over graph-structured data emerges in many network science applications. To efficiently manage learning over graphs, variants of graph neural networks (GNNs) have been developed recently. Despite their success in practice, most of existing methods are unable to handle graphs with uncertain nodal attributes. Challenges also arise due to distributional uncertainties associated with data acquired by noisy measurements. A distributionally robust learning framework is developed, where the objective is to train models that exhibit quantifiable robustness against perturbations.
  arXiv  Detail & Related papers  (2021-10-20T14:23:54Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  We propose a hybrid approach to combine the best of the two worlds, in which a bi-level framework is developed with an upper-level learning method to optimize the graph. Such a bi-level approach simplifies the learning on the original hard CO and can effectively mitigate the demand for model capacity.
  arXiv  Detail & Related papers  (2021-06-09T09:18:18Z)
• Consistent Second-Order Conic Integer Programming for Learning Bayesian Networks [2.7473982588529653]
  We study the problem of learning the sparse DAG structure of a BN from continuous observational data. The optimal solution to this mathematical program is known to have desirable statistical properties under certain conditions. We propose a concrete early stopping criterion to terminate the branch-and-bound process in order to obtain a near-optimal solution.
  arXiv  Detail & Related papers  (2020-05-29T00:13:15Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  Simple algorithms have been shown to lead to good empirical results in many contexts. Several works have pursued rigorous analytical justification for studying non optimization problems. A key insight in these analyses is that perturbations play a critical role in allowing local descent algorithms.
  arXiv  Detail & Related papers  (2020-03-31T16:54:22Z)

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.