Curator's Take
This work tackles a critical but often overlooked bottleneck in quantum computing: how to physically arrange qubits so their natural connectivity matches the structure of optimization problems we want to solve. While most quantum computing discussions focus on algorithms or error correction, this research addresses the fundamental challenge of mapping abstract mathematical problems onto real quantum hardware, specifically neutral Rydberg atom systems where qubit interactions are determined by their physical proximity. The neural network approach represents a clever solution to what is essentially a complex geometric puzzle - finding arrangements of atoms that create the right pattern of quantum interactions for a given optimization problem. This type of embedding work is crucial for making quantum optimization practical, as even the most sophisticated quantum algorithms are useless if you can't properly map your problem onto the available hardware connectivity.
— Mark Eatherly
Summary
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.