Contact: Will Kwong, [email protected]; USC Media Relations, [email protected] or (213) 740-2215

A quantum computer has the capability to address optimization challenges more swiftly than traditional supercomputers, a phenomenon referred to as “quantum advantage,” recently showcased by a USC researcher in a publication in Physical Review Letters.

The research illustrates how quantum annealing, a distinct type of quantum computing, surpasses the most advanced classical algorithms when looking for near-optimal resolutions in intricate issues.

“Quantum annealing operates by identifying low-energy states within quantum systems, which correspond to optimal or near-optimal answers to the problems at hand,” stated Daniel Lidar, lead author of the research and professor of electrical and computer engineering, chemistry, as well as physics and astronomy at the USC Viterbi School of Engineering and the USC Dornsife College of Letters, Arts and Sciences.

Approximate optimization

For years, scientists have endeavored to showcase quantum scaling advantage (where the quantum benefit amplifies as the problem size expands) using a quantum annealer. While quantum annealing has long been posited to provide computational benefits for optimization, clear proof of scaling enhancements over classical approaches has been hard to obtain. This research shifts attention from precise optimization (where quantum advantage remains unverified) to approximate optimization, a domain with extensive relevance in industry and research.

Quantum annealing is a specific form of quantum computing that harnesses quantum physics principles to discover high-quality solutions for challenging optimization tasks. Instead of requiring exact optimal answers, this study concentrated on obtaining solutions within a certain margin (≥1%) of the optimal value.

Numerous real-world scenarios do not demand exact solutions, rendering this method pragmatically significant. For instance, in deciding which stocks to include in a mutual fund, it is frequently sufficient to merely outperform a leading market index rather than surpassing every single stock portfolio.

To illustrate algorithmic quantum scaling advantage, the researchers employed a D-Wave Advantage quantum annealing processor, a specialized quantum computing device installed at USC’s Information Sciences Institute. As is the case with all existing quantum computers, noise significantly undermines quantum advantage in quantum annealing.

To mitigate this challenge, the team applied a technique known as quantum annealing correction (QAC) on the D-Wave’s processor, establishing over 1,300 error-suppressed logical qubits. This error mitigation was crucial in achieving an advantage over parallel tempering with isoenergetic cluster moves (PT-ICM), the most effective classical algorithm currently available for similar problems.

‘Time-to-epsilon’ performance

The research substantiated quantum advantage by utilizing multiple investigative methods and zeroed in on a series of two-dimensional spin-glass challenges with high-precision interactions. “Spin-glass issues are a category of complex optimization dilemmas that arise from statistical physics models of disordered magnetic systems,” Lidar noted. Rather than pursuing exact solutions, the researchers evaluated “time-to-epsilon” performance, gauging how swiftly each method could find solutions within a designated margin of the optimal response.

The researchers aspire to broaden their findings to denser, higher-dimensional problems and examine real-world optimization applications. Lidar indicated that further enhancements in quantum hardware and error suppression could amplify the observed benefits. “This paves the way for new prospects in quantum algorithms for optimization tasks where near-optimal solutions suffice.”

# # #

About the study: The research was co-authored by Humberto Munoz-Bauza of the NASA Ames Research Center and Lidar.

The research was funded by: Defense Advanced Research Projects Agency (DARPA) Grants HR00112190071 and NASA-DARPA SAA2-403688, U.S. Army Research Office Grant W911NF2310255, NASA.