Hacker News Reader

Maybe you've just used "items" in a non-standard way? The number of bits (N) is indeed being halved, but the standard way of talking about Grover's search is that you're searching for an item in the "database" of bit configurations (i.e., keyspace), which is 2^N. No one would refer to the bits as "items".

Ah, I see what you mean. Yes, I didn’t intend to refer to the bits themselves as items; rather I was referring to the bit-security.

O(2^(N/2)) is a quadratic speedup over O(2^N). Halving the search space, on the other hand, would only give you a linear speedup.

Edit: just to be clear: one half of 2^N is just 2^(N-1).

Yes, I see the issue now. I wasn’t referring to bits being halved. I was referring to bit-security (i.e. 128-bit versus 64-bit).

2^10 = 1024

2^20 = 1048576