Breaking the speed limits of quantum computing

Quantum computing promises to solve problems much more quickly than the classical computers we are familiar with.

However, for a broad range of computing problems called total functions, which include common operations like searching and sorting, the speed improvement is assumed to be at most quadratic (a power of two), requiring 2N/2 steps compared to 2N steps for classical computing.

Take the ubiquitous problem of searching, for example. A quantum computer is currently able to find a desired item in a database using quadratically fewer look-ups to the database than a classical computer needs using a standard algorithm.

In this study, Assoc Prof Troy Lee of NTU’s School of Physical and Mathematical Sciences, together with researchers from the National University of Singapore and the University of Latvia, gave an example of a total function that can be solved by a quantum computer in a fourth power fewer steps than classical computing (2N/4 steps compared to 2N steps).

This means that, tasked with a database search, for instance, a classical computer might need 100 million steps to find a desired item in a database while it would take a quantum computer only 10,000 steps with a quadratic speedup and only 100 steps with a fourth power speedup.

By demonstrating that a quantum computer is able to solve a total function more quickly than believed possible, the researchers’ findings may inspire further exploration of super-quadratic speedups for other computing problems.

The study “Separations in query complexity based on pointer functions” appeared in Journal of the Association for Computing Machinery (2017), DOI: 10.1145/3106234.
This article appeared first in NTU’s research & innovation magazine Pushing Frontiers (issue #14, December 2018).

You may also like...