Quantum optimization methods handle optimization issues using quantum techniques. Mathematical optimization is the process of selecting the optimal solution to a problem from a group of alternatives. The optimization problem is commonly expressed as a minimization problem, in which one attempts to reduce an error that depends on the answer: the optimal solution has the smallest error. Different optimization approaches are used in a variety of industries, including mechanics, economics, and engineering, and as the complexity and amount of data involved increase, more efficient methods of addressing optimization problems are required.
A cooperation between Harvard University and scientists from QuEra Computing, MIT, the University of Innsbruck, and other institutions has proven a ground-breaking application of neutral-atom quantum processors to practical challenges.
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 5th, 2022, in Science Magazine.
Neutral-atom quantum processors had previously been proposed to efficiently encode certain difficult combinatorial optimization problems. The authors not only demonstrate the first implementation of effective quantum optimization on a genuine quantum computer in this important paper, but they also demonstrate unprecedented quantum hardware power.
The presence of a quantum speedup for difficult issue situations is quite encouraging. These findings aid in the development of stronger algorithms and more powerful hardware to address some of the most difficult and pressing computational challenges.
Mikhail Lukin
The calculations were carried out on Harvard’s quantum processor, which has 289 qubits and operates in analog mode with effective circuit depths of up to 32. Unlike prior examples of quantum optimization, the high system size and circuit depth used in this work made it difficult to pre-optimize the control parameters using classical simulations. A closed loop quantum-classical hybrid method with direct, automated feedback to the quantum processor was required.
This combination of system size, circuit depth, and exceptional quantum control resulted in a quantum leap: problem instances with empirically better-than-expected performance on the quantum processor versus classical heuristics were discovered. The scientists discovered examples that defied classical computers but were more effectively solved with the neutral-atom quantum processor by characterizing the difficulty of the optimization problem instances with a “hardness parameter.” When compared to a class of generic classical algorithms, a super-linear quantum speedup was discovered. QuEra’s open-source packages GenericTensorNetworks.jl and Bloqade.jl were instrumental in discovering hard instances and understanding quantum performance.
“A comprehensive grasp of the underlying physics of the quantum algorithm as well as the fundamental limits of its classical equivalent allowed us to envision possibilities for the quantum machine to achieve a speedup,” explains Madelyn Cain, a Harvard graduate student and one of the primary authors.
The importance of matching 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 team’s solution to the “largest independent set” problem is a paradigmatic hard job in computer science with broad applications in logistics, network design, finance, and other fields. The identification of classically difficult problem instances with quantum-accelerated solutions paves the way for quantum computing to be applied to real-world industrial and social requirements.
“These findings constitute the first step in bringing useful quantum advantage to complex optimization issues important to numerous industries,” said Alex Keesling, CEO of QuEra Computing and co-author on the paper. “We are really pleased to see quantum computing begin to mature to the point where the hardware can inform the creation of algorithms beyond what can be predicted in advance using classical compute methods. Furthermore, the presence of a quantum speedup for difficult issue situations is quite encouraging. These findings aid in the development of stronger algorithms and more powerful hardware to address some of the most difficult and pressing computational challenges.”
