Pi Connects Colliding Blocks to a Quantum Search Algorithm | Hacker News Reader

Pi Connects Colliding Blocks to a Quantum Search Algorithm

abstractions.nautil.us

189 pointsrudrarch23 comments

Here is the 3blue1brown video that is alluded to in the article: https://youtu.be/jsYwFizhncE

The posted article is by 3blue1brown (Grant Sanderson) himself. Where the article says "Early in 2019, I published a set of three videos about Galperin’s result..." the link is to the playlist https://www.youtube.com/playlist?list=PLZHQObOWTQDMalCO_AXOC... of which the video you posted is the second video. IMO, it's best to watch all three (or at least the first two) together :-)

If you want to learn more about the quantum search algorithm, I got a lot out of this pretty in-depth essay on how it works-

https://quantum.country/search

I just saw the quantum country article pop up yesterday and have since been doing a lot of reading on the authors: Andy Matuschuck & Michael Nielsen

I started with their mnemonic medium and look forward to diving into quantum country.

What an exciting time to want to learn!

I got to the "mnemonic medium" part of that and promptly lost interest. No, I don't want you to track me.

Quantum Country is a fantastically useful learning resource. They're tracking you so you don't have to digest it all in one gulp, and can pick up where you leave off.

anything that is cyclical or periodic is going to have a Pi in the formula that describes its behavior

Often this is the case, and pi crops up plenty of other unexpected places, but counterexamples abound as well.

Pick any function defined on [0, 1], and replicate it along the real line at unit intervals. You can force a description of it using pi, but the most natural descriptions won't have any reference to it at all.

>replicate

you mean construct the periodic extension?

>You can force a description of it using pi

don't know what about the fourier series is forced...?

>but the most natural descriptions won't have any reference to it at all

can you give an example? when comparing piece-wise definitions and fourier series definitions i think the fourier series is the more natural.

> can you give an example?

How about a sawtooth; no pi needed, and the period is 1.

f(x) = x-floor(x)

The Gibbs phenomenon is my proof that Fourier series is not more natural.

Why? The Gibbs phenomenon is just an exhibit of a finite Fourier series, no?

It depends on which kind of convergence you like to think about.

fourier series converges pointwise but not uniformly. for many use cases you would like uniform convergence (e.g. approximation in an entire neighborhood of a point) and a fourier series won't give you that no matter how many terms you add. but like i said above - gibbs only occurs at non-removable discontinuities and so you shouldn't expect it to be well behaved at those points regardless of the representation.

gibbs phenomenon only occurs for discontinuous functions. so it's a reflection of a pathology, not a pathology per se. what i mean is the problem is with the function itself (it's got non-removable discontinuities!) not the fourier series representation.

>you mean construct the periodic extension?

Yes. A more common language felt appropriate given the broad background of the audience, and I also didn't handle any boundaries or edge cases in the functions whose existence I invoked -- if you'd like to poke holes.

>don't know what about the fourier series is forced...?

Does it not feel at least a little unnatural to require infinitely many coefficients to describe a process that can otherwise be understood with a small, finite number of elementary operations? Simplicity is in the eye of the beholder, and I can't fault you if that's your viewpoint, but I do not agree.

>can you give an example? when comparing piece-wise definitions and fourier series definitions i think the fourier series is the more natural.

Another comment mentioned the sawtooth function. It seems your viewpoint is that the fourier series is the more natural description of periodic phenomena, perhaps because of its ability to represent many (but definitely not all) periodic functions. One can, however, capture _all_ periodic functions with a piecewise description, and depending on the function (e.g. the sawtooth) this alternative approach might be considerably simpler to write out and explain. That doesn't necessarily make it more elegant in your eyes (and IMO theorems which are too general purpose can lose sight of what made them worthwhile in the first place), but if not then I'm not sure that either of us have enough material to convince the other of their chosen view.

>but definitely not all

integrable is quite a general class of functions (especially if you define the coefficients in terms of the lebesgue integral instead of the riemann integral).

>a small, finite number of elementary operations

piece-wise definition is not an elementary operation. you can't easily add/multiply/compose piece-wise defined functions. you can't easily differentiate/integrate them either. fourier space representations don't suffer from any of these issues.

>integrable is quite a general class of functions (especially if you define the coefficients in terms of the lebesgue integral instead of the riemann integral).

Quite true, but it's still just a subset of all functions, and you're still left with some sticky points with respect to pointwise convergence vs convergence almost everywhere.

>piece-wise definition is not an elementary operation. you can't easily add/multiply/compose piece-wise defined functions. you can't easily differentiate/integrate them either. fourier space representations don't suffer from any of these issues.

I'll give you composition as a tricky operation, but fourier series aren't particularly amenable to composition either. Addition, multiplication, differentiation, integration, and whatnot are very straightforward though. You use a refinement of the two respective piecewise partitions, perform the desire operations, and potentially have to reconcile misbehaviors along the boundaries. Fourier series have a different set of formulaic approaches to the same operations, but they have roughly the same pitfalls (e.g. regions of non-differentiability) and additionally have problems like the aforementioned Gibbs phenomenon if finite approximations are desired or else some difficulty in deciphering which elementary functions might describe the series.

While this may be obvious to anyone familiar with elementary physics, it’s still fascinating that it shows up in something called “quantum search”!

Who could possibly have imagined that somehow search relates to something cyclic?

I guess when you think about classical search algorithms, there back and forth and back and forth, but still!

Any second-order linear ODE is going to involve sinusoids in its solution. But nonlinear equations can be quasi-cyclical (e.g. strange attractors) and not involve sinusoids or Pi.

This is fascinating to this very-much-a-math-beginner person.

It's like a glimpse into another dimension.

or, indeed, many dimensions.

Grant Sanderson is doing such amazing work in divulgation of science and mathematics, promoting, I think, real understanding rather than the mere illusion of fluency. He's like the opposite extreme from WIRED Magazine, Chris Anderson, Malcolm Gladwell, and Deepak Chopra.

And here I was wondering if 3B would be powerful enough, or would I need to get a 4.

Reply on news.ycombinator.com