Encoding computationally hard problems in triangular Rydberg atom arrays

• URL: http://arxiv.org/abs/2510.25249v1
• Date: Wed, 29 Oct 2025 07:56:14 GMT
• Title: Encoding computationally hard problems in triangular Rydberg atom arrays
• Abstract summary: Rydberg atom arrays are a promising platform for quantum optimization.<n>We develop an encoding scheme that can universally encode computationally hard problems on triangular lattices.
• Score: 2.418500182135797
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 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: the 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 post-processing 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 quantum optimization on triangular lattices reduces independence-constraint violations by approximately two orders of magnitude compared to King's subgraphs, substantially alleviating the need for post-processing in experiments.

Related papers

• Tail-Aware Post-Training Quantization for 3D Geometry Models [58.79500829118265]
  Post-Training Quantization (PTQ) enables efficient inference without retraining.<n>PTQ fails to transfer effectively to 3D models due to intricate feature distributions and prohibitive calibration overhead.<n>We propose TAPTQ, a Tail-Aware Post-Training Quantization pipeline for 3D geometric learning.
  arXiv  Detail & Related papers  (2026-02-02T07:21:15Z)
• 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)
• Approximate combinatorial optimization with Rydberg atoms: the barrier of interpretability [0.0]
  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.
  arXiv  Detail & Related papers  (2025-07-30T15:22:50Z)
• An Efficient Quantum Classifier Based on Hamiltonian Representations [50.467930253994155]
  Quantum machine learning (QML) is a discipline that seeks to transfer the advantages of quantum computing to data-driven tasks.<n>We propose an efficient approach that circumvents the costs associated with data encoding by mapping inputs to a finite set of Pauli strings.<n>We evaluate our approach on text and image classification tasks, against well-established classical and quantum models.
  arXiv  Detail & Related papers  (2025-04-13T11:49:53Z)
• Demonstrating dynamic surface codes [118.67046728951689]
  We experimentally demonstrate three time-dynamic implementations of the surface code.<n>First, we embed the surface code on a hexagonal lattice, reducing the necessary couplings per qubit from four to three.<n>Second, we walk a surface code, swapping the role of data and measure qubits each round, achieving error correction with built-in removal of accumulated non-computational errors.<n>Third, we realize the surface code using iSWAP gates instead of the traditional CNOT, extending the set of viable gates for error correction without additional overhead.
  arXiv  Detail & Related papers  (2024-12-18T21:56:50Z)
• 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)
• 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)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• 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)
• 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)
• Towards Quantum Graph Neural Networks: An Ego-Graph Learning Approach [47.19265172105025]
  We propose a novel hybrid quantum-classical algorithm for graph-structured data, which we refer to as the Ego-graph based Quantum Graph Neural Network (egoQGNN) egoQGNN implements the GNN theoretical framework using the tensor product and unity matrix representation, which greatly reduces the number of model parameters required. The architecture is based on a novel mapping from real-world data to Hilbert space.
  arXiv  Detail & Related papers  (2022-01-13T16:35:45Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)

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.