What would you do with a small quantum computer?

[xilman]

Originally Posted by LaurV

You didn't pay attention!

You're correct.

In that case, advertise on eBay that time on a quantum computer is available for a modest fee.

[retina]

Originally Posted by CRGreathouse

(it's tamperproof)

Just to note here that nothing can be tamperproof. Temperresistant I can accept.

So if it just has one of those sticky labels that says "warranty void if seal broken" or some of alien version of the pentalobe screws, or welded rivets, or a combination lock with a key, or indeed any other type of sealing mechanism then it won't be immune to tampering or opening and thus can be examined. Therefore I would examine it, and attempt to make a larger (i.e. more QC bits) version.

1. Examine.
2. ???
3. Profit!

[CRGreathouse]

Originally Posted by henryzz

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

Very fast, I think. I was trying to calculate a time but it's hard (lots of possible quantum algorithms, lots of unknown O-constants, unspecified classical time). Using Beauregard it would be slow (1 second?) but it looks like Cleve-Watrous might just be doable and it's so fast (at the cost of larger quantum storage, limiting you to no more than about 100 bits) that the time comes down to "as long as the classical pre-/post-processing takes". Let's say 1 microsecond for the sake of discussion.

[CRGreathouse]

Originally Posted by retina

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?

Originally Posted by retina

Just to note here that nothing can be tamperproof. Temperresistant I can accept.

So if it just has one of those sticky labels that says "warranty void if seal broken" or some of alien version of the pentalobe screws, or welded rivets, or a combination lock with a key, or indeed any other type of sealing mechanism then it won't be immune to tampering or opening and thus can be examined. Therefore I would examine it, and attempt to make a larger (i.e. more QC bits) version.

1. Examine.
2. ???
3. Profit!

The aliens take the quantum computer back. Sorry!

[CRGreathouse]

Originally Posted by bsquared

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.

I thought Grover's algorithm requires that the items to be searched fits in the qubits, so with 800 qubits you can't search a space larger than 800 or so. If I'm wrong about this, of course, I'd love to know! That's why I posted, of course...

[CRGreathouse]

Originally Posted by chris2be8

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.

Nice.

Originally Posted by LaurV

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

I'm not 100% sure I understand, but that sounds like a really good use.

[CRGreathouse]

Originally Posted by xilman

In that case, advertise on eBay that time on a quantum computer is available for a modest fee.

...

OK, in that case the interesting question becomes, "what do your customers do with it?".

Originally Posted by jwaltos

Program it to play a scaled down version of GO.

Can quantum computers do this efficiently?

Originally Posted by jwaltos

Bind it to a simple cellular/biological process to determine if it can echo or resonate with this process in real time.

Not sure I understand this one...

Originally Posted by jwaltos

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.

...or this one.

[CRGreathouse]

Originally Posted by only_human

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.

Yes, I certainly think that would be useful. A lot of supercomputer time goes into simulating quantum computing classically so we can do this, and a quantum computer would obviously be ideally suited for the task.

Originally Posted by only_human

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?

Harrow-Hassidim-Lloyd. Very nice, I hadn't heard of this before! It looks extremely powerful, like with even 800 qubits we could approximate the solution of a system of linear equations of essentially any size. If I'm reading the paper right, a system too large to solve with our quantum computer would be too large to write out in our universe.

I don't know what relation-finding could be done on a QC but that seems well-suited to their abilities. Given the usefulness of PSLQ/LLL this seems very practical.

[science_man_88]

Originally Posted by CRGreathouse

I thought Grover's algorithm requires that the items to be searched fits in the qubits, so with 800 qubits you can't search a space larger than 800 or so. If I'm wrong about this, of course, I'd love to know! That's why I posted, of course...

Originally Posted by "http://en.wikipedia.org/wiki/Grover's_algorithm"

Consider an unsorted database with N entries. The algorithm requires an N-dimensional state space H, which can be supplied by n=log2 N qubits

I don't quite know enough to decipher this.

[CRGreathouse]

Originally Posted by science_man_88

I don't quite know enough to decipher this.

It means I was wrong. So Grover looks possible!

[Batalov]

Originally Posted by retina

Just to note here that nothing can be tamperproof. Temperresistant I can accept.

1. Examine.
2. ???
3. Profit!

...I was clearing the pile of mementos from my last trip to Russia and found a metro pass card. I guess it is not much different from SmarTrip. Carefully took it apart and found a plastic layer with a periferal antenna and a small unit in the center. Fun!! (Apparently made by "Sitronics".)