But what is quantum computing? (Grover's Algorithm)

A lot of pop science outlets give a certain summary of quantum computing that I can almost guarantee leads to misconceptions. The summary goes something like this. In a classical computer, data is stored with bits, some sequence of ones and zeros. But in a quantum computer, you are able to represent every possible sequence of bits of some fixed length all at once in one big thing known as a superp position.

And sometimes the implication of these summaries is that quantum computers can be faster by basically doing whatever a classical computer would do but to all of these sequences in parallel. Now this does gesture at something that's kind of true. But let me see if I can prove to you why I think this leads to misconceptions. And I'll prove it using a quiz.

To set it up, I want you to imagine that I have a mystery function and I tell you that there's a certain secret number among all the numbers from 0 up to n minus one where if you plug that value into my function, it returns true. But if you were to plug in any other value, it returns false. And let's say you can't look at the inards of the function to learn anything about it. The only thing you're allowed to do with it is just try it out on numbers.

The warm-up question is, how many times on average would you have to apply this mystery function in order to find the secret key? Well, if the setup was in an ordinary classical computer, there's really nothing better that you can do than guess and check. You go through all the numbers, and maybe you're lucky and find it early. Maybe you're unlucky and it doesn't come up until later.

But on average, with a list of n possibilities, it takes 1/2 of n attempts to find the key. Now, in computer science, people care about how runtimes scale. If you had a list 10 times as big, how much longer would it take? And computer scientists have a way of categorizing run times.

They would call this one O of N where that big O communicates that maybe there's some constants like the 1/2 or maybe some factors that grow slower than N. But the factor of N is what explains how quickly it scales as N ...