Exploring the impact of graph locality for the resolution of MIS with neutral atom devices

• URL: http://arxiv.org/abs/2306.13373v1
• Date: Fri, 23 Jun 2023 08:53:16 GMT
• Title: Exploring the impact of graph locality for the resolution of MIS with neutral atom devices
• Authors: Constantin Dalyac, Louis-Paul Henry, Minhyuk Kim, Jaewook Ahn, Lo\"ic Henriet
• Abstract summary: 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.
• Score: 0.755972004983746
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the past years, many quantum algorithms have been proposed to tackle hard combinatorial problems. In particular, the Maximum Independent Set (MIS) is a known NP-hard problem that can be naturally encoded in Rydberg atom arrays. By representing a graph with an ensemble of neutral atoms one can leverage Rydberg dynamics to naturally encode the constraints and the solution to MIS. However, the classes of graphs that can be directly mapped ``vertex-to-atom" on standard devices with 2D capabilities are currently limited to Unit-Disk graphs. In this setting, the inherent spatial locality of the graphs can be leveraged by classical polynomial-time approximation schemes (PTAS) that guarantee an $\epsilon$-approximate solution. In this work, we build upon recent progress made for using 3D arrangements of atoms to embed more complex classes of graphs. We report experimental and theoretical results which represent important steps towards tackling combinatorial tasks on quantum computers for which no classical efficient $\varepsilon$-approximation scheme exists.

Related papers

• Generation of quantum phases of matter and finding maximum-weight independent set of unit-disk graphs using Rydberg atoms [4.619601221994331]
  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.
  arXiv  Detail & Related papers  (2024-05-16T04:23:17Z)
• 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)
• Rydberg-atom graphs for quadratic unconstrained binary optimization problems [0.3562485774739681]
  We present an experimental demonstration of how the quadratic unconstrained binary optimization problem can be effectively addressed using Rydbergatom graphs. The Rydberg-atom graphs are configurations of neutral atoms into mathematical graphs facilitated by programmable optical tweezers.
  arXiv  Detail & Related papers  (2023-09-26T11:22:38Z)
• 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)
• 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)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• GeoMol: Torsional Geometric Generation of Molecular 3D Conformer Ensembles [60.12186997181117]
  Prediction of a molecule's 3D conformer ensemble from the molecular graph holds a key role in areas of cheminformatics and drug discovery. Existing generative models have several drawbacks including lack of modeling important molecular geometry elements. We propose GeoMol, an end-to-end, non-autoregressive and SE(3)-invariant machine learning approach to generate 3D conformers.
  arXiv  Detail & Related papers  (2021-06-08T14:17:59Z)
• Hardware-Efficient, Fault-Tolerant Quantum Computation with Rydberg Atoms [55.41644538483948]
  We provide the first complete characterization of sources of error in a neutral-atom quantum computer. We develop a novel and distinctly efficient method to address the most important errors associated with the decay of atomic qubits to states outside of the computational subspace. Our protocols can be implemented in the near-term using state-of-the-art neutral atom platforms with qubits encoded in both alkali and alkaline-earth atoms.
  arXiv  Detail & Related papers  (2021-05-27T23:29:53Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  One of the main challenges in using deep learning-based methods for simulating physical systems is formulating physics-based data. We propose a novel multi-level graph neural network framework that captures interaction at all ranges with only linear complexity. Experiments confirm our multi-graph network learns discretization-invariant solution operators to PDEs and can be evaluated in linear time.
  arXiv  Detail & Related papers  (2020-06-16T21:56:22Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  Graph representation learning has achieved a remarkable success in many graph-based applications, such as node classification, prediction, and community detection. However, for some kind of graph applications, such as graph compression and edge partition, it is very hard to reduce them to some graph representation learning tasks. In this paper, we propose to attack the graph ordering problem behind such applications by a novel learning approach.
  arXiv  Detail & Related papers  (2020-01-18T09:14:16Z)

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.