Post

Very nice video! It's incredible that the pi-with-blocks problem has a "real life" application. Btw, I had on my list to make a video of ordinary probability vs quantum probability and this video is sparking joy. Would it be ok with you if I used some clips/screenshots from your video in my video?

Great video, my only hangup is: how can you translate the classical algorithm to a quantum one if it's a black box? And how did grover know that was possible? The premise of the problem is that f(n) isn't exactly known, yet Grover's relies on translating it to a set of quantum gates

That part of the video could have been better phrased. For any problem you'd want to use this for, you would know the gates, so it's not a black-box in that sense. But to have a catch-all stand-in example, I want to presume there's no insight you gain about the answer by analyzing those gates.

A common misconception about quantum computers is that they would solve hard problems by trying all possible solutions in parallel. This vaguely gestures at something true, but the reality is more subtle.

What do they do then? This video builds up to Grover’s algorithm, a general method in quantum computing for finding solutions to any NP problem, i.e., anything where you have a quick way to verify solutions, even if finding them in the first place may be hard.

As a generic stand-in for the kind of problem it solves, suppose you have a function acting on {1, ..., N} which returns True on one and only one value in this set. If all you can do with this function is try it out on numbers, then it takes an average of (1/2)N steps to find the answer.