Australasian Science: Australia's authority on science since 1938

The Simplest Quantum Computer That Could Beat Classical Computers

A collaboration that included researchers from Google, NASA and the University of Technology, Sydney (UTS) has drawn a line between quantum and classical computations to answer the question: ”What is the smallest computational task a quantum computer can achieve that is prohibitively hard for today’s classical computers?”

The research, published in Nature Physics (, is the first to identify benchmarks for experimental teams hoping to build near-term quantum computers that might be capable of surpassing the power of classical computers.

“The advantage offered by quantum computers is subtle. Some applications can have an exponential quantum speed-up over classical computers, while others receive no benefit at all,” said Prof Michael Bremner, Chief Investigator at the UTS node of the ARC Centre for Quantum Computation and Communication Technology. “Understanding when quantum computers become useful is essential, especially when we are limited to using the noisy intermediate-scale devices that currently exist.

“Many things can affect the utility of a quantum computer for a given application: the number of qubits, the required circuit depth, and the level of noise in the system are just a few. We attempted to find the frontier between classical and quantum computing; we wanted to find the smallest quantum circuits that can do something that cannot be done at all on a classical computer.”

The team extended recent breakthroughs in quantum computational complexity theory to identify potential benchmarks, and then probed these with classical computational modelling. “We focused our attention on chaotic, or random, quantum circuits because as they get bigger the amount of entanglement grows rapidly. Such circuits produce subtle non-local correlations that make them particularly difficult to model on a classical computer,” Bremner said.

The research found that chaotic circuits of 49 qubits at around circuit depth 40 became difficult to simulate classically at realistically achievable levels of noise. By contrast, Shor’s famous algorithm for determining the prime factors of a number requires thousands of logical qubits (qubits with no noise at all) to outperform the best classical algorithms for this task.