phys.org is reporting that a team of South African Researchers have successfully run Simon's algorithm on a quantum computer.
Simon's algorithm, named after Daniel Simon, is a solution to Simon's Problem that is:
...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.
If verified it's the first unambiguous case where an algorithm designed specifically for a quantum computer has been able to demonstrate an exponential gap to the equivalent classical computer algorithm run time.
The paper detailing this experiment is available at arXiv.
(Score: 3, Funny) by bob_super on Wednesday November 19 2014, @04:12PM
"Darling, I told you we all needed this quantum computer. Look, it's proven exponentially faster at running Simon. The kids are going to love playing with it, if they can pry it from me."
(Score: 1, Funny) by Anonymous Coward on Wednesday November 19 2014, @06:11PM
My sister had a Simon [wikipedia.org] back in the 70's. Who knew it was a quantum computer?
(Score: 3, Interesting) by VLM on Wednesday November 19 2014, @04:18PM
Its interesting academically, but there is an assumption that quantum computing WILL scale to important sizes because traditional computing did "just because".
However the "just because" is a perfect storm of chemistry, physics, industrial mass production, such that we went from "Built a single bit full adder out of vacuum tubes in 1940s" to IBM system 360 in the 60s and lisp machines in the 80s.
I'm just saying specifically the being able to scale quantum stuff to useful sizes is unproven, not definitely yes like traditional computing and not definitely no like fusion reactors and flying cars.
Its quite possible that within our lifetimes there will be plenty of amazing O(n) quantum computers, where n is never larger for practical technological reasons than what a COTS 75 cent microcontroller could calculate the old slow O(O^n) way in a second or two. Or maybe for no apparent reasons it'll scale beautifully up to millions of qubits by 2030 and won't that ever be interesting.
(Score: 2) by DeathMonkey on Wednesday November 19 2014, @07:26PM
A Quantum Co-Processor like the Math Co-Processors of yore might be interesting.
All the benefits of a traditional processor but divert to the quantum processor to run that O(n^n) operation.
(Score: 3, Funny) by Ryuugami on Wednesday November 19 2014, @07:43PM
I'm just saying specifically the being able to scale quantum stuff to useful sizes is unproven, not definitely yes like traditional computing and not definitely no like fusion reactors and flying cars
So it currently exists as a superposition of yes and no, until we observe it and determine which it is?
Sounds really fitting for a quantum computer :)
If a shit storm's on the horizon, it's good to know far enough ahead you can at least bring along an umbrella. - D.Weber
(Score: 2) by khakipuce on Thursday November 20 2014, @07:51AM
designed specifically to run faster on a quantum computer than it would, on a standard computer
Has anyone designed an algorithm that will run faster on a "standard computer" than on a quantum one? Is it such a surprise that an algorithm designed for a specific technology runs better on that technology? I've designed a vehicle that that runs faster on water than the standard, consumer grade vehicle owned by most people*. I call my vehicle a boat *i.e. a car
(Score: 0) by Anonymous Coward on Thursday November 20 2014, @08:19AM
Yes, because it shows conclusively that this is a difference in kind between the two computers.
Sure we've thought that with very high certainly for a while, bit you have to verify your theories at some point otherwise why bother?
(Score: 0) by Anonymous Coward on Thursday November 20 2014, @08:26AM
Its confirmation that this is super-Turing computation. The first real proof that Turing machines do no capture all of computation.
Its not like your vehicle going faster, that's boring; It's more akin to your vehicle appearing to go faster than c by warping space.
No hard limit has actually been broken, but our model and definitions of hard limits need to change.