Quantum computing

[Anders Breindahl]

On 200704191925, Robert J. Hansen wrote:
> While I agree that commercial development _may_ lead to developments  
> in QC, I think it's equally likely that the engineering difficulties  
> will be insurmountable.  Which means that, from where I sit, we  
> should just shrug and say "we really can't say with any confidence  
> what the future will or will not hold".

Well. Yeah. But the thing that was and is fascinating about cryptography
is that it -- assuming some model of computing -- is ``provable too
hard'' to bypass. I'm worried that the future holds in store revolutions
in computability that will shake those assumptions on ``too hard''.

This is in contrast to quantum cryptography, which, IINM, is provably
uninterceptable (but, unlike traditional cryptography, has many
weaknesses beyond the purely theoretical ones).


> > found -- this pragmatism causes me to ponder the scenario in which
> > something like Rice' theorem could be established for quantum  
> > computers'
> > ability (or traditional computers' inability):
> 
> What do you mean?  Rice's theorem applies to QC.

Again, if I got it correctly, Rice' theorem came into a world where
science was occupied with proving that this and that property was
undecidable. Something ``like'' Rice' theorem would in a similar way
alter the way that the scientific field is on.

> It's true that in mathematics there could always be a proof delivered  
> tomorrow by some hungry graduate student which will utterly shatter  
> our knowledge of math as we know it.  But this is true for all of  
> mathematics.  It's not as if this risk is special to QC.

I was mostly focusing on positive proofs, by which I mean those that
define what _is_ doable or assumable, rather than the negative proofs
that define what is undoable.

Both are convenient. However, the proofs that consolidate the security
of programs like gnupg, assume some model of computation... And in the
face of quantum computing, that assumption may (=has the potential to)
radically change.

So what I would love to see is some proof that -- even when faced with
this new model of computing, ignoring its practical limitations -- the
best-known attack on gnupg's algorithms takes factor ten of the lifetime
of the universe or would cost twice the energy of the sun.

Which can't be said of RSA on a huge quantum computer, if I understood
you correctly.

> You should  be just as concerned about the prospect of P=NP.

I haven't had my introductory courses in computability theory yet. I
don't know what that is, and will patiently wait for it.

Thanks for the lecture.

Regards, skrewz.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : /pipermail/attachments/20070420/b45394bb/attachment-0001.pgp