What would you do with a small quantum computer?

CRGreathouse · 2012-07-20, 07:26

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.)

jasong · 2012-07-20, 13:28

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.

henryzz · 2012-07-20, 15:48

How fast would it factorize small numbers of maybe 100 bits? Would it be fast enough to use factorizing large primes in NFS?

retina · 2012-07-20, 16:12

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?

bsquared · 2012-07-20, 16:13

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, log₂N qu-bits using Grover's algorithm allows one to exhausively search a keyspace of size 2^N in time 2^(N/2). So 2⁶⁴ operations to break a 128 bit key... maybe on the edge of practicality for a relatively small keyspace.

LaurV · 2012-07-20, 16:22

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!)

chris2be8 · 2012-07-20, 16:51

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

xilman · 2012-07-20, 17:08

Sell it on eBay?

only_human · 2012-07-20, 18:15

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?

2012-07-21, 02:22

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."

LaurV · 2012-07-21, 05:48

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"..)

2012-07-20, 07:26	#1
CRGreathouse Aug 2006 1764₁₆ 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 3×7×167 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, 16:22	#6
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 41×251 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 2log2(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, 18:15	#9
only_human "Gang aft agley" Sep 2002 7252₈ 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 3³·269 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-20, 15:48	#3
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 13775₈ 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:51	#7
chris2be8 Sep 2009 5×17×29 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×17×347 Posts	Sell it on eBay?

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