Quantum computers, technologies that perform computations leveraging quantum mechanical phenomena, could eventually outperform classical computers on many complex computational and optimization problems. While some quantum computers have attained remarkable results on some tasks, their advantage over classical computers is yet to be conclusively and consistently demonstrated.
Ramis Movassagh, a researcher at Google Quantum AI, who was formerly at IBM Quantum, recently carried out a theoretical study aimed at mathematically demonstrating the notable advantages of quantum computers. His paper, published in Nature Physics, mathematically shows that simulating random quantum circuits and estimating their outputs is so-called #P-hard for classical computers (i.e., meaning that is highly difficult).
“A key question in the field of quantum computation is: Are quantum computers exponentially more powerful than classical ones?” Ramis Movassagh, who carried out the study, told Phys.org. “Quantum supremacy conjecture (which we renamed to Quantum Primacy conjecture) says yes. However, mathematically it’s been a major open problem to establish rigorously.”