Simon's algorithm run on quantum computer for the first time—faster than on standard computer

November 17, 2014 by Bob Yirka, report

Experimental setup. Credit: arXiv:1410.3859 [quant-ph]
( —A team of researchers working in South Africa has reported that they've successfully run Simon's algorithm on a quantum computer for the first time. In their paper published in Physical Review Letters, the team describes how they ran the algorithm, the results they found and what doing so means for the future of quantum computing.

A quantum computer is a computing device that relies on quantum bits () rather than the standard digital bits that have been used by most every computing device made. It's believed that such a computer would be able to run certain algorithms faster or more efficiently than standard computers due to their ability to take advantage of quantum mechanics properties such as entanglement and superposition. Until now, however, it's not been possible to run algorithms created specifically for such machines, to test out this theory.

In this new effort, the team ran what is known as Simon's , for Daniel Simon, who, twenty years ago, came up with an algorithm designed specifically to run faster on a quantum computer than it would, on a standard computer. Its purpose is to figure out whether a black box returns a unique output for every possible input. The team ran the simplest version of the algorithm on a quantum computer that used just six qubits, and report that it took just two iterations to solve the problem, where it would take a normal computer three. That may not seem like much, but it is believed that as more qubits are added, the larger the difference would be between the two approaches, which means, the quantum computer would be able to solve the algorithm much faster, or technically, more efficiently than standard computers. That's the good news. The bad news is that thus far, there is no practical benefit to running Simon's algorithm—its sole purpose is to show that for one algorithm, the quantum computer does better.

But that's not the end of the story, showing that one such algorithm can return a result more quickly on a computer offers researchers hope that other algorithms, such as Shor's algorithm (which can be used to factor large numbers into their primes—an important part of encryption schemes) could be run much faster as well.

Explore further: D-Wave and predecessors: From simulated to quantum annealing

More information: Experimental Realization of a One-Way Quantum Computer Algorithm Solving Simon's Problem, Phys. Rev. Lett. 113, 200501 – Published 11 November 2014 . On Arxiv:

We report an experimental demonstration of a one-way implementation of a quantum algorithm solving Simon's problem—a black-box period-finding problem that has an exponential gap between the classical and quantum runtime. Using an all-optical setup and modifying the bases of single-qubit measurements on a five-qubit cluster state, key representative functions of the logical two-qubit version's black box can be queried and solved. To the best of our knowledge, this work represents the first experimental realization of the quantum algorithm solving Simon's problem. The experimental results are in excellent agreement with the theoretical model, demonstrating the successful performance of the algorithm. With a view to scaling up to larger numbers of qubits, we analyze the resource requirements for an n-qubit version. This work helps highlight how one-way quantum computing provides a practical route to experimentally investigating the quantum-classical gap in the query complexity model.

Related Stories

D-Wave and predecessors: From simulated to quantum annealing

June 23, 2014

The D-Wave computer is currently the latest link of a long chain of computers designed for the solution of optimization problems. In what sense does it realize quantum computation? We describe the evolution of such computers ...

The quantum revolution is a step closer

September 11, 2014

A new way to run a quantum algorithm using much simpler methods than previously thought has been discovered by a team of researchers at the University of Bristol. These findings could dramatically bring forward the development ...

Efficient distributed quantum computing

February 21, 2013

(—A quantum computer doesn't need to be a single large device but could be built from a network of small parts, new research from the University of Bristol has demonstrated. As a result, building such a computer ...

Quantum algorithm breakthrough

February 24, 2013

An international research group led by scientists from the University of Bristol, UK, and the University of Queensland, Australia, has demonstrated a quantum algorithm that performs a true calculation for the first time. ...

Recommended for you

Coffee-based colloids for direct solar absorption

March 22, 2019

Solar energy is one of the most promising resources to help reduce fossil fuel consumption and mitigate greenhouse gas emissions to power a sustainable future. Devices presently in use to convert solar energy into thermal ...

Physicists reveal why matter dominates universe

March 21, 2019

Physicists in the College of Arts and Sciences at Syracuse University have confirmed that matter and antimatter decay differently for elementary particles containing charmed quarks.

ATLAS experiment observes light scattering off light

March 20, 2019

Light-by-light scattering is a very rare phenomenon in which two photons interact, producing another pair of photons. This process was among the earliest predictions of quantum electrodynamics (QED), the quantum theory of ...

How heavy elements come about in the universe

March 19, 2019

Heavy elements are produced during stellar explosion or on the surfaces of neutron stars through the capture of hydrogen nuclei (protons). This occurs at extremely high temperatures, but at relatively low energies. An international ...


Adjust slider to filter visible comments by rank

Display comments: newest first

5 / 5 (1) Nov 17, 2014
what are the names of the scientists??
5 / 5 (4) Nov 17, 2014
I'm with computer scientist Scott Aaronson in this. The algorithms that are faster on quantum computers are not exponentially sped up as some naively believes from looking at entangled systems, they are logarithmic gains. The question then is if the small gains can balance the increased costs.

@hjbasutu: Why don't you follow the arxiv link? It should have a complete author list with and in the free paper.
Whydening Gyre
5 / 5 (1) Nov 17, 2014
Forgive the comparison, but doesn't it seem like this is just a more quantized version of analog?
1.5 / 5 (2) Nov 17, 2014
there are loopholes in Bell's inequality experiments. although i won't get into details here, but i'd like to say that quantum entanglement may not be a real phenomenon at all, but the result of local hidden variables.
5 / 5 (2) Nov 17, 2014
The names of the scientists are entangled.
Da Schneib
5 / 5 (1) Nov 20, 2014
Shor's algorithm can factor products of large primes in polynomial time; no classical algorithm can do it in less than super-polynomial time. That's a lot more than an exponential speedup, potentially. And if they're right and adding more bits speeds it up, then there is a path to fast factoring of products of large primes.

It's probably the "best" quantum algorithm yet.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.