P-computers can solve spin-glass problems faster than quantum systems

Summary

“To solve this problem required us to build p-computers at sizes we had never gone to before,” Çamsarı said, “We used millions of p-bits and then did simulations on CPUs to see how they will behave at much larger scales, using existing chips that we customize.” The idea to use so many p-bits came accidentally. Two Ph.D. students from the University of Messina, in Italy — Andrea Grimaldi who was visiting the Çamsari lab, and Eleonora Raimondo, who was in Messina — began to see non-intuitive favorable behavior while working with very large numbers of p-bits. “It took a year or so to understand and develop a theory for why having lots of p-bits in parallel improves performance in such an unexpected way,” Chowdhury recalled. “Then, we wondered, ‘Can we build it?’ So, we got more collaborators to work on the paper and their collective opinion was, ‘Yes, in principle, this chip will work.’” Chowdhury spent two years on the project. The result was the paper establishing that, when co-designed with hardware to implement powerful Monte Carlo algorithms, a p-computer provides a compelling and scalable classical pathway for solving hard optimization problems. Focusing on two key algorithms applied to 3D spin glasses — discrete-time simulated quantum annealing and adaptive parallel tempering — the researchers showed that the p-computer outperformed a leading quantum annealer on the same problems. They further demonstrated, the team writes, that “These algorithms are readily implementable using currently available hardware, suggesting that specialized chips can leverage massive parallelism to accelerate these algorithms by orders of magnitude while drastically improving energy efficiency. Our results establish a new and rigorous classical baseline, clarifying the landscape for assessing a practical quantum advantage.” “We previously had a chip with tens of thousands of p-bits, but modern semiconductor technology makes it possible to build one that can house millions of p-bits,” ...