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, mathematically shows that simulating random quantum circuits and estimating their outputs is so-called #P-hard for classical computers . "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 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 ," 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!"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 are as hard as the worst-case . "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 , 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 . 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. 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 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!"
Trending
A gorgeous April afternoon in store across the Denver metro area 
‘Artemis Mission Cannot Lead To Interplanetary Wild West,’ Astronomer Warns 
Trump says US forces will ‘finish the job’ soon in first prime-time speech since starting Iran war 
Former Wisconsin football player, who left the sport amid mental health struggles, dead at 24 
Drew McIntyre Gives Honest Take About His Recent WWE Title Reign 
U.S. Sen. Bernie Sanders introduces bill that could keep the Padres in San Diego United States Latest News, United States Headlines
Similar News:You can also read news stories similar to this one that we have collected from other news sources.
Better cybersecurity with quantum random number generation based on a perovskite light emitting diodeDigital information exchange can be safer, cheaper and more environmentally friendly with the help of a new type of random number generator for encryption developed at Linköping University, Sweden. The researchers behind the study believe that the new technology paves the way for a new type of quantum communication.
Read more »
Scientists manipulate quantum mechanics to slow down a chemical reaction by 100 billion timesUsing a quantum device, researchers have observed, for the first time, a molecular process called conical intersection that is important in reactions such as photosynthesis.
Read more »
Checkmate! Quantum Computing Breakthrough Via Scalable Quantum Dot ChessboardNew approach for addressing quantum dots gives prospects to scale the number of qubits in quantum systems and represents a breakthrough for quantum computing. Researchers have developed a way to address many quantum dots with only a few control lines using a chessboard-like method. This enabled the
Read more »
The quantum threat and an effort to make computers safeQuantum computing threatens to unravel all your digital and financial secrets, but new encryption algorithms promise a way out.
Read more »
Graphene’s Quantum Magic: Perfection Is OverratedThe carbon material graphene has excellent electronic properties. But are they also stable enough to be useful in practice? New calculations say: Yes. New computer model demonstrates that graphene's exceptional electronic properties remain stable, even with imperfections, endorsing its potential
Read more »
A theory of strong-field non-perturbative physics driven by quantum lightNon-perturbative interactions (i.e., interactions too strong to be described by so-called perturbation theory) between light and matter have been the topic of numerous research studies. Yet the role that quantum properties of light play in these interactions and the phenomena arising from them have so far remained widely unexplored.
Read more »