The paper could be improved by including a strong classical non-Ising-machine solution approach as one of the methods benchmarked against.
E.g. take the same 8-core Ryzen machine they use to implement their simulated Ising Machine HbSB method & use it to run a standard classical solver as would be done industrially to tackle these kinds of problems outside of academia - perhaps an industrial grade commercial MIP solver (Gurobi) for those problem classes that are known to have reasonable MIP formulations, or a good constraint solver for Sudoku, etc.
Depending on how hard the specific test problem instances are, perhaps a commercial MIP solver would be able to solve some of these problems optimally & instantly using its black box of presolve witchcraft tricks.
I’ve been working with MIP solvers a lot at work recently, and the depth of black magic is so deep it’s hard to comprehend. Even after the presolve there are so many tradeoffs and structures to exploit it’s hard to understand the whole system
Kind of like the “uncooked spaghetti length” sorting algorithm: gravity. Hold them in your fist vertically, let them gently fall to a flat surface. Sorted.
Dropping spaghetti is an O(1) operation. Once that's done there's a straightforward O(N) sort by removing noodles in the order that they're intersected by horizontal plane descending from max_noodle_length to the table.
Assuming that the spaghetti is being held in such a way that longer pieces hit the surface first. If the pieces are being held at random points, or such that the bottoms line up rather than the tops, then this approach won't work.
You don't have to assume that. We can take each randomly oriented noodle and orient it correctly in O(1) as a preprocessing step. Since the complexity would be additive, the overall complexity remains O(N).
Ising machines are interesting, but I don't understand the point of the BAW delay line at all. It doesn't act like an array of coupled oscillators or resonators, just an old-school circulating delay-line memory, right? The kind they used to build with mercury in the days before RoHS was a thing?
If the FPGA is doing the actual matrix math based on measurements of the pulses circulating in the delay line, with no coupling interaction between those pulses, why not just store the phases and amplitudes digitally in block RAM as well?
Fun fact: CSIRAC, Australia's first digital computer, used mercury delay line memory. It is on display at Scienceworks, Spotswood, Melbourne. https://en.wikipedia.org/wiki/CSIRAC
Sudoku is really not a “really hard puzzle” unless you're you generalize it to larger puzzles—the 9x9 form (used in the paper) is trivially solvable with even an old 6502 processor.
I'd argue that the statement from the conclusion “Beyond MAX-CUT, we solve more complex tasks such as number partitioning and Sudoku, highlighting its practical utility for real-world problems” is simply a lie, akin to claiming that factoring 221 on a quantum computer proves practical utility on real-world problems. At best it's a proof of concept.
The paper could be improved by including a strong classical non-Ising-machine solution approach as one of the methods benchmarked against.
E.g. take the same 8-core Ryzen machine they use to implement their simulated Ising Machine HbSB method & use it to run a standard classical solver as would be done industrially to tackle these kinds of problems outside of academia - perhaps an industrial grade commercial MIP solver (Gurobi) for those problem classes that are known to have reasonable MIP formulations, or a good constraint solver for Sudoku, etc.
Depending on how hard the specific test problem instances are, perhaps a commercial MIP solver would be able to solve some of these problems optimally & instantly using its black box of presolve witchcraft tricks.
I’ve been working with MIP solvers a lot at work recently, and the depth of black magic is so deep it’s hard to comprehend. Even after the presolve there are so many tradeoffs and structures to exploit it’s hard to understand the whole system
The abstract reads like copy for the Turbo encabulator
The authors really must improve the abstract before publication.
Kind of like the “uncooked spaghetti length” sorting algorithm: gravity. Hold them in your fist vertically, let them gently fall to a flat surface. Sorted.
Spaghetti length is made visible (quickly comparable), but it's still not sorted.
Dropping spaghetti is an O(1) operation. Once that's done there's a straightforward O(N) sort by removing noodles in the order that they're intersected by horizontal plane descending from max_noodle_length to the table.
Assuming that the spaghetti is being held in such a way that longer pieces hit the surface first. If the pieces are being held at random points, or such that the bottoms line up rather than the tops, then this approach won't work.
You don't have to assume that. We can take each randomly oriented noodle and orient it correctly in O(1) as a preprocessing step. Since the complexity would be additive, the overall complexity remains O(N).
It is sorted chronologically
Ising machines are interesting, but I don't understand the point of the BAW delay line at all. It doesn't act like an array of coupled oscillators or resonators, just an old-school circulating delay-line memory, right? The kind they used to build with mercury in the days before RoHS was a thing?
If the FPGA is doing the actual matrix math based on measurements of the pulses circulating in the delay line, with no coupling interaction between those pulses, why not just store the phases and amplitudes digitally in block RAM as well?
Fun fact: CSIRAC, Australia's first digital computer, used mercury delay line memory. It is on display at Scienceworks, Spotswood, Melbourne. https://en.wikipedia.org/wiki/CSIRAC
[dead]
tl;dr:
A new, stable computer uses sound waves to solve really hard puzzles.
Not the game 2048. But yes, the game Sodoku.
Sudoku is really not a “really hard puzzle” unless you're you generalize it to larger puzzles—the 9x9 form (used in the paper) is trivially solvable with even an old 6502 processor.
I'd argue that the statement from the conclusion “Beyond MAX-CUT, we solve more complex tasks such as number partitioning and Sudoku, highlighting its practical utility for real-world problems” is simply a lie, akin to claiming that factoring 221 on a quantum computer proves practical utility on real-world problems. At best it's a proof of concept.
Yes, reading those in the same sentence I also thought about a spin on 2048, the game.