More 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.

More 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.