3 ms·
I guess you're right, I remember seeing quantum algorithms that were assumed to be more efficient than any classical algorithm and then people devised equally e
by outlace 7y ago
I guess you're right, I remember seeing quantum algorithms that were assumed to be more efficient than any classical algorithm and then people devised equally efficient classical algorithms. E.g. work by Ewin Tang https://arxiv.org/abs/1811.00414 https://arxiv.org/abs/1811.00414
- jessriedel 7y agoThey were definitely not being assumed to be faster. It was considered very uncertain. Quantum algorithms for which people are pretty confident there is no classical algorithm of similar speed, while still unproven, are Shor's algorithm (i.e., no fast classical factoring) and the present case of sampling for supremacy.