quantum chip built

[leichter_jerrold at emc.com]

| I'm fairly ignorant of quantum computers, 
I'm no expert myself.  I can say a few things, but take them with a grain of
salt.

|					    having had the opportunity
| to see Schor lecture at a local university but unfortunately finding
| myself quickly out of my depth (I still don't understand the weird
| notation they use for representing [superpositions of?] "states" in
| Bell inequalities and his lecture was full of diagrams that I didn't
| grok at all).  So, I have a few questions:
| 
| 1) Are there quantum encryption algorithms that we will use on quantum
| computers to prevent quantum cryptanalysis?  Not just key
| distribution; ID Quantique is commercially selling units for that
| already.
I don't recall seeing any quantum encryption algorithms proposed.  Someone
may
have done so, of course - the field is moving quickly.  Our understanding of
quantum computation is very limited so far.  Quantum key exchange is one
pretty well-developed area.  The main other algorithms are variations of
search.  A number of years down the road, I'm sure both will be seen as
"obvious" applications of ideas that had been around for years.  (Quantum
key
exchange is the practical application of ideas from thought experiments
going
back to the birth of quantum mechanics.  Search algorithms are pretty
straightforward applications of the basic idea of quantization.  There was
never a reason to look at these things as computational mechanisms until
recently.)

| 2) Can't they superimpose more than two states on an particle, such
| that the precision of the equipment is the limiting factor and not the
| number of entangled particles?
There is actually a limit to the number of distinct quantum states that
any system can have, based mainly on the *area*, not volume, of the system.
(In some sense, we seem to have a 2-space-dimensional universe!)  The limit
for an elementary particle is pretty small.

BTW, this has some interesting implications.  We usually argue that some
computation, while beyond our current reach, is "in principle" possible.
But
in fact one can compute a bound on the number of primitive computational
events that could have taken place since the creation of the universe.  If
a computation required more than that number of computations - think bit
flips, if you like - then "in principle" it would seem to be impossible, not
possible!  One can flip this around:  Suppose you wanted to do a brute-force
attack against a 128-bit key.  OK, that requires at least 2^128
computational
steps.  Suppose you wanted the result in 100 years.  Then the computation
can't require a volume of space more than 100 light-years across.  (Well,
really 50.)  You can compute how many bit flips could take place in a volume
of space-time 100 light-years by 100 years across.  If it's less than 2^128,
then even "in principle", no such attack is possible.

I did some *very* rough calculations based on some published results - I
didn't have enough details or knowledge to do more than make a very rough
estimate - and it turns out that we are very near the "not possible in
principle" point.  If I remember right, a 128-bit key is, in principle, just
barely attackable in 100 years; but a 256-bit key is completely out of
bounds.
So much for the snake-oil "my 1500-bit key is much more secure than your
256-bit key" claims!


| 3) Does anyone remember the paper on the statistical quantum method
| that uses a large source of molecules as the computing device?  I
| think it was jokingly suggested that a cup of coffee could be used as
| the computing device.  What became of that?  All this delicate mucking
| about with single atoms is beyond my means for the forseeable future. 
| I still have hopes of progress on the classical system but if that
| doesn't work out my second bet is on computation en masse.
There are some very recent - last couple of weeks - results on creating
entangled systems of 100's of thousands of particles.  (Hence my suggestion
that we are doing quantum "transistors", but will eventually do quantum
"IC's".)
							-- Jerry

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com