May 1 2017
A new theoretical framework to identify computations that occupy the 'quantum frontier' has been developed by a team of researchers from the UK and Australia. The 'quantum frontier' refers to the boundary at which problems become impossible for the today's available computers and can only be solved with the help of a quantum computer.
The researchers most importantly demonstrate that these computations can be carried out with near-term, intermediate, quantum computers.
Quantum Circuits that form part of the new theoretical framework published in Quantum journal. Credit: Michael Bremner/cqc2t.org
"Until recently it has been difficult to say definitively when quantum computers can outperform classical computers," said Professor Michael Bremner, Chief Investigator at the Centre for Quantum Computation and Communication Technology and founding member of the UTS Centre for Quantum Software and Information (UTS:QSI).
The big challenge for quantum complexity theorists over the last decade has been to find stronger evidence for the existence of the quantum frontier, and then to identify where it lives. We're now getting a sense of this, and beginning to understand the resources required to cross the frontier to solve problems that today's computers can't.
Professor Michael Bremner
These researchers have identified quantum computations that need the least known physical resources that are essential to go beyond the capabilities of classical computers. This indeed is important because of the technological challenges related to scaling up quantum computers.
Prof Bremner explained that the result also highlights that full fault-tolerance may not be needed to outperform classical computers.
To date, it has been widely accepted that error correction would be a necessary component of future quantum computers, but no one has yet been able to achieve this at a meaningful scale.
Bremner.
"Our work shows that while some level of error mitigation is needed to cross the quantum frontier, we may be able to outperform classical computers without the added design complexity of full fault tolerance," he said.
To develop the framework, Dr Ashley Montanaro of the University of Bristol collaborated with Bremner.
"We started out with the goal of defining the minimum resources required to build a post-classical quantum computer, but then found that our model could be classically simulated with a small amount of noise, or physical imperfection," said Montanaro.
"The hope among scientists had always been that if the amount of noise in a quantum system was small enough then it would still be superior to a classical computer, however we have now shown that this probably isn't the case, at least for this particular class of computations," he said.
"We then realised that it is possible to use a classical encoding on a quantum circuit to overcome 'noise' in a much simpler way to mitigate these errors. The effectiveness of this approach was surprising. What it suggests is that we could use such structures to develop new quantum algorithms in a way that can directly avoid certain types of errors."
"This is a result that could lead to useful 'intermediate' quantum computers in the medium term, while we continue to pursue the goal of a full-scale universal quantum computer."