Quantum Hamiltonian Algorithms for Maximum Independent Sets

Abstract

With qubits encoded into atomic ground and Rydberg states and situated on the vertexes of a graph, the conditional quantum dynamics of Rydberg blockade, which inhibits simultaneous excitation of nearby atoms, has been employed recently to find maximum independent sets following an adiabatic evolution algorithm hereafter denoted by HV [Science 376, 1209 (2022)]. An alternative algorithm, short named the PK algorithm, reveals that the independent sets diffuse over a media graph governed by a non-abelian gauge matrix of an emergent PXP model. This work shows the above two algorithms are mathematically equivalent, despite of their seemingly different physical implementations. More importantly, we demonstrated that although the two are mathematically equivalent, the PK algorithm exhibits more efficient and resource-saving performance. Within the same range of experimental parameters, our numerical studies suggest that the PK algorithm performs at least 25% better on average and saves at least $6\times 10^6$ measurements ($\sim 900$ hours of continuous operation) for each graph when compared to the HV algorithm. We further consider the measurement error and point out that this may cause the oscillations in the performance of the HV's optimization process.

7pages, 6figures

References in corpus (26)

• Quantum information with Rydberg atoms
• Probing many-body dynamics on a 51-atom quantum simulator
• Logical quantum processor based on reconfigurable atom arrays
• Quantum many-body scars
• Quantum Many-Body Scars and Weak Breaking of Ergodicity
• High-fidelity parallel entangling gates on a neutral atom quantum computer
• Quantum scarred eigenstates in a Rydberg atom chain: entanglement, breakdown of thermalization, and stability to perturbations
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• High-fidelity control and entanglement of Rydberg atom qubits
• Emergent SU(2) dynamics and perfect quantum many-body scars
• Competing density-wave orders in a one-dimensional hard-boson model
• Mott insulators in strong electric fields
• Analysis of imperfections in the coherent optical excitation of single atoms to Rydberg states
• Quantum phases of Rydberg atoms on a kagome lattice
• A concise review of Rydberg atom based quantum computation and quantum simulation
• Consistency of the Adiabatic Theorem
• Entangling two atoms of different isotopes via Rydberg blockade
• Exact Algorithms for Maximum Independent Set
• Many-body Hilbert space scarring on a superconducting processor
• High-fidelity Rydberg-blockade entangling gate using shaped, analytic pulses
• Quantum Computing with Circular Rydberg Atoms
• Adiabatic Spectroscopy and a Variational Quantum Adiabatic Algorithm
• Manipulating synthetic gauge fluxes via multicolor dressing of Rydberg-atom arrays
• Circumventing superexponential runtimes for hard instances of quantum adiabatic optimization
• Quantum independent set problem and non-abelian adiabatic mixing
• Quantum Algorithm for Approximating Maximum Independent Sets