We present our work on effectively representing unit-disk graphs on the registers of neutral atom quantum machines. Specifically, we aimed to embed graphs corresponding to proteins and cellular antenna networks into unit-disk graphs, ensuring compatibility with the registers of two real QPUs: Orion Alpha by PASQAL and Aquila by QuEra. To address machine-specific constraints, we made adjustments and integrated Distance Encoder Networks (DEN) from our previous work. Despite these challenges, we successfully embedded up to 76% of protein-representing graphs for a quantum machine learning classification task on the Aquila QPU, and all subgraphs derived from 90 antenna geographical positions in Turin, Italy, on the Orion Alpha QPU. In the latter case, the graphs represented instances of the graph coloring problem, which we tackled using the hybrid quantum-classical algorithm BBQ-mIS. These promising results underscore the effectiveness and versatility of our embedding approach for representing unit-disk graphs on neutral atom quantum computers across diverse applications.
Journal reference
2024 IEEE International Conference on Quantum Computing and Engineering (QCE). IEEE, 2024. p. 217-222
We present our work on effectively representing unit-disk graphs on the registers of neutral atom quantum machines. Specifically, we aimed to embed graphs corresponding to proteins and cellular antenna networks into unit-disk graphs, ensuring compatibility with the registers of two real QPUs: Orion Alpha by PASQAL and Aquila by QuEra. To address machine-specific constraints, we made adjustments and integrated Distance Encoder Networks (DEN) from our previous work. Despite these challenges, we successfully embedded up to 76% of protein-representing graphs for a quantum machine learning classification task on the Aquila QPU, and all subgraphs derived from 90 antenna geographical positions in Turin, Italy, on the Orion Alpha QPU. In the latter case, the graphs represented instances of the graph coloring problem, which we tackled using the hybrid quantum-classical algorithm BBQ-mIS. These promising results underscore the effectiveness and versatility of our embedding approach for representing unit-disk graphs on neutral atom quantum computers across diverse applications.
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.
In the past years, many quantum algorithms have been proposed to tackle hard combinatorial problems. In particular, the maximum independent set (MIS) is a known NP-hard problem that can be naturally encoded in Rydberg atom arrays. By representing a graph with an ensemble of neutral atoms one can leverage Rydberg dynamics to naturally encode the constraints and the solution to MIS. However, the classes of graphs that can be directly mapped ``vertex-to-atom'' on standard devices with two-dimensional capabilities are currently limited to Unit-Disk graphs. In this setting, the inherent spatial locality of the graphs can be leveraged by classical polynomial-time approximation schemes (PTAS) that guarantee an $\ensuremath{\epsilon}$-approximate solution. In this work, we build upon recent progress made for using three-dimensioanl arrangements of atoms to embed more complex classes of graphs. We report experimental and theoretical results which represent important steps towards tackling combinatorial tasks on quantum computers for which no classical efficient $\ensuremath{\varepsilon}$-approximation scheme exists.
Neutral atom platforms are analogue quantum simulators that offer the possibility to map graphs onto a 2D qubit register using programmable Rubidium atoms arrays, whose valence electrons' energy state is used as qubits, using optical tweezers. This makes it possible to implement algorithms for solving graph combinatorial optimization and Quantum Machine Learning (QML) tasks, such as graph classification. However, the restrictions of real hardware, as well as the very low number of publicly available machines, make such implementation non-trivial. In this work, we manage to compute the Quantum Evolution Kernel (QEK) to extract the features from graphs of the PROTEINS dataset using the 256-qubits Aquila platform (available through AWS) and then we apply classical Machine Learning (ML) techniques for the final classification. The method is benchmarked against classical kernels, resulting in slightly better performance, proving the effectiveness of the method, even in the case of a noisy quantum simulator.
In the past years, many quantum algorithms have been proposed to tackle hard combinatorial problems. In particular, the Maximum Independent Set (MIS) is a known NP-hard problem that can be naturally encoded in Rydberg atom arrays. By representing a graph with an ensemble of neutral atoms one can leverage Rydberg dynamics to naturally encode the constraints and the solution to MIS. However, the classes of graphs that can be directly mapped ``vertex-to-atom" on standard devices with 2D capabilities are currently limited to Unit-Disk graphs. In this setting, the inherent spatial locality of the graphs can be leveraged by classical polynomial-time approximation schemes (PTAS) that guarantee an ε-approximate solution. In this work, we build upon recent progress made for using 3D arrangements of atoms to embed more complex classes of graphs. We report experimental and theoretical results which represent important steps towards tackling combinatorial tasks on quantum computers for which no classical efficient ε-approximation scheme exists.
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 architectures based on neutral atoms have gained significant attention in recent years as specialized computational machines due to their ability to directly encode the independent set constraint on graphs, exploiting the Rydberg blockade mechanism. In this work, we address the Drone Delivery Packing Problem via a hybrid quantum-classical framework leveraging a neutral-atom quantum processing unit (QPU). We reformulate the optimization task as a graph-partitioning problem based on the independent sets (ISs) of a scheduling graph that encodes delivery incompatibilities. Each partition corresponds to deliveries assigned to a single drone, with the objective of minimizing the total number of partitions. While the ISs represent time-feasible schedules, battery-duration constraints are enforced through a classical post-processing routine. This methodology enables the recovery of optimal delivery schedules, provided a sufficient number of samples is collected from the QPU to resolve the solution space. We benchmark the hybrid workflow through numerical emulations and demonstrate its effectiveness on Pasqal's Fresnel QPU, reporting hardware experiments with configurations of up to 100 atoms.