Quantum computers, with their ability to leverage quantum mechanical phenomena, hold the promise of outperforming classical computers in complex computational and optimization problems. While some quantum computers have achieved impressive results in specific tasks, their advantage over classical computers has yet to be conclusively and consistently demonstrated. However, a recent theoretical study conducted by Ramis Movassagh, a researcher at Google Quantum AI, sheds new light on the advantages of quantum computers. His paper, published in Nature Physics, mathematically demonstrates that simulating random quantum circuits and estimating their outputs is highly difficult for classical computers.
A Longstanding Problem
The field of quantum computation has long grappled with the question of whether quantum computers are exponentially more powerful than classical ones. This question, known as the Quantum Supremacy conjecture, remains a major open problem that poses challenges for researchers. Movassagh’s study aimed to establish a rigorous mathematical proof for the Quantum Supremacy conjecture, which has proved elusive thus far.
Demonstrating the Hardness of Random Circuit Sampling
To mathematically demonstrate the advantages of quantum computers, researchers have been exploring various avenues, both theoretical and experimental. Key to this endeavor is proving that classical computers struggle to achieve the same results as quantum computers with high precision and minimal margin of error. Movassagh recalls a colleague giving a talk at MIT in 2018 on the hardness of random circuit sampling (RCS), where RCS refers to the task of sampling from the output of a random quantum circuit. Google had proposed RCS as a candidate for demonstrating Quantum Supremacy.
While the proof presented by Movassagh’s colleague in 2018 marked progress towards demonstrating quantum primacy, it still fell short of conclusively solving the problem. The proof relied on a series of approximations and truncation of series, introducing unnecessary errors. Movassagh, with his passion for bridging mathematics to solve significant problems, saw an opportunity to find a better proof.
Movassagh’s mathematical proof diverges from previous approaches, utilizing a new set of techniques to demonstrate that the output probabilities of average-case (random quantum circuits) are as difficult as worst-case scenarios. The proof introduces the concept of the Cayley path, a low-degree algebraic function that allows interpolation between arbitrary circuits, including the worst-case and average-case scenarios. By showing that random circuits are as hard as the worst case with high probability, Movassagh’s proof eschews approximations and offers a more direct approach.
Unlike previous mathematical proofs, Movassagh’s proof explicitly bounds errors and quantifies its robustness. This feature allows researchers to assess its tolerance to errors and opens up possibilities for further refinement and improvement.
Movassagh’s proof of the hardness of estimating the output probabilities of quantum circuits is a significant contribution to ongoing research on the advantages of quantum computers. The techniques employed in the proof, such as the Cayley path and rational function version of Berlekemp-Welch, carry independent interest for quantum cryptography, computation, complexity, and coding theory. Moreover, this work represents a promising path towards refuting the Extended Church-Turing thesis, a crucial goal of quantum complexity theory.
While Movassagh’s proof has been tested and improved by his research group and other teams, it holds the potential to inform future studies that explore the power of quantum computers even further. Movassagh plans to build upon this work, extending it to other tasks to gain a better understanding of the tractability of quantum systems. Additionally, he aims to investigate the applications of his findings in quantum cryptography, among other areas. Ultimately, his goal is to prove the quantum primacy conjecture and demonstrate that the Extended Church-Turing thesis is false.
To conclude, Movassagh’s recent mathematical proof represents a substantial advancement in the quest for Quantum Supremacy. By demonstrating the inherent difficulties classical computers face in simulating quantum circuits, this work cements the advantages of quantum computers and sets the stage for future exploration of their potential in solving complex problems.
Leave a Reply