3 ms·
Note: nitpicking follows :) RAM machines are an abstraction, there's no such thing as constant-time access to a random address in any physical store. At best y
by cmrx64 10y ago
Note: nitpicking follows :)
RAM machines are an abstraction, there's no such thing as constant-time access to a random address in any physical store. At best you're looking at O(n^0.5) where n is the number of bits in the store. Still a speedup, but not nearly as much as predicted by using a RAM machine.
Grover's algorithm doesn't offer exponential speedup over classical algorithms, its complexity is O(n^0.5) queries, where n the size of the list being searched, versus O(n) queries classically.
- gizmo686 10y agoMore nitpicks: You should be able to get memory down to O(n^1/3) if you move into 3D. For Grover's algorithm, it depends on how you paramiterize the problem. For example, consider brute forcing a key. We generally parameterize this problem by the size in bits of the key, in which case we are looking at O(2^n) queries. Grovers algorithm lets us reduce this to O(2^.5n) querires, which is an exponential speedup.