3 ms·
Don't we have a provable guarantee in the case of the traversal of glued trees via oracle, i.e. no classical algorithm has lower query-complexity? (Granted, the
by kvathupo 5y ago
Don't we have a provable guarantee in the case of the traversal of glued trees via oracle, i.e. no classical algorithm has lower query-complexity? (Granted, the same can't be said for Grover's)
See section 16.4 of these notes (pdf warning) [1].
[1] - http://www.cs.umd.edu/~amchilds/qa/qa.pdf http://www.cs.umd.edu/~amchilds/qa/qa.pdf
- simiones 5y agoThese are two somewhat separate problems: 1. Do theoretical quantum computers have different properties than theoretical classical computers? (or, QBP = P? ) 2. Does some particular physical device show the properties associated with a theoretical quantum computer? Of course, if 1 is false, than 2 is more or less irrelevant. However, even if 1 true, that still leaves the question of 2 for any particular device. The Google and Chinese experiments have proven 2 for their own particular devices. This is an important milestone not just for these particular devices, but also because, prior to this, there was also a question 3: do QM systems actually exhibit the properties of a theoretical quantum computer? After the Google result, this has been almost entirely put to rest: the answer is yes.
- reikonomusha 5y agoExcellent explanation and separation of concerns.