Along the way, they have shown that even simple error-prone quantum computers could have the edge over classical computers for some problems.

“Until recently it has been difficult to say definitively when quantum computers can out-perform classical computers,” said Professor Michael Bremner, chief investigator at the Australian Centre for Quantum Computation and Communication Technology. “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.”

The team has identified quantum computations that require the least known physical resources required to go beyond the capabilities of classical computers and, according to Bremner, result indicate that full fault-tolerance may not be required.

“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,” said 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.”

Dr Ashley Montanaro of the University of Bristol works on the team.

“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,” said Montanaro. “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.”

Such ‘intermediate’ quantum computers could be used in the medium term, while routes to full-scale universal quantum computers are sought.

Image credit
Michael Bremner Australian Centre for Quantum Computation and Communication Technology