Generation of quantum phases of matter and finding maximum-weight independent set of unit-disk graphs using Rydberg atoms
- URL: http://arxiv.org/abs/2405.09803v2
- Date: Fri, 5 Jul 2024 10:05:25 GMT
- Title: Generation of quantum phases of matter and finding maximum-weight independent set of unit-disk graphs using Rydberg atoms
- Authors: Ahmed M. Farouk, I. I. Beterov, Peng Xu, I. I. Ryabtsev,
- Abstract summary: We consider the problem of maximum-weight independent set (MWIS) of unit-disk graphs.
The edges of the graph can be drawn according to the unit disk criterion.
We consider driving the quantum system of interacting atoms to the many-body ground state using a non-linear quasi-adiabatic profile.
- Score: 4.619601221994331
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent progress in quantum computing and quantum simulation of many-body systems with arrays of neutral atoms using Rydberg excitation brought unforeseen opportunities towards computational advantage in solving various optimization problems. The problem of maximum-weight independent set (MWIS) of unit-disk graphs is an example of NP-hard optimization problems. 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 the resonance at Rydberg excitation defines weights of these vertices. The edges of the graph can be drawn according to the unit disk criterion. MWIS can be obtained by applying a variational quantum adiabatic algorithm (VQAA). 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 1D and 2D spatial arrangement of the atomic array.
Related papers
- An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem.
We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
arXiv Detail & Related papers (2024-06-11T04:40:05Z) - Gaussian Entanglement Measure: Applications to Multipartite Entanglement
of Graph States and Bosonic Field Theory [50.24983453990065]
An entanglement measure based on the Fubini-Study metric has been recently introduced by Cocchiarella and co-workers.
We present the Gaussian Entanglement Measure (GEM), a generalization of geometric entanglement measure for multimode Gaussian states.
By providing a computable multipartite entanglement measure for systems with a large number of degrees of freedom, we show that our definition can be used to obtain insights into a free bosonic field theory.
arXiv Detail & Related papers (2024-01-31T15:50:50Z) - Generation of complete graph states in a spin-$1/2$ Heisenberg chain
with a globally optimized magnetic field [0.0]
We introduce a method for generating multiparticle complete graph states using a spin$1/2$ Heisenberg $XX$ chain subjected to a time-varying magnetic field.
Our scheme relies exclusively on nearest-neighbor interactions between atoms, with real-time magnetic field formation facilitated by quantum optimal control theory.
arXiv Detail & Related papers (2024-01-03T21:32:35Z) - Exploring the impact of graph locality for the resolution of MIS with
neutral atom devices [0.755972004983746]
We build upon recent progress made for using 3D arrangements to embed more complex classes of graphs.
We report experimental and theoretical results which represent important steps towards tackling hard problems on quantum computers.
arXiv Detail & Related papers (2023-06-23T08:53:16Z) - Embedding the MIS problem for non-local graphs with bounded degree using
3D arrays of atoms [0.0]
The Maximum Independent Set (MIS) is a known NP-hard problem that can be naturally encoded in Rydberg atom arrays.
We present a deterministic and efficient construction to embed a large family of non-local graphs in 3D atomic arrays.
This construction is a first crucial step towards tackling tasks on quantum computers for which no classical efficient epsilon-approximation scheme exists.
arXiv Detail & Related papers (2022-09-12T11:46:10Z) - Quantum optimization with arbitrary connectivity using Rydberg atom
arrays [0.0]
We extend the classes of problems that can be efficiently encoded in Rydberg arrays by constructing explicit mappings from the original problems.
We analyze several examples, including: maximum weighted independent set on graphs with arbitrary connectivity, quadratic unconstrained binary optimization problems with arbitrary or restricted connectivity, and integer factorization.
arXiv Detail & Related papers (2022-09-08T18:00:00Z) - Quantum Optimization of Maximum Independent Set using Rydberg Atom
Arrays [39.76254807200083]
We experimentally investigate quantum algorithms for solving the Maximum Independent Set problem.
We find the problem hardness is controlled by the solution degeneracy and number of local minima.
On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions.
arXiv Detail & Related papers (2022-02-18T19:00:01Z) - Anderson localization of a Rydberg electron [68.8204255655161]
Rydberg atoms inherit their level structure, symmetries, and scaling behavior from the hydrogen atom.
limit is reached by simultaneously increasing the number of ground state atoms and the level of excitation of the Rydberg atom.
arXiv Detail & Related papers (2021-11-19T18:01:24Z) - Rydberg Quantum Wires for Maximum Independent Set Problems with
Nonplanar and High-Degree Graphs [0.7046417074932257]
We present experiments with Rydberg atoms to solve non-deterministic-time hard (NP-hard) problems.
We introduce the Rydberg quantum wire scheme with auxiliary atoms to engineer long-ranged networks of qubit atoms.
Three-dimensional (3D) Rydberg-atom arrays are constructed, overcoming the intrinsic limitations of two-dimensional arrays.
arXiv Detail & Related papers (2021-09-08T09:37:18Z) - Programmable quantum simulation of 2D antiferromagnets with hundreds of
Rydberg atoms [43.55994393060723]
Quantum simulation using synthetic systems is a promising route to solve outstanding quantum many-body problems.
Here, we use programmable arrays of individual atoms trapped in optical tweezers to implement an iconic many-body problem.
We push this platform to an unprecedented regime with up to 196 atoms manipulated with high fidelity.
arXiv Detail & Related papers (2020-12-22T19:00:00Z) - Quantum Simulation of 2D Quantum Chemistry in Optical Lattices [59.89454513692418]
We propose an analog simulator for discrete 2D quantum chemistry models based on cold atoms in optical lattices.
We first analyze how to simulate simple models, like the discrete versions of H and H$+$, using a single fermionic atom.
We then show that a single bosonic atom can mediate an effective Coulomb repulsion between two fermions, leading to the analog of molecular Hydrogen in two dimensions.
arXiv Detail & Related papers (2020-02-21T16:00:36Z)
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.