# What is the relation between this CGI device and a quantum sorting algorithm?

I just came across this (apparently) entropy-reversing video. It is in fact nothing more than a computer-generated animation: first rendering the physical simulation of a bean machine (often seen in statistical mechanics educational experiments) using color-neutral balls and then assigning color by their destination bin. I find this amusing from a computational perspective, and hence my questions:

• If it was possible to achieve the portrayed effect physically, a spontaneous sorting based on pairwise interactions between the objects, what would be the computational implications of such effect?
• Are there any quantum algorithms described/implemented that achieve some kind of spontaneous sorting based on interference between the objects to be sorted?
• Could you add a link to the video you describe? It may help others in answering the question. May 1 '18 at 21:21
• sure! wasn't sure about linking YT and such May 1 '18 at 21:24
• I just read in the YT explanation that this is CGI... I will look that up and clarify it. If needed, I delete the post May 1 '18 at 21:27
• Don't be too quick in deleting it. It seems your main question is whether this effect would be useful/interesting for quantum computing. I don't think that this video displaying a real phenomenon is a requirement for that question. May 1 '18 at 21:30
• If you are able to carefully re-write the question so that there is no confusion between fact and fiction for a future visitor, that would be great. That will help in boiling this down to the actual question on quantum computing. May 2 '18 at 4:15

We could assign integers from $1$ to $k$ for each colour. This then becomes an integer sort of $n$ balls over a range of integers $r$.

I'm no expert on such sorting algorithms, but it seems that they can be done with a worst case time complexity of $O(n+r)$.

For the interacting bean machine to beat this, it would need to be faster to pass $n$ balls through a board of width $r$ (and I'll assume height $r$ too).

If we pass the balls through one-by-one, the falling process would presumably take $O(r)$ time in each case. So for the $n$ balls, that makes $O(nr)$ time, which is much too slow. They also wouldn't get any opportunity to interact, unless the falling was a quantum process with interference effects.

If we pass many balls through at once, the time taken for the process will depend on the dynamics of the balls, which depends on how they interact. If the interaction were to simulate a known sorting algorithm, the falling time would reflect that algorithm's time complexity. If the interaction does not simulate a known sorting algorithm, it could be used to define a new algorithm. The nature of the interaction (classical or quantum) would determine the kind of computer that we could run that algorithm on.

So in answer to your first question, we would need to know how the spontaneous sorting occurs to know how it compares to known algorithms.

• Thanks @James, as always very enlightning! Sep 16 '19 at 16:41