|
|
|
|
|
|
by gizmo686
4378 days ago
|
|
|
Not quite. Suppose there is some problem, whose best classical algorithm C, and whose best quantum algorithm is Q, with Q in o(c) [0]. Given that this relationship cannot exist in reverse (that is, quantum computers are at least as powerful as classical ones), this would mean that quantum computers are more powerful. The statement BQP!=P means that there exists a problem that a quantum computer can solve in polynomial time, but a classical computer cannot. This is a stronger requirement. For example, consider Shoore's algorithm, which can search an unsorted list in O(sqrt(n)) time, strictly better than the O(n) time it takes a classical algorithm. [0] Note that the little-o means strictly less, whereas big-O means less than or equal to. |
|
|
Aaahhh! Please don't say that when you're clarifying a technical point about theory!
Besides, it's explicitly stated in that article that "more powerful" is to be interpreted as P != BQP.