Successful demonstration of the difficulty of simulating random quantum circuits by classical computers!

As Moore's Law reaches its limits, quantum computers continue to emerge, promising to dramatically outperform classical computers. It is now possible to create quantum processors with more than 400 quantum bits, which are expected to surpass classical simulations. Along with these developments, the expectation is that at some point quantum computers will be able to accomplish tasks that are nearly impossible for any classical computer.

The main candidate for reaching this threshold is random circuit sampling-that is, sampling the output of a quantum computer after implementing a sequence of random quantum operations. However, it is difficult to theoretically guarantee that classical computers will simulate random quantum circuits with any degree of difficulty.

Ramis Movassagh, a current Google Quantum Artificial Intelligence researcher who worked at IBM Quantum, recently conducted a theoretical study aimed at mathematically demonstrating the significant advantages of quantum computers. His paper, published in Nature Physics, shows mathematically that simulating random quantum circuits and estimating their output is what is known as #P-hard (i.e., very difficult) for classical computers.

"The Quantum Superiority Conjecture is unproven.

"A key question in the field of quantum computing is: are quantum computers exponentially more powerful than classical computers?" Ramis Movassagh, who conducted the study, said, "The Quantum supremacy conjecture (QSC) argues that it is. However, it has been a major open question to establish this rigorously, mathematically speaking."

Recently, researchers have been trying to prove the advantage of quantum computers over classical computers in various ways through theoretical and experimental studies. The key to proving this mathematically is to show that it is difficult for classical computers to achieve the high precision and small error results of quantum computers.

In 2018, an academic gave a talk at MIT on what was then a recent result that sought to provide evidence for the hardness of random circuit sampling (RCS.) Movassagh explains, "RCS is a task that samples from the output of random quantum circuits, which Google has just proposed as the proof of the the leading candidate for quantum superiority."

The mathematical proof presented by Movassagh's colleagues at MIT in 2018 doesn't conclusively address the long-standing problem of proving quantum superiority, but it's a big step toward that goal. The proof was realized through a series of approximations and a so-called truncated series; as such, it was somewhat indirect, and introduced unwanted errors.

Direct proof of the difficulty of estimating the output probability of quantum circuits

"My idea is that the Cayley path proposed in the paper can be utilized to interpolate between any two arbitrary circuits, in which case the two arbitrary circuits are considered to be between the worst case and the average case." The 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 allows interpolation to the average case and proves that the random circuits are essentially as hard as the worst case with high probability.

In contrast to other mathematical proofs derived in the past, Movassagh's proof involves no approximations and is very straightforward. This means that it allows researchers to explicitly bound the error involved and quantify its robustness (i.e., tolerance to error).

Since Movassagh first presented the proof, his research group and others have tested it further and improved its robustness. As such, it could soon inform other research aimed at improving the proof or using it to highlight the potential of quantum computers.

"We have achieved a direct proof of the difficulty of estimating the output probability of quantum circuits, which provides a computational barrier to classical simulations of quantum circuits. The new technique has independent implications for quantum cryptography, computation and complexity, and coding theory. For now, it is the most promising avenue for the eventual refutation of the Extended Church Turing Theory, which is a pressing goal of quantum complexity theory."

Movassagh's latest findings contribute significantly to current research efforts exploring the advantages of quantum computers over classical computers. In future research, he plans to build on existing proofs and mathematically demonstrate the great potential of quantum computers to solve specific problems.

"In my next research, I hope to relate this work to the difficulty of other tasks to better characterize the (dis)operability of quantum systems. I am looking at applications of this work in areas such as quantum cryptography. Last but not least, I hope to prove the Quantum Superiority Conjecture and show that the Extended Church-Turing Theory is wrong!"