Physicists Designed a Quantum Rubik's Cube and Found the Best Way to Solve It
sciencealert.com
sciencealert.com
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.
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.
They did... something to handle a 2x2 grid that can have 2 colors.
They likely wrote the paper the way they did because (1) Rubick's cube math is much more convoluted to explain, just because it is much larger, (2) Just working out the matrix representation for large groups is a pain. I know because I worked on this sort of representation theory in my PhD, and in fact, I thought of a very similar idea back then but never got around to writing a paper. Partially because nice implementations of representation theory algorithms do (or at least did) not exist.