The Wavefunction Collapse Algorithm Explained

I think people are saying that the algorithm isn't cool enough for its name.

Bubbles aren't cool, so bubble sort must be rightly chided. /s

Quantum physics? Now that's cool, regardless of how much one knows about it.

I don't think the reason gets much deeper than that, barring any disagreements that it is just plain misleading.

I guess you could argue to some degree that a name should be usefully informative to an outsider or newbie. But that doesn't really apply to things that have already established their cool factor, like 'deep learning', 'crypto', 'agile', 'serverless', etc..

I’m complaining about it because when I first heard about it, I tried to look up information to understand the algorithm and.. it turns out that “wavefunction collapse” is not useful, at all, as search terms or a starting point to learn anything about this algorithm. The name is completely useless to understanding it or finding out any more about it.

You could say the same about bubble sort or whatever, sure, and a case might have been made about the name when it was first introduced, but now they’re established names where “bubble sort” are good search terms that will help you find lots of information about the algorithm, but “Wavefunction collapse” isn’t a widely used algorithm and the name has a lot of existing publications that are not related (because they’re to do with actual quantum physics, not this algorithm). Even searching “wavefunctoin collapse algorithm”, when I last did it, only found quantum physics result (that seems to have changed though, as I just did a google search and the entire first page is about this algorithm, but I see most of the results are quite recent: within the last few months)

I understand what you're saying but I'd like to push back a little. The loose analogy of superposition applies to a very large number of algorithms just as much as it applies to this one. You could likewise apply it to sorting - a "Wave Function Collapsing Sort" considers all elements of a set to be in superposition, then gradually "collapses" each index to the element which matches. It does this iteratively until it either sorts incorrectly and must start over, or until it produces the correct sort.

In other words, this isn't actually a superposition. You could definitely say there's entropy involved, but really this is replacing the word "uncertainty" with "superposition." If you do that, an extraordinary number of algorithms suddenly fit the template of wave function collapse. Basically anything that has a probability distribution and iterative reduction, because that's what this is (and not a wave function).

I'd also say that flood fill actually looks like a flood filling a room if you see a 2-dimensional visual of it pathfinding around obstacles. Personally I don't really care about how algorithms are named, but I think flood fill is a bad example because it actually looks like a flood filling a room.

> I have my own theory on why people like to complain about this particular analogy, but for the sake of not causing offence I will leave it there ;p

Why even mention it then? "I'm thinking something that might be offensive so I won't say anything"; sort of undoes the whole not saying anything bit, doesn't it?

> until a single 'observation' is made, which causes a reduction in the available possibilities, which propagates across the space/structure

wavefunction collapse is a singular event not an iterative process, results are not equiprobable, alternative probabilities become 0, there is no undo/traceback etc etc. the analogy doesnt make sense, it's just a fancy name

Not only that, but “wavefunction collapse” makes it sound a lot more complex and makes it more daunting to understand. A simple description of the simple tiled model algorithm in the article is basically “pick a candidate at random and prune remaining lists to remove now-invalid candidates” or something similar. Building the rules is simply “list all of the pairs in the example and store how frequently they occur. The frequency count prioritises more common pairs and pairs not encountered in the example can’t occur in the output”. No “quantum” or “wavefunction” or anything here. A list of candidate items isn’t a wavefunciton.

When I first saw this technique, I was interested in replicating it. So I started reading about wavefunction collapse on wikipedia. It had a bunch of complex quantum math and I gave up thiniking the technique was beyond me. But now I see it was also completely irrelevant. Thanks to the bad name, I gave up on it (until now, at least, when I see that its a lot simpler).

>the crucial property of quantum systems is interference, specifically "negative probabilities".

This suggests that it be called "PDF collapse," because it is collapsing a probability distribution function instead of a wavefunction.

\begin{pedant} Not negative probabilities, but negative probability amplitudes. The former doesn't make sense :) \end{pedant}

Cool names seem to work.

Take the Mersenne twister algorithm for instance. It is a non secure pseudo random number generator that is found everywhere even though there are alternatives that are better IMHO. I'm sure it's success comes from the fact that it is good enough and that it has a cool name.

I also think it is the rationale behind named vulnerabilities like heartbleed and spectre. Grabs attention.