Hacker News
new
|
past
|
comments
|
ask
|
show
|
jobs
|
submit
login
wbl
on June 30, 2019
|
parent
|
context
|
favorite
| on:
Factoring may be easier than we think (2016)
That's true but Grover search shows that quantum computers can give big speedups so I don't know why I would believe BPP=BQP.
nabla9
on June 30, 2019
[–]
Grover's algorithm still takes exponentially many operations to solve a search problem that can be brute-forced in exponentially many steps. Much faster, but still in EXPTIME. No jump from exponential to polynomial complexity class.
Consider applying for YC's Winter 2026 batch! Applications are open till Nov 10
Guidelines
|
FAQ
|
Lists
|
API
|
Security
|
Legal
|
Apply to YC
|
Contact
Search:
