Physicists Designed a Quantum Rubik's Cube and Found the Best Way to Solve It

>> 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.

[1] https://arxiv.org/pdf/2410.22287

Reading the article, they did not.

They did... something to handle a 2x2 grid that can have 2 colors.