7 ms·
Optical solutions to NP-Complete problems
- dekhn 10y agoAmusingly, physics people were doing fourier transforms using optical techniques (lenses) well over a hundred years ago.
- dkarapetyan 10y agoThis is like sleep sort: https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort. Same principles apply. Time delays are used to achieve the result. I thought this would have used the quantum/wavelike properties of light but I was wrong.
- zitterbewegung 10y agoOptical quantum computers do exist https://en.m.wikipedia.org/wiki/Linear_optical_quantum_computing https://en.m.wikipedia.org/wiki/Linear_optical_quantum_compu...
- SilasX 10y agoI meant to reply to this but put it under a different comment by accident: https://news.ycombinator.com/item?id=12364273 https://news.ycombinator.com/item?id=12364273
- adrianratnapala 10y agoWhat do they do for the nonlinear parts? I.e. the gates. Is it all like Fourier transform where all the work is linear; or do they have to convert it to electricity and then back to light? If they do that, then do they gain anything over purely electronic solutions?
- echelon 10y agoUsing physical space and particle interactions for solving computational problems seems like such an elegant hack. Proteins fold and chemistry just works in 3D space, yet we have problem computing these things. I wonder why we don't do more computing on the physical fabric of the universe itself. It seems like an optimally efficient tool for problem solving. Are there any other approaches along this same vein? It's incredibly fascinating.
- yablak 10y agoBefore computers had the kind of processing power they do now, engineers would build analog circuits to solve differential equations. A modern-day quick link: http://www.dummies.com/education/science/science-electronics/how-to-solve-differential-equations-using-op-amps/ http://www.dummies.com/education/science/science-electronics...
- yablak 10y ago(nowadays it's usually the other way around, of course ;)
- versteegen 10y agoBefore electronic computers existed, engineers built mechanical analog devices called differential analysers [1] to compute derivatives and integrals, invented in 1876 by brothers James Thomson and Lord Kelvin. Famously, cheap differential analysers were built out of Meccano starting in 1934 [2]. After scientists gained access to electronic computers, these old analysers were repeatedly handed down through lower-budget institutions, schools and eventually museums. [1] https://en.wikipedia.org/wiki/Differential_analyser https://en.wikipedia.org/wiki/Differential_analyser [2] http://amg.nzfmm.co.nz/differential_analyser_explained.html http://amg.nzfmm.co.nz/differential_analyser_explained.html
- Sharlin 10y agoThis old US Navy training film on mechanical fire control calculators (called "computers" back then, used to calculate firing solutions on warships) is pretty fascinating: https://www.youtube.com/watch?v=s1i-dnAH9Y4 https://www.youtube.com/watch?v=s1i-dnAH9Y4
- SilasX 10y agoAs I understand it, it's exploiting how light signals move very fast and thus you can sweep through many solutions. But, as they seem to note in "weaknesses", you're effectively offloading an exponential amount of work to the light, and so haven't done anything for the big-O behavior; you're just making a (potentially) less scarce resource applicable to the problem, no different (economically) from finding cheaper ways to build computers.
- hammock 10y agoYou could say the same about fiber optics vs copper wire. Increasing bandwidth can drive revolutionary change.
- partycoder 10y agoReminds me of the infamous "sleep sort".
- dharma1 10y agoLove this. This is interesting too - optical computing for machine learning http://www.lighton.io/ http://www.lighton.io/ I think we'll see much more physical computing in the future for specific things
- benten10 10y agoFor those who may not be aware -- As always in these situations: Scott Aronson said it first! For reference, here's the highly amusing and interesting paper he's written on this: "NP-complete Problems and Physical Reality" http://www.scottaaronson.com/papers/npcomplete.pdf http://www.scottaaronson.com/papers/npcomplete.pdf Abstract: "Can NP-complete problems be solved efficiently in the physical universe? I survey proposals including soap bubbles, protein folding, quantum computing, quantum advice, quantum adiabatic algorithms, quantum-mechanical nonlinearities, hidden variables, relativistic time dilation, analog computing, Malament-Hogarth spacetimes, quantum gravity, closed timelike curves, and “anthropic computing.” The section on soap bubbles even includes some “experimental” results. While I do not believe that any of the proposals will let us solve NP-complete problems efficiently, I argue that by studying them, we can learn something not only about computation but also about physics."
- dogecoinbase 10y agoA favorite example of mine, using photons to solve Traveling Salesman in quadratic time: https://www.osapublishing.org/oe/abstract.cfm?id=140598 https://www.osapublishing.org/oe/abstract.cfm?id=140598 Spoiler: the number of photons required scales up so quickly that the phenomenon cannot be observed for sufficiently high N.