Simon's says quantum computing will work

Boffins blast algorithm with half a dozen qubits

One of the hard parts of quantum computing is turning laboratory qubits into a calculation of anything. Now, South African scientists claim they've tested a handful of qubits against a 20-year-old algorithm to demonstrate that yes, a quantum computer can run it “faster” than a classical machine.

Regular readers of quantum-computing stories will know that D Wave has made controversial claims that it can solve some algorithms faster than classical computers using quantum annealing, but that those claims have become the subject of academic to-and-fro about their validity.

The new claim isn't anywhere near as startling: what the researchers from the University of KwaZulu-Natal in Durban say is that they've demonstrated that a six-qubit quantum computer solves what's called Simon's algorithm in fewer iterations than a classical computer would require.

The abstract of their paper is here.

That's not necessarily “faster”, since a multi-gigahertz processor can throw iterations up against the wall much faster than a quantum machine can at the moment. However, if / when quantum machines reach classical-like clocking (or rather the quantum computing equivalent thereof), the quantum machine would outpace its iterative competitor.

So – what's Simon's algorithm? It's one of the earliest bits of mathematics to propose a way to test whether there are problems for which quantum computers are a better way to solve a problem.

A detailed explanation is here. You could think of it as looking at a state machine: to test whether all the outputs are unique for all the inputs, a classical computer would have to cycle through all the possible input combinations.

The algorithm has to work out whether there's a 1:1 input-output relationship (that is, every input has a distinct output) or a 2:1 relationship (two inputs can have the same output), and it formed a key input to the formation of Shor's algorithm (which proposed using quantum computers to factor prime numbers).

The South African group, led by physicist Mark Tame, ran a six-qubit optical quantum computer for their test, and found that it ran the quantum algorithm twice (on average) to solve the simplified Simon's algorithm. A classical machine would, they say, need three cycles to achieve the result iteratively.

While it's useless in practical terms, demonstrating Simon's predictions is still important from a research perspective, because it “provides a practical route to experimentally investigating the quantum-classical gap in the query complexity model.”

To put that another way: if we know that a quantum computer can be made to outperform a classical machine, we've got a bit more confidence that the research money isn't being wasted. ®

Biting the hand that feeds IT © 1998–2017