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 – a sweet delicious treat, and a sign that serious progress is being made in the field of quantum computing.
The Quantum world is weird
A quantum computer is a computation system that makes direct use of quantum-mechanical phenomena, such as superposition and entanglement, to perform operations on data. Quantum computers are fundamentally different from traditional computers, which are based on transistors. Many believe that quantum computers are the future of computing altogether.
It’s difficult to grasp just how quantum computers work, but in a simplified model digital computers require data to be encoded into binary digits (bits), each of which is always in one of two definite states (0 or 1). Instead of bits, quantum computers use qubits – quantum bits which are in a state of superposition – that is, they exist partly in all its particular theoretically possible states simultaneously and only take a certain value when measured. Yeah, the quantum world is weird. The field is still in its infancy but experiments have been carried out in which quantum computational operations were executed on a very small number of qubits.
A milestone algorithm
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. Simon’s algorithm solves the problem exponentially faster than any (deterministic or probabilistic) classical algorithm, proving the efficiency of using quantum calculations. The fact that this algorithm was actually run on a quantum computer is in turn, a milestone achievement.
Mark Tame, a physicist at the University of KwaZulu-Natal in Durban, South Africa, lead a team which ran a simple version of Simon’s algorithm on a computer with only six quantum bits. The program took two tries on average to solve the problem, whereas a classical computer would take nearly three tries on average – a significant reduction. The results match Simon’s predictions, and the gap is expected to rise as the number of possible computations is increased.
Simon’s algorithm has no potential applications… yet. Tame says the experiment is a step toward implementing quantum software which could have huge implications, especially in data encryption and cyber security.
Journal Reference: M. S. Tame, B. A. Bell, C. Di Franco, W. J. Wadsworth, and J. G. Rarity. Experimental Realization of a One-Way Quantum Computer Algorithm Solving Simon’s Problem. Phys. Rev. Lett. 113, 200501.