20101116, 06:04  #1 
"Lucan"
Dec 2006
England
2·3·13·83 Posts 
Quantum Computers and Shor
A few questions:
Nobody has doubted the possibility of nuclear fusion for at least 60 years. Does anyone here suspect that QC may be a similar story? How many Qbits are necessary to factorise a typical Mersenne number? Any prospect of this aiding GIMPS? David 
20101116, 06:18  #2  
Aug 2006
3^{2}×5×7×19 Posts 
Quote:
Peter Shor posts at MathOverflow; if you're really interested you could ask there. Last fiddled with by CRGreathouse on 20101116 at 06:18 

20101116, 07:16  #3  
"Lucan"
Dec 2006
England
2·3·13·83 Posts 
Quote:
Nice response. But ~1000 begs the question "What size did he (David) mean by a "typical" Mersenne number"? As to your second suggestion, I don't think I'm in Peter Shor's league (at least these days!). I'll check out the site though, and might mention it to Paul Seymour when I send him a long overdue reply to his latest email. David Last fiddled with by davieddy on 20101116 at 07:30 

20101116, 07:35  #4 
"Lucan"
Dec 2006
England
6474_{10} Posts 

20101116, 14:37  #5  
Aug 2006
3^{2}×5×7×19 Posts 
Quote:
I think that an nbit number requires at least 2n qubits for calculation, and that kn^3 qubits is known to be feasible (where k is close to 1). So if you wanted a 300 million bit number, you'll need 6e8 to 3e25 qubits. Clearly, this won't be happening in your lifetime. For comparison, LL requires something like 2n bits. The essential differences: there's an extra factor of n in the upper bound because we don't understand quantum algorithms that well, and there's an extra factor of n for current methods of error correction. Classical error correction takes an extra constant fraction of bits for a given degree of certainty, while quantum error correction takes an extra factor of n. It's a little harsh. But if you could get around that, either by developing a new method of error correction or by having quantum gates that are much faster than the decoherence time, you could get closer to an exponent of 2 (or 1 with improvements to the algorithm itself, perhaps). 

20101116, 21:22  #7  
Aug 2006
3^{2}·5·7·19 Posts 
Quote:
* No need for error correction, so that reduces the upperend exponent by 1. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Shor's Algorithm  flouran  Math  3  20091027 09:31 
Shor's Factoring Algorithm  does it even work?  Citrix  Factoring  37  20080816 14:19 
Quantum Algorithms?  ShiningArcanine  Lounge  4  20071216 12:11 
when do you think we will have practical quantum computers?  ixfd64  Lounge  3  20031107 13:22 
quantum computer  sagan_fan  Math  4  20030326 05:01 