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...
My Tweets
Followers
FeedBurner FeedCount
Recent Comments
Labels
- research (65)
- miscellaneous (43)
- community (38)
- blogosphere (25)
- soda (20)
- socg (17)
- publishing (16)
- conferences (15)
- awards (14)
- funding (13)
- teaching (13)
- humor (12)
- outreach (12)
- nsf (10)
- jobs (8)
- p-vs-nc (8)
- clustering (7)
- focs (7)
- deadline (6)
- latex (6)
- stoc (6)
- academy (5)
- data-mining (5)
- socg-2010 (5)
- books (4)
- personal (4)
- GIA (3)
- cs.CG (3)
- geometry (3)
- DBR (2)
- alenex (2)
- cs.CC (2)
- cs.DS (2)
- game theory (2)
- godel (2)
- math.PR (2)
- p-vs-np (2)
- turing (2)
- PPAD (1)
- acceptances (1)
- acm (1)
- analco (1)
- coffee (1)
- complexity (1)
- cricket (1)
- cs.LG (1)
- distributions (1)
- eda (1)
- esa (1)
- expanders (1)
- fonts (1)
- history (1)
- knuth (1)
- media (1)
- multicore (1)
- nih (1)
- obituary (1)
- quant-ph (1)
- quantum (1)
- rajeev motwani (1)
- randomness (1)
- software (1)
- streaming (1)
- surveys (1)
- twitter (1)
- video (1)
- wads (1)
- writing (1)
- xkcd (1)
Things I'm reading
Blogs I read
7 comments:
Is this for real? I thought someone had proved that Grover's algorithm was optimal?
Posted by Anonymous
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
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
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
interesting. If you learn more, do post a comment (or email me).
Posted by Suresh
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
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
Post a Comment