mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Science & Technology

Reply
 
Thread Tools
Old 2010-11-16, 06:04   #1
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default 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
davieddy is offline   Reply With Quote
Old 2010-11-16, 06:18   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32×5×7×19 Posts
Default

Quote:
Originally Posted by davieddy View Post
How many Qbits are necessary to factorise a typical Mersenne
number?
A thousand, maybe. I talked to a researcher at one point about this, but unfortunately I didn't think to take notes.

Peter Shor posts at MathOverflow; if you're really interested you could ask there.

Last fiddled with by CRGreathouse on 2010-11-16 at 06:18
CRGreathouse is offline   Reply With Quote
Old 2010-11-16, 07:16   #3
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
A thousand, maybe. I talked to a researcher at one point about this, but unfortunately I didn't think to take notes.

Peter Shor posts at MathOverflow; if you're really interested you could ask there.

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 2010-11-16 at 07:30
davieddy is offline   Reply With Quote
Old 2010-11-16, 07:35   #4
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

647410 Posts
Default

Quote:
Originally Posted by davieddy View Post

"What size did he (David) mean
by a "typical" Mersenne number"?
As a physicist acquainted with "orders of magnitude" I
assume that you were implicitly thinking of exponents
between 30M and 300M.

David
davieddy is offline   Reply With Quote
Old 2010-11-16, 14:37   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32×5×7×19 Posts
Default

Quote:
Originally Posted by davieddy View Post
But ~1000 begs the question "What size did he (David) mean
by a "typical" Mersenne number"?
I was hoping you wouldn't mention, so the size could shift to whatever would be doable at that size. 1000 qubits is roughly a 'best case' for one of the small unfactored composite Mersenne numbers.

I think that an n-bit 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).
CRGreathouse is offline   Reply With Quote
Old 2010-11-16, 17:43   #6
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

133558 Posts
Default

Under simulation this is now possible.
henryzz is online now   Reply With Quote
Old 2010-11-16, 21:22   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32·5·7·19 Posts
Default

Quote:
Originally Posted by henryzz View Post
Under simulation this is now possible.
Hmm... a 14-bit number with 42 (perfect*) qubits. Assuming the first and last are implicit, that's 0.29n2 or 3.5n. Either way, nice.

* No need for error correction, so that reduces the upper-end exponent by 1.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Shor's Algorithm flouran Math 3 2009-10-27 09:31
Shor's Factoring Algorithm - does it even work? Citrix Factoring 37 2008-08-16 14:19
Quantum Algorithms? ShiningArcanine Lounge 4 2007-12-16 12:11
when do you think we will have practical quantum computers? ixfd64 Lounge 3 2003-11-07 13:22
quantum computer sagan_fan Math 4 2003-03-26 05:01

All times are UTC. The time now is 13:42.

Fri May 7 13:42:36 UTC 2021 up 29 days, 8:23, 0 users, load averages: 2.88, 2.85, 2.64

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.