# Could Grover's algorithm perform a search in N/2 for a match in a particular subset of a hash function preimage?

Suppose I first define some function f(x) where x is some unsigned 256-bit integer, and the function's output is a set of distinct strings of any length so that output set would be 2^256 unique strings, i.e. a bijection for the specified domain of x.

Example f(x) = 0xAA || x || 0xBB (|| indicates byte concatenation), but it could also be more complex like f(x) = 0xAA || g(x) || 0xBB.

Then, if I plugged that function into some Hash_256 function, like so: Hash_256(f(x)), could a quantum computer reveal a matching f(x) for some known output of the composite function, and that in 2^128 attempts? By treating the composite function as the "black box" function and do a quantum search on x, would that work?

Context: Bitcoin addresses, trying to answer my own question here. It is really a message template search against 160-bit hash that I'm after.

Yes, but note that these operations must be performed serially as Grover's algorithm is highly non-parallelisable. Even if we build quantum computers which can evaluate the function in one cycle and clock rates comparable to modern computers (both very extreme advances) this will take over $$2^{80}$$-years. If you wish to take 1/10th the time then you would have to buy 100 times more of this high-end quantum computer.
• Highly non-parallelisable means that using $4^k$ CPUs will take time $2^{128-k}$ for the 256-bit problem and $2^{80-k}$ for the 180-bit problem i.e. dividing the search space means that resources scale inverse quadratically with time. Thus a single threaded QCPU running for 10 million years could be replaced 100 trillion QCPUs working for a year. Nov 4, 2022 at 7:07