Scientists observe quantum speed-up in optimization problems

The study was co-led by Mikhail Lukin, the George Vasmer Leverett Professor of Physics at Harvard and co-director of the Harvard Quantum Initiative, Markus Greiner, George Vasmer Leverett Professor of Physics, and Vladan Vuletic, Lester Wolfe Professor of Physics at MIT. Titled "Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays," was published on May 5^th, 2022, in Science Magazine.

Previously, neutral-atom quantum processors had been proposed to efficiently encode certain hard combinatorial optimization problems. In this landmark publication, the authors not only deploy the first implementation of efficient quantum optimization on a real quantum computer, but also showcase unprecedented quantum hardware power.

The calculations were performed on Harvard's quantum processor of 289 qubits operating in the analog mode, with effective circuit depths up to 32. Unlike in previous examples of quantum optimization, the large system size and circuit depth used in this work made it impossible to use classical simulations to pre-optimize the control parameters. A quantum-classical hybrid algorithm had to be deployed in a closed loop, with direct, automated feedback to the quantum processor.

This combination of system size, circuit depth, and outstanding quantum control culminated in a quantum leap: problem instances were found with empirically better-than-expected performance on the quantum processor versus classical heuristics. Characterizing the difficulty of the optimization problem instances with a "hardness parameter," the team identified cases that challenged classical computers, but that were more efficiently solved with the neutral-atom quantum processor. A super-linear quantum speed-up was found compared to a class of generic classical algorithms. QuEra's open-source packages GenericTensorNetworks.jl and Bloqade.jl were instrumental in discovering hard instances and understanding quantum performance.

"A deep understanding of the underlying physics of the quantum algorithm as well as the fundamental limitations of its classical counterpart allowed us to realize ways for the quantum machine to achieve a speedup," says Madelyn Cain, Harvard graduate student and one of the lead authors. The importance of match-making between problem and quantum hardware is central to this work: "In the near future, to extract as much quantum power as possible, it is critical to identify problems that can be natively mapped to the specific quantum architecture, with little to no overhead," said Shengtao Wang, Senior Scientist at QuEra Computing and one of the coinventors of the quantum algorithms used in this work, "and we achieved exactly that in this demonstration."

The "maximum independent set" problem, solved by the team, is a paradigmatic hard task in computer science and has broad applications in logistics, network design, finance, and more. The identification of classically challenging problem instances with quantum-accelerated solutions paves the path for applying quantum computing to cater to real-world industrial and social needs.

"These results represent the first step towards bringing useful quantum advantage to hard optimization problems relevant to multiple industries.," added Alex Keesling CEO of QuEra Computing and co-author on the published work. "We are very happy to see quantum computing start to reach the necessary level of maturity where the hardware can inform the development of algorithms beyond what can be predicted in advance with classical compute methods. Moreover, the presence of a quantum speedup for hard problem instances is extremely encouraging. These results help us develop better algorithms and more advanced hardware to tackle some of the hardest, most relevant computational problems."