Integer Programming Using A Single Atom
arXiv:2402.16541 · doi:10.1088/2058-9565/ad6735
Abstract
Integer programming (IP), as the name suggests is an integer-variable-based approach commonly used to formulate real-world optimization problems with constraints. Currently, quantum algorithms reformulate the IP into an unconstrained form through the use of binary variables, which is an indirect and resource-consuming way of solving it. We develop an algorithm that maps and solves an IP problem in its original form to any quantum system possessing a large number of accessible internal degrees of freedom that are controlled with sufficient accuracy. This work leverages the principle of superposition to solve the optimization problem. Using a single Rydberg atom as an example, we associate the integer values to electronic states belonging to different manifolds and implement a selective superposition of different states to solve the full IP problem. The optimal solution is found within a few microseconds for prototypical IP problems with up to eight variables and four constraints. This also includes non-linear IP problems, which are usually harder to solve with classical algorithms when compared to their linear counterparts. Our algorithm for solving IP is benchmarked by a well-known classical algorithm (branch and bound) in terms of the number of steps needed for convergence to the solution. This approach carries the potential to improve the solutions obtained for larger-size problems using hybrid quantum-classical algorithms.
20 pages, 7 figures
References in corpus (27)
- Quantum information with Rydberg atoms
- Noisy intermediate-scale quantum (NISQ) algorithms
- Trapped-Ion Quantum Computing: Progress and Challenges
- Quantum algorithms: an overview
- Experimental quantum computing without entanglement
- Coherent optical detection of highly excited Rydberg states using electromagnetically induced transparency
- Synthetic Dimension in Photonics
- Quantum computing with neutral atoms
- Topological quantum matter in synthetic dimensions
- Ultrafast many-body interferometry of impurities coupled to a Fermi sea
- Quantum simulation of an extra dimension
- Ultracold polar molecules as qudits
- Quantum search without entanglement
- Realizing Su-Schrieffer-Heeger topological edge states in Rydberg-atom synthetic dimensions
- Quantum Computing Without Entanglement
- Ultracold Rydberg Molecules
- Strongly interacting ultracold polar molecules
- An atom optics approach to studying lattice transport phenomena
- Rydberg-dressing of atoms in optical lattices
- Quantum logic and entanglement by neutral Rydberg atoms: methods and fidelity
- Synthetic dimensions in ultracold molecules: quantum strings and membranes
- Bayesian optimal control of GHZ states in Rydberg lattices
- Preparation of ordered states in ultra-cold gases using Bayesian optimization
- Solving optimization problems with local light shift encoding on Rydberg quantum annealers
- Charge dynamics of a molecular ion immersed in a Rydberg-dressed atomic lattice gas
- Controlled preparation of phases in two-dimensional time crystals
- Optimizing for an arbitrary Schrödinger cat state