2
$\begingroup$

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.

enter image description here

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?
Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ Could you add a link to the video you describe? It may help others in answering the question. $\endgroup$
    – Discrete lizard
    Commented May 1, 2018 at 21:21
  • $\begingroup$ sure! wasn't sure about linking YT and such $\endgroup$
    – fr_andres
    Commented May 1, 2018 at 21:24
  • $\begingroup$ 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 $\endgroup$
    – fr_andres
    Commented May 1, 2018 at 21:27
  • $\begingroup$ 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. $\endgroup$
    – Discrete lizard
    Commented May 1, 2018 at 21:30
  • 3
    $\begingroup$ 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. $\endgroup$
    – agaitaarino
    Commented May 2, 2018 at 4:15

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks @James, as always very enlightning! $\endgroup$
    – fr_andres
    Commented Sep 16, 2019 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.