4 ms·
https://arxiv.org/abs/1704.00690 https://arxiv.org/abs/1704.00690
by omazurov 8y ago
https://arxiv.org/abs/1704.00690 https://arxiv.org/abs/1704.00690
- utopcell 8y agoIs it the case that a logarithmic gap is shown for a specific problem ? Why is this a big deal ? Doesn't Grover's algorithm already demonstrate a sqrt(n) gap ?
- 21 8y agoGrover is sqrt(n) versus n, this paper says for their problem is 1 (constant depth) versus log n: > In contrast, we show that this problem can be solved with certainty by a constant-depth quantum circuit
- chowells 8y agoOnly if you assume that the classical counterparts of it are optimal. There's no proof of that.
- 21 8y agoFor 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.
- wolfgke 8y ago> 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).