mersenneforum.org What would you do with a small quantum computer?
 Register FAQ Search Today's Posts Mark Forums Read

 2012-07-20, 07:26 #1 CRGreathouse     Aug 2006 32×5×7×19 Posts What would you do with a small quantum computer? Suppose you had a chance to use an 800-qubit quantum computer. Yes, that's way beyond what we can make; maybe it's from a genie or an alien. You can't sell it or examine its inner workings (it's tamperproof); you can only use it on your own. What could you do? Suppose decoherence time is sufficiently large. As far as I can tell you could factor small-ish numbers fairly quickly, though I'm not sure how large or how fast. "How large" has to do with the amount of quantum error correction needed; if you don't need any you could factor numbers up to 398 bits (Beauregard's version of Shor's algorithm), or somewhat fewer with an error-correcting code (I'm guessing about 350 using Calderbank-Rains-Shor-Sloane, by extrapolation from Table III, in the best case that you only need to correct a single error). What use could you find for lots of somewhat-small factorizations? What other algorithms besides Shor's would be useful on a quantum computer of this size? (I can't imagine Grover's algorithm would be useful on any quantum computer that will be built in my lifetime, it seems to require too many qubits and give too little speedup.)
 2012-07-20, 13:28 #2 jasong     "Jason Goatcher" Mar 2005 66638 Posts I don't pretend to know the ins and outs of quantum computing, but couldn't the problem be stated by a regular computer, then solved by the quantum computer side? Additionally, what about having leading bits, and then sieve each portion with the quantum part. So you could sieve in chunks of 2^398, or whatever, bits. Again, I don't understand quantum computers, maybe it's a requirement that the entire program be contained within the qubits. Edit: Alternately, couldn't any animal with an organic brain count as a quantum computer? If I carry a mouse in my pocket, am I not also carrying a quantum computer in my pocket? Not the way CRGreathouse intended, but, hey, it's that kind of forum. Last fiddled with by jasong on 2012-07-20 at 13:31
 2012-07-20, 15:48 #3 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 5,857 Posts How fast would it factorize small numbers of maybe 100 bits? Would it be fast enough to use factorizing large primes in NFS?
2012-07-20, 16:12   #4
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

612010 Posts

Quote:
 Originally Posted by CRGreathouse What would you do with a small quantum computer?
Me? Personally? Probably nothing. There would appear to be very little of value that one could do with an 800-bit QC.

So nothing really except for purely research things. Like, perhaps, examining it with a view towards making a larger QC?

2012-07-20, 16:13   #5
bsquared

"Ben"
Feb 2007

22×23×37 Posts

Quote:
 Originally Posted by CRGreathouse What other algorithms besides Shor's would be useful on a quantum computer of this size? (I can't imagine Grover's algorithm would be useful on any quantum computer that will be built in my lifetime, it seems to require too many qubits and give too little speedup.)
Would it be useful for attacks on block ciphers? IIRC, log2N qu-bits using Grover's algorithm allows one to exhausively search a keyspace of size 2N in time 2(N/2). So 264 operations to break a 128 bit key... maybe on the edge of practicality for a relatively small keyspace.

 2012-07-20, 16:22 #6 LaurV Romulan Interpreter     Jun 2011 Thailand 9,377 Posts I would certainly find all factors F with less then 402 bits of the mersenne numbers with prime exponent p smaller then 1G. That is feasible if one is able to factor really fast (instant) the odd D in D=(F-1)/(2^s), then check for all factors p of D if F divides Mp. 800 (qu)bits is enough for this. Say that computer runs at 3GHz, it would need about 2*log2(10^9) clocks to clear one F (too see if this F is factor of any Mp with p smaller then 10^9) so this time is negligible comparing with primality prove. So, the task is reduced at enumerating all primes which are 1 or 7 mod 8 from 1 bit to 402 bits (But what need eons of eons of eons on a sequential computer might be much fast on the QC, as every qubit has an infinite amount of states, all F's might be tested in parallel - hold your stone, that is me dreaming!) Last fiddled with by LaurV on 2012-07-20 at 16:25
 2012-07-20, 16:51 #7 chris2be8     Sep 2009 37548 Posts I'd use it to speed up the work I'm doing to factor the smaller composites in factordb. There are plenty to do. Just how big a number it can factor makes a lot of difference. 398 bits is about 120 digits, there are about 135000 composites under that size. 350 bits is about 107 digits, but there are still a few thousand composites in that range. Chris
 2012-07-20, 17:08 #8 xilman Bamboozled!     "πΊππ·π·π­" May 2003 Down not across 2·5,323 Posts Sell it on eBay?
 2012-07-20, 18:15 #9 only_human     "Gang aft agley" Sep 2002 375410 Posts I think it would be best utilized for algorithmic development. At first blush one might think that quantum algorithms can be developed well enough without experimental mathematical approaches or any actual quantum hardware (since we do that already), but looking at how we develop algorithms for conventional hardware, having actual machines and including tables of data and timings is really useful. Everyone goes on about factoring and database lookup but there is relations work that could be useful. First faster quantum algorithms for solving systems of linear equations (HHL). Second what PSLQ like algorithms would be possible? Last fiddled with by only_human on 2012-07-20 at 18:28 Reason: grammar s/there is all kinds of relations work, there is relations work/ and it still looks wrong
 2012-07-21, 02:22 #10 jwaltos     Apr 2012 Brady 18116 Posts Program it to play a scaled down version of GO. Bind it to a simple cellular/biological process to determine if it can echo or resonate with this process in real time. Examine what exactly composes the geometry of space/time - may possibly require another quantum box to decipher and present the results in one's preferred formalism. An old Calvin and Hobbes comic had Calvin saying (when looking at a large dinosaur) "it's so big you have to look at it twice to see it once." Last fiddled with by jwaltos on 2012-07-21 at 02:33
2012-07-21, 05:48   #11
LaurV
Romulan Interpreter

Jun 2011
Thailand

9,377 Posts

Quote:
 Originally Posted by xilman Sell it on eBay?
You didn't pay attention!

Quote:
 Originally Posted by CRGreathouse You can't sell it or examine its inner workings (it's tamperproof); you can only use it on your own. What could you do?
Sit on it?

(from kungfu panda 1st:
"what are you going to do big guy, sit on me?"
"don't tempt me"..)

 Similar Threads Thread Thread Starter Forum Replies Last Post tServo Hardware 6 2016-05-06 15:52 petrw1 PrimeNet 3 2015-11-19 21:37 mathemajikian Hardware 24 2009-02-03 04:38 Dr-S Science & Technology 7 2007-02-19 07:35 sagan_fan Math 4 2003-03-26 05:01

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

Sun Apr 18 06:42:32 UTC 2021 up 10 days, 1:23, 0 users, load averages: 1.51, 1.60, 1.73