Synopsis: Simon Says Speed Up

A function finder called Simon’s algorithm has been experimentally tested on a prototype quantum computer for the first time.
Synopsis figure
M. Tame/University of KwaZulu-Natal

Many quantum algorithms are expected to solve problems faster than their classical equivalents, but few have been tested experimentally. Now Mark Tame, from the University of KwaZulu-Natal in South Africa, and his colleagues have used a prototype quantum computer to run the quantum version of Simon’s algorithm—historically, the first algorithm predicted to run exponentially faster on a quantum computer than a classical one. Although Simon’s algorithm doesn’t have practical applications, it could provide a useful way to test the capabilities of future quantum computers.

Simon’s algorithm determines the properties of a “black-box” function f(x), figuring out if a function is 1 to 1 [each input x has a different output f(x)], or 2 to 1 [two inputs x1 and x2 have the same output f(x1)=f(x2)]. The algorithm works out which by querying the black box and monitoring the output. If it’s a 2 to 1 function, the algorithm also finds the difference between x1 and x2, known as the period. Classically, the number of times the black box has to be queried to deduce the function is exponentially greater than the number of times it would take a quantum system.

Tame and collaborators ran a quantum version of this algorithm on an optical quantum computer, in which entangled photons served as qubits. Their setup, which utilizes a total of six qubits, solved Simon’s problem in three quarters of the steps that it would take a classical computer to solve the equivalent classical black box function. Assuming theoretical predictions about Simon’s algorithm’s performance are correct, this gain in efficiency will increase exponentially on computers with more qubits.

This research is published in Physical Review Letters.

–Katherine Wright


Features

More Features »

Announcements

More Announcements »

Subject Areas

Quantum Information

Previous Synopsis

Next Synopsis

Atomic and Molecular Physics

Spinning a Condensate with Light

Read More »

Related Articles

Viewpoint: Seeing Scrambled Spins
Atomic and Molecular Physics

Viewpoint: Seeing Scrambled Spins

Two experimental groups have taken a step towards observing the “scrambling” of information that occurs as a many-body quantum system thermalizes.   Read More »

Viewpoint: Type-II Dirac Fermions Spotted
Quantum Information

Viewpoint: Type-II Dirac Fermions Spotted

Three separate groups report experimental evidence of novel type-II Dirac quasiparticles, suggesting possible applications in future quantum technology. Read More »

Viewpoint: A Roadmap for a Scalable Topological Quantum Computer
Condensed Matter Physics

Viewpoint: A Roadmap for a Scalable Topological Quantum Computer

A team of experimentalists and theorists proposes a scalable protocol for quantum computation based on topological superconductors. Read More »

More Articles