Real world performance of (still theoretical) Grover's Algorithm

Question

Grover's Algorithm is a quantum algorithm for searching "black box" functions and could be used to reduce the search space for things like symmetric ciphers and hashes by as much as half (quadratic speedup). This would effectively reduce e.g. SHA-256 to 128 bits or AES-128 to 64 bits.

... in theory, of course. Nobody's built a QC that can run Grover's Algorithm yet and I doubt one will exist that can do it for anything other than toy problems for quite a while.

That being said I have a question about how Grover's algorithm works.

My understanding is that in Grover's algorithm there is a classical step in which the classical function must be evaluated for a given point to test if that point is the correct answer.

If that's the case, could you practically limit the performance of a post-quantum search by designing an intentionally expensive and inefficient algorithm? I'm thinking of some of the memory-hard compound hash monstrosities like CryptoNight that are used in the cryptocurrency world as block hash / mining functions. Would a slow complicated memory-hard algorithm effectively limit the performance of Grover's algorithm in the real world by making each iteration terribly slow? So even if you get quadratic speedup, 2^64 or 2^128 searches of something that takes 250ms of classical compute time per search would still take an absurd amount of time.

Thoughts?

Answer 1

You are right. Indeed, Grover's algorithm has to evaluate the function that is attacked in each iteration (actually the algorithm complexity measure in which you get the square root speed-up is query complexity). And of course, if you make that function more expensive you also make an attack more expensive -- classical as well as quantum. However, here we are switching from asymptotic statements to exact statements. These tend to depend on the exact architecture of a device. E.g., many functions will have different speed on different CPUs even if the clock speed is the same. The problem is that we do not yet know which architecture a future quantum computer will have.

The common thing in research papers is to measure exact complexity of quantum algorithms in terms of T-gate depth. However, this makes two assumptions. First, that the gate set used will be CNOT, T, and second, that T gates dominate execution time (which in this setting is pretty likely). This makes it hard to determine which kind of functions will be especially slow on a quantum computer.

Moreover, also the relation between cost of memory compared to cost of execution time is still open for quantum computers. Hence, it is not clear if a memory-hard function is better than a function that is slow, independent of the available memory. There exist architectures for qubits where keeping state is a lot easier than manipulating it. In these cases the bottleneck would probably be speed, not memory. However, this is all just a look into a crystal ball..., at most confined guessing.