>> 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.
In the paper [1] they do discuss generalizing to larger boards. Puzzle's like the 2D slide puzzle or 3D Rubick's cube are modeled by different permutation groups. So, their techniques will work for the Rubick's cube as well.
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.
That's quantum computing news for you. A whole lot of hype for a nothing burger. Another thinly veiled advertisement for a technology nowhere near maturity, whose only quality is being utterly incomprehensible to the investors sinking money into it.
Your critique of quantum computing news generally is accurate (and GP's critique of the misleading headline is accurate). However, this article is actually not about quantum computing at all, nor does it claim to be, nor is it explicitly or implicitly an advertisement for any quantum computing technology, so your critique as applied here is an unfair one.
>> 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
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.
Reading the article, they did not.
They did... something to handle a 2x2 grid that can have 2 colors.
In the paper [1] they do discuss generalizing to larger boards. Puzzle's like the 2D slide puzzle or 3D Rubick's cube are modeled by different permutation groups. So, their techniques will work for the Rubick's cube as well.
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
That's quantum computing news for you. A whole lot of hype for a nothing burger. Another thinly veiled advertisement for a technology nowhere near maturity, whose only quality is being utterly incomprehensible to the investors sinking money into it.
Your critique of quantum computing news generally is accurate (and GP's critique of the misleading headline is accurate). However, this article is actually not about quantum computing at all, nor does it claim to be, nor is it explicitly or implicitly an advertisement for any quantum computing technology, so your critique as applied here is an unfair one.