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 (25)

• Variational Quantum Algorithms
• Ising formulations of many NP problems
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Dipole Blockade and Quantum Information Processing in Mesoscopic Atomic Ensembles
• Adiabatic Quantum Computing
• Shortcuts to adiabaticity: concepts, methods, and applications
• Quantum optimization using variational algorithms on near-term quantum devices
• Tensor networks for complex quantum systems
• Shortcuts to adiabaticity by counter-diabatic driving
• Quantum computing with neutral atoms
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Minimizing irreversible losses in quantum systems by local counter-diabatic driving
• Challenges and Opportunities in Quantum Optimization
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Reverse annealing for the fully connected $p$-spin model
• Pulser: An open-source package for the design of pulse sequences in programmable neutral-atom arrays
• Tropical Tensor Network for Ground States of Spin Glasses
• Adiabatic Spectroscopy and a Variational Quantum Adiabatic Algorithm
• NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems
• Quantum-Informed Recursive Optimization Algorithms
• Computing solution space properties of combinatorial optimization problems via generic tensor networks
• 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