Approximate combinatorial optimization with Rydberg atoms: the barrier of interpretability

Abstract

Analog quantum computing with Rydberg atoms is seen as an avenue to solve hard graph optimization problems, because they naturally encode the Maximum Independent Set (MIS) problem on Unit-Disk (UD) graphs, a problem that admits rather efficient approximation schemes on classical computers. Going beyond UD-MIS to address generic graphs requires embedding schemes, typically with chains of ancilla atoms, and an interpretation algorithm to map results back to the original problem. However, interpreting approximate solutions obtained with realistic quantum computers proves to be a difficult problem. As a case study, we evaluate the ability of two interpretation strategies to correct errors in the recently introduced Crossing Lattice embedding. We find that one strategy, based on finding the closest embedding solution, leads to very high qualities, albeit at an exponential cost. The second strategy, based on ignoring defective regions of the embedding graph, is polynomial in the graph size, but it leads to a degradation of the solution quality which is prohibitive under realistic assumptions on the defect generation. Moreover, more favorable defect scalings lead to a contradiction with well-known approximability conjectures. Therefore, it is unlikely that a scalable and generic improvement in solution quality can be achieved with Rydberg platforms -- thus moving the focus to heuristic algorithms.

24 pages, 19 figures

References in corpus (15)

• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Adiabatic Quantum Computing
• Observation of Rydberg blockade between two atoms
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Quantum optimization with arbitrary connectivity using Rydberg atom arrays
• Rydberg blockade based parity quantum optimization
• Solving optimization problems with Rydberg analog quantum computers: Realistic requirements for quantum advantage using noisy simulation and classical benchmarks
• Computing solution space properties of combinatorial optimization problems via generic tensor networks
• The Quantum PCP Conjecture
• Benchmarking digital quantum simulations above hundreds of qubits using quantum critical dynamics
• Demonstration of weighted graph optimization on a Rydberg atom array using local light-shifts
• Circumventing superexponential runtimes for hard instances of quantum adiabatic optimization
• Rydberg-atom graphs for quadratic unconstrained binary optimization problems
• Quantum adiabatic optimization with Rydberg arrays: localization phenomena and encoding strategies
• A Rydberg-atom approach to the integer factorization problem