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

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.”

Researchers have recently been trying to demonstrate the advantages of quantum computers over classical computers in various ways, both via theoretical and experimental studies. A key to demonstrating this mathematically would be to prove that it is hard for classical computers to achieve the results of quantum computers with high precision and small margins of error.

“In 2018 a colleague gave a talk at MIT on, at the time, a recent result which tried to provide evidence for the hardness of random circuit 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 lead candidate for demonstrating quantum primacy. I was in the audience and had never worked on quantum complexity before; in fact, I remember that as a grad student I even vowed I’d never work in this field!”

The mathematical proof that Movassagh’s colleague presented at MIT in 2018 did not conclusively solve the long-standing problem of demonstrating quantum primacy yet it was a considerable advancement toward this goal. The proof was achieved via a series of approximations and so-called truncation of series; thus, it was somewhat indirect and introduced unnecessary errors.

“I love to bridge mathematics to solve big open problems, especially if the math is direct, less known to the experts in that field, and is beautiful,” Movassagh said. “In this case, I felt that I could probably find a better proof, and naively thought that if I solved the problem the right way then I might solve the big open problem. So, I set out to work on it.”

The mathematical proof presented by Movassagh greatly differs from those introduced 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., random quantum circuit) are as hard as the worst-case (i.e., most contrived).

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

In contrast with other mathematical proofs derived in the past, Movassagh’s proof does not involve any approximations and is quite direct. This means that it allows researchers to explicitly bound involved errors and quantify its robustness (i.e., its tolerance to errors).

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

“We realized direct proofs of the hardness of estimating the output probabilities of quantum circuits,” Movassagh said, “These provide computational barriers for the classical simulation of quantum circuits. The new techniques such as the Cayley path and rational function version of Berlekemp-Welch are of independent interest for quantum cryptography, computation and complexity, and coding theory. Currently, this is the most promising path toward eventual refutation of Extended-Church Turing thesis, which is an imperative goal of quantum complexity theory.”

The recent work by Movassagh greatly is a key 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 proof to mathematically demonstrate the huge potential of quantum computers for tackling specific problems.

“In my next studies, I hope to bridge this work to the hardness of other tasks to better map out the (in)tractability of quantum systems,” Movassagh added. “I am investigating the applications of this work in quantum cryptography among others. And last but not least, I hope to prove the quantum primacy conjecture and prove that the Extended Church-Turing thesis is false!”

© 2023 Science X Network