A study demonstrating the difficulty of simulating random quantum circuits for classical computers

Quantum computers, technologies that perform computational operations that take advantage of the phenomena of quantum mechanics, could eventually outperform classical computers on many complex computational and optimization problems. While some quantum computers have achieved remarkable results in some tasks, their superiority over classical computers has not yet been conclusively and consistently demonstrated.

Google Quantum AI researcher Ramis Mufasagh, formerly of IBM Quantum, recently conducted a theoretical study aimed at mathematically demonstrating the remarkable advantages of quantum computers. His paper published in nature physicsmathematically showing that simulating random quantum circuits and estimating their output is called #P-hard for classical computers (that is, very difficult).

“A key question in the field of quantum computation is: Are quantum computers exponentially more powerful than classical computers?” Ramis Mufasagh, who conducted the study, told Phys.org. “The quantum supremacy conjecture (which we have renamed the quantum supremacy conjecture) says yes. However, mathematically speaking, it was a big open problem that had to be rigorously proven.”

Recently, researchers have been trying to prove the advantages of quantum computers over classical computers in various ways, either through theoretical or experimental studies. The key to proving this mathematically is to prove that it is difficult for classical computers to achieve the results of quantum computers with high accuracy and a small margin of error.

“In 2018, a colleague gave a talk at MIT, at the time, about a recent result that attempted to provide evidence for the robustness of random circuit sampling (RCS),” Mufasag explained. “RCS is a task of sampling the output of an arbitrary quantum circuit and Google has just proposed it as a prime candidate for quantum primacy. I was in the audience and had never worked on quantum complexity before; in fact, I remember it as a graduate student, swearing I would never work In this area!”

The mathematical proof presented by a Mufasagh colleague at MIT in 2018 did not definitively solve the long-standing problem of demonstrating quantum primacy, and yet it was a significant advance toward that goal. The proof is achieved by a series of approximations and what is called series truncation; Thus, it was somewhat indirect and introduced unnecessary errors.

“I like to connect mathematics to solve large open-ended problems, especially if the mathematics is straightforward, less known to the experts in the field, and beautiful,” Mufasag said. “In this case, I felt that maybe I could find a better clue, and I naively thought that if I solved the problem in the right way, I might be able to solve the big open problem. So, I set to work on it.”

The mathematical proof presented by Mufasagh differs significantly from that presented thus far. It relies on a new set of mathematical techniques that collectively show that the output probabilities for an average state (ie a random quantum circuit) are just as difficult as the worst case (ie the most contrived).

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

In contrast to other mathematical proofs derived in the past, Mufasagh’s proof does not involve any approximations and is quite straightforward. This means that it allows researchers to explicitly correlate the errors in question and measure their robustness (that is, their tolerance to errors).

Since Mufasagh first came up with the proof, his research group and others have tested it and improved its robustness. So it could soon provide additional information for studies aimed at improving the evidence or using it to highlight the potential of quantum computers.

“We recognized direct evidence of the difficulty in estimating output probabilities of quantum circuits. These provide computational barriers to classical simulations of quantum circuits,” Mofasag said. “New techniques such as the Cayley path and Berlekemp-Welch rational function version are of independent interest to quantum cryptography, computation and complexity, and cryptography theory.” . Currently, this is the most promising path toward refuting Turing’s extended church thesis, which is an inevitable goal of quantum complexity theory.”

Mufasagh’s recent work is largely a major contribution to the ongoing research effort to explore the advantages of quantum computers over classical computers. In future studies, he plans to build on his current proof to mathematically prove the enormous potential of quantum computers to tackle specific problems.

“In my next study, I hope to correlate this work with the difficulty of other tasks in order to better map the tractability of quantum systems,” Mufasag added. “I am investigating the applications of this work in quantum cryptography among others. Last but not least, I hope to prove the quantum primacy conjecture and prove the extended Church-Turing thesis wrong!”