Reducibility of native weighted graphs on Rydberg Arrays

• URL: http://arxiv.org/abs/2605.07952v1
• Date: Fri, 08 May 2026 16:18:09 GMT
• Title: Reducibility of native weighted graphs on Rydberg Arrays
• Abstract summary: We investigate the classical reducibility of random unit-disk graph (UDG) instances of the maximum independent set (MIS) and maximum weighted independent set (MWIS) problems.<n>We find that for the remaining finite kernels, quantum execution would require non-native embeddings with substantial resource overheads.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate the classical reducibility of random unit-disk graph (UDG) instances of the maximum independent set (MIS) and maximum weighted independent set (MWIS) problems, which can be natively realised in Rydberg atom quantum processors. Using state-of-the-art kernelisation techniques, we systematically probe how far classical preprocessing can simplify such native optimisation problems of varying size and connectivity. While many small or sparse instances can be fully reduced, dense graphs often retain finite irreducible kernels even after extensive reductions. Introducing vertex weights tends to increase reducibility, whereas extending the interaction range in the underlying UDG connectivity suppresses the reduction efficiency. By exploring where classical reductions cease to be effective, we aim to delineate the regime of problem instances that remain computationally demanding - those most relevant for testing and benchmarking near-term quantum optimisation hardware. We find that for the remaining finite kernels, quantum execution would require non-native embeddings with substantial resource overheads, suggesting that directly running native instances may be more practical than embedding a reduced kernel.

Related papers

• Balancing Expressivity and Learnability in Quantum Kernel Bandit Optimization [50.880384999888044]
  We develop misspecified GP bandit algorithms and derive regret bounds that characterize the trade-off between approximation error and information gain.<n>Our methods outperform full quantum kernels in sample efficiency, while substantially reducing computational overhead.
  arXiv  Detail & Related papers  (2026-07-01T15:38:00Z)
• Quantum Optimization Methods for the Generalized Traveling Salesman Problem [2.4029307306254513]
  This paper studies quantum optimization baselines for the Generalized Traveling Salesman Problem (GTSP)<n>We propose a novel GTSP QUBO formulation focused on maintaining feasible solutions for quantum annealing.<n>We implement a constrained QAOA variant using an XY-mixer, which preserves the stepwise Hamming weight in the ideal circuit model.
  arXiv  Detail & Related papers  (2026-04-28T11:58:35Z)
• EQE-QAOA: An Equivalence-Preserving Qubit Efficient Framework for Combinatorial Optimization [54.05451096499336]
  Existing techniques rely on qubit reduction at the cost of information loss, leading to degraded computational performance.<n>We propose the Equivalence-preserving Qubit Efficient QAOA, which significantly reduces the required number of qubits without degrading performance.<n>We show that it is broadly applicable to large-scale optimization problems, excluding only unconstrained problems with completely independent variables.
  arXiv  Detail & Related papers  (2026-04-20T13:57:49Z)
• A quantum feasibility preserving modeling for the min cut problem [1.3701366534590498]
  We study the minimum cut problem in weighted undirected graphs using variational quantum algorithms.<n>We employ a ring structured XY mixer that restricts the quantum evolution to the subspace of valid cut configurations.
  arXiv  Detail & Related papers  (2026-02-26T12:34:59Z)
• Quantum Optimization on Rydberg Atom Arrays with Arbitrary Connectivity: Gadgets Limitations and a Heuristic Approach [0.5497663232622965]
  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.
  arXiv  Detail & Related papers  (2025-08-08T08:50:29Z)
• Cutting Slack: Quantum Optimization with Slack-Free Methods for Combinatorial Benchmarks [4.266376725904727]
  Constraint handling remains a key bottleneck in quantum optimization.<n>We investigate a suite of Lagrangian-based optimization techniques for solving constrained problems on quantum simulators and hardware.<n>Our results highlight the flexibility of Lagrangian formulations as a scalable alternative to QUBO penalization.
  arXiv  Detail & Related papers  (2025-07-16T11:39:47Z)
• MPQ-DMv2: Flexible Residual Mixed Precision Quantization for Low-Bit Diffusion Models with Temporal Distillation [74.34220141721231]
  We present MPQ-DMv2, an improved textbfMixed textbfPrecision textbfQuantization framework for extremely low-bit textbfDiffusion textbfModels.
  arXiv  Detail & Related papers  (2025-07-06T08:16:50Z)
• 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)
• QT-DoG: Quantization-aware Training for Domain Generalization [58.439816306817306]
  We propose Quantization-aware Training for Domain Generalization (QT-DoG)<n>We demonstrate that weight quantization effectively leads to flatter minima in the loss landscape.<n> QT-DoG exploits quantization as an implicit regularizer by inducing noise in model weights.
  arXiv  Detail & Related papers  (2024-10-08T13:21:48Z)
• Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration [72.15369769265398]
  Experimentally, ECORD achieves a new SOTA for RL algorithms on the Maximum Cut problem. Compared to the nearest competitor, ECORD reduces the optimality gap by up to 73%.
  arXiv  Detail & Related papers  (2022-05-27T17:13:10Z)
• Efficient Micro-Structured Weight Unification and Pruning for Neural Network Compression [56.83861738731913]
  Deep Neural Network (DNN) models are essential for practical applications, especially for resource limited devices. Previous unstructured or structured weight pruning methods can hardly truly accelerate inference. We propose a generalized weight unification framework at a hardware compatible micro-structured level to achieve high amount of compression and acceleration.
  arXiv  Detail & Related papers  (2021-06-15T17:22:59Z)

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.