Efficient algorithms to solve atom reconfiguration problems. III. The bird and batching algorithms and other parallel implementations on GPUs

• URL: http://arxiv.org/abs/2504.06182v1
• Date: Tue, 08 Apr 2025 16:22:42 GMT
• Title: Efficient algorithms to solve atom reconfiguration problems. III. The bird and batching algorithms and other parallel implementations on GPUs
• Authors: Fouad Afiouni, Remy El Sabeh, Naomi Nishimura, Izzat El Hajj, Amer E. Mouawad, Alexandre Cooper,
• Abstract summary: We present efficient implementations of atom reconfiguration algorithms for both CPU and GPU.<n>Our approach derives improved algorithms that achieve reduced time complexity and faster operational running times.<n>These algorithms can be used to prepare defect-free configurations of neutral atoms in arrays of optical traps.
• Score: 38.2058847337805
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present efficient implementations of atom reconfiguration algorithms for both CPUs and GPUs, along with a batching routine to merge displacement operations for parallel execution. Leveraging graph-theoretic methods, our approach derives improved algorithms that achieve reduced time complexity and faster operational running times. First, we introduce an enhanced version of the redistribution-reconfiguration (red-rec) algorithm, which offers superior operational and runtime performance. We detail its efficient implementation on a GPU using a parallel approach. Next, we present an optimized version of the assignment-reconfiguration-ordering (aro) algorithm, specifically tailored for unweighted grid graphs. Finally, we introduce the bird algorithm to solve reconfiguration problems on grids, achieving performance gains over both red-rec and aro. These algorithms can be used to prepare defect-free configurations of neutral atoms in arrays of optical traps, serve as subroutines in more complex algorithms, or cross-benchmark the operational and runtime performance of new algorithms. They are suitable for realizing quantum circuits incorporating displacement operations and are optimized for real-time operation on increasingly large system sizes.

Related papers

• Performance Evaluation of Evolutionary Algorithms for Analog Integrated Circuit Design Optimisation [0.0]
  An automated sizing approach for analog circuits is presented in this paper. A targeted search of the search space has been implemented using a particle generation function and a repair-bounds function. The algorithms are tuned and modified to converge to a better optimal solution.
  arXiv  Detail & Related papers  (2023-10-19T03:26:36Z)
• BCDDO: Binary Child Drawing Development Optimization [4.395397502990339]
  A Binary Child Drawing Development Optimization (BCDDO) is suggested for choosing the wrapper features in this study. To achieve the best classification accuracy, a subset of crucial features is selected using the suggestedBCDDO. The suggested approach has significantly outperformed discussed techniques in the area of feature selection to increase classification accuracy.
  arXiv  Detail & Related papers  (2023-07-19T11:32:34Z)
• VAPI: Vectorization of Algorithm for Performance Improvement [5.835939416417458]
  Vectorization is a technique for converting an algorithm, which operates on a single value at a time to one that operates on a collection of values at a time to execute rapidly. The vectorization technique also operates by replacing multiple iterations into a single operation, which improves the algorithm's performance in speed. The objective of this study is to use the vectorization technique on one of the metaheuristic algorithms and compare the results of the vectorized algorithm with the algorithm which is non-vectorized.
  arXiv  Detail & Related papers  (2023-07-19T11:23:03Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Efficient algorithms to solve atom reconfiguration problems. II. The assignment-rerouting-ordering (aro) algorithm [35.300779480388705]
  atom reconfiguration problems require solving an atom problem quickly and efficiently.<n>A typical approach to solve atom reconfiguration problems is to use an assignment algorithm to determine which atoms to move to which traps.<n>This approach does not optimize for the number of displaced atoms or the number of times each atom is displaced.<n>We propose the assignment-rerouting-ordering (aro) algorithm to improve the performance of assignment-based algorithms in solving atom reconfiguration problems.
  arXiv  Detail & Related papers  (2022-12-11T19:48:25Z)
• Efficient algorithms to solve atom reconfiguration problems. I. The redistribution-reconfiguration (red-rec) algorithm [35.300779480388705]
  Red-rec exploits simples and exact subroutines to solve atom reconfiguration problems on grids.<n>Red-rec enables assembling large configurations of atoms with high mean success probability.
  arXiv  Detail & Related papers  (2022-12-07T19:00:01Z)
• Improving the Efficiency of Gradient Descent Algorithms Applied to Optimization Problems with Dynamical Constraints [3.3722008527102894]
  We introduce two block coordinate descent algorithms for solving optimization problems with ordinary differential equations. The algorithms do not need to implement direct or adjoint sensitivity analysis methods to evaluate loss function gradients.
  arXiv  Detail & Related papers  (2022-08-26T18:26:50Z)
• Review of Serial and Parallel Min-Cut/Max-Flow Algorithms for Computer Vision [6.574107319036238]
  Hochbaum pseudoflow algorithm is fastest serial algorithm, Boykov-Kolmogorov algorithm is most memory efficient. Existing parallel min-cut/max-flow algorithms can significantly outperform serial algorithms on large problems but suffers from added overhead on small to medium problems.
  arXiv  Detail & Related papers  (2022-02-01T14:06:27Z)
• A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse [121.54116938140754]
  We propose a new Hessian inverse free Fully Single Loop Algorithm for bilevel optimization problems. We show that our algorithm converges with the rate of $O(epsilon-2)$.
  arXiv  Detail & Related papers  (2021-12-09T02:27:52Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
  Kernel methods provide an elegant and principled approach to nonparametric learning, but so far could hardly be used in large scale problems. Recent advances have shown the benefits of a number of algorithmic ideas, for example combining optimization, numerical linear algebra and random projections. Here, we push these efforts further to develop and test a solver that takes full advantage of GPU hardware.
  arXiv  Detail & Related papers  (2020-06-18T08:16:25Z)

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

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.