One example here is the Steiner tree problem, which is NP-complete and can sort of be solved using soap films. Bringsjord and Taylor claimed this implies that P = NP. Scott Aaronson did some experimentation and found that soap films 1) can get stuck at local minima and 2) might take a long time to settle into a good configuration.
Heh. I remember that one, and thinking, “No… no, you can’t possibly do that using a soap bubble, that’s not even quantum and you can’t do that in classical, how would the soap molecules know where to move?”
Well. I mean, it’s quantum. But the ground state is a lump of iron, or maybe a black hole, not a low-energy soap film, so I don’t think waiting for quantum annealing will help.
I saw someone do the experiment once (school science project). Soap bubbles are pretty good at solving three- and four-element cases, as long as you make sure that all the points are actually connected.
I don’t think that three- and four-element cases have local minima, do they? That avoids (1) and a bit of gentle shaking can help speed up (2).
One example here is the Steiner tree problem, which is NP-complete and can sort of be solved using soap films. Bringsjord and Taylor claimed this implies that P = NP. Scott Aaronson did some experimentation and found that soap films 1) can get stuck at local minima and 2) might take a long time to settle into a good configuration.
Heh. I remember that one, and thinking, “No… no, you can’t possibly do that using a soap bubble, that’s not even quantum and you can’t do that in classical, how would the soap molecules know where to move?”
Well. I mean, it’s quantum. But the ground state is a lump of iron, or maybe a black hole, not a low-energy soap film, so I don’t think waiting for quantum annealing will help.
waves soap-covered wire so it settles into low-energy minimum
dies as it turns into iron
I also seem to recall Penrose hypothesizing something about quasicrystals, though he does have an axe to grind so I’m quite sceptical.
I saw someone do the experiment once (school science project). Soap bubbles are pretty good at solving three- and four-element cases, as long as you make sure that all the points are actually connected.
I don’t think that three- and four-element cases have local minima, do they? That avoids (1) and a bit of gentle shaking can help speed up (2).