I promise I'm not trying to rain on your parade, and I blame the academics for this, but:
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.
This is a personal project aiming to replicate analog coupling dynamics with asynchronous digital circuits FPGAs, not a claim that we can solve NP complete problems with a fundamental speedup.
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 :)
> This is a personal project aiming to replicate analog coupling dynamics with asynchronous digital circuits FPGAs, not a claim that we can solve NP complete problems with a fundamental speedup.
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.
I dunno man, I think saying "this is a personal project of mine" and linking to an open source github repo implies that it's a casual side project. I never made any performance claims, it's just for fun. I'm not trying to put up clickbait.
And yeah, I think the fact that you can build a classical, analog, D-Wave-sans-qubits machine on an FPGA is cool!
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.