A recent study published in Physical Review Letters demonstrates that a quantum computer can outperform traditional supercomputers in solving optimization problems. This process, known as “quantum advantage,” was showcased by researchers using quantum annealing, a specialized form of quantum computing.
The study highlights how quantum annealing outstrips current classical algorithms in finding near-optimal solutions to complex problems. Daniel Lidar, the study’s corresponding author and a professor at the USC Viterbi School of Engineering and the USC Dornsife College of Letters, Arts and Sciences, explained, “The way quantum annealing works is by finding low-energy states in quantum systems, which correspond to optimal or near-optimal solutions to the problems being solved.”
While quantum annealing has long been thought to hold computational benefits for optimization, clear evidence of scaling improvements over classical methods has been hard to come by. This study shifts attention from exact optimization—where quantum advantage is still unproven—to approximate optimization, which has significant potential in both industry and scientific fields.
The researchers used a D-Wave Advantage quantum annealing processor housed at USC’s Information Sciences Institute to demonstrate quantum scaling advantage. They employed a technique called quantum annealing correction (QAC), which created over 1,300 error-suppressed logical qubits. This error suppression was key to achieving performance gains over the parallel tempering with isoenergetic cluster moves (PT-ICM), the leading classical algorithm for similar problems.
Part of the study’s focus was on a category of problems known as two-dimensional spin-glass problems. These challenges are rooted in statistical physics models of disordered magnetic systems. Instead of pursuing exact solutions, the research concentrated on “time-to-epsilon” performance, measuring how swiftly solutions could be found within a specified percentage of the optimal answer.
The researchers hope to extend their work to more complex, higher-dimensional issues and to explore practical applications in real-world optimization problems. Lidar noted that enhancing quantum hardware and error suppression could further boost the observed advantages, saying, “This opens new avenues for quantum algorithms in optimization tasks where near-optimal solutions are sufficient.”
The study was co-authored by Humberto Munoz-Bauza from NASA Ames Research Center and Daniel Lidar. It received support from the Defense Advanced Research Projects Agency (DARPA), U.S. Army Research Office, and NASA.
