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

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