Study proves the difficulty of simulating random quantum circuits for classical computers

Quantum computers, technologies that perform calculations exploiting quantum mechanical phenomena, could eventually outperform classical computers on many complex computational and optimization problems. Even though some quantum computers have achieved remarkable results on certain tasks, their advantage over classical computers has not yet been conclusively and consistently demonstrated.

Ramis Movassagh, a researcher at Google Quantum AI, formerly at IBM Quantum, recently carried out a theoretical study aimed at mathematically demonstrating the notable advantages of quantum computers. His article, published in Natural Physicsshows mathematically that simulating random quantum circuits and estimating their outputs is what is called #P-hard for classical computers (i.e. it is very hard).

“A key question in the field of quantum computing is: are quantum computers exponentially more powerful than classical computers? Ramis Movassagh, who carried out the study, told Phys.org. “The quantum supremacy conjecture (which we have renamed the quantum primacy conjecture) says yes. However, mathematically it has been a major open problem to be rigorously established.”

Researchers have recently attempted to demonstrate the advantages of quantum computers over classical computers in a variety of ways, both through theoretical and experimental studies. A key to demonstrating this mathematically would be to prove that it is difficult for classical computers to obtain the results of quantum computers with high precision and small margins of error.

“In 2018, a colleague gave a talk at MIT on a then-recent result that attempted to provide evidence for the harshness of in-circuit random sampling (RCS),” Movassagh explained. “RCS is the task of sampling from the output of a random quantum circuit and Google had just proposed it as the main candidate for demonstrating quantum primacy. I was in the audience and had never worked on complexity quantum before; in fact, I remember this. As a graduate student, I even swore never to work in this field!”

The mathematical proof presented by Movassagh’s colleague at MIT in 2018 did not conclusively solve the long-standing problem of proving quantum primacy, but it was a huge step towards that goal. The proof was carried out via a series of approximations and what is called the truncation of the series; it was therefore somewhat indirect and introduced unnecessary errors.

“I like to relate math to solving big open problems, especially if the math is straightforward, less known to experts in the field, and beautiful,” Movassagh said. “In this case, I felt I could probably find better evidence, and I naively thought that if I solved the problem the right way, then I could solve the big open problem. So, I started to work on it.”

The mathematical proof presented by Movassagh differs greatly from those presented so far. It is based on a new set of mathematical techniques that collectively show that the output probabilities of an average case (i.e. a random quantum circuit) are as difficult as the worst case (i.e. say the most artificial).

“The idea is that you can use the Cayley path proposed in the paper to interpolate between two arbitrary circuits, which in this case are considered to be between the worst case and the average case,” Movassagh said. “The Cayley path is a low-degree algebraic function. Since the worst case is known to be #P hard (i.e. a very difficult problem), using the Cayley path, one can interpolate to the average case and show that random circuits are essentially as hard as the worst case with high probability.”

Unlike other mathematical proofs derived from the past, Movassagh’s proof does not involve any approximation and is quite straightforward. This means that it allows researchers to explicitly delineate the errors involved and quantify its robustness (i.e. error tolerance).

Since Movassagh first presented this evidence, his research group and other teams have tested it further and improved its robustness. It could thus soon inform further studies aimed at improving the proof or using it to highlight the potential of quantum computers.

“We achieved direct evidence of the difficulty of estimating the output probabilities of quantum circuits,” Movassagh said. “These provide computational barriers for the classical simulation of quantum circuits. Newer techniques such as the Cayley way and the Berlekemp-Welch version of rational functions” are of independent interest for quantum cryptography, computation, complexity and coding theory. Currently, this is the most promising path to an eventual refutation of Turing’s thesis of the extended Church, which is an imperative goal of quantum complexity theory. ”

Movassagh’s recent work is an essential contribution to ongoing research efforts exploring the advantages of quantum computers over classical computers. In his future studies, he plans to build on his current evidence to mathematically demonstrate the enormous potential of quantum computers to solve specific problems.

“In my future studies, I hope to link this work to the difficulty of other tasks to better map the (in)processability of quantum systems,” Movassagh added. “I study the applications of this work, among others, in quantum cryptography. And finally, I hope to prove the conjecture of quantum primacy and prove that the extended Church-Turing thesis is wrong!”