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.
arXiv comment13 pages, 9 figures
References in corpus (40)
- Probing many-body dynamics on a 51-atom quantum simulator
- Many-Body Physics with Individually-Controlled Rydberg Atoms
- Quantum Phases of Matter on a 256-Atom Programmable Quantum Simulator
- Probing Topological Spin Liquids on a Programmable Quantum Simulator
- Dynamics of a Quantum Phase Transition
- Programmable quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- Demonstration of multi-qubit entanglement and algorithms on a programmable neutral atom quantum computer
- Quantum Kibble-Zurek mechanism and critical dynamics on a programmable Rydberg simulator
- ARC: An open-source library for calculating properties of alkali Rydberg atoms
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- Competing density-wave orders in a one-dimensional hard-boson model
- Kibble-Zurek Mechanism in a Spin-1 Bose-Einstein Condensate
- Quantum optimization with arbitrary connectivity using Rydberg atom arrays
- Numerical study of the chiral quantum phase transition in one spatial dimension
- Rydberg blockade, Förster resonances, and quantum state measurements with different atomic species
- A Coherent Quantum Annealer with Rydberg Atoms
- Towards adiabatic quantum computing using compressed quantum circuits
- Bounding the costs of quantum simulation of many-body physics in real space
- Two-qubit gates using adiabatic passage of the Stark-tuned Förster resonances in Rydberg atoms
- Driver Hamiltonians for constrained optimization in quantum annealing
- Quantum simulation of Ising spins on Platonic graphs
- Adiabatic Spectroscopy and a Variational Quantum Adiabatic Algorithm
- Programmable Quantum Annealing Architectures with Ising Quantum Wires
- 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