A new path towards quantum supremacy is revealed in research led by the University of Technology Sydney’s Centre for Quantum Computation and Intelligent Systems and published in today’s edition of Physical Review Letters.
Driven by the demand for greater computational power, there is now a worldwide race to experimentally demonstrate the supremacy of quantum computers. Quantum computers use the principles of quantum mechanics to run applications that are theorized not to be possible on even the most powerful of current supercomputers.
“The really exciting implication of our results is that really quite simple quantum computers are likely to achieve quantum supremacy. Within a few years we will be doing quantum computations that could, in principle, take an entire lifetime for a traditional, classical, computer to perform,” said first author Professor Michael Bremner (UTS).
So far, a clear demonstration of quantum supremacy has not been achieved because of the
- technological challenges that quantum computers present, and
- difficulty of identifying computations that definitively exhibit a quantum speedup.
Prof Bremner and colleagues from the University of Bristol and CESG have addressed both of these problems.
They have mathematically identified a class of commuting quantum circuits with the key features of quantum supremacy while being technologically simpler to build than general-purpose quantum computers.
“The biggest theoretical challenge in quantum computing is to convincingly prove that they truly outperform classical computers. We have managed to simplify a problem to a straightforward conjecture that, while not solved, is much more approachable due to its deep connections to topics in statistical physics and mathematics,” he said.
Average-case complexity versus approximate simulation of commuting quantum computations
Authors Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd