Tuesday, June 21, 2005

Intriguing

Via Quantum Algorithms, a new paper by Andreas de Vries that if correct would imply that NP is contained in BQP. I don't have the quantum computing chops to understand this, but am curious if anyone knows anything more about what's going on ?

Update: The Quantum Pontiff swats at it lazily...

7 comments:

  1. Is this for real? I thought someone had proved that Grover's algorithm was optimal? 

    Posted by Anonymous

    ReplyDelete
  2. If you are referring to the Bennett et al paper  , my quick reading of it indicates that the lower bound is a relativized one (relative to a random oracle).  

    Posted by Suresh

    ReplyDelete
  3. The paper has been submitted to Physical Review D so I suspect we'll be hearing a lot more about this if it makes it in (relatively) unscathed.  

    Posted by Jon

    ReplyDelete
  4. Actually, this new paper uses an oracle in much the same way Grover's algorithm does. The author claims that the O(sqrt(n)) lower bounds does not apply because his algorithm uses an 2n bit register (where n is the number of bits needed to represent the problem) while the earlier proof assumed at most n bits are used. 

    Posted by Jon

    ReplyDelete
  5. interesting. If you learn more, do post a comment (or email me).  

    Posted by Suresh

    ReplyDelete
  6. OK, so I'm lazy ;) It turns out the author has already made a mistake in Eq. 5. There the author has miscontrued the tensor product. Indeed if you accept his formula then his magical gate takes the 00 state to....zero amplitude. Which is a problem since the author correctly claims the circuit element is unitary. It's unitary, but the author's miscalculated the effect of the gate.
     

    Posted by Dave Bacon

    ReplyDelete
  7. One more mistake is in Eq. 9, where the autor says C²=C-I. This isn't a very important error but this sample that are several errors in this paper. I think that, when this paper will be refereed by the Journal's reviewers (Phys. Rev. D) de Vires will make some modifications for the algorithm to correct these problems but the demostration about NP C BQP isn't realizable for now.
    (Sorry for my bad english) 

    Posted by Alejandro Díaz-Caro

    ReplyDelete

Disqus for The Geomblog