This quantum does not compute

From the New Scientist, also known as ‘Godstrewth Mate’.

“Quantum computers should be much faster than ordinary ones, but only at tasks for which there is a quantum algorithm – software that takes advantage of the computer’s quantum nature. Without these algorithms, quantum computers are just regular computers that are much harder to build.”

And “Designing an algorithm that takes advantage of a quantum computer is tricky, so there aren’t many around.”

Fifteen to be exact.

The two most important are:

Shor’s algorithm – Given an integer N, find its prime factors. This is exponentially faster on a quantum computer. But a quantum computer is exponentially more expensive to build, so it’s ‘evens’ on a practical level for now.

Grover’s algorithm – searching an unsorted database with N entries in O(N1/2) time and using O(log N) storage space (see big O notation). This is only quadratically faster on a quantum computer.

The rest are curios:

Deutsch–Jozsa algorithm
Simon’s algorithm
Quantum phase estimation algorithm
Hidden subgroup problem
Estimating Gauss sums
Fourier fishing and Fourier checking
Quantum counting
Element distinctness problem
Triangle-finding problem
Formula evaluation
Group commutativity
Computing knot invariants
Quantum simulation

Let’s hope people come up with some more useful algorithms. Without these, the incentive to invest in scaling the hardware will be financially diminished and it simply won’t happen.

And it is important to note that the development of algorithms does not require a computer – it is all old-school pen, paper and the mad mathematician.

Worryingly, the rate of development of new quantum computing algorithms is not increasing. Just like successful new drug releases it seems to be slowing, suggesting that the easy algorithms were those first developed.

If I was a betting man I would bet that this technology will probably not get the massive private sector investment it will need to become anything other than a university curiosity.