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 http://theory.caltech.edu/~mnielsen/ [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=" http://clickme.onelist.com/ad/dblselect5 ">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: http://www.onelist.com/community/transhumantech Old archive: http://mail.planetx.com/transhumantech/
