Researchers implement 3-qubit Grover search on a quantum computer | Hacker News Reader

Researchers implement 3-qubit Grover search on a quantum computer

phys.org

45 pointsrbanffy12 comments

Two reminders, for anyone reading this and wondering about the implications for cryptography:

1. Grover's algorithm is applicable to symmetric cryptosystems, like AES. It searches for secret keys in a quantum-optimal manner. Shor's algorithm is the much more serious threat which endangers asymmetric (public-key) cryptosystems like RSA. It uses the quantum Fourier transform to attack integer factorization and discrete logarithm problems.

2. This 3-qubit implementation corresponds to 2^3 items; it is still extremely far off from being practically usable against AES-128. Moreover, Grover's algorithm can't be credibly used to break AES-256, as it improves the search time by approximately halving the number of items to be searched (i.e. AES-256 is reduced to 128 bits of security, AES-128 is reduced to 64, etc).

> it improves the search time by approximately halving the number of items to be searched (i.e. AES-256 is reduced to 128 bits of security, AES-128 is reduced to 64, etc).

No, "halving the number of items to be searched" would be a constant factor (1/2) change, which would be trivial. Computers get that much faster in a year.

Rather, using Grover brute search to crack a hash reduces the effective number of items to try by a square root. Each bit of AES increases cracking time by a factor of 2, which is why decreasing the cracking time by a square root is equivalent to halving the number of bits of security: sqrt(2^N) = 2^(N/2)

I’m confused by your comment, because it doesn’t seem like we’re disagreeing. The end result of Grover’s algorithm is that a 2^N keyspace can be searched in a worst case of 2^N/2 steps instead of 2^N steps. So yes, it does halve the number of items to be searched.

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

https://en.wikipedia.org/wiki/Grover%27s_algorithm describes the search algorithm in more detail.

What’s the Big-O factor for the initialization step? Seems it’s at least o(# qubits) which should be O(log n) where N is the database size, but the story acts like it it’s O(1) overall.

If I remember from when I worked on this, Grover allows searching N=2^n items with complexity O(sqrt(N)). Even if init was O(log N), this would be much smaller than O(sqrt(N)) for large N, so can be (almost) ignored.

O(sqrt(N) + log N) = O(sqrt(N)) by definition

Reply on news.ycombinator.com