Harry Buhrman, University of Amsterdam
"...for certain problems the community has found algorithms that seem to be much more efficient, much faster than any classical algorithm."
For those who don't know, quantum computing is on the path of gaining huge advantages in speed over conventional computers, achieved by carrying out massive parallel computations simultaneously.
It has significant implications for the global economy, particularly for industries coping with computational bulk in an era of big data in sectors such as financial markets, cyber security, and data base management, for example.
And figuring out exactly which problems quantum algorithms are going to be able to solve is a job for Harry Buhrman, group leader for Algorithms and Complexity at the Centre for Mathematics and Computer Science in the University of Amsterdam.
Quantum algorithms are especially well suited for calculating factors for big numbers. What used to take tens of thousands of years now takes minutes. Meanwhile, the world's encryption technology relies on such numbers taking too much time to hack into using brute force tactics.
Quantum computing has potential applications for exactly those types of problems for which there are no known fast algorithms, meaning that solving them would take exponential time. But which problems those are is still a research field in development.
To explain, Buhrman uses an example of finding routes to get places between cities. Calculating the shortest distance between two points is easy, but calculating the longest route takes longer than the age of the universe for relatively small instances.
"There are two ways in speeding up problems. One is buying a faster computer and the other is by coming up with smarter algorithms," Buhrman said.
And just buying more computer power doesn't exactly solve the issue for problems that take the age of the universe to solve, if you just cut the runtime in half.
Enter quantum computing
At the great risk of oversimplifying, quantum computers could be put to work because of concepts known as superposition and interference.
Superposition is demonstrated in 'Schrödinger's cat', which is a concrete illustration of the theory that a particle can be in two states at the same time. In the cat's case, alive and dead. In a computer's case, 0 and 1. Instead of bits, quantum computers have qubits, which is a superposition of 0 and 1, and can be in two different states at the same time. Looking at a qubit in superposition will yield a probabilistic outcome of 0 or 1.
Every extra qubit doubles the number of superpositions, or the number of states that your superposition can be in, explained Buhrman.
"The leap in mind that you have to take is to think of these superpositions as computations of your computer. If your computer uses 50 qubits, then potentially it can do 2^50 different computations all at the same time," Buhrman said. "You can do more computations than we have molecules in the universe on 300 qubits."
The catch is that as soon as you observe a quantum state, it collapses into one computation. And that's where interference kicks in.
"If you have a good quantum algorithm, then depending on the problem you are solving, sometimes you can arrange it in such a way that you use interference to see the computation that you are interested in. You amplify the ones that you want to see, and you let the ones that you don't care about cancel each other out."
So how do you know which outcomes you want?
"That is the person who designs the algorithm. It is very complicated and we really don't understand very well what you can and cannot do," he said. "What I can tell you is that for certain problems the community has found algorithms that seem to be much more efficient, much faster than any classical algorithm."
Going back to the example of optimal routes via cities, could the same problem be repurposed for the financial markets? Say, finding the most optimal route across global trading venues given a desired asset class and trading parameters?
Maybe, said Buhrman, maybe not.
*A spokesperson for Renaissance Technologies did not reply to questions at time of publication.