In the fifth and final of a series of guest videos I've been posting, @BenSyversen delves into a question anybody who has had to do ruler and compass constructions in a geometry class may have wondered: What's the point?

For context, I knew I'd want to take some time away this year (paternity leave!), so I reached out to a few other creators whose work I respect and asked if they'd be interested in me commissioning a guest video during my absence. It's a pretty good lineup coming!

To get around the question P=NP, and whether some clever analysis of the gates could also reveal the answer, the framing here is to assume the only thing you can do with the function is try it out on inputs.

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.

It's known you cannot do better than O(√N), which is certainly not as earth-shattering as an exponential speed-up would be, and questionably useful given the enormous overheads of quantum computing. Nonetheless, it's thought-provoking that such a thing is possible!

If you translate this setup into a quantum computer (explained in the video), Grover's algorithm offers a "faster" way to do this, in that it's O(√N).

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.

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.

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.

I hope so too, the thought of a high school teacher using this idea for a lesson was a key motivator in the back of my mind.

If you do this, you can reach out to the channel via this page. 3blue1brown.com/contact

Be sure to have a link to footage of the experiment. If anyone can get it to work with 100-to-1, I'd be happy, and if anyone can do it for 10,000-to-1, I'd be both delighted and amazed.

More generally, with a mass ratio of N-to-1, the number of collisions is around π / arctan(1 / sqrt(N)). So any big mass ratio gives you an approximation of pi by multiplying the number of collisions by arctan(1/sqrt(N))

Note, there's no reason to restrict yourself to powers of 100. For example, you could use powers of 4 to compute pi in binary. A mass ratio of 64-to-1 should give 25 collisions, which is 11001 in binary, and pi looks like 11.001...

Also, it's a wildly inefficient way to compute pi. To even get "3.14" you'd need this to work with a 10,000-to-1 mass ratio and have a way to count all 314 collisions. Matt Parker and I actually gave this a go, and the results were...okay, but could definitely have been improved :)