From: jamesd@netcom.com (James A. Donald)
Date: Wed, 25 May 94 10:28:00 PDT
To: cypherpunks@toad.com
Subject: Factoring with a quantum computer (Citation)
Message-ID: <199405251727.KAA24317@netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


First:   Don't panic.
 
So far no usable quantum computer has been built.  It will
be a long time before one is.  Secondly a quantum computer
capable of factoring 1024 bit keys will require
polynomially high precision in its extremely tiny
components, whereas a classical computer will only require
order one precision, regardless of the number of bits. This
may well not be feasible until we are close to achieving
nanotechnology.
 
(That is polynomially high precision, which achievable.
Non polynomially high component precision is of course
impossible for problems large enough to be interesting)
 
Secondly: Yes, quantum computers will indeed be able to
solve in polynomial time many problems that require non
polynomial time for classical computers.  In plain English
that means that they can solve problem classes that
ordinary computers cannot solve.  Factoring is one of those
problems.
 
This result was established by  E. Bernstein and U.
Vazirani, and has recently been published as:  Quantum
Complexity Theory, Proc. 25th ACM Symp. on Theory of
Computation, pp.  11--20 (1993).
 
Barak Pearlmutter summarizes the current status as follows:
 
    The class of things a quantum computer can compute in
    polynomial time is called QRP.  The class of things a
    regular randomized computer can compute in polynomial time
    is called RP.  It is not known whether RP>P.  But, under
    the usual assumptions, we know RP < QRP <= P^#P.
 
    It is not known whether QRP < NP.
 
    Factoring has not been shown to be in RP, nor has it been
    shown to be NP-complete.  (If factoring were shown to be
    NP-complete, then we would have NP=coNP, a big deal, and
    also NP <= QRP, an immense deal assuming that accuracy
    problems don't make them impossible to build.)
 
    So it might be that NP <= QRP.  Also plausible is RP < QRP < NP.
 
    In any case, the public key cryptosystems we thought were
    secure (RSA, discrete logs) has now had their viability
    brought into serious question.  Even if QRP<NP (which it
    might not be) it might be the case that any public key
    cryptosystem can be broken in QRP, since no public key
    cryptosystem has been exhibited for which the inverse
    problem is NP-complete.  (Some have been related to
    NP-complete problems, but with the reductino in the wrong
    direction, which proved fatal.)
 
 
I will shortly give a hand waving explanation of why it is
so, why a quantum computer is potentially capable of
solving problems that a classical computer cannot solve
within the lifetime of the universe.
 
I am not able to cite Shor's result, showing that factoring
is among the problems that a quantum computer can solve
efficiently, because he is not yet published.  I am
attempting to reconstruct his results from information that
people have given me about them, but so far I am making
fairly heavy weather of it.  He is applying the remarkable
result of Bernstein and Vazirani to a particular
interesting case.  So if you want to go an prove that his
method cannot possibly work, simply go and prove that the
methods of Bernstein and Vazirani, cannot possibly work.
The quantum magic part is in Bernstein and Vazirani's
work, not Shor's work.
 
(I can assure that they will work.)
 
Some of you folk may remember the great flame war on this
topic on the Extropians mailing list.  I mentioned this
result, without giving source or authority  (it had not
been published to my knowledge at that time), and Price
flamed me vigorously, calling me an idiot, an ignoramus, a
crackpot, and a fool, and so forth, and offered to bet 5000
British pounds, then about US$7500, on the matter.
 
$7500 bet!
 
I of course cheerfully accepted.  Alas I wanted the judging
to be done by somebody who had published on quantum
computing in a refereed journal, (like Bernstein) and I
wanted that person to hold the pot.  Michael reluctantly
agreed to having the bet judged by a qualified person but
he wanted the pot held by a bunch of people who are
involved in a business concerning which I have very grave
and serious suspicions.  I attempted my various means of
persuasion to get him to put up the pot. Alas, Michael was
not willing to let the pot for the bet go outside the
control of him or these dubious people. Eventually I
resorted to a vigorous attempt to shame him into putting up
the money.
 
My unkind comments concerning Michael and his pals
eventually resulted in me being expelled from the
Extropians list, for flaming Michael and defaming the Exi
board.
 
But since Bernstein and Vazirani are now published, and no
further suckers seem willing to come forward and bet, I am
now going to give an vague hand waving explanation of their
results.
 
A quantum event has many outcomes, all of them
happening at once.
 
Consider a quantum computer with 1024 bits of memory. (128
bytes, not 128 megabytes)  A classical computer can only be
in one state at a time.  A quantum computer can be, and
usually will be, 2^1024 states simultaneously.  That is
10^306 states, or about 1 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000 000 states
simultaneously.
 
Obviously a quantum computer can explore state space a lot
more efficiently than a classical computer can.  In fact a
classical computer simply cannot explore a space that big,
even if the computer were to fill then entire universe.
 
This however is not much use, because the probability of
observing it in the correct state is equally low.  The
clever trick of Bernstein Vazirani is to arrange for
constructive interference between  correct answers and
destructive interference between incorrect answers.  This
requires the quantum computer to retain quantum coherence.
It is evident that most of the people blowing off and
saying "Quantum computers are bullshit" do not understand
quantum coherence etc.  (At least Michael Price had some
faint grasp of quantum mechanics.)
 
Thus a quantum computer has vast potential for problems
that involve the combinatorial explosion.
 
Unfortunately, because the transformation is unitary, a
quantum computer cannot efficiently report back the one
correct result that it has discovered to the any one
particular reality
 
Although getting the information out of a quantum computer
is inherently inefficient, it is not always
nonpolynomially inefficient.
 
My judgment, for what it is worth, is that (for the vast
majority of problems that are not NP complete, but are NP
and are actually interesting, because they have an answer
that is true rather than an answer that is marginally
better than other answers) it will be reasonably easy to
find ways of persuading a quantum computer to disgorge the
necessary information that are only polynomially
inefficient.  These methods will be extremely general,
rather than domain specific, and algorithms will improve in
the direction of generality.
 
A quantum computer will always operate very rapidly, for
any algorithm that one would wish to program on a quantum
computer.
 
For many algorithms, the probability of it emitting the
right answer is rather low.  If the probability is non
polynomially low, then the algorithm is of course useless.
A number of algorithms have now been shown, including
factoring, where the probability is only polynomially low,
which is of course enormously better than non polynomially
low.
 
The precision of the components of the quantum computer
must be proportional to the time taken by one shot of the
algorithm, since in order to get the information out of
the computer with a reasonably high probability, we require
the class of true answers to interfere constructively,
while the vastly larger class of incorrect answers
interferes destructively.  If the computer sits there for
too long, random thermal noise will destroy coherence, and
all the answers will interfere randomly, so the probability
of getting the right answer out (observing the computer in
the desired state) will be non polynomially low.
 
Similarly, if the quantum computer takes too many steps,
imperfections in its components will destroy quantum
coherence.
 
When the coherence is lost, a quantum computer is
equivalent to a non deterministic computer.  When it
retains quantum coherence, it can surpass a non
deterministic computer by an exponentially large factor.
 
 ---------------------------------------------------------------------
We have the right to defend ourselves and our     |
property, because of the kind of animals that we  |         James A. Donald
are.  True law derives from this right, not from  |
the arbitrary power of the omnipotent state.      |        jamesd@netcom.com