Scientists observe quantum speed-up in optimization problems
Date:
May 5, 2022
Source:
Harvard University
Summary:
Scientists have demonstrated a breakthrough application of
neutral-atom quantum processors to solve problems of practical use.
FULL STORY ==========================================================================
A collaboration between Harvard University with scientists at QuEra
Computing, MIT, University of Innsbruck and other institutions has
demonstrated a breakthrough application of neutral-atom quantum processors
to solve problems of practical use.
==========================================================================
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.
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."
========================================================================== Story Source: Materials provided by Harvard_University. Note: Content
may be edited for style and length.
========================================================================== Journal Reference:
1. S. Ebadi, A. Keesling, M. Cain, T. T. Wang, H. Levine, D. Bluvstein,
G.
Semeghini, A. Omran, J.-G. Liu, R. Samajdar, X.-Z. Luo,
B. Nash, X. Gao, B. Barak, E. Farhi, S. Sachdev, N. Gemelke,
L. Zhou, S. Choi, H. Pichler, S.-T. Wang, M. Greiner, V. Vuletic,
M. D. Lukin. Quantum optimization of maximum independent set using
Rydberg atom arrays. Science, 2022; DOI: 10.1126/science.abo6587 ==========================================================================
Link to news story:
https://www.sciencedaily.com/releases/2022/05/220505150340.htm
--- up 9 weeks, 3 days, 10 hours, 50 minutes
* Origin: -=> Castle Rock BBS <=- Now Husky HPT Powered! (1:317/3)