New! Sign up for our free email newsletter.
Science News
from research organizations

Theoretical quantum speedup with the quantum approximate optimization algorithm

May 29, 2024
DOE/Argonne National Laboratory
Researchers demonstrated a quantum algorithmic speedup with the quantum approximate optimization algorithm, laying the groundwork for advancements in telecommunications, financial modeling, materials science and more.

In a new paper in Science Advances on May 29, researchers at JPMorgan Chase, the U.S. Department of Energy's (DOE) Argonne National Laboratory and Quantinuum have demonstrated clear evidence of a quantum algorithmic speedup for the quantum approximate optimization algorithm (QAOA).

This algorithm has been studied extensively and has been implemented on many quantum computers. It has potential application in fields such as logistics, telecommunications, financial modeling and materials science.

"This work is a significant step towards reaching quantum advantage, laying the foundation for future impact in production," said Marco Pistoia, head of Global Technology Applied Research at JPMorgan Chase.

The team examined whether a quantum algorithm with low implementation costs could provide a quantum speedup over the best-known classical methods. QAOA was applied to the Low Autocorrelation Binary Sequences problem, which has significance in understanding the behavior of physical systems, signal processing and cryptography. The study showed that if the algorithm was asked to tackle increasingly larger problems, the time it would take to solve them would grow at a slower rate than that of a classical solver.

To explore the quantum algorithm's performance in an ideal noiseless setting, JPMorgan Chase and Argonne jointly developed a simulator to evaluate the algorithm's performance at scale. It was built on the Polaris supercomputer, accessed through the Argonne Leadership Computing Facility (ALCF), a DOE Office of Science user facility. The ALCF is supported by DOE's Advanced Scientific Computing Research program.

"The large-scale quantum circuit simulations efficiently utilized the DOE petascale supercomputer Polaris located at the ALCF. These results show how high performance computing can complement and advance the field of quantum information science," said Yuri Alexeev, a computational scientist at Argonne. Jeffrey Larson, a computational mathematician in Argonne's Mathematics and Computer Science Division, also contributed to this research.

To take the first step toward practical realization of the speedup in the algorithm, the researchers demonstrated a small-scale implementation on Quantinuum's System Model H1 and H2 trapped-ion quantum computers. Using algorithm-specific error detection, the team reduced the impact of errors on algorithmic performance by up to 65%.

"Our long-standing partnership with JPMorgan Chase led to this meaningful and noteworthy three-way research experiment that also brought in Argonne. The results could not have been achieved without the unprecedented and world leading quality of our H-Series Quantum Computer, which provides a flexible device for executing error-correcting and error-detecting experiments on top of gate fidelities that are years ahead of other quantum computers," said Ilyas Khan, founder and chief product officer of Quantinuum.

Story Source:

Materials provided by DOE/Argonne National Laboratory. Note: Content may be edited for style and length.

Journal Reference:

  1. Ruslan Shaydulin, Changhao Li, Shouvanik Chakrabarti, Matthew DeCross, Dylan Herman, Niraj Kumar, Jeffrey Larson, Danylo Lykov, Pierre Minssen, Yue Sun, Yuri Alexeev, Joan M. Dreiling, John P. Gaebler, Thomas M. Gatterman, Justin A. Gerber, Kevin Gilmore, Dan Gresh, Nathan Hewitt, Chandler V. Horst, Shaohan Hu, Jacob Johansen, Mitchell Matheny, Tanner Mengle, Michael Mills, Steven A. Moses, Brian Neyenhuis, Peter Siegfried, Romina Yalovetzky, Marco Pistoia. Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem. Science Advances, 2024; 10 (22) DOI: 10.1126/sciadv.adm6761

Cite This Page:

DOE/Argonne National Laboratory. "Theoretical quantum speedup with the quantum approximate optimization algorithm." ScienceDaily. ScienceDaily, 29 May 2024. <>.
DOE/Argonne National Laboratory. (2024, May 29). Theoretical quantum speedup with the quantum approximate optimization algorithm. ScienceDaily. Retrieved June 19, 2024 from
DOE/Argonne National Laboratory. "Theoretical quantum speedup with the quantum approximate optimization algorithm." ScienceDaily. (accessed June 19, 2024).

Explore More

from ScienceDaily