# Grover's algorithm: number of searches required to find a key

I would like to start my question with a quote:

If an encrypted document and its source can be obtained, it is possible to attempt to find the 56-bit key. An exhaustive search by conventional means would make it necessary to search 2 to the power 55 keys before hitting the correct one. This would take more than a year even if one billion keys were tried every second, by comparison, Grover's algorithm could find the key after only 185 searches.

This quote is from A Brief History of Quantum Computing By Simon Bone and Matias Castro

As a reader, I wonder how the authors got the magic number of 185. Unfortunately, that is not justified.

I thought about it myself. To calculate the number of iterations, the Grover algorithm uses this formula:

$$k=\frac{\pi}{4\cdot \sin^{-1}\left(\frac{1}{\sqrt{2^n}}\right)}-0.5$$

If I just do that for the number $$2^{56}$$ (DES keysize), then it follows that you need k iterations:

$$k=\frac{\pi}{4\cdot \sin^{-1}\left(\frac{1}{\sqrt{2^{56}}}\right)}-0.5=210828713$$

That's still not the number the authors suggest. Therefore I ask here, if anyone can imagine, how the authors came to the number. Is my consideration correct?

Assuming it were $$2^{16}$$, then you would need about 200 iterations, which are still not 185. I am not aware of a cryptographic system with a key length of $$2^{16}$$ ...

• it does sound wrong. Generally speaking, Grover gives you a quadratic speed up, so $2^{55}$ classical queries would become $\sim 2^{55/2}\simeq 2^{27}$ queries in the quantum case. That's quite different from "$185$ searches" – glS Apr 1 '19 at 11:30
• Ok, I think so too, but do you agree with my calculation, or is $2^{56}$ wrong in the calculation: $k=\frac{\pi}{4\cdot \sin^{-1}\left(\frac{1}{\sqrt{2^{56}}}\right)}-0.5=210828713$ – user4961 Apr 1 '19 at 11:38
• well yes, I agree with the fact that the quoted result is pretty off. My calculation is just a rough approximation of the more precise estimate you compute. $2^{27.5}\sim1.9e8$ so this would be relatively close to $185e6$. Maybe it's just a typo in the text? – glS Apr 1 '19 at 16:38

I think your answer is right, the original article Searching a Quantum Phone Book said that Grover's algorithm would solve the problem after quantum-DES enciphering the known clear text a mere 185 million times.

Although it is different from the results you calculated, but it looks much better than 185.

• Well, how exactly that came to 185 million is not explained in both articles. Even if the original gives at least a better estimate :) I would say that for a key size of $2^{56}$, 210828713 Grover iterations would be needed to find the key. – user4961 Apr 1 '19 at 14:31
• Yes, I think so too. – Yijun Wang Apr 1 '19 at 14:37