Efficient algorithms to solve atom reconfiguration problems. II. Assignment-rerouting-ordering algorithm
- 4 August 2023
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review A
- Vol. 108 (2) , 023108
Abstract
Programmable arrays of optical traps enable the assembly of configurations of single atoms to perform controlled experiments on quantum many-body systems. Finding the sequence of control operations to transform an arbitrary configuration of atoms into a predetermined one requires solving an atom reconfiguration problem quickly and efficiently. A typical approach to solving atom reconfiguration problems is to use an assignment algorithm to determine which atoms to move to which traps. This approach results in control protocols that exactly minimize the number of displacement operations; however, this approach does not optimize for the number of displaced atoms or the number of times each atom is displaced, resulting in unnecessary control operations that increase the execution time and failure rate of the control protocol. In this work we propose the assignment-rerouting-ordering (ARO) algorithm to improve the performance of assignment-based algorithms in solving atom reconfiguration problems. The ARO algorithm uses an assignment subroutine to minimize the total distance traveled by all atoms, a rerouting subroutine to reduce the number of displaced atoms, and an ordering subroutine to guarantee that each atom is displaced at most once. The ordering subroutine relies on the existence of a partial ordering of moves that can be obtained using a polynomial-time algorithm that we introduce within the formal framework of graph theory. We numerically quantify the performance of the ARO algorithm in the presence and in the absence of loss and show that it outperforms the exact, approximation, and heuristic algorithms that we use as benchmarks. Our results are useful for assembling large configurations of atoms with high success probability and fast preparation time, as well as for designing and benchmarking novel atom reconfiguration algorithms.Keywords
All Related Versions
Funding Information
- Canada First Research Excellence Fund
- Natural Sciences and Engineering Research Council of Canada
This publication has 36 references indexed in Scilit:
- On the complexity of reconfiguration problemsTheoretical Computer Science, 2011
- Holographic generation of microtrap arrays for single atoms by use of a programmable phase modulatorJournal of the Optical Society of America B, 2004
- High-speed holographic optical tweezers using a ferroelectric liquid crystal microdisplayOptics Express, 2003
- Dynamic holographic optical tweezersOptics Communications, 2002
- Dipole Blockade and Quantum Information Processing in Mesoscopic Atomic EnsemblesPhysical Review Letters, 2001
- Acousto-optic generation of two-dimensional spot arraysOptics Letters, 1991
- Programmable optical interconnections by multilevel synthetic acousto-optic hologramsOptics Letters, 1991
- Theoretical Improvements in Algorithmic Efficiency for Network Flow ProblemsJournal of the ACM, 1972
- Topological sorting of large networksCommunications of the ACM, 1962
- The Hungarian method for the assignment problemNaval Research Logistics Quarterly, 1955