Re: JSH: Easy math, easy solution

From: David McAnally (zzdmcana_at_uq.net.au)
Date: 02/25/05 

Date: Fri, 25 Feb 2005 00:45:39 +0000 (UTC)

I am not sure if what I responded previously got through, so I will send
it again.

Richard Henry wrote:
> "David McAnally" <D.McAnally@i'm_a_gnu.uq.net.au> wrote in message
> news:cujlue$2bhi$1@bunyip2.cc.uq.edu.au...
> > D.McAnally@i'm_a_gnu.uq.net.au (David McAnally) writes:
> >
> > >"Steven" <somewherenonexistant@yahoo.com> writes:
> >
> > >>ccording to your reasoning,
> > >>the trial-division algorithm is even *simpler*, but it is as slow
as
> > >>heck. The algorithm you posted (Pollard?) is only marginally
better
> > >>than trial-division,
> >
> > >It was not Pollard. Also, the algorithm that I posted can be
performed
> in
> > >POLYNOMIAL TIME with a QUANTUM COMPUTER and a classical computer.
> > >Classical computers, we already have. We only have to wait for
quantum
> > >computers to be invented.
> >
> > I would add that a quantum computer has no need of a Pollard style
> > algorithm
>
> That depends on the speed of your quantum computer. For some values
of its
> speed, and for some values to be factored, a Pollard-style algorithm
on a
> fast classic digital von Neumann (or Harvard) architecture machine
will be
> faster. I cannot imagine a functioning (future) quantum computer
existing
> in isolation from a digital computer, if only to handle its I/O.

That was not what I wrote. What I wrote was that a quantum computer
had no need to use a Pollard style algorithm. This is independent of
whether or not there are classical computers which are faster using the
algorithm.

A quantum computer can implement a polynomial-time algorithm
simultaneously for exponentially many different values for parameters,
in polynomial time. Specifically, for any x and n, a quantum computer
can simultaneously compute the value of x^b mod n for a number of
values of b (the number of values being a polynomial of n) in a time
which is polynomial in log n, and using an amount of space which is
polynomial in log n.

Also, the requirement of a classical computer in the algorithm is much
more than just handling its I/O. The output of the quantum computer in
Shor's algorithm is still raw data, which needs to be input into the
classical computer so that the classical computer can convert it into
something useful. In the case of Shor's algorithm, the role of the
quantum computer is to identify a fraction with known denominator which
is polynomial in n (not necessarily in lowest terms) which is in the
neighbourhood of a fraction whose denominator is the order of x modulo
n (not necessarily in lowest terms), and the role of the classical
computer is to identify the fraction whose denominator is the order.
This is done by the classical computer by using continued fractions.
In other words, the role of the quantum computer is to narrow down the
range of the search that has to be made by the classical computer to
something manageable in polynomial time. The classical computer is
also needed to test for being the order of x modulo n (this only
requires a single evaluation of x^b modulo n).

By choosing an appropriate polynomial of n for the denominator of the
fraction identified by the quantum computer, it is possible to rid the
classical computer of the need for any search at all, by just using
least common multiples (Shor's own choice of polynomial does not allow
for this option, but there are polynomials which do allow it).

David

-----

Relevant Pages

  • Re: JSH: Easy math, easy solution
    ... The algorithm you posted is only marginally better ... >POLYNOMIAL TIME with a QUANTUM COMPUTER and a classical computer. ... I would add that a quantum computer has no need of a Pollard style ...
    (sci.math)
  • Re: JSH: Easy math, easy solution
    ... >>It was not Pollard. ... the algorithm that I posted can be performed ... >>POLYNOMIAL TIME with a QUANTUM COMPUTER and a classical computer. ...
    (sci.math)
  • Re: Tech building
    ... classical computer, and many vary great disadvantages, ... but there are some things a quantum computer can do, ... As for neural nets, they are good for certain kinds of problems. ... neural nets were the *second* best technique ...
    (rec.arts.sf.composition)
  • Re: How long would it take a computer to completely "solve" chess?
    ... The kind of tree search you need to do to determine the ... a quantum computer will turn it into an easy one. ... the types of problem for which there's an algorithm to solve it using ... because each other type of problem in PSPACE can be reduced to it. ...
    (sci.math)
  • Re: A unique number for every "person" - can it be done?
    ... > This similarity in calculation between a classical and quantum computer ... a classical computer would be able ... Turing machine can be said to set the computational limits for the one, ... - Gerry Quinn ...
    (sci.math)