5 ms·
A scalable photonic computer solving the subset sum problem
- Gatsky 7y agoI have to say, this stuff is really cool. Maybe one day we’ll get good enough at shifting atoms around so that custom computing substrates can be built much faster and cheaper.
- grej 7y agoVery cool. The problem reminds me of Kadanes algorithm, a dynamic programming approach to solve the maximum sum subset problem in linear time.
- shireboy 7y agoI actually have this problem in a work project: matching 1-n point of sale transactions, credit card payments etc to 1-n bank transactions for large companies. Ie “these three credit card payments totaling 300 match this bank transfer for 290 2 days later.” Can confirm it’s difficult and would love any creative solutions.
- pipnasti 7y agoThat sounds like an interesting problem. Would love to know more of the contraints.
- shireboy 7y agoIt's for reconciling customers' items such as point of sale, payroll, and other systems with bank transactions. Each client item has date, description, and amount. Each transaction similarly has date, description and amount. The goal is to match all items with corresponding bank transactions. However, it is more complicated because: * bank dates and item dates may not be the same. A sale may take a few days to clear the bank. * amounts may not be the same. A credit card sale may be for 100, but when it clears the bank, the CC provider has deducted fees, so it's 98. * quantities may not be the same. Ten sales may be deposited as one deposit. In some cases, multiple items may match to multiple transactions. * there are rules about which matches are best. A sale may match ten transactions, but it can be important to match the right one, typically the closest date. As others have suggested, I can take shortcuts by ignoring some sets. But it is tricky and slow, especially for large sets.
- ampdepolymerase 7y agoThe secret solution is called Z3.
- ganzuul 7y agoThis? https://github.com/z3prover/z3 https://github.com/z3prover/z3 What is secret about it?
- anderskaseorg 7y agoYou're looking for a mixed integer programming solver. Although the problem is NP-hard, in practice, state of the art MIP solvers run much faster than brute force search in most non-pathological cases.
- ampdepolymerase 7y agoAre SMT solvers insufficient?
- Hercuros 7y agoMixed integer programming is a more specialized task than SMT solving, therefore an MIP implementation is likely to be more optimized for the task, even if you might be able to use an SMT solver to solve the same problem. Moreover, SMT solvers are focused on finding some solution to some constraints, whereas MIP solvers are focused on finding the best solution to the constraints according to some linear objective. Finally, an SMT solver is basically a SAT solver combined with a theory solver for reasoning about integers, etc. If the problem can be expressed just as a conjunction of constraints (i.e, it has no interesting propositional structure), then you don’t really need the SAT solver part and can just use a specialized theory solver (optimizer, in this case) directly.
- tgflynn 7y agoLike the comment above yours says there are algorithms for SSP that are polynomial in the target value of the sum. For values on the order of something someone would buy with a credit card I think they should be practical. See: https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-poly... The problem only becomes really difficult when the numbers are so large that it takes a large number of bits to represent them.
- peter_d_sherman 7y agoExcerpt: Photonic chip fabrication "Waveguide networks in three-dimensional architecture were written by the femtosecond laser with a repetition rate of 1 MHz, a central wavelength of 513 nm, a pulse duration of 290 fs, and a pulse energy of 190 nJ. Before radiating into the borosilicate substrate at a depth of 170 μm, the laser beam was shaped by a cylindrical lens and then focused by a 100× objective with a numerical aperture of 0.7. During the fabrication, the translational stage moved in x, y, and z directions according to the user-defined program at a constant speed of 15 mm/s. The careful measurements and characterization on the geometric parameter dependence of the three types of junction, such as coupling length, coupling distance, decoupling distance, and curvature, were taken to optimize the performance to form the standard elements."
- anderskaseorg 7y agoThe problem with using a classical computer to solve an NP-hard problem is that as the problem size increases, in the worst case, as far as we know, the running time increases exponentially. The problem with using a photonic computer to solve an NP-hard problem is that as the problem size increases, the amount of light at the output node drops exponentially. Even under the assumption that you can get rid of all background noise, that means you need to run your detector for longer so as to be able to detect the output photons, and…the running time increases exponentially. Perhaps there are interesting quantum effects that could be exploited, but the authors specifically note that they aren’t doing that. So this is a neat engineering project but an almost certainly irrelevant computational project.
- scythe 7y agoFigure 3 does indeed show an exponential time complexity, but the base exponent is much smaller than for a classical computer. That is an asymptotic improvement at least.
- anderskaseorg 7y agoThat figure is extrapolated based on the longest photon path length through the device. It isn't based on real experimental results (the device was demonstrated with n = 4), and it does not take into account the exponential quantity of photons you'd need to pump through the device before getting a measurable result. Fundamentally, there's nothing this device is doing that a classical computer couldn't, so there's no reason the exponential base should be any different under physically realizable conditions.
- yagyu 7y agoAgreed. Moreover, the physical size of the device will grow exponentially with problem size, so manufacturing will be impractical. The device is small only for simple instances of the SSP. But for those instances you could simulate the device in a few lines of code on a classical computer :) In fact, this device is based on earlier work on a biological computer [1] which suffers from the same drawbacks [2]. [1] https://www.pnas.org/content/113/10/2591.short https://www.pnas.org/content/113/10/2591.short (discussed https://news.ycombinator.com/item?id=11186640 https://news.ycombinator.com/item?id=11186640 ) [2] https://www.pnas.org/content/113/23/E3187 https://www.pnas.org/content/113/23/E3187 EDIT: it is _really_ neat engineering though. EDIT2: Old HN link & grammar
- deepnotderp 7y agoThis is basically the same problem as the DNA computing thing and the memcomputing thing- it's kicking the exponential problem down the road.
- praptak 7y agoSubset sum is only weakly NP-hard. It has a polynomial solution not in the size of the input but rather in the value of the numbers (dynamic programming). Since numbers are encoded logarithmically, this algorithm is exponential in the size of the input. So, solving subset sum is only impressive if you can solve it for very large numbers.