From: Michael Nielsen <[EMAIL PROTECTED]>

On Thu, 2 Dec 1999 [EMAIL PROTECTED] wrote:

> From: dmolnar <[EMAIL PROTECTED]>
> On 3 Dec 1999, lcs Mixmaster Remailer wrote:
> > NTRU is a lattice based system.  Solving these systems involves some
> > linear algebra and matrix operations.  These are not known to be
> > accelerated by quantum computers.
> This is true. It's also true that the problem of finding shortest 
> vectors in a lattice has recently been shown to be NP-complete. Also
> I've heard that there are arguments that quantum computers may not be
> "powerful enough" to decide all problems in NP. 

Well, sort of.  A result of Bennett, Bernstein, Brassard and Vazirani
(SIAM Journal on Computing, 1997) shows that there is a class of
approaches to solving NP-complete problems on quantum computers that
won't work. 

The class of problems is what might be called "naive search" algorithms.
This class of algorithms is defined in the following way: given an
instance of an NP-complete problem --- say, a graph which we wish
to test for the presence of a Hamiltonian cycle --- the algorithm is only
allowed to make use of information about the graph which is obtained by
querying an "oracle" which tells the algorithm whether a
particular candidate path around the graph is a Hamiltonian cycle for
that graph or not.  Bennett et al show that such an algorithm requires
exponential resources even on a quantum computer.

Obviously, this class of algorithms is quite restrictive, as such 
algorithms ignore a lot of potentially useful information about the 
problem instance.  Nevertheless, if you believe (as many people do)
that what makes the NP-complete problems hard is that there is essentially
no structure in the problems to make them amenable to solution, then this
result implies that quantum computers won't be able to solve NP-complete
problems efficiently.

Of course, it's quite possible that this belief is wrong, and perhaps
quantum computers can even solve NP-complete problems efficiently.  We'll
just have to wait and see.  (I'm not holding my breath, mind you...)

Michael Nielsen
Room 3,  East Bridge,  Mail Code 12-33,  Caltech,  Pasadena CA 91125 
Ph:  626 395 8431                                  Fax: 626 793 9506     [EMAIL PROTECTED]

--------------------------- ONElist Sponsor ----------------------------

Essential Feynman Library for $7.99! (3 books/ 6 audio tapes -$97 value) 
Learn physics from the legenary Richard Feynman, renown for making
complex ideas easy to understand. Order NOW at Library of Science:
<a href=" ">Click Here</a>

Community email addresses:
  Post message: [EMAIL PROTECTED]
  Subscribe:    [EMAIL PROTECTED]
  Unsubscribe:  [EMAIL PROTECTED]
  List owner:   [EMAIL PROTECTED]

Shortcut URL to this page:
Old archive:

Reply via email to