Milestone algorithm runs on quantum computer

A 20-year-old algorithm that demonstrated the benefit of using quantum mechanics to solve certain problems has finally been run on a quantum computer.

Simon’s algorithm, proposed by computer scientist Daniel Simon in 1994, provides instructions for a computer to determine whether a black box returns a distinct output for every possible input. It was the first example of problem-solving software that quantum computers should be able to execute exponentially faster than conventional computers as the problem gets harder.

Mark Tame, a physicist at the University of KwaZulu-Natal in Durban, South Africa, and colleagues report in the Nov. 14 Physical Review Letters that they ran a simple version of Simon’s algorithm on a computer with six quantum bits. The quantum computer ran the algorithm twice on average to solve the problem; a conventional computer would require nearly three tries on average. The results match Simon’s predictions, the researchers say. The gap in the amount of tries would rise exponentially as the number of possible inputs increased.

Although Simon’s algorithm has no practical applications, Tame says the experiment is a step toward implementing quantum software such as Shor’s algorithm (SN Online: 4/10/14), a number-factoring program that has major implications for data encryption.