Graph embedding is a recurrent problem in quantum computing, for instance, quantum annealers need to solve a minor graph embedding in order to map a given Quadratic Unconstrained Binary Optimization (QUBO) problem onto their internal connectivity pattern. This work presents a novel approach to constrained unit disk graph embedding, which is encountered when trying to solve combinatorial optimization problems in QUBO form, using quantum hardware based on neutral Rydberg atoms. The qubits, physically represented by the atoms, are excited to the Rydberg state through laser pulses. Whenever qubits pairs are closer together than the blockade radius, entanglement can be reached, thus preventing entangled qubits to be simultaneously in the excited state. Hence, the blockade radius determines the adjacency pattern among qubits, corresponding to a unit disk configuration. Although it is straightforward to compute the adjacency pattern given the qubit coordinates, identifying a feasible unit disk arrangement that matches the desired QUBO matrix is, on the other hand, a much harder task. In the context of quantum optimization, this issue translates into the physical placement of the qubits in the 2D/3D register to match the machine's Ising-like Hamiltonian with the QUBO formulation of the optimization problems. The proposed solution exploits the power of neural networks to transform an initial embedding configuration, which does not match the quantum hardware requirements or does not account for the unit disk property, into a feasible embedding properly representing the target optimization problems. Experimental results show that this new approach overcomes in performance Gurobi solver.
Journal reference
2022 IEEE International Conference on Quantum Computing and Engineering (QCE). IEEE, 2022. p. 186-196
Graph embedding is a recurrent problem in quantum computing, for instance, quantum annealers need to solve a minor graph embedding in order to map a given Quadratic Unconstrained Binary Optimization (QUBO) problem onto their internal connectivity pattern. This work presents a novel approach to constrained unit disk graph embedding, which is encountered when trying to solve combinatorial optimization problems in QUBO form, using quantum hardware based on neutral Rydberg atoms. The qubits, physically represented by the atoms, are excited to the Rydberg state through laser pulses. Whenever qubits pairs are closer together than the blockade radius, entanglement can be reached, thus preventing entangled qubits to be simultaneously in the excited state. Hence, the blockade radius determines the adjacency pattern among qubits, corresponding to a unit disk configuration. Although it is straightforward to compute the adjacency pattern given the qubit coordinates, identifying a feasible unit disk arrangement that matches the desired QUBO matrix is, on the other hand, a much harder task. In the context of quantum optimization, this issue translates into the physical placement of the qubits in the 2D/3D register to match the machine's Ising-like Hamiltonian with the QUBO formulation of the optimization problems. The proposed solution exploits the power of neural networks to transform an initial embedding configuration, which does not match the quantum hardware requirements or does not account for the unit disk property, into a feasible embedding properly representing the target optimization problems. Experimental results show that this new approach overcomes in performance Gurobi solver.
Quantum machines are among the most promising technologies expected to provide significant improvements in the following years. However, bridging the gap between real-world applications and their implementation on quantum hardware is still a complicated task. One of the main challenges is to represent through qubits (i.e., the basic units of quantum information) the problems of interest. According to the specific technology underlying the quantum machine, it is necessary to implement a proper representation strategy, generally referred to as embedding. This paper introduces a neural-enhanced optimization framework to solve the constrained unit disk problem, which arises in the context of qubits positioning for neutral atoms-based quantum hardware. The proposed approach involves a modified autoencoder model, i.e., the Distances Encoder Network, and a custom loss, i.e., the Embedding Loss Function, respectively, to compute Euclidean distances and model the optimization constraints. The core idea behind this design relies on the capability of neural networks to approximate non-linear transformations to make the Distances Encoder Network learn the spatial transformation that maps initial non-feasible solutions of the constrained unit disk problem into feasible ones. The proposed approach outperforms classical solvers, given fixed comparable computation times, and paves the way to address other optimization problems through a similar strategy.
Rydberg atom arrays are a powerful platform for solving combinatorial optimization problems, owing to the Rydberg blockade mechanism, which imposes effective constraints on simultaneous atomic excitations. These constraints have enabled the encoding of the Maximum Independent Set (MIS) problem on unit disk graphs, where atoms interact within a fixed, globally defined blockade radius. However, this restriction limits the class of addressable problems. A natural extension is to consider disk graphs, which generalize unit disk graphs by allowing arbitrary disk radii and correspond to the intersection graphs of disks in the plane. Embedding such graphs in Rydberg systems requires moving beyond the standard, globally uniform blockade model. In this work, we introduce a local Rydberg blockade regime, which emerges when local drives are applied to different pairs of atoms involved in a potential interaction. We develop a general theoretical framework for this regime and propose two novel metrics, the correlation matrix and the maximum independence violation, to quantify the quality of the embedding. Using these metrics, we demonstrate that disk graphs can be meaningfully embedded into Rydberg atom arrays under local drive schemes, thereby expanding the landscape of quantum-addressable optimization problems. Finally, when evaluating approximate solutions of the MIS problem, characterized by near-optimal independent sets, local drive approaches exhibit significantly improved performance over global ones. These results highlight the practical advantage of local blockade engineering for approximate combinatorial optimization and open a path toward leveraging the analog capabilities of Rydberg platforms beyond conventional geometric constraints.
Programmable quantum systems based on Rydberg atom arrays have recently been used for hardwareefficient tests of quantum optimization algorithms [Ebadi et al., Science, 376, 1209 (2022)] with hundreds of qubits.In particular, the maximum independent set problem on so-called unit-disk graphs, was shown to be efficiently encodable in such a quantum system.Here, we extend the classes of problems that can be efficiently encoded in Rydberg arrays by constructing explicit mappings from a wide class of problems to maximum-weighted independent set problems on unit-disk graphs, with at most a quadratic overhead in the number of qubits.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.Numerical simulations on small system sizes indicate that the adiabatic time scale for solving the mapped problems is strongly correlated with that of the original problems.Our work provides a blueprint for using Rydberg atom arrays to solve a wide range of combinatorial optimization problems with arbitrary connectivity, beyond the restrictions imposed by the hardware geometry.
One of the main bottlenecks in solving combinatorial optimization problems with quantum annealers is the qubit connectivity in the hardware. A possible solution for larger connectivity is minor embedding. This technique makes the geometrical properties of the combinatorial optimization problem, encoded as a Hamiltonian, match the properties of the quantum annealing hardware. The embedding itself is a hard computational problem, and therefore heuristic algorithms are required. In this work we present fixed, modular, and scalable embeddings that can be used to embed any combinatorial optimization problem described as an Ising Hamiltonian. These embeddings are the result of an extension of the well-known parity mapping, which has been used in the past to map higher-order Ising Hamiltonians to quadratic Hamiltonians, which are suitable for existing quantum hardware. We show how our new embeddings can be mapped to existing quantum annealers and that the embedded Hamiltonian physical properties match the original Hamiltonian properties.
Neutral atom arrays provide a versatile platform to implement coherent quantum annealing as an approach to solving hard combinatorial optimization problems. Here we present and experimentally demonstrate an efficient encoding scheme based on chains of Rydberg-blockaded atoms, which we call quantum wires, to natively embed maximum weighted independent set (MWIS) and quadratic unconstrained binary optimization (QUBO) problems on a neutral atom architecture. For graphs with quasi-unit-disk connectivity, in which only a few long-range edges are required, our approach requires a significantly lower overhead in the number of ancilla qubits than previous proposals, facilitating the implementation on currently available hardware. To demonstrate the approach, we perform annealing of weighted graphs on a programmable atom array using local light shifts to encode problem-specific weights across graphs of varying sizes. This approach successfully identifies the solutions to the original MWIS and QUBO graph instances. Our work expands the operational toolkit of near-term neutral atom arrays, enhancing their potential for scalable quantum optimization.
Quadratic Unconstrained Binary Optimization (QUBO) problems are prevalent in real-world applications, such as portfolio optimization, but pose significant computational challenges for large-scale instances. We propose a hybrid quantum-classical framework that leverages neutral atom quantum computing to address QUBO problems by mapping them to the Maximum Weighted Independent Set (MWIS) problem on unit disk graphs. Our approach employs spatial grid partitioning to decompose the problem into manageable subgraphs, solves each subgraph using Analog Hamiltonian Simulation (AHS), and merges solutions greedily to approximate the global optimum. We evaluate the framework on a 50-asset portfolio optimization problem using historical S&P 500 data, benchmarking against classical simulated annealing. Results demonstrate competitive performance, highlighting the scalability and practical potential of our method in the Noisy Intermediate-Scale Quantum (NISQ) era. As neutral atom quantum hardware advances, our framework offers a promising path toward solving large-scale optimization problems efficiently.