Pop quiz time! Try to answer without looking it up.
Suppose I have a mystery function, and I tell you that there’s some secret value among all the numbers from 1 to N, where if you plug that value into my function, it returns True, otherwise, it returns false. For example, maybe it simply looks something like "f(n): return (n == 123)". But you can't see the inside of the function; it's a black box.
How long does it take to find this secret value? For a classical computer, there's no better method than to guess and check all N possibilities. Sometimes you're lucky and get it early; sometimes you're unlucky, and it takes closer to N; on average, it's N / 2. In CS, we call that an O(N) run time, disregarding the constant because we just care about how things scale as N grows.
Here's your quiz: How long would it take a quantum computer to do the same task?
3Blue1Brown
Pop quiz time! Try to answer without looking it up.
Suppose I have a mystery function, and I tell you that there’s some secret value among all the numbers from 1 to N, where if you plug that value into my function, it returns True, otherwise, it returns false. For example, maybe it simply looks something like "f(n): return (n == 123)". But you can't see the inside of the function; it's a black box.
How long does it take to find this secret value? For a classical computer, there's no better method than to guess and check all N possibilities. Sometimes you're lucky and get it early; sometimes you're unlucky, and it takes closer to N; on average, it's N / 2. In CS, we call that an O(N) run time, disregarding the constant because we just care about how things scale as N grows.
Here's your quiz: How long would it take a quantum computer to do the same task?
5 days ago | [YT] | 4,616