So you’ve built a quantum computer. Now what can it do?

A practical quantum computer is probably achievable within the next decade. That’s the belief of many experts, anyway. But once we have one, what can we do with it?

“We are just starting to grapple with that question,” said Michele Mosca, a pioneer in quantum algorithm design at Perimeter Institute and the Institute for Quantum Computing, earlier this summer. “It is like trying to ask, before we had the internet, what will the internet be useful for? Even when we had it, in the 1990s, we didn’t really know. The predictions we had then did not really capture everything we are using it for today.”

But that doesn’t mean theorists can’t begin to search for applications now. Indeed, there is a whole field of study dedicated to the search for new quantum algorithms: the instruction manuals that quantum computers will need to follow to carry out tasks.

Algorithms as problem solvers

All computers, both classical and quantum, use algorithms. Most people are familiar with social media algorithms, for example, which are designed to find and deliver content related to the user’s interests. But algorithms can help solve all kinds of problems. 

For quantum algorithms, the aim is to enable a quantum machine to achieve a result more efficiently than a classical machine by taking advantage of the unique probabilistic nature of quantum bits, or qubits. The goal is to achieve so-called quantum advantage – the milestone where a quantum computer successfully solves a problem or completes a calculation more efficiently than the best possible classical computer.

This is just one of several criteria that quantum algorithms must meet to be considered useful. A second criterion is that it must also be possible to prove mathematically that the algorithm will actually do what it says on the tin (since we can’t yet test it practically, at least not at full scale). And lastly, it ought to do something actually useful, or solve an actual problem, and not just resolve a numerical curiosity.

Some quantum algorithms already exist that approach these standards. And while we don’t yet have a full-scale quantum computer to test potential algorithms on, theorists can use known laws of physics and mathematics to tease out which quantum algorithms might be useful, and which are dead ends. And of course, today’s noisy, small-scale quantum computers are able to probe the possibilities of various quantum algorithms at an experimental level.

The quantum algorithm that shook the world

It was, in fact, the development of a theoretical quantum algorithm that sparked the quantum computing race in the first place. In the early 1990s, quantum computing seemed so far from reality that most experts didn’t take it seriously. That all changed with the development of Shor’s algorithm by mathematician Peter Shor in 1994.

Shor’s algorithm suggests that a quantum computer would be able to factor large integers, and quickly. Far more quickly than a classical computer can. In doing so, it would undermine one of the most widely used cybersecurity encryption methods worldwide, known as RSA. 

RSA works because factoring large integers is difficult.

In RSA, you have a private key that only you know, which consists of two large prime numbers. But there is also a public key that allows you to send or verify messages, and the public key is the product of the prime numbers.

If Shor’s algorithm suddenly made factoring the product of two prime numbers trivially easy – well, that would be bad news for global cybersecurity.

With Shor’s algorithm, quantum computing suddenly became a topic of real global importance, rather than a theoretical curiosity, and lots of work has been done since then to make sure cybersecurity systems are ready for the quantum era.

More quantum algorithms, quantum simulations, and early experimental verification

Since 1994, the search for new algorithms has been ongoing. Another famous example is Grover’s algorithm, a search algorithm that can speed up search times (quadratically, not exponentially). 

There are also quantum approaches to optimization problems like quantum annealing, which could, for example, help find the lowest-energy solution among a variety of options and reduce the power requirements of new technologies.

Among the most valuable scientific applications of quantum algorithms discovered so far are those that help simulate quantum systems. As a quantum system evolves, or as the number of particles in a system grows, the challenges of simulating it grow exponentially, making research in this area prohibitively resource-intensive. But quantum techniques could make such simulations much more feasible – indeed, they already are.

The first experimental implementation of a quantum algorithm on a physical system was achieved in 1998, by Mosca and Jonathan A. Jones at Oxford University. This was an algorithm called Deutsch’s algorithm (which was, in fact, the first ever quantum algorithm). 

Deutsch’s algorithm does not meet all the criteria for a ‘useful’ quantum algorithm, as it relates to a problem that can technically be solved with a classical computer in a reasonable time. But the successful execution of Deutsch's algorithm on a quantum computer was a world first for the practical implementation of quantum algorithms.

Today, researchers in Canada and elsewhere are testing more and more complex quantum simulations, refining quantum algorithms to run on noisy quantum computers, and pushing the field in new directions. As the hardware and error-correction techniques for quantum computing catch up, the search for new, powerful quantum algorithms continues.