>> Unsurprisingly, the combined solver performed the best, solving the puzzle in an average of 4.77 moves. The quantum solver was next, with an average of 5.32 moves, while the classical solver came in last place with 5.88 moves on average.
This effect is pretty neat. From the paper [1], the quantum solver can only do what they call "square root SWAPs", which is like a tile swap that relies on certain superposition rules. The classical solver can only use standard tile SWAPs. The combined solver can do both. A little over half the puzzle states are solved faster by the classical solver, but certain tricky states benefit from this new "move type". So the game had this quantum-like computation option tacked on, but certain initial positions just don't benefit from it.
I don't see any sort of "applications" section in the paper. They talk about how I guess you could build the puzzle thing with "arrays of ultracold atoms in optical lattices", but that still doesn't answer the question. My takeaway is that even problems which benefit dramatically from quantum algorithms in some cases (in a future where that's cheap and widely available) should have careful algorithm design built on other heuristics.
They also allow the solvers a move that measures the superposition, and if the state collapses to the solved state then that's a finish (otherwise the puzzle resets to the initial scrambled state). So a viable quantum strategy is to just repeatedly get decent overlap with the solved state until you get lucky; you don't need to be perfect.
Something I initially did't understand is why their classical solver ever takes more than 4 moves to solve the puzzle. At most one move to ensure a green square is in the top row, and then at most two moves to move the other green square into the other top row slot, and then a move to certify the solution. The issue is that the puzzle can start in superposed states, where the classical solver can only permute which states have which amplitudes and so always only has a chance of verification succeeding and relatively few variations on this. Whereas the quantum solver can use interference effects to make a big amplitude that it can then move to the solved state.
I was sort of hoping that they would show, for example, that superposed moves could transition from some classical unsolved states to the solved state in fewer steps deterministically. Some sort of known-source-known-destination variation on Grover's algorithm. But nothing like that unfortunately. An obvious obstacle to this is that the square-root-of-swaps don't commute with each other in a simple way, so almost all sequences of them don't correspond to a classical permutation; you basically have to undo what you did to get back to the classical manifold.