Related papers: A Unified Local Light-shifts Encoding For Solving Optimization Problems on a Rydberg Annealer

A Unified Local Light-shifts Encoding For Solving Optimization Problems on a Rydberg Annealer

URL: http://arxiv.org/abs/2605.07627v1
Date: Fri, 08 May 2026 11:56:12 GMT
Title: A Unified Local Light-shifts Encoding For Solving Optimization Problems on a Rydberg Annealer
Abstract summary: We present a unified framework for solving such optimization problems as two-SAT, XOR-SAT, mixed-two-XOR-SAT, set packing, quadratic assignment, binary clustering, and protein folding.<n>A direct mapping from the QUBO form of these problems onto the Rydberg quantum platform is demonstrated.<n>The framework can handle a variety of problems, each with different complexity.
Score: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Combinatorial optimization problems play a central role in computer science with many real world applications. A number of relevant problems remain computationally difficult to solve as they lie in the NP-hard complexity class. We present a unified framework for solving such optimization problems represented in the quadratic unconstrained binary optimization (QUBO) formalism, namely two-SAT, XOR-SAT, mixed-two-XOR-SAT, set packing, quadratic assignment, binary clustering, and protein folding, by expanding the domain of applications of \textit{PRR, 6(2), 023031}. A direct mapping from the QUBO form of these problems onto the Rydberg quantum platform is demonstrated as our first step. This mapping to the Rydberg system depends on distance-dependent long-range interactions and configurable local detuning, thus reducing resource overhead and improving scalability. Following-up on the encoding, the solution is reached by steering the system toward the ground state of the target Hamiltonian using an optimized quantum annealing protocol that controls the time-dependent detuning and Rabi frequency profiles. The framework can handle a variety of problems, each with different complexity. To quantify the complexity of any problem, a generalized hardness parameter is introduced that compares different problems based on the structure of their optimization landscapes. This is a proceedings contribution to the Athens Workshop in Theoretical Physics: 10th Anniversary, held at the National and Kapodistrian University of Athens on December 17-19 2025.

Related papers

A Scalable Distributed Quantum Optimization Framework via Factor Graph Paradigm [46.08923284345648]
We introduce a structure-aware framework for distributed quantum optimization.<n>We find that for a search space of size $N$, our framework achieves $O(sqrtN)$ query complexity up to processors and separator dependent factors.<n>We show that structure-aware decomposition delivers a practical path to scalable distributed quantum optimization on quantum networks.
arXiv Detail & Related papers (2026-03-08T15:15:52Z)
Encoding Matters: Benchmarking Binary and D-ary Representations for Quantum Combinatorial Optimization [1.3824488054100907]
We study Quadratic Unconstrained D-ary Optimization (QUDO) as an alternative formulation in which decision variables are encoded directly in higher dimensional Hilbert spaces.<n>We demonstrate that QUDO naturally captures structural constraints across a range of problem classes, including the Traveling Salesman Problem, graph coloring, job scheduling, and Max-K-Cut, without the need for extensive penalty constructions.<n>Our study show consistently improved approximation ratios and substantially reduced computational overhead at comparable circuit depths, highlighting QUDO as a scalable and expressive representation for quantum optimization.
arXiv Detail & Related papers (2026-02-07T04:37:32Z)
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)
A Method for Learning to Solve Parametric Bilevel Optimization with Coupling Constraints [46.74496760711108]
This paper proposes a framework for learning to solve a broad class of challenging bilevel optimization problems.<n>The framework is illustrated on an array of synthetic bilevel programs, as well as challenging control system co-design problems.
arXiv Detail & Related papers (2025-07-11T21:48:21Z)
A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints [66.61399765513383]
We develop a BLOCC algorithm to tackle BiLevel Optimization problems with Coupled Constraints. We demonstrate its effectiveness on two well-known real-world applications.
arXiv Detail & Related papers (2024-06-14T15:59:36Z)
Solving optimization problems with local light shift encoding on Rydberg quantum annealers [0.0]
We provide a non-unit disk framework to solve optimization problems on a Rydberg quantum annealer. Our setup consists of a many-body interacting Rydberg system where locally controllable light shifts are applied to individual qubits. Our numerical simulations implement the local-detuning protocol while globally driving the Rydberg annealer to the desired many-body ground state.
arXiv Detail & Related papers (2023-08-15T14:24:45Z)
Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
Vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry. In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables.
arXiv Detail & Related papers (2023-06-14T13:44:35Z)
Optimal Solutions for Joint Beamforming and Antenna Selection: From Branch and Bound to Machine Learning [47.10315221141495]
This work revisits the joint beamforming (BF) and antenna selection (AS) problem, as well as its robust beamforming (RBF) version under imperfect channel state information (CSI) The main contribution of this work is threefold. First, an effective it branch and bound (B&B) framework for solving the problems of interest is proposed. Second, to expedite the potentially costly B&B algorithm, a machine learning (ML)-based scheme is proposed to help skip intermediate states of the B&B search tree.
arXiv Detail & Related papers (2022-06-11T17:43:02Z)
Nonequilibrium Monte Carlo for unfreezing variables in hard combinatorial optimization [1.1783108699768]
We introduce a quantum-inspired family of nonlocal Nonequilibrium Monte Carlo (NMC) algorithms by developing an adaptive gradient-free strategy. We observe significant speedup and robustness over both specialized solvers and generic solvers.
arXiv Detail & Related papers (2021-11-26T17:45:32Z)
Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
CNF-based SAT and MaxSAT solvers are central to logic synthesis and verification systems. In this work, we propose a one-shot model derived from the Transformer architecture to solve the MaxSAT problem.
arXiv Detail & Related papers (2021-07-15T04:47:35Z)
Computational Overhead of Locality Reduction in Binary Optimization Problems [0.0]
We discuss the effects of locality reduction needed for the majority of solvers that can only accommodate 2-local (quadratic) cost functions. Using a parallel tempering Monte Carlo solver on Microsoft Azure Quantum, we show that post reduction to a corresponding 2-local representation the problems become considerably harder to solve.
arXiv Detail & Related papers (2020-12-17T15:49:55Z)

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