Julian Assange <[EMAIL PROTECTED]> writes:
> 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.
No. The abstract says, from http://xxx.lanl.gov/abs/quant-ph/9910033:
Simon as extended by Brassard and H{\o}yer shows that there are
tasks on which quantum machines are exponentially faster than each
classical machine infinitely often. The present paper shows that
there are tasks on which quantum machines are exponentially faster
than each classical machine almost everywhere.
It does not say that all tasks, or almost all tasks, can be made to run
exponentially faster. It says that "there are tasks" on which quantum
computers are exponentially faster on almost all inputs. In fact the
paper constructs a specific type of task for which this is the case.
Previously it was known that a task could be constructed for which the
QC was exponentially faster on infinitely many inputs. But this was
still an infinitisimal fraction of all possible inputs. Specifically,
the QC was faster on one value for each possible input length. The new
result shows that a task can be found for which the QC is faster on
almost all inputs (all but a finite number of inputs).
This is interesting for the theoreticians but not of any practical
value or import, unlike Shor's and Grover's algorithms. Unless it can
be applied to specific problems of interest to cryptographers, rather
than artificial ones designed to explore the nature of quantum computing,
it is not relevant here.
