Researchers Prove Quantum Computers Are More Powerful Than Classical Computers

Re:Researchers Prove Quantum Computers Are More Powerful Tha... by chowells on Saturday October 20, 2018 @06:41PM (#18265878)

Only if you assume that the classical counterparts of it are optimal. There's no proof of that.

[ Parent | on HN ]

Re:Researchers Prove Quantum Computers Are More Powerful Tha... by 21 on Saturday October 20, 2018 @06:43PM (#18265885)

For Groover algorithm, which is applied to the problem of search you can prove that there is no classical algorithm faster than O(N) - looking at each item in the worst case scenario.

[ Parent | on HN ]

Re:Researchers Prove Quantum Computers Are More Powerful Tha... by wolfgke on Saturday October 20, 2018 @06:49PM (#18265905)

> For Groover algorithm, which is applied to the problem of search you can prove that there is no classical algorithm faster than O(N) - looking at each item in the worst case scenario.

Assuming that you cannot "look into the black box of the oracle" (i.e. we are only allowed to use a given oracle to evaluate an item at an index).

[ Parent | on HN ]

Re:Researchers Prove Quantum Computers Are More Powerful Tha... by 21 on Saturday October 20, 2018 @06:53PM (#18265916)

You still have the case of a list of perfect random numbers. There is nothing in the box then.

[ Parent | on HN ]

Re:Researchers Prove Quantum Computers Are More Powerful Tha... by wolfgke on Saturday October 20, 2018 @07:14PM (#18265975)

But perfect random numbers cannot be evaluated by an algorithm. Evaluating the black box/oracle must be done in a run of Grovers's algorithm.

[ Parent | on HN ]