From: "David A. Wagner" <dawagner@phoenix.Princeton.EDU>
Date: Mon, 3 Oct 94 13:27:46 PDT
To: solman@MIT.EDU
Subject: Re: Anyone seen the 'quantum cryptanalysis' thread?
In-Reply-To: <9410030816.AA25214@ua.MIT.EDU>
Message-ID: <9410032008.AA23352@burn.Princeton.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)".

I think it's been shown that, relative to a random oracle, it's not
true that NP is contained in BQP.  Then again, I'm told that oracle
results are often misleading and usually not worth a bean.  <shrug>
I don't know much about this stuff. :-(

[This oracle result is mentioned in Schor's paper.]

Hopefully someone more clueful than I will explain this stuff :-)

-------------------------------------------------------------------------------
David Wagner                                             dawagner@princeton.edu