mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Lounge

Reply
 
Thread Tools
Old 2012-07-20, 07:26   #1
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

597910 Posts
Default 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.)
CRGreathouse is offline   Reply With Quote
Old 2012-07-20, 13:28   #2
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

3×7×167 Posts
Default

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
jasong is offline   Reply With Quote
Old 2012-07-20, 15:48   #3
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

25·5·37 Posts
Default

How fast would it factorize small numbers of maybe 100 bits? Would it be fast enough to use factorizing large primes in NFS?
henryzz is online now   Reply With Quote
Old 2012-07-20, 16:12   #4
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

11000100011002 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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?
retina is online now   Reply With Quote
Old 2012-07-20, 16:13   #5
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×1,789 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
bsquared is offline   Reply With Quote
Old 2012-07-20, 16:22   #6
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

978610 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2012-07-20, 16:51   #7
chris2be8
 
chris2be8's Avatar
 
Sep 2009

7·311 Posts
Default

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
chris2be8 is offline   Reply With Quote
Old 2012-07-20, 17:08   #8
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

22·3·11·83 Posts
Default

Sell it on eBay?
xilman is online now   Reply With Quote
Old 2012-07-20, 18:15   #9
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

1110101010102 Posts
Default

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
only_human is offline   Reply With Quote
Old 2012-07-21, 02:22   #10
jwaltos
 
jwaltos's Avatar
 
Apr 2012
Gracie on alert.

24×52 Posts
Default

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
jwaltos is offline   Reply With Quote
Old 2012-07-21, 05:48   #11
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

2×3×7×233 Posts
Default

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

Quote:
Originally Posted by CRGreathouse View Post
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"..)
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Want to play with IBM's quantum computer? tServo Hardware 6 2016-05-06 15:52
ok who turned on the Quantum Computer? petrw1 PrimeNet 3 2015-11-19 21:37
Quantum Computer mathemajikian Hardware 24 2009-02-03 04:38
Quantum Computer Demonstrated ! Dr-S Science & Technology 7 2007-02-19 07:35
quantum computer sagan_fan Math 4 2003-03-26 05:01

All times are UTC. The time now is 09:29.


Fri Oct 22 09:29:31 UTC 2021 up 91 days, 3:58, 1 user, load averages: 1.51, 1.55, 1.45

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.