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 resolve optimization issues more swiftly than traditional supercomputers, a phenomenon referred to as “quantum advantage” and illustrated by a USC researcher in a paper recently published in Physical Review Letters.

The research indicates how quantum annealing, a unique variant of quantum computing, exceeds the best existing classical algorithms when searching for near-optimal solutions in intricate challenges.

“Quantum annealing functions by locating low-energy conditions in quantum systems, which correspond to optimal or near-optimal solutions for the problems being addressed,” stated Daniel Lidar, primary 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

Researchers have been striving to prove quantum scaling advantage (where the quantum benefit increases as the size of the problem grows) using a quantum annealer for numerous years. Quantum annealing has long been proposed to offer computational benefits for optimization, yet concrete proof of scaling enhancements over classical approaches has been hard to find. This research redirects the emphasis from exact optimization (where quantum benefit remains unsubstantiated) to approximate optimization, a domain with extensive relevance in both industry and science.

Quantum annealing represents a distinctive kind of quantum computing that employs principles from quantum physics to identify high-quality solutions to challenging optimization problems. Instead of requiring precise optimal outcomes, this research concentrated on sourcing solutions within a given percentage (≥1%) of the optimal value.

Many real-life issues don’t necessitate exact solutions, making this method highly applicable. For instance, when determining stocks to include in a mutual fund, it is usually satisfactory to surpass a leading market index rather than outperform every other stock portfolio.

To illustrate algorithmic quantum scaling advantage, the researchers employed a D-Wave Advantage quantum annealing processor, a specialized type of quantum computing equipment established at USC’s Information Sciences Institute. Similar to all current quantum machines, noise significantly impacts diminishing quantum advantage in quantum annealing.

In addressing this challenge, the team utilized a method called quantum annealing correction (QAC) on the D-Wave’s processor, resulting in over 1,300 error-suppressed logical qubits. This error suppression was crucial in securing the advantage over parallel tempering with isoenergetic cluster moves (PT-ICM), the most effective current classical algorithm for analogous problems.

‘Time-to-epsilon’ performance

The research evidenced quantum advantage by implementing various research methodologies and concentrated on a suite of two-dimensional spin-glass problems with high-precision interactions. “Spin-glass problems represent a category of complicated optimization issues derived from statistical physics models of disordered magnetic systems,” Lidar remarked. Rather than pursuing precise solutions, the researchers assessed “time-to-epsilon” performance, tracking how promptly each method could discover solutions within a predetermined percentage of the optimal result.

The team aspires to broaden their findings to denser, higher-dimensional challenges and investigate real-world optimization applications. Lidar noted that further advancements in quantum hardware and error suppression could enhance the observed advantage. “This paves the way for new pathways in quantum algorithms for optimization tasks where near-optimal solutions suffice.”

# # #

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

The study received support from: Defense Advanced Research Projects Agency (DARPA) Grants HR00112190071 and NASA-DARPA SAA2-403688, U.S. Army Research Office Grant W911NF2310255, NASA.