From: solman@MIT.EDU
Date: Mon, 3 Oct 94 21:01:48 PDT
To: "David A. Wagner" <dawagner@phoenix.Princeton.EDU>
Subject: Re: Anyone seen the 'quantum cryptanalysis' thread?
In-Reply-To: <9410032008.AA23352@burn.Princeton.EDU>
Message-ID: <9410040401.AA03583@ua.MIT.EDU>
MIME-Version: 1.0
Content-Type: text/plain


> > As I'm sure somebody else has pointed out somewhere along this thread, the
> > ability to simultaneously analyze a superposition of an arbitrarilly large
> > subset of all possible imputs (as our theoretical quantum cryptanalytic
> > device might) implies to ability to solve, in polynomial time, any
> > exponential time problem.
 
> I just wanted to point out that I'm not sure this is true.
> 
> I might be wrong; I'm a total newbie here.  However, my impression
> was that it is *not* known that "anything in NP is solvable in
> quantum polytime (BQP)".

Well its quite possible that I am wrong since I didn't exactly have the
easiest time reading the papers on the subject. But this is my reasoning:

If you can create a machine that gives you a yes or no result (yes at least
one of the subset of possible inputs entered into the machine contains
the properties you are looking for [i.e. does not destructively interfere],
or no there aren't any) then you can construct an quantum computer that
tests for the property(s) the correct answer must have (in the case of
factoring, the machine will test whether or not inputs divide the modulus).
You can now repeatedly enter as inputs superpositions of inputs that include
precisely half of all inputs that might (given the information that has
already been gathered) be correct). You will now be able to mount a brute
force attack searching through 2^n possibilities in order n time. It should
be possible to nest these machines (although admitedly this does nasty
things to the physical complexity of the quantum computer. It doesn't
seem like the complexity would grow exponentially in the case of nesting
[in fact it seems like it would go quadratically with the nesting level]
but I'd have to think about it some more before I could claim to be confident
of that.) thus allowing us to reduce any problem of time complexity
e^X(n) (where X is either a polynomial in n or of the form e^X(n) [this
goes on recursively]) to a problem of polynomial time complexity.

JWS