Introduction to Quantum Computing (17) - Grover's Algorithm: Problem Statement

Grover's algorithm solves the problem of finding a special input to a function. Specifically, suppose we have a function f whose value is 0 for all inputs, except for some special input, x*, for which its value is 1. Grover's algorithm finds x*. Given no additional information about f (that is, all we can do is evaluate it), the most efficient way to find x* is to sequentially test all inputs until one returns 1. Here's an implementation in Python. Now you may be thinking this seems very silly. We can see what x* is. It's 8. We don't need an algorithm to tell us that. It's right there. There are two ways to address this. One: this is just a toy example. In reality, Grover's algorithm assumes f is a black box. We can't look inside to see its internals. We just give it an input and get an output. This explanation isn't very compelling to me. It makes Grover's algorithm seem impractical. The explanation I like better is that this problem is equivalent to function inversion, which is very practical; there are many functions we know how to compute but don't know how to invert. The security of password storage relies on this fact. In this context these difficult to invert functions are called hash functions. Password cracking is inverting a hash function. It's straight-forward to modify the initial implementation of Grover's algorithm I gave to invert functions, and specifically invert a hash function and crack my password.

[pmcgktr]

This is the only series on quantum computing I haven’t gave up on tbh

[littlewhitebutterflies]

For your example python code, I think you should've set x* using a random number generator. In that way, your function would act more like a blackbox and the example would be more intuitive for watchers. I love this serious though, good work

[zeebay]

really good explanation and easy to understand.

[sshado]

Excellent series. Please keep up the good work.

[SunnyFly]

Thank you so much! Great content. Please continue.

[solarium]

Great series ! Can't wait for the following videos

[orduan]

Please keep explaining algorithms with python! This is make so much sense! SUBSCRIBED.

[techsinc]

This requires knowing the exact hash function. Would a real attempt at cracking a password have to go through different (known) hash functions in addition to the list of possible passwords?

[irrealesdisruptrealestatew]

A video about how Grover's algorithm and quantum computers will take over Bitcoin sha256 would be awesome. On single actor could take over 51% of the Bitcoin hashrate of Bitcoin using this algorithm and a powerful enough QC

[furqueue]

Well... sure but what's the point of the hash? Just move the hash into the algorithm you are testing and Grover over the whole thing. You don't need to think deeper than this. You just use Grover to brute-force every possible password. It 'obviously' lends itself to cracking passwords because you just spawn a billion different universes trivially and each tests a different password. That's why it's not elaborated on in the texts. It's trivial.