Anonymous <[EMAIL PROTECTED]> writes:
> Quantum computers help cryptanalysis in a couple of specific ways.
> They aren't all-purpose speeder-upers.
No. The reason I posted this abstract is because it says exactly the
opposite. *almost* any given Turing machine T can be turned into a
quantum machine Q which runs exponentially faster. That "almost" is
interesting. It represents a lower bound, not an upper bound. If it is
shown to be an upper bound as well, then perhaps within that small
subset of T, there exists useful crypto algorithms. Personally, I
doubt it.
Cheers,
Julian.
--
Stefan Kahrs in [Kah96] discusses the
notion of completeness--programs which never go wrong can be
type-checked--which complements Milner's notion of
soundness--type-checked programs never go wrong [Mil78].
