Hardness-dependent quantum adiabatic schedules for the maximum-independent-set problem

Abstract

We propose a numerical approach to design highly efficient adiabatic schedules for analog quantum computing, focusing on the maximum-independent-set problem and neutral atom platforms. On the basis of a representative dataset of small graphs, we present numerical evidence that the optimum schedules depend principally on the hardness of the problem rather than on its size. These schedules perform better than the benchmark protocols and admit a straightforward implementation in the hardware. This allows us to extrapolate the results to larger graphs and to successfully solve moderately hard problems using QuEra's 256-qubit Aquila computer. We believe that extending our approach to hybrid algorithms could be the key to solving the hardest instances with the current technology, making yet another step toward real-world applications.

References in corpus (7)

• Quantum computing with neutral atoms
• Challenges and Opportunities in Quantum Optimization
• Quantum-Informed Recursive Optimization Algorithms
• Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups
• Designing Quantum Annealing Schedules using Bayesian Optimization
• Circumventing superexponential runtimes for hard instances of quantum adiabatic optimization
• Quantum Computing Dataset of Maximum Independent Set Problem on King's Lattice of over Hundred Rydberg Atoms