Ising Machines: Non-Von Neumann Computing with Nonlinear Optics – Alireza Marandi – 6/7/2019

July 14, 2019

presented by Caltech thanks for the invitation it's really great to be back here at Cal Tech only get out here every couple of years now even there was such a short plane ride from Stanford and of course it's really wonderful that this program and this fund has been set up and said I would just share a few comments about my background and how I came to end up in Carver's lab and what I thought was the there's so many things that that I learned from him and but I'm trying to focus on the oh wow this is like my favorite cough drop so I'll try and focus on the the most just just one we don't have a lot of time but so let me just say put things in perspective I Hadi III my first neuromorphic chip paper was published in 1989 in May of 1989 which was 30 years ago from last month and I mentioned this to a EE Times reporter and he put out a story we had an interview and we he talked about you know you know how the field was and the evolutionary way where I think things are going now and and that it's a really exciting time that we are in right now and but the title I say they added I picked the title for the article that AI veteran pushes for neuromorphic chip so I guess I'm officially a veteran but anyway he of course asked me what you know to make some comments about cover and what did I learn from cover and so forth and to put that into perspective I'll back up a little bit so I was an undergrad at Hopkins and 8687 when I took a VLSI design class a lot of you would know about this with this was using techniques that Carver pioneered and made it possible for actually students and universities and people who didn't actually own these fobs to be able to do that and he went around traveling around the country evangelizing running workshops as well and so forth so I benefited from that and this was the met a second half of the 80s when you're all networks where we're hot and everybody was getting into it and so my first chip that I built was based on one of these abstract my monocle models of neural networks and and the reason why I was interested in that was when I got my first computer as a teenager I was like night you know so and my father was in sabbatical and he brought one of these BBC micro computers home and I always had a little lab or tree I used to think of it that way well I was taking things apart and building things and so on and so forth and you know it was each one of those experiments to me was a new adventure right but my parents called it con caca you know the noise that you make with a hammer taking things apart so he's doing concoction and I was thinking I'm having new adventures here so I love that name of the of the program because that's how it felt and but I was too intimidated to take the computer apart so I went in the library and I stayed the everything I could about computers you know PC memory Lu logic inin and so on and so forth all the way down to the zeros of ones boolean logic and building all the way up to be able to do these operations and so forth and I thought that was a tremendous amount of work this poor little computer had to do cover described it as he basically flogged the house really hard and get him to really gallop really really fast and if you can get do that eventually you'll get some results yeah and so I I looked at it and I was like I I think there has to be a better way to do this there has to be a more elegant way to do this and but you know I had no idea I didn't know anything about the brain I hated biology so I get to Hopkins and this kind of millio of this wave of neural networks hype and so forth and and I saw wow okay this is actually a much better way this is much more elegant right and but I wasn't I still had some doubts about myself because I talked to these guys you know I came from Ghana I took these Americans and they all about computers everybody loves computers they'll have to program all the stuff so when I you know med cover the most important thing that he told me was you should trust your gut okay like basically these doubts that I had just like just go with your gut and that actually made me more of Who I am right I basically yeah so that was a real gift like to send me on a path where I really persisted and trusted that and he encouraged me to do that and so I wore this bright shirt here you know no cover because that was one of the things that stood out about him you know in Africa we wear these bright shirts and I come to America and everybody is like white and like like pastel colors and Kaba shows up and is this design on a and it was just like wow okay who's this guy you know and so that made me feel really at home my father was a professor my father was a professor he made a point in showing up in every lecture with a nice bright dynamic shirt because you know yeah so that was an instant point of identification so so that's the background by just to close the loop and so now we are in 2019 and neuromorphic chips are all the rage there's all these hardware AI companies everybody's making chips now for about 10 years where we thought it wasn't going to happen and you know so he was right and so I think people have been emphasized is that cover is really a visionary okay he's done this several times where he's looked into his crystal ball and being able to tell us what's gonna happen in 20 years and 30 years and so on and so forth so yeah that's how he trusts his how much he trusts his God okay so with that let's do a few introductions to the speakers that are coming up but I want to make one comment about the talks before which were really fascinating and you know it really kind of gives me this same feeling I had when I was here as a graduate student this special thing about Caltech whereas just everybody who's just doing such incredible things and they are so humble and they explain it so simply and it's like yeah of course okay so so so anyway but the most interesting one was the talk by the philosopher and if I had if he had spent any time around I usually yeah I would have liked the same question that came from that side of the audience but I have spent some time around philosophers and I realized that you know what philosophers do really belongs in science because they actually are trained as to how do you frame a question that's answerable okay so they don't come up with the answers but they come up with the questions that are answerable and that's what you have to do in science and that's why I originally it was called natural philosophy okay so yeah so thanks for being here with the philosophy aspect of it okay so we'll press ahead the next talk and I know a little bit about both of these talks so I'm really looking forward to this these talks they're in my area so the next one by Ali Reiser mirandy I just gave you a little bit of his background it turns out that he got his PhD from Stanford let me try and get the year correctly in 2013 and so yeah nice to see some stuff with folks here and his background he's an assistant professor ala reason miranda is a full name he's an assistant professor in Electrical Engineering and Applied Physics and he is basically looking at photonic computing and this is another area of course we at the end of Moore's Law as cover predicted and we have to figure out where we go from here so these are one of the new exciting adventures that we're going on and so with that I'll let our Reiser take the air [Applause] good afternoon everyone so before I start the talk I should thank the organizers Adam and oz it's over putting together the symposium and also the opportunity to speak here it's really a glad great pleasure to be here and talk in front of this audience and of course it's great to be here in front of Carver and all the inspiration for many generations of scientists and engineers so today I'm going to talk about Ising machines which is basically a hardware platform as an optical computer and I'm going to talk about this platform which is not the standard digital computer as we know it it's targeting very specific types of problems so before I dive into details I should mention that some of the results that I'm going to show is a result of contributions of many people from my previous life at the University of North with a wonderful group of students and postdocs and also professors and collaborators from all over the world most importantly Peter McMahon and Ryan hammer Li are responsible to some of the recent experimental results and also my new group here at Caltech which is now composed of three students and two postdocs some of them already here so they're giving me more stress than the other part of the audience and with collaborators from all over the place so in computer science there is this class of problems known as NP problems and one of the characteristics of these problems is that if you use a brute force algorithm on a standard computer the computation time scales exponentially or faster as the size of these problems grows and these problems are everywhere so in biology for instance protein folding is known to be an NP problem in sociology maximizing the fluence and a social network is known to be an NP problem and we have a large class of combinatorial optimization and there are two examples of them in engineering that belongs to this class of NP problems so there is a demand for thinking about a machine or a hardware platform that can maybe target these types of problems and can maybe solve them a little more efficiently than the standard computer so we pick one of these problems which is called the icing problem and the icing problem is basically based on the Ising model in physics so the model is that if you have a magnetic structure which is made of a bunch of magnetic domains and each domain is either up or down magnetic spin as you know magnetic and they're coupled to each other so they interact with each other through a magnetic field you can explain the energy of the whole system by this simple summation the icing problem is that if you have a magnetic structure and you want to figure out what would be the spin configuration for these domains that would give you the lowest energy for the whole system is actually the icing problem so if you know the J or J the interactions between these domains what is the spin configuration as the ground state so finding the ground state of the Ising Hamiltonian so this is important from the computer science perspective because it falls into this category of so-called np-hard so the term part here is important because that means that this problem is a representative of the whole class of NP meaning that you can map any NP problem to an icing problem with polynomial time overhead so that means that in principle if you have a machine that can solve the icing problem efficiently you can think of having a machine that can solve almost all sorts of NP problems efficiently in principle in practice it's a little more different so the idea of icing machine is that can we make a physical system which is made of a bunch of elements and each element has this variable that can be either plus 1 or minus 1 to represent an icing spin and if we can connect these spins to each other these domains to each other arbitrarily then we can program this machine to a given icing problem but just connecting those magnetic domains to each other and you can expect that this physical system will have an energy that would represent the icing energy of the problem that you programmed on a machine which has the tendency to go to the lowest energy state so it has the tendency to operate in the ground state so that means that if you turn it on it should converge to something close to the ground state and you should be able to measure that and that's how you can have a solution to the problem that you programmed on the machine so we pick an element a building block to actually make such an icing machine which is based on degenerate optical parametric oscillator and what it is is that it's an optical resonator which has a nonlinear element in this and that's usually just a special type of crystal but what happens in this nonlinear resonator is that you start with a pump so you start with a pump frequency a laser and then you generate an output which is that half the frequency of the pump and that's important because if you go through the math you realize that whenever you turn such a system on it either goes to a zero phase or PI phase or there's a natural bifurcation that happens around the oscillation threshold meaning that you turn it on it either gives you zero phase or pi phase so you can use that to represent an icing spin so now the idea of using these opioids to make an icing machine is that now you know each of these ochio's can represent an icing spin if I can arbitrarily connect them to each other by just taking the field from one and just injecting it into another and do this for all the couplings that I want so maybe I can map the problem of finding the ground state of icing Hamiltonian – something in this physical system that the system has the tendency to solve it for him and the mapping seems to actually work really well and what happens is that the icing Hamiltonian or the problem of finding ground state maps to this problem of what would be the phase stays for each of these Oh POS that would satisfy maximum number of couplings because each of those couplings are going to put a constraint on the face and then when the Opio is turned on and they pick up either 0 pi they're either going to satisfy the couplings between them or not so the problem becomes can this Opio satisfy the maximum number of coupling constraints and the way it works is that when you turn the system on there is no photon at the output so you basically have quantum noise whatever that is so you start to building up your photons by just pumping it more and more and these opioids are going to start talking to each other to decide about how they can satisfy maximum number of coupling constraints and then they're going to freeze into one of these phase states when they go above threshold and you hope that this thing is close to the ground state of the problem you mapped on it and then you can measure that and you have an answer to that so this is the idea of making an nonlinear optical based computer which is not a standard von Neumann architecture and it's also specific about the icing problem so when we had the idea we thought about doing some numerical simulations using just the simplest possible models we could use for each of these O POS to just see that it does anything that looks like computation and it looked like it did so we went ahead to actually build a machine like that so the building block in the actual machine is actually pulse Tokio meaning that I started with pum pulses which has a carrier frequency of pump Omega pump and then a generate pulses which has a carry frequency of exactly half of this and how it looks like is that it's a long resonator so the light can go around this path and it resonance in it with a nonlinear crystal which in this case is how it looks like in real life but the key is that the round-trip time of this resonator is exactly matched the repetition period of the pump so one pulse goes one round-trip the next pulse comes exactly on top of that so it's a synchronous pumping of this resonator so we have been working on these for different applications which I'm not going to talk about but I'm gonna tell you how we actually get the important property of these ochio's which is the binary phase that we can use for for representing an icing spin so to emphasize on that I'm gonna show you a mechanical analogy in this video I'm gonna use two pendula each of those pendula are is a parametric oscillator it's a parametric oscillator and in this video I'm gonna modulate a parameter of this pendulum which is the length by pressing on this string and that modulation is going to lead to oscillations so that's how it's a nonlinear system and what you're going to see is that the frequency of pump which is my hand is twice the frequency of oscillation and the oscillation starts with small amplitude and then it gets amplified and then they start oscillating each of them is oscillating in a different phase state so you see they're 0 or PI with respect to each other so that's basically how things look like in parametric oscillators at degeneracy so in the early days we need an exact experiment but with optics so we built two resonators two of these nonlinear resonators we pumped them with the same pump and we try to see if they actually show that phase state selection the difference is that in the mechanical case the oscillation starts from some mechanical vibration that exists in the and in them in the optical case there is no photon at those wavelengths that we're talking about so it starts from so-called vacuum fluctuation and quantum noise so they pick one of these phase days and we can see that in the experiment through the interference purely based on quantum noise so it's a quantum random process so if you have an individual up here you turn it on it's just based on quantum no it's gonna pick up either 0 pi so now we want to use them and couple them to each other to actually solve in an experiment computational problem so I want to tell you what kind of problem are these problems that we're trying to solve and I'm going to give you this example of maxcut which is mostly all the problems that I'm going to show you in the actual experiments so the maxcut problem is a problem in graph theory which is if you're given a graph how can you split that into two sub graphs and you cut the maximum number of edges and it's shown that this is an np-hard problem and if you have this graph which has four nodes and all the possible edges if you split it through the middle you're cutting four edges so that's the maximum number of edges you can cut but if you split three nodes on one side and one no than the other you're only cutting through edges so that's not a Mexico so this is basically how the problem looks like so this maps to an Opio network problem by making four ochio's and just coupling them all out of phase so out of phase means that I take the light from mono peel I flip its face whatever that phase is and I inject it into the other and I do it for all these possible couplings so I know that each time I turn these o peels on they're either gonna be in 0 or PI so if two of them are in PI and two of them are in 0 I know that this coupling which is out of phase is satisfied these couplings are all satisfied so we have four satisfied couplings and that corresponds to cutting these four edges and if three of them end up in 0 1 in pi that corresponds to only satisfying these three edges so it's not the maximum number of satisfaction for these coupling constraints so it's not a Mexica so that's basically how the max cut problem one-to-one maps to this Opio Network problem and this is one of the early experiments that we did so how can we make 4 o POS coupled them all together out of phase and see if it actually computes the this instance of np-hard problem or the max cut solution so I'm just gonna skip a lot of details I'm just gonna talk about a magic technique that we use that later enabled us making really large machines and that is called time division multiplexing so remember I said the round-trip time in the resonator is one repetition period so we always have one pulse in the cavity in this case we make the round-trip time four times the repetition period so we always have four pulses in the cavity so we can think of this as four temporarily separated o POS in one resonator and then what happens is that you can actually now make them interact with each other so you can introduce those couplings between those ochio's by just introducing a slight output coupling and delayed by exactly one repetition period and injecting it back so you take the field out you wait until the next pulse comes in and then you inject it on top and you do that for all the integer factor of the repetition period when you do that you make three delay lines and you make sure all those couplings are out of phase then you have a machine that represents that maxcut problem that I talked about so now the question is can I measure the output and the output measurement is simple you can just look at the phase of the output of the o POS and the question is how many times does it find the answer and how many times it fails so this was the first experiment and we ran it a thousand times and we counted which phase states we see how many times and it looks like that all the times that it turned on it actually found one of the answers of the Mexican problem so one computer for one instance of an np-hard problem the smallest np-hard problem with 106 100 percent success rate so it was a good starting point but now the question is how can we scale up and make a larger machine so that we can actually show computation with this so the magic of time division multiplexing is that you can make the resonator long so you can put as many pulses as you want in principle in that resonator and if you make n minus 1 delay lines and you can control those delay lines sync nicely with your pump you can actually create any arbitrary icing problem on that machine you can think of using optical fiber technologies and devices that we have available and implement such a such a hardware and you can also think about using the evolving integrated photonics technologies that have the required non-linearity in them so these are the directions that we are we are taking I'm gonna just briefly talk about another idea that enabled us to make a large machine in a quick and dirty way so I mean you tell you a little bit about that idea so if you look at this network in the time division multiplexing scheme so you have a long resonator with end pulses in it and then you have a network of beam splitters and modulators so the idea measurement feedback is that can we simulate what would have happened this network of beam splitters on an FPGA and replicate what would have happened at the output of such a network and inject it back into the resonator so of course this is not equivalent to that optical interactions and that's why it's a quick and dirty way of doing this but it's so tempting because now you don't need to make all these optical systems you can test if there is any meaningful computation with such a machine so that's why we did this and this is actually how the machine looks like so it is a bunch of optics with off-the-shelf FPGA a long resonator in this case we had 160 pulses in the cavity so we could use a hundred of them and we could implement any one hundred to one hundred kind of couplings between them so we could implement a large number of icing problems on the machine and see if this type of machine is actually doing any computation so that enabled us to run several thousands of problems so that we can actually look at it now as a computer so of course I'm now going to show you a lot of the results I'm just gonna pick some and just tell you why they're interesting and promising so this is one example of the graphs that we put on the machine and we looked at how much time it takes to actually find an actual ground state of this problems that we put on as a function of graph size so 4 all the way n equals 100 and the blue curve is what you should look at now which is the actual time it takes for finding the ground state of the Mexico the Ising Hamiltonian and as you see there is no exponential speed-up so it scales exponentially and as you expect it so as you increase the size of the graph it gets slower and slower but what is interesting in this experiment is that if you relax your requirement for finding the absolute ground state and you say you're satisfied with something within 6 percent of the actual ground state then you get something like this red curve which is flat as a function of graph size so that means that it might be useful from many practical applications when you don't actually need the exact solution but you want something quickly so we're still continuing the benchmarking and trying to see if there is any way forward to actually use this as a better computer for these types of problems but I'm gonna show you another type of and other comparisons that we did and that's with the d-wave quantum annealer that is now commercially available so apart from the differences in the physical properties including the price you can actually look at the computation performance of these machines and this is for a special type of graphs that we we actually implemented on those on both machines and if you look at the results on the Ising machine again the graph size and then the time to solution you see the similar curve there's the gained exponential decay and exponential growth in the in the time to solution in the Ising machine but if you look at the d-wave machine you see that it's exponential with N squared instead of exponential N and the reason that that's the case is because in the optical implementation we have possibility of all-to-all connection so you can take any Opio and connect – any other Opio and that's one of the one of the critical things in the in the time division multiplexing an optical implementation but in the d-wave machine we are limited to this sparse connectivity of the hardware which is which is implemented in the so called chimera graph so that means that if you have a dense graph and you want to implement it on two thousand cuban machine you actually need to use multiple Hardware qubits to implement one node of the graph and that usually scales by N squared so you have the overhead in terms of how large of a graph you can actually implement and that's why we couldn't go larger than 50 even though we had 2,000 cubits and also the computational time scales as a number of exponentially by the number of actual Hardware qubits not the number of nodes in the graph that's why you see an exponential N squared as opposed to exponential L so just to plug numbers and you see that this matters even though there's nothing about the physical processes that is responsible for doing the computation but we're just assuming that everything is going to stay exponential but because of connectivity you're gonna you're going to pay a big price for for the computational time so this is one of the benefits of optics and that's why optics provides some opportunities to actually implement these types of non-linear 'men architectures so what we have done so far is that we know the idea kind of works there is computation at least so it's not just giving us noise there is something that looks like computation we know we can make large machines we can get the connectivity so I'm gonna just tell you what are we working on now and what is the what is the future look like so if you think about where we are now and if you compare it with how computers digital computers have have evolved in the past 60 to 70 years you see that we have gone from like 1800 vacuum-tube digital computers to more than seven billion transistors and in the palm of your hand so where we are now in terms of optical computing is probably very similar to what what we had with the vacuum tubes so it's a tabletop large kind of setup and it doesn't really allow you to make really large number of opioids in the setup so one of the directions that we're working on is how we can bring nanophotonics in and how we can get those types of architectures implemented on a chip so the other direction that we're working on is that how we can utilize other physical mechanisms that are available in the optical domain that we can actually hopefully use for computation so one of the things is about quantum behavior so the pendulum that I showed you which was either 0 pi phase that the question is can we bring that into the optical domain and have the Opio operate in this quantum superposition of these zero and PI phase States and you do some calculation and it looks like that in principle you can get there and if you get there you will access the regime that is already available to the superconducting qubits in terms of the quantum behaviors and if you do that then you can utilize the other opportunities that optics provides most importantly the connectivity and the scalability and then you can make really large scale computers that can probably benefit from the quantum nature or other types of physical processes in them and that path also goes through making things on the chip and an integrated platform so the other important thing is that we're of course not limited to icing the icing was a simple case because the math was one-to-one and I told you at the beginning that icing is special because it's empty hard so you can map anything else to the icing in principle that's true and that doesn't sound hard on the paper because it's only polynomial in practice polynomial means a lot so and cube even though it's not exponential it already means a lot so the question is can we have a way of mapping different types of problems onto the hardware in a more efficient way and of course can we utilize that to do more like quantum algorithms and the quantum type computation with these types of platforms so with that I stop here and I thank you for your attention [Applause] can you get the hello thank you very much sherry enjoyed it and I have a strange question you showed a chip with with a small tunnel underneath it if I felt it was a and then you showed a resin and some yet there now when you do a micro my question is this is you have there an optical bench then you have you have a chip is there a difference or as anybody ever tried that to have a ramen beam to see if you have obtained some type of resonance use a ramen effect as opposed to get the type of so so I think your question is about the type of non-linearity and you're asking about Raman non-linearity right and to see if if you see some type of connectivity between the two as your as an intake so in this case we are trying to avoid Rahman so Rahman is not the type of non-linearity that helps us do the computation so we're trying to make the other non-linearity which would give us the face bifurcation and as your pie face stronger than ramen but Raman usually exists everywhere right so all we are trying to do is to make sure that the non-linearity we care about is much stronger than vomit oh okay yeah yeah but ramen exists thank you okay okay I guess we can tank that's one oh sorry oh yeah right there okay I was looking at way sounds like it sounds like this technique would be very interesting for factory scheduling specifically I'm familiar with doing it for semiconductor factories and it's a interesting problem that's right yes I think the scheduling is one of the problems that people have mapped to np-hard problems and again that falls into the other categories of not directly being the icing problem but there is a map and if we can do the direct mapping to the hardware I think that would be a polynomial beneficial thing to do that's right so np-complete is a well depending on how you classify thing is a subclass of np-hard okay so thanks thanks Larissa again [Applause]

You Might Also Like

No Comments

Leave a Reply