Re: Quantum Computer beats conventional computer for the first time

[John Clark]

On Mon, May 13, 2013 at 1:56 AM, meekerdb  wrote:

> See the actual paper:
>
> http://arxiv.org/pdf/1304.4595v1.pdf
>

That's not the same paper and as far as I can tell Catherine McGeoch had
nothing to do with it. And the paper you refer to is about a 108 qbit
computer but these new results are for a 439 qbit computer. This was just a
announcement, the actual paper about these new results won't be available
till Wednesday.  It's true that these results have not yet been published
in a peer reviewed journal but if they hold up it's huge. The fact that
firms like Google and Lockheed have payed good money for earlier versions
of D Wave's machines gives me some confidence that it's not just hot air.

  John K Clark

-- 
You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at http://groups.google.com/group/everything-list?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.

Re: Quantum Computer beats conventional computer for the first time

[meekerdb]

On 5/12/2013 9:46 PM, John Clark wrote:
On Sun, May 12, 2013 at 2:45 PM, meekerdb > wrote:


> It's very doubtful that the D-wave computer is a quantum device at all  
and has
anything to do with qubits.


That old view is changing, acording to the most recent information it's very likely that 
the D-wave computer is a quantum device after all. And even if it's not a quantum 
computer (and it probably is)  it solves problems in a way no computer has before and 
its very very fast. See:


http://blogs.nature.com/news/2013/04/further-proof-for-controversial-quantum-computer.html


See the actual paper:

http://arxiv.org/pdf/1304.4595v1.pdf

It is not very, very fast. "Considering the pure annealing time, the performance for 
typical (median) instances matches that of a highly
optimised classical annealing code on a high-end Intel CPUSimulated annealers require 
about three orders of magnitude more computational e ffort for N = 512 spins compared to N 
= 108 spins for our problems, and there will be potential to see advantages of a quantum 
annealer over classical algorithms."


In other words, maybe, if it scales up as predicted it will be very fast.

Brent



> It only solves one particular NP-hard problem


Yes but that is a very important problem that among other things includes the all 
important protein folding problem.


  John K Clark





--
You received this message because you are subscribed to the Google Groups "Everything 
List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to 
everything-list+unsubscr...@googlegroups.com.

To post to this group, send email to everything-list@googlegroups.com.
Visit this group at http://groups.google.com/group/everything-list?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.


No virus found in this message.
Checked by AVG - www.avg.com 
Version: 2013.0.3336 / Virus Database: 3162/6319 - Release Date: 05/12/13



--
You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at http://groups.google.com/group/everything-list?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.

Re: Quantum Computer beats conventional computer for the first time

[John Clark]

On Sun, May 12, 2013 at 2:45 PM, meekerdb  wrote:

 > It's very doubtful that the D-wave computer is a quantum device at all
> and has anything to do with qubits.
>

That old view is changing, acording to the most recent information it's
very likely that the D-wave computer is a quantum device after all. And
even if it's not a quantum computer (and it probably is)  it solves
problems in a way no computer has before and its very very fast. See:

http://blogs.nature.com/news/2013/04/further-proof-for-controversial-quantum-computer.html

> It only solves one particular NP-hard problem
>

Yes but that is a very important problem that among other things includes
the all important protein folding problem.

  John K Clark

-- 
You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at http://groups.google.com/group/everything-list?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.

Re: Quantum Computer beats conventional computer for the first time

[meekerdb]

It's very doubtful that the D-wave computer is a quantum device at all  and has anything 
to do with qubits.  It only solves one particular NP-hard problem (minimizing the energy 
of ~100 Ising spins with pairwise interaction) and the solutions are approximate. See 
Scott Aronson's blog:


http://www.scottaaronson.com/blog/?p=954

It seems likely it's just a fancy ASIC designed for this problem.

Brent

On 5/12/2013 10:30 AM, John Clark wrote:
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,