News
An international collaboration of physicists and computer scientists led by the Harvard-MIT CUA Professors Lukin, Greiner, and Vuletic demonstrated an important milestone in the broad effort to realize practical quantum advantage. The researchers used a programmable Rydberg atom array quantum simulator with up to 289 qubits to solve classically hard combinatorial optimization problems.
They used a hardware-efficient encoding to experimentally implement quantum algorithms for solving the Maximum Independent Set (MIS) problem (See Fig. 1), a combinatorial optimization problem that involves finding the largest set of vertices of a graph that do not share an edge. This problem is not only of theoretical importance, due to being one of the original 21 Karp’s NP-Hard problems, but it’s also of practical importance as it naturally arises in industrial settings such as network communications.
Researchers used closed-loop classical feedback to optimize the performance of the quantum simulator, which coherently operated at large system sizes and circuit depths – far beyond the simulation capabilities of classical computers and other quantum machines. With deep quantum circuits, the quantum simulator was then benchmarked against simulated annealing, a foundational classical algorithm aimed at solving optimization problems. They identified that the hardest problem instances are those who have numerous sub-optimal solutions, but only a few optimal ones. Because of the many-body quantum coherence observed on the quantum simulator for these graph instances, researchers observed a nearly quadratic speedup over simulated annealing in solving for the MIS.
Figure 1: The MIS problem is encoded with atoms placed at the vertices of the target graph, and with interatomic spacing chosen such that each vertex is connected to its nearest and next-nearest neighbors. Shown is an example of a fluorescence image of atoms, with gray lines added to indicate edges between connected vertices. The system undergoes coherent quantum many-body evolution under a programmed laser drive. A site-resolved projective measurement reads out the final quantum many-body state, with atoms excited to the Rydberg state (red circles) corresponding to vertices forming an independent set. A classical optimizer uses the results to update the parameters of the quantum evolution to maximize the size of independent sets found.