Where my explanation of Grover’s algorithm failed

Last week, I put up a video introducing quantum computing. And in the final section, we were stepping through something known as Grover's algorithm. And based on the comments that I saw, I think there was a very common point of confusion that reveals I clearly could have done a better job explaining a core piece of it. Right here, I wanted to throw together a very quick supplement in the hopes of adding a bit of clarity.

The premise was to have a function which is somehow triggered by a unique value out of a big bag of options. And the puzzle is basically to figure out how do you find that unique value just by applying the function on various inputs. Now in a classical setting, it's not a very interesting question. The best you can do is guess and check.

But what we walked through was a completely different approach that you can take that becomes possible in the setting of a quantum computer. When we did this, there was a certain key step where, if I'm understanding the comments correctly, it looked to a lot of people like in order to apply this key step, you would have to already know the value that you're searching for, which would of course defeat the whole purpose of the algorithm. More specifically, we had this very highdimensional vector space and one of the axes in that space corresponded to the value that we're searching for. And this step of the algorithm looked like flipping along that axis, multiplying any component of a vector in that direction by -1.

Now, viewers were essentially asking, "Whoa, whoa, whoa. How could you know how to do that without already knowing which axis you're searching for?" I genuinely tried to forestall that objection, but I think I failed. So, backing up, I think the whole discussion might be clearer if we focus on a very concrete example, something like solving a sedoku. On your normal classical computer, it's not hard to write a function that checks whether a proposed solution follows all of the Sudoku rules and solves the puzzle.

You know, it would check the rows, the columns, squares for duplicates, things like that. If you have written this function, just because you know how to verify a solution, it's not at all obvious what the solution is in the first ...