Quantum computer surpasses supercomputers in approximate optimization tasks

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

A quantum computer can address optimization challenges more swiftly than traditional supercomputers, a phenomenon termed “quantum advantage,” as demonstrated by a researcher from USC in a paper recently published in Physical Review Letters.

The research illustrates how quantum annealing, a distinct type of quantum computing, surpasses the best existing classical algorithms when it comes to locating nearly-optimal solutions for intricate issues.

“Quantum annealing functions by identifying low-energy states in quantum systems, which correlate to optimal or nearly-optimal results for the problems at hand,” stated Daniel Lidar, the study’s corresponding author and professor of electrical and computer engineering, chemistry, and physics and astronomy at the USC Viterbi School of Engineering and the USC Dornsife College of Letters, Arts and Sciences.

Approximate optimization

Researchers have been laboring to demonstrate quantum scaling advantage (where the quantum advantage enlarges as the problem scale increases) through the use of a quantum annealer for numerous years. Quantum annealing has long been hypothesized to provide computational benefits for optimization, yet conclusive evidence of scaling enhancements over classical techniques has remained hard to find. This study redirects the emphasis from exact optimization (where quantum advantage still lacks validation) to approximate optimization, a field with extensive relevance in both industry and science.

Quantum annealing is a certain category of quantum computing that leverages quantum physics principles to seek high-quality solutions for challenging optimization issues. Instead of demanding exact optimal solutions, the investigation concentrated on securing results within a specified range (≥1%) of the optimal figure.

Numerous real-world challenges do not necessitate precise solutions, making this method greatly applicable. For instance, when deciding which stocks to include in a mutual fund, it often suffices to merely outperform a leading market index rather than exceeding every other stock portfolio.

To illustrate algorithmic quantum scaling advantage, the investigators utilized a D-Wave Advantage quantum annealing processor, a specialized form of quantum computing device situated at USC’s Information Sciences Institute. As with all current quantum computers, noise plays a significant role in undermining quantum advantage in quantum annealing.

To mitigate this complication, the team applied a technique known as quantum annealing correction (QAC) on the D-Wave’s processor, generating over 1,300 error-suppressed logical qubits. This error mitigation was critical to achieving an advantage over parallel tempering with isoenergetic cluster moves (PT-ICM), which is the most effective contemporary classical algorithm for parallel problems.

‘Time-to-epsilon’ performance

The exploration exhibited quantum advantage by employing various research methodologies and centered on a class of two-dimensional spin-glass issues with high-precision interactions. “Spin-glass issues are a category of complex optimization challenges stemming from statistical physics models of disordered magnetic systems,” Lidar remarked. Rather than pursuing exact answers, the researchers evaluated “time-to-epsilon” performance, gauging how swiftly each method could identify solutions within a given percentage of the ideal response.

The researchers aspire to broaden their discoveries to denser, higher-dimensional challenges and investigate applications in real-world optimization. Lidar indicated that further enhancements in quantum hardware and error suppression could amplify the recognized advantage. “This opens fresh pathways for quantum algorithms in optimization tasks where near-optimal results are adequate.”

# # #

About the research: The study was co-authored by Humberto Munoz-Bauza of the NASA Ames Research Center along with 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.