Once I finish the write-up I'm planning on posting it on HN :)
1. NP-complete problems are (today) global search problems (3-SAT algos search for a satisfying assignment...);
2. Combinatorial search spaces are not only non-convex, they don't have gradients (sub-gradients don't count) and even if they did, without convexity, it's still hopeless.
Thus, you cannot (today) appreciably parallelize NP-complete algos, you can only draw more lottery tickets (for where to seed your search), i.e., constant factor improvement.
I'm just putting this out there in case someone gets tantalized by the "fancy math/physics/fpga thing solves NP-complete problems" hook. Yes it can but no better than your computer (despite what paper authors claim in order to get published). To wit: if this were a compelling solution to NP-complete problems it would either a) already be a proof that NP=P or b) be implemented in absolutely every single SAT solver (using GPU or whatever rather than FPGA). In contrast, every single SAT solver uses CDCL which is ~roughly DFS with clever backtracking.
And I say this as someone that has investigated solving ILPs on FPGA - i.e., I wish it were true but it ain't.
Also, these sorts of Ising architectures get their speed-up are based on oscillator interaction, not parallelism. It's relevant to this article because it leverages oscillators on FPGAs in a nifty way :)
Then you shouldn't have led with that? It's like academic clickbait to say "here's this thing I'm working on, it uses XYZ technique to solve REALLY HARD PROBLEM" but omit the "...very poorly" part. Like I said I don't entirely blame you, I blame the academics that have an entire cottage industry and culture around these kinds of "results".
> These sorts of Ising architectures get their speed-up are based on oscillator interaction, not parallelism.
Not sure what you're trying to say - it's quantum annealing "brought to life" using simple 2-state (up/down) particles/phonos/whatever you want to call them. The quantum in quantum annealing means superposition ie parallelism; your implementation is basically a D-Wave machine without the qubits.
And yeah, I think the fact that you can build a classical, analog, D-Wave-sans-qubits machine on an FPGA is cool!
They presented their v1 chip architecture at ISSCC in 2015 much to the consternation of a few quantum computing people who (rightly) objected to the characterization of it as an "Ising" chip, because it cannot represent superposition.
It's a pretty cool sort of system that should be able to solve pseudo-energy-minimization problems, but they are only theoretically sound when energy minimization corresponds to minimizing a Lyapunov function. Sadly, it's not clear that there is a way to generically construct a Lyapunov function with a minimum that corresponds to an NP-complete problem. The Fujitsu device supposedly is good at "easy" versions of problems, but so is a SAT solver.
I personally think it's super cool that we can replicate analog coupling dynamics using asynchronous digital logic!
That's why I posted it here: it's a fun use-case for asynchronous stuff you can do on FPGAs.
In all seriousness, I'm hoping that "Lyapunov computing" will get some more theoretical attention, because it is very easy to simulate extremely complicated dynamic systems (not constraining yourself to linked oscillator systems), but quantum computing has sort of sucked the air out of the "alternative computing technologies" ecosystem. In any case, the circuits have far outpaced the development of theory in this area.
https://www.dcs.gla.ac.uk/~wpc/reports/HwRelaxParadigm-submi...