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]

(Phys.org) —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: Efficient distributed quantum computing

More information: Experimental Realization of a One-Way Quantum Computer Algorithm Solving Simon's Problem, Phys. Rev. Lett. 113, 200501 – Published 11 November 2014 dx.doi.org/10.1103/PhysRevLett.113.200501 . On Arxiv: arxiv.org/abs/1410.3859

ABSTRACT
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

Efficient distributed quantum computing

February 21, 2013

(Phys.org)—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. ...

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 ...

Recommended for you

Understanding nature's patterns with plasmas

August 23, 2016

Patterns abound in nature, from zebra stripes and leopard spots to honeycombs and bands of clouds. Somehow, these patterns form and organize all by themselves. To better understand how, researchers have now created a new ...

Measuring tiny forces with light

August 25, 2016

Photons are bizarre: They have no mass, but they do have momentum. And that allows researchers to do counterintuitive things with photons, such as using light to push matter around.

Light and matter merge in quantum coupling

August 22, 2016

Where light and matter intersect, the world illuminates. Where light and matter interact so strongly that they become one, they illuminate a world of new physics, according to Rice University scientists.

A new study looks for the cortical conscious network

August 26, 2016

New research published in the New Journal of Physics tries to decompose the structural layers of the cortical network to different hierarchies enabling to identify the network's nucleus, from which our consciousness could ...

6 comments

Adjust slider to filter visible comments by rank

Display comments: newest first

hjbasutu
5 / 5 (1) Nov 17, 2014
what are the names of the scientists??
Torbjorn_Larsson_OM
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?
feath3r
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.
fourinfinities
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.