Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I don't understand this question? Grover's algorithm is itself faster than classical search algos.

It is as of yet unknown whether quantum computers are more powerful than classical computers; there is no proof that BQP is strictly bigger than P. There is oracle separation but that's not the same thing.



I think that BQP > P is not so important. Exponential advantage of known qalg vs known c_alg when the hardware is available is what's important.


that's what everyone says but imagine 10 years from now someone proves BQP < P. since that proof will entail a ptime reduction you'll immediately have a ptime shor's and etc.


We have a p time Shor's !

I don't think BQP<P makes sense... BQP <NP? I think you may be mocking me :(




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: