Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Commercial quantum computer leaves PC in the dust

newscientist.com

Post reply on HN
Print view View original

31–40 of 45 posts

Re: Commercial quantum computer leaves PC in the dust

#31

Post by lifeisstillgood »

pja wrote: post #16
swombat wrote: post #4

So, basically, as soon a someone builds one of those optimised for factoring primes, all our encryption methods are finished, as is the Bitcoin economy, right? Assuming the contents of the article are true (which is possible), how long before that happens? A few years? A decade?

Pretty much: Quantum Computers (QCs) can factor numbers (Shor's algorithm) and calculate discrete logarithms in polynomial time. I don't know whether there's an algorithm for hash-calculation that will let someone dominate the BitCoin hashing chain with a QC though. On the other hand, no one actually knows whether it's possible to build a quantum computer with enough q-bits that will stay coherent for long enough to…

Thank you - I did feel I had missed a decade reading the article.

Re: Commercial quantum computer leaves PC in the dust

#32

Post by pja »

shadowmint wrote: post #27
pja wrote: post #16

Earlier quoted context omitted.

Pretty much: Quantum Computers (QCs) can factor numbers (Shor's algorithm) and calculate discrete logarithms in polynomial time. I don't know whether there's an algorithm for hash-calculation that will let someone dominate the BitCoin hashing chain with a QC though. On the other hand, no one actually knows whether it's possible to build a quantum computer with enough q-bits that will stay coherent for long enough to…

I actually thought that error correction codes were largely considered to solve the problem of decoherence, at least theoretically. (aka. http://www.google.com.au/url?sa=t&rct=j&q=&esrc=... or perhaps more easily explained @ http://en.wikipedia.org/wiki/Quantum_error_correction )

As I understand things (and I'm not anything close to being an expert, just an interested outsider with enough of a physics education to be dangerous), you can add q-bits to cope with errors introduced by decoherence, but whether these codes work depends quite finely on the error rate. So if you can manage to keep the error rate low enough, then everything will be fine.

If it turns out that the error rate depends (for physical reasons) on the the size of the system, then for some size of QC, adding error correcting q-bits will be counter-productive. Given that (in public) no-one has made a QC with more than a handful of coherent q-bits, no-one really knows where the limits are: it might well be that error-correction lets you build arbitrary sized coherent QCs, or there might be insurmountable physical limits that prevent that from happening. I look forward to people finding out! It's a fascinating new experimental field of physics.

Re: Commercial quantum computer leaves PC in the dust

#33

Post by IgorCarron »

Let me make a simple observation here:

In the Paper of Catherine McGeoch and her co-author Cong Wang, they write:

"...As a case in point, our second project compares the V5 hardware chip used in our first study to a V6 chip that became operational after the study was completed. V6 is three to five times faster than V5, and can solve problems as large as n = 502...."

In other words, during the time it took to set up the algorithm and perform the study, Moore's law had been able to enable a classical approach to go five times faster. I am a big supporter of anything that does quantum computing but one should never lose sight of Moore's law.

http://nuit-blanche.blogspot.com/2013/05/randomized-thoughts...

Re: Commercial quantum computer leaves PC in the dust

#35

Post by greenmountin »

Eliezer wrote: post #28

Probably not what it seems. http://www.scottaaronson.com/blog/?p=954

There's a theorist from ETH who also has been working with the D-Wave computers, and visited Scott at MIT last week. There should be a new post about it soon, I'm sure it will be mostly cold water.

Re: Commercial quantum computer leaves PC in the dust

#36

Post by zeus13i »

tristanj wrote: post #6
zeus13i wrote: post #3

I really wish there was more information in this article.

Her website (linked in the article) has a copy of the paper. http://www.cs.amherst.edu/ccm/cf14-mcgeoch.pdf Quoting her paper, she used the D-Wave computer to solve instances of three NP-Hard problems: Quadratic Unconstrained Binary Optimization (QUBO); Weighed Maximum 2-Satis ability (W2SAT), and the Quadratic Assignment Problem (QAP). She then compared the runtime with current software libraries run on Intel Xenons…

Cheers! I missed that link.

Re: Commercial quantum computer leaves PC in the dust

#38

Post by larrydag »

I'm a bit confused by this article. Is it comparing computers or comparing algorithms? CPLEX is software to run linear and mixed-integer optimization algorithms. CPLEX is not a computer. Perhaps I misunderstood the article. Could you not run CPLEX on the D-Wave computer?

Re: Commercial quantum computer leaves PC in the dust

#40

Post by jwr »

pja wrote: post #16
swombat wrote: post #4

So, basically, as soon a someone builds one of those optimised for factoring primes, all our encryption methods are finished, as is the Bitcoin economy, right? Assuming the contents of the article are true (which is possible), how long before that happens? A few years? A decade?

Pretty much: Quantum Computers (QCs) can factor numbers (Shor's algorithm) and calculate discrete logarithms in polynomial time. I don't know whether there's an algorithm for hash-calculation that will let someone dominate the BitCoin hashing chain with a QC though. On the other hand, no one actually knows whether it's possible to build a quantum computer with enough q-bits that will stay coherent for long enough to…

What about elliptic curves-based asymmetric cryptography?
Post reply on HN