Solving optimization problems with local light shift encoding on Rydberg quantum annealers

• URL: http://arxiv.org/abs/2308.07798v2
• Date: Fri, 22 Dec 2023 11:26:03 GMT
• Title: Solving optimization problems with local light shift encoding on Rydberg quantum annealers
• Authors: Kapil Goswami, Rick Mukherjee, Herwig Ott, Peter Schmelcher
• Abstract summary: We provide a non-unit disk framework to solve optimization problems on a Rydberg quantum annealer. Our setup consists of a many-body interacting Rydberg system where locally controllable light shifts are applied to individual qubits. Our numerical simulations implement the local-detuning protocol while globally driving the Rydberg annealer to the desired many-body ground state.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We provide a non-unit disk framework to solve combinatorial optimization problems such as Maximum Cut (Max-Cut) and Maximum Independent Set (MIS) on a Rydberg quantum annealer. Our setup consists of a many-body interacting Rydberg system where locally controllable light shifts are applied to individual qubits in order to map the graph problem onto the Ising spin model. Exploiting the flexibility that optical tweezers offer in terms of spatial arrangement, our numerical simulations implement the local-detuning protocol while globally driving the Rydberg annealer to the desired many-body ground state, which is also the solution to the optimization problem. Using optimal control methods, these solutions are obtained for prototype graphs with varying sizes at time scales well within the system lifetime and with approximation ratios close to one. The non-blockade approach facilitates the encoding of graph problems with specific topologies that can be realized in two-dimensional Rydberg configurations and is applicable to both unweighted as well as weighted graphs. A comparative analysis with fast simulated annealing is provided which highlights the advantages of our scheme in terms of system size, hardness of the graph, and the number of iterations required to converge to the solution.

Related papers

• Quantum adiabatic optimization with Rydberg arrays: localization phenomena and encoding strategies [0.9500919522633157]
  We study the quantum dynamics of the encoding scheme proposed in [Nguyen et al., PRX Quantum 4, 010316 (2023) We look at minimum gap scaling with system size along adiabatic protocols. We observe such localization and its effect on the success probability of finding the correct solution.
  arXiv  Detail & Related papers  (2024-11-07T12:10:01Z)
• Quantization Avoids Saddle Points in Distributed Optimization [1.579622195923387]
  Distributed non optimization underpins key functionalities of numerous distributed systems. The aim of this paper is to prove that it can effectively escape saddle points convergence to a second-order stationary point convergence. With an easily adjustable quantization, the approach allows a user control to aggressively reduce communication overhead.
  arXiv  Detail & Related papers  (2024-03-15T15:58:20Z)
• SIGMA: Scale-Invariant Global Sparse Shape Matching [50.385414715675076]
  We propose a novel mixed-integer programming (MIP) formulation for generating precise sparse correspondences for non-rigid shapes. We show state-of-the-art results for sparse non-rigid matching on several challenging 3D datasets.
  arXiv  Detail & Related papers  (2023-08-16T14:25:30Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  We develop an adaptive inexact Newton method for equality-constrained nonlinear, nonIBS optimization problems. We demonstrate the superior performance of our method on benchmark nonlinear problems, constrained logistic regression with data from LVM, and a PDE-constrained problem.
  arXiv  Detail & Related papers  (2023-05-28T06:33:37Z)
• 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)
• Nonequilibrium Monte Carlo for unfreezing variables in hard combinatorial optimization [1.1783108699768]
  We introduce a quantum-inspired family of nonlocal Nonequilibrium Monte Carlo (NMC) algorithms by developing an adaptive gradient-free strategy. We observe significant speedup and robustness over both specialized solvers and generic solvers.
  arXiv  Detail & Related papers  (2021-11-26T17:45:32Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation. We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions.
  arXiv  Detail & Related papers  (2021-08-18T09:26:17Z)
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks [0.0]
  We show how graph neural networks can be used to solve optimization problems. We find that the neural network performs on par or outperforms existing solvers.
  arXiv  Detail & Related papers  (2021-07-02T16:54:35Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  We propose a hybrid approach to combine the best of the two worlds, in which a bi-level framework is developed with an upper-level learning method to optimize the graph. Such a bi-level approach simplifies the learning on the original hard CO and can effectively mitigate the demand for model capacity.
  arXiv  Detail & Related papers  (2021-06-09T09:18:18Z)
• Pushing the Envelope of Rotation Averaging for Visual SLAM [69.7375052440794]
  We propose a novel optimization backbone for visual SLAM systems. We leverage averaging to improve the accuracy, efficiency and robustness of conventional monocular SLAM systems. Our approach can exhibit up to 10x faster with comparable accuracy against the state-art on public benchmarks.
  arXiv  Detail & Related papers  (2020-11-02T18:02:26Z)

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.