麻豆传媒

The first piece of software to show the potential of quantum computing has finally been run on a real machine, 20 years after it was initially dreamed up. Although it doesn鈥檛 do anything useful on its own, implementing the algorithm could lead to more practical computers powered by the strange properties of quantum mechanics.

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鈥檚 quantum nature. Without these algorithms, quantum computers are just regular computers that are much harder to build.

One of the best-known pieces of quantum software is Shor鈥檚 algorithm, which factorises large numbers into their prime components 鈥� a notoriously slow and difficult problem to solve classically. Shor鈥檚 algorithm has been run in a limited way using photons sent through the air and on silicon chips 鈥� but a full-blown quantum computer capable of running it could threaten online encryption, which relies on large primes.

Designing an algorithm that takes advantage of a quantum computer is tricky, so there aren鈥檛 many around. In 1994, Daniel Simon, then at the University of Montreal, Canada, came up with one of the earliest examples. Crucially, his was the first that showed a quantum computer could solve a problem exponentially faster than an ordinary computer. Previous algorithms had only shown a slight speed boost, or none at all.

Sceptical

Simon was a quantum computing sceptic, but in attempting to prove they would never be useful, he stumbled across a problem that showed the exact opposite. Imagine you feed a string of bits, like 0101, into a black box and get another string, like 1100, out in return. There are a finite number of possible outputs, but you don鈥檛 know how the black box produces them. Simon鈥檚 problem asks: does the black box give a unique output for every possible input, or do some inputs give a common output? The problem doesn鈥檛 show up in any real-world applications, but Simon鈥檚 algorithm for solving it inspired the more useful Shor鈥檚 algorithm and the field of quantum computing as a whole.

鈥淚t has a kind of special place in the history of the development of quantum algorithms,鈥� says at the University of KwaZulu-Natal in Durban, South Africa. 鈥淗owever, despite being the first to show that an exponential gap exists, it was surprisingly never experimentally realised in all the years since.鈥�

That鈥檚 why Tame and his colleagues have now run Simon鈥檚 algorithm for the first time. They used a one-way quantum computer, so-called because it uses up some of the qubits, or quantum bits, during calculation. The computer used six photons as qubits to solve a two-qubit version of Simon鈥檚 problem, the simplest possible. The algorithm is probabilistic, meaning you have to run it multiple times to get an answer.

Completed jigsaw

Tame鈥檚 quantum computer needed an average of two runs to succeed, while an ordinary computer needed an average of eight-thirds runs 鈥� the first step in an exponential speed-up in line with theoretical predictions. 鈥淔or me it has been like finding the missing piece of a jigsaw and putting it in its place to complete the picture,鈥� he says.

鈥淚 don鈥檛 think I ever really thought about anyone bothering, since it鈥檚 not of practical value in itself,鈥� says Simon, who now works in computer security at Microsoft. But Tame says running the algorithm has helped test the team鈥檚 one-way quantum computer, and they now hope to build more advanced versions. 鈥淭he demonstration was more a proof of principle,鈥� says Tame.

鈥淚t鈥檚 great that someone finally got around to doing this,鈥� says at the Massachusetts Institute of Technology, though he isn鈥檛 convinced the speed-up itself matters. 鈥淭he right question is not what 鈥榮peed-up鈥� you鈥檙e getting today, but what experimental advances you鈥檝e made that could lead to a real speed-up in the future.鈥�

Reference: