Researchers reveal largest quantum speed-up

Quantum computing researchers have for long tried to understand which problems quantum computers can solve faster than classical computers and how big the speed-up can be (i.e. how faster can a problem be solved by quantum computers compared to classical ones). Researchers from Microsoft, the University of Texas at Austin, the University of Waterloo, and the University of California, Berkeley have recently found that the best possible speed-up is quartic (i.e. to the fourth power) for unstructured problems. (An unstructured problem is a problem whose variables we cannot identify until the problem occurs.) This means that, when a quantum computer solves a problem in time T, a classical computer needs time T4 to solve it. The finding enables researchers to better understand the opportunities and limits of quantum computers, but a crucial task remains to find more examples of unstructured problems that can be solved through such methods.