[ExI] Quantum Computer beats conventional computer for the first time

[John Clark]

A quantum computer was found to be 3600 times as fast as a high end PC for
a certain class on problems. The following article was just published today
in New Scientist magazine and it could be huge:
==========

For the first time, a commercially available quantum computer has been
pitted against an ordinary PC – and the quantum device left the regular
machine in the dust.

D-Wave, a company based in Burnaby, Canada, has been selling quantum
computers since 2011, although critics expressed doubt that their chips
were actually harnessing the spooky action of quantum mechanics. That's
because they use a non-mainstream method called adiabatic quantum computing.

Unlike classical bits, quantum bits, or qubits, can take the values 0 and 1
at the same time, theoretically offering much faster computing speed. To be
truly quantum, the qubits must be linked via the quantum property of
entanglement. That's impossible to measure while the device is operating.
But in March, two separate tests of the D-Wave device showed indirect
evidence for entanglement.

Now Catherine McGeoch of Amherst College, Massachusetts, a consultant to
D-Wave, has put their computer through its paces and shown that it can beat
regular machines. The D-Wave hardware is designed to solve a particular
kind of optimisation problem: minimising the solution of a complicated
equation by choosing the values of certain variables. It sounds esoteric,
but the problem crops up in many practical applications, such as image
recognition and machine learning.

McGeoch and her colleague Cong Wang of Simon Fraser University, in Burnaby,
ran the problem on a D-Wave Two computer, which has 439 qubits formed from
superconducting niobium loops. They also tried to solve the problem using
three leading algorithms running on a high-end desktop computer. The D-Wave
machine turned out to be around 3600 times faster than the best
conventional algorithm.

McGeoch gave each system roughly half a second to find the best solution to
a version of the optimisation problem, and repeated the trial with 100
different versions. She then did the experiment for problems involving even
more variables and a more complicated equation.

The D-Wave computer found the best solution every time within half a
second. The three regular algorithms struggled to keep up for problems with
more than 100 or so variables. The best of the three, CPLEX, had to run for
half an hour to match D-Wave's performance on the largest problems.

McGeoch also looked at how the devices tackled two other problems. The
D-Wave computer can't solve these directly so employs an extra piece of
software to convert them into a form it can handle. D-wave's device had a
smaller edge in these cases but still matched or exceeded the capabilities
of the algorithms on regular computers. McGeoch will present the results
next week at the ACM International Conference on Computing Frontiers in
Ischia, Italy.

The number-crunching face-off suggests that the benefits of quantum
computers may be harnessed sooner than we imagined. "It's becoming
increasingly compelling," says Jeremy O'Brien of the University of Bristol,
UK. "If you are a forward-looking business, then you might be that much
more compelled to really understand how to use these devices."

It is still possible that D-Wave's device has a strange but highly
optimised way of calculating that does  not rely on entanglement. Teams
will have to repeat the experiments to confirm the quantum effect.

he speed tests are also not quite fair, because generic computers will
always perform less well than a device dedicated to solving a specific
problem, says McGeoch. "A next step would be to build a conventional
processor optimised for this task, for a fairer comparison," says O'Brien.

D-Wave's Colin Williams is more certain, pointing out that the company's
device finds the best solution  in a very different way to regular
algorithms. In a classical system, the solutions are poor to begin with but
rapidly improve, and then they slowly converge on the best answer. D-Wave's
computer reaches the best solution almost instantly. "I've never seen
anything like that in a classical algorithm before."

What really matters to the D-Wave team now is convincing customers it has a
new kind of device that can help them solve problems more efficiently.
"Rather than spending all our time on this academic benchmarking, we would
prefer to spend our time on developing real-world applications at this
point," says Williams.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.extropy.org/pipermail/extropy-chat/attachments/20130512/ac240668/attachment.html>