Generation of quantum phases of matter and finding a maximum-weight independent set of unit-disk graphs using Rydberg atoms
arXiv:2405.09803 · doi:10.1103/PhysRevA.110.022442
Abstract
Recent progress in quantum computing and quantum simulation of many-body systems with arrays of neutral atoms using Rydberg excitation has provided unforeseen opportunities towards computational advantage in solving various optimization problems. The problem of a maximum-weight independent set of unit-disk graphs is an example of an NP-hard optimization problem. It involves finding the largest set of vertices with the maximum sum of their weights for a graph which has edges connecting all pairs of vertices within a unit distance. This problem can be solved using quantum annealing with an array of interacting Rydberg atoms. For a particular graph, a spatial arrangement of atoms represents vertices of the graph, while the detuning from resonance at Rydberg excitation defines the weights of these vertices. The edges of the graph can be drawn according to the unit disk criterion. Maximum-weight independent sets can be obtained by applying a variational quantum adiabatic algorithm. We consider driving the quantum system of interacting atoms to the many-body ground state using a non-linear quasi-adiabatic profile for sweeping the Rydberg detuning. We also propose using a quantum wire which is a set of auxiliary atoms of a different chemical element to mediate strong coupling between the remote vertices of the graph. We investigate this effect for different lengths of the quantum wire. We also investigate the quantum phases of matter realizing commensurate and incommensurate phases in one- and two-dimensional spatial arrangements of the atomic array.
13 pages, 9 figures
References in corpus (26)
- Probing many-body dynamics on a 51-atom quantum simulator
- Many-Body Physics with Individually-Controlled Rydberg Atoms
- Probing Topological Spin Liquids on a Programmable Quantum Simulator
- Demonstration of multi-qubit entanglement and algorithms on a programmable neutral atom quantum computer
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- Competing density-wave orders in a one-dimensional hard-boson model
- Quantum optimization with arbitrary connectivity using Rydberg atom arrays
- Towards adiabatic quantum computing using compressed quantum circuits
- Quantum simulation of Ising spins on Platonic graphs
- Adiabatic Spectroscopy and a Variational Quantum Adiabatic Algorithm
- Quantum-Informed Recursive Optimization Algorithms
- Universal Quantum Computation in Globally Driven Rydberg Atom Arrays
- Rydberg blockade based parity quantum optimization
- Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
- Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups
- Conformal and chiral phase transitions in Rydberg chains
- Designing Quantum Annealing Schedules using Bayesian Optimization
- Quantum Computing Dataset of Maximum Independent Set Problem on King's Lattice of over Hundred Rydberg Atoms
- Circumventing superexponential runtimes for hard instances of quantum adiabatic optimization
- Solving optimization problems with local light shift encoding on Rydberg quantum annealers
- Rydberg-atom graphs for quadratic unconstrained binary optimization problems
- Interspecies Förster resonances of Rb-Cs Rydberg -states for enhanced multi-qubit gate fidelities
- Low-depth Clifford circuits approximately solve MaxCut
- Parallel implementation of CNOT and CNOT gates via homonuclear and heteronuclear Förster interactions of Rydberg atoms
- Benchmarking a Neutral-Atom Quantum Computer
- Scalable Heteronuclear Architecture of Neutral Atoms Based on EIT