Neural-powered unit disk graph embedding: qubits connectivity for some QUBO problems
arXiv:2605.04736 · doi:10.1109/QCE53715.2022.00038
Abstract
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.
References in corpus (11)
- Decoupled Weight Decay Regularization
- Ising formulations of many NP problems
- Observation of Rydberg blockade between two atoms
- An atom-by-atom assembler of defect-free arbitrary 2d atomic arrays
- Entanglement of two individual neutral atoms using Rydberg blockade
- Quantum computing with neutral atoms
- A practical heuristic for finding graph minors
- A Tutorial on Formulating and Using QUBO Models
- Pulser: An open-source package for the design of pulse sequences in programmable neutral-atom arrays
- Programmable Quantum Annealing Architectures with Ising Quantum Wires
- Solving optimization problems with Rydberg analog quantum computers: Realistic requirements for quantum advantage using noisy simulation and classical benchmarks