Recent Progress in Coherent Ising Machines

professor yamamoto from ntt research was kind enough to actually come to trieste and he will give a talk on recent progress in

coherentizing machines okay professor yamamoto please recording in progress morning again do you hear me okay

uh so let me first thank the organizers for inviting me to this very important meeting and

today i am going to talk about recent topics and progress in coherent rising machines do you hear well

also is there a switch that maybe you have see if it's should be on the top no it's not muted okay so try again

oh yes can you hear me not really well maybe maybe maybe now is better i can speak loud okay great

okay ah all right uh here is the outline of my talk today or i will start the state of the art

coherentizing machines and then i will describe the principles of two types of coherentizing machines are

optical delay line based and the measurement feedback-based cims then i will describe some benchmark results against

quantum computing and quantum inspired algorithm on digital platform i will also talk about their energy to solution

in all optical cim uh then i switch the gear a little bit and talk about the fair sampling property

of this device for all degenerate ground states and low energy excited states and if i have a time

i will briefly describe the new machine called coherent satmacing using chaotic nonlinear dynamics then i will conclude

here the research on cim has started around 2010 so the first proposal

are is actually to use injection locked lasers or both einstein condensate to represent spins in this

case kuraskaro xy spin model is implemented then a few years later our use of degenerate optical parametric

oscillator has been proposed in this case a classical ising spin is implemented on this device

as for the hardware development they have 2016 100 spins all to all connected

with 10 000 are weights uh this machine was demonstrated at stanford at the same year

ntt demonstrated the slightly larger machine with two thousand spins or two all connected with four million weights

as for the prototype last year ntt announced the hundred thousand spins again all to all connected with 10 billion weights

and if cim differential equation ode is implemented as a heuristic program

either on fpga or gpu we can construct a machine on cyber space and this cyber cim with 100 spins with sparse connection was

also demonstrated at ntt there are two opio coupling schemes are employed for those machines the first type is

optical delay line-based coherentizing machine and first of all the single suitable ring cavity can support any identical and

defectively opio pulses pumped by the moderate laser power strain in degenerate optical parametric oscillator

and the part of those opo pulses is extracted by the output coupler and the use of optical delay lines with our eom modulators

we can introduce dynamically using time division multiplexing technique or to all coupling this scheme has an

advantage of high speed and low energy operation but their external optical circuit are necessarily very complex

the second type is called measurement feedback based coherentizing machine and in this case external optical direct circuit is

replaced by optical homodyne detector analog to digital converter fpga and digital to analog converter again and

then drive the eom modulator this second scheme has advantage of all to all amplitude control coupling

can be easily implemented by a single measurement feedback circuit but of course the speed and energy cost of such an approach is limited by the

digital platform here it's our incomplete list of cim research groups at present time

as for the hardware research a variety of different physical systems such as optical parametric oscillator second harmonic generator

atomic cavity qed various laser systems and superconducting circuit under the investigation are

the theory of cim has been developed from the perspective of quantum optics condensed metaphysics and neuroscience

there are also various algorithms sort of development based on chaotic such are [Music] continuous time dynamical system

ode mixed integer linear programming and neural inspired algorithm and finally in application areas are several groups

have been working on machine learning compressed sensing drug discovery and communication network areas

so let me start with our operational principles of optical delay line based coherentizing machine the

left top panel shows the degree of entanglement the minus tilde smaller than one represent the existence of internal

entanglement among opio pulses in this particular configuration and as you can see that the unnecessary and sufficient condition

for inseparability is satisfied in the entire complete but maximum entanglement is formed after

opio oscillation threshold the second step of this device is quantum correlation induced corrective symmetry breaking at

threshold each opo has a simple harmonic potential for which the electric field amplitude zero is a stable point but at

the threshold this harmonic potential is deformed to bistable zero phase pi phasor potential and the symmetry is broken

instead of random break breaking of symmetry at ops ratio the device actually collectively breaks the symmetry

for instance if op01 breaks a symmetry to zero phase or po2 actually breaks a symmetry to downspin and so on

because of the existence of quantum entanglement right bottom panel shows the success probability for n equal 16

antiferromagnetically uh coupled eisenstein model and for this case the success probability of random guess is about 10 to the minus 5

and then immediately after a few round trips of opio pulses success probability is increased by two orders of magnitude and

this enhancement of the success probability originate from the formation of internal entanglement then at the threshold region

collective symmetry breaking sets in and one of the two degenerate ground state is selected and its amplitude is exponentially increased

and the unselected ground state amplitude is exponentially suppressed and

this exponential amplification and the amplification is actually the last step of our crm search process

this sort of physics is somehow related to the so-called concept iron selection which appears in physics of quantum to classical transition

are it is a typical sort of physics are often observed in open dissipative quantum system and

as shown in the uh left bottom figure the opio network system is disputably

coupled to a vacuum state reservoirs and during this disputed coupling internal quantum correlation or entanglement formed among opio policies

at the same time external quantum correlation between system and the reservoir is actually formed and the right bottom panel

shows the quantum uncertainty relation for the for each opo pulse it starts from vacuum state at the beginning of the computation

and then are at opio threshold maximum entanglement is formed uh between opio policies then

are at above threshold those entanglement decreases and eventually the computation

finishes with quasi-coherent state and this suitable dynamical sort of change of internal quantum state

is so-called vacuum induced ion selection namely the here when system wants to sort of transit to

a classical system it actually must eliminate any quantum correlation between system and reservoir and in this way

such a classical system can broadcast its internal state without any disturbance and this is a definition of classicality or

objective reality and this type of cim actually indeed are features this kind of ein selection

the next machine the measurement feedback cim operational principle is much more subtle are as shown on the left panel

the incident squeeze the vacuum state into the external beam splitter

uh create internal external quantum correlation and that induces sort of a measurement induced state reduction

for the measured state xj and this sort of our positive amplitude measurement result may occur

a displacement for the target opo pulse x i are and in this way the two opo pulses x

i and x j are positively correlated in this are fellow magnetic coupling case and so in the end in this type of a second type of our

cim actually convert each time internal external quantum correlation into uh internal classical correlation

are and the right top panel shows the success probability as a function of saturation parameter g

squared and this saturation parameter is a key parameter for cim it actually decides the classicality and the quantumness

of the operation and with increasing g squared toward one quantum correlation increases and the machine becomes more quantum mechanical as you can see that

the exact density operator master equation model is well described by two types of gaussian quantum model are

based on this quantum measurement theory but not by the classical measurement theory neglecting the state reduction induced by homodyne measurement

our the next concept chaotic amplitude control is most advanced heuristic

are attached to a measurement feedback cim the whole point of this new uh heuristic is that

the normally ising coupling term is linearly sort of implemented into the machine which is called linear feedback or

via non-linear filter such as tangent hyperbolic function this is called non-linear feedback both linear feedback non-linear feedback system is gradient

decent and often trapped by local minima and can never reach the true ground state the new our operational mode quality amplitude

control introduces the error signal e of i and this error signal is exponentially increased or

exponentially decreased depending on the as our present time intensity is lower or higher than the target amplitude

and this sort over are our dynamical or exponentially varying error signal

introduces a correlated sort of noise injected noise external noise is in correlated internal state

and also introduces asymmetric coupling and this asymmetric coupling introduces a new sort of physics into

the machine which is celtic such as you can see on the top panel the here x i and x j are program

variables and its space and the e of i the vertical axis is a new sort of a dimension introduced by the

era signal whenever the machine approaches a local minimum or global minimum a stable point

the machine internally generates error signal e of i and make this sort of a stable point unstable and therefore the machine can escape

so so in this way uh you can see that the right bottom panel the trajectory of amplitude control cim

the uh internal opo powers are constantly flip its face uh forever even though it is actually identified

global minimum uh this stable point is destabilized by the our amplitude control feedback so that it permanently

explodes the new state and this is in sharp contrast to simple gradient descent so uh let me show you a few

benchmark results uh here are the first one is coherentizing machine versus quantum computing and we actually picked up a

sharing tone patrick all to all coupling spin glass model our left panel shows the time to solution the ground state versus program size

square root of problem size and the two suitable quantum computing model

are assumes ideal hardware namely node coherence no gate error therefore there is no quantum error correction needed

and also all to all qubit coupling are somehow realized and even such ideal quantum computing hardware

grover such and discrete adiabatic compute computing such actually features exponential scaling while

amplitude control cim the time to solution actually scales as a square root of problem size and this sort of scaling difference is

traced back to our linear amplification in unitary system versus exponential

amplitude amplification in dissipative system namely if you look at the right top figure in the case of global such we prepare

the linear superposition of all candidate states and one step of growth iteration

increase the amplitude of the ground state by 1 over square root of 2 to m therefore in order to

actually realize 100 percent success probability or amplitude probability of ground state equal 1 we have to repeat square root of

2 to n times for this global iteration and that leads to exponential scaling of quantum computing approach

right bottom panel we show that the amplitude of the ground state are is exponentially increased at their

opio threshold corrective symmetry breaking point and this comes from open dissipative nature of this particular device second benchmark result

are actually described the performance of cyber cim on cpu versus state-of-the-art digital

heuristic in this case a breakout local research one of the best heuristic which constantly features

our best associate solution for max cut our three panels for program size n equal 100 200

500 spins actually demonstrate the general trend our cyber cim is less performant than bls

when the given program instances are easy but if the program instance are hard then the cyber cim is more performant

namely with appropriate computation time it can always report and return the correct optimum solutions

while bls does not our last benchmark result is cyber cim are

implemented on gpu versus a discrete simulated bifurcation machine this discrete simulated bifurcation machine is

very similar to cim open dissipative system digital platform even though it was originally invented as a superconducting unitary device but

now it is a digital heuristic and the left bottom panel compares cim and discrete simulated bifurcation

machine and the trend is actually similar to the previous slide when the given program instances are easy a discrete simulated bifurcation machine

is faster but when the program instance is really really hard then cim is actually better to find the solution

light panel shows our time to solution for sparse graph a so-called g-set problem from program size 800

to 2000.

and as you can see in the histogram of the right most two panels they are discrete

simulated bifurcation machine actually shows the slowest speed and the celtic feedback control which is similar

to what previously described the celtic amplitude control is actually fastest among the soluble problems and the three machines

are tested here cannot a few actually are are gsat programs which is shown by black suit of a histogram

are this is actually they are all optical implementation of quality complicated control as i said the

quality amplitude control actually normally implemented in digital platform consisting of adc fpga dse but

if we can construct such optical non-linear optical circuit then we can actually implement this

algorithm or optically under our red solid soto bar our device

uh or the thin film resume annihilate uh degenerate optical parametric amplifier device and accept a few suitable passive elements

sort of active device are constructed by a different opa device and if we employ those approach as shown on the

right bottom panel are energy to solution or two approach one is cyber cim on gpu the other is all optically implemented crm

the energy two solution is different three orders of magnitude so if we multiply time to solution uh to this result a probably all optical sort of

approach enjoys five to six orders of magnitude lower a sort of delta e delta t product compared to cyber cim let me

change the subject a little bit uh now i would like to talk about fair sampling are of

degenerate ground states and low energy excited states normally icing machine is designed to find any one of the ground states

one optimum solutions are good enough but some other applications such as boltzmann sampling for machine learning or structure-based virtual

screening for drug discovery or decomposition of large optimization programs into our sub-programs to be solved separately

we need actually to get the reasonable number of optimum and sub optimum solutions and as shown on the left bottom panel

adiabatic quantum computation is poorly suited for such application because the final state is connected to

the initial ground state are in this adiabatic transition so that one particular ground state has exponential bias over other degenerate

ground states or of course are excited low energy states on the other hand coherentizing machine they are

our oscillation property are as a function of external pumping into opa opo

is shown on the right panel and the first bifurcation happens at maximum eigenstate of jij matrix this is not a ground state and

the ground state actually appears are [Music] very later pump rate but all those sort of

ground state and low energy excited state have more or less similar a suitable threshold populate gains ratio so that the stochastic

nature of the such process of cim can actually sample those good solutions with a

fairly equal probability and the next slide actually confirms this theoretical prediction

as you can see from the here left bottom panel uh here is our soto bar if we perform the

[Music] single run computation of cim uh 1000 times uh for particular

program instance for which our eight degenerate ground states and the six degenerate fast excited state and four degenerate

second excited state exist and lower panel shows a histogram are how many times out of one thousand trials

the single run actually one thousand run actually report those state and as you can see that the lowest uh

probability to report particular state is larger than 10 percent which means that at most if we can run 10 times

cim we can exhaust all of those ground state and fast excited state and the second excited states single iran

can deport many sort of desired states because as i have described already whenever machine approaches are local minimum

or global minimum it generate internal error signal and destabilize that state and migrate to the next one so light panel

shows some surprising result normally the quantum device improves its performance when the system

is more closed in the case of a cavity device high q cavity is always preferred compared to low q cavity but if i plot

the sampling time are as a function of cavity q value or cavity decay time per round trip

you can see that the time to sample decreases monotonically which are uh decreasing the

cavity decay time and if cavity decay time is one lower panel which means that the

field decays one over e even after one round trip it's extremely extremely low key cavity device but the performance is

still improved and the optimum point sweet spot is actually tdk is 0.2 this is a ridiculously low q cavity

divisor and that is actually demonstrate the power of external dissipation for some time of computational task so let me

finish my presentation this morning by introducing a new machine which solves our satisfiability problem or max sub

problem with continuous variable as you know the k sub problem for instance k equal three three sub

problem that each clause has three program variables uh x one or x five bar something like that and this given problem is defined by coefficient

c i j if c i j is 1 it means that a problem variable x i is included j

screws and if it is minus 1 which means that x i bar is included in the j scrolls and if c i j equals 0 then

both x i and x i bar are not included so once we introduce c i j matrix then we actually sort of define completely the given

three sort problems then the js closed state is represented by capital kj which is a product of one

minus ckj xk over 2 and this is 0 if j cross is already closed and 1 if j scrolls is not satisfied okay and

we thought about redux the program variable continuous variables from discrete to continuous namely introduce soft spins then the sat

program and the max sat problem is respectively defined by our summation kj equals zero or minimize kg

and the next slide shows uh how to suitable define this machine the first equation differential equation

described here each opo amplitude x i last term is an important amplitude error correction feedback term which is actually

our are determined by they are light suitable

figure uh if x i is included in close j1 j2 and j3 are the two other variables except x i is

coupled to x i through these are feedback term f i uh to sort over are satisfy each clause

the error function e of i is as i said already are targeted to stabilize to target

intensity otherwise it is exponentially increasing or exponentially decreasing as shown on the right lower panel are

and the left lower panel shows a problem uh variable amplitude and you can as you can see that they are mostly clamped at either plus one or minus one are

true or false are and then features chaotical nonlinear dynamics and then a benchmark result

summarized in this slide the first are [Music] the two top panels actually

are compared the two strategies the first first strategy is three-set program is mapped to ising model and then ising mass

program is mod solved by the occultic amplitude controlled and as you can see that those sort of

reset to ising mapping strategy is four to five orders of magnitude slower than the than the direct use of sat

cfc machine by the way two figures the horizontal axis is a number of crows normalized by number of

program variables so called alpha parameter and their program size capital m lower two panels shows the

state-of-the-art sat server based on continuous variables ctds and as you can see on the

left lower panel ctds cannot actually find the satisfying solution for alpha equal 4.26

this is a phase transition point and the most difficult uh point for any solver encounters are

only sat cfc can find satisfying solution for this phase transition point and then are at even at this phase transition point the

here cfc features polynomial scaling if the program size is smaller than 1000

if larger we don't know the answer so let me conclude my talk uh the present day i think a physical computing

research is somehow combination of four or more computational concepts they are either

analog computing optical computing quantum computing neuromorphic computing they are definitely not the mainstream of computing technology mainstream is of

course based on cmos hardware and application specific heuristic are in the mainstream digital computing uh nice thing about this technology is

hardware development and algorithm development are completely independent so each expat group actually

worked on that but the physical computing it's early stage still so our hardware algorithm co-design

is indispensable and are also those sort of a different concept of nobel computing scheme

can be nicely combined towards the future thank you [Applause]

professor yamamoto for the beautiful talk with impressive results so we have time for a few questions from the

audience and then maybe from the from the online participants as well thank you for the very nice talk i had some questions about the benchmarking

results i think it was slide 11 or 12.

this is yes yes 11 uh actually i guess it applies to both but the plot on the left so are these actual um

runs on on on a cim uh or or is it this is all numerical yes

this is our the cimcac case is implemented on gpu and the global such and discrete adiabatic

computing is a probably cpu i don't know here one qubit can actually answer what digital platform gpu

cpu yes okay because the um sharkhand kirkpatrick is is np hard so it would seem like you have a polynomial solution for an np-hard

problem uh with the uh the cim oh the are you asking why cim features a square root

exponential for such np hard problem right we believe this is a finite problem size effect as you can see problem size is really

small less than one thousand and that's why these are other questions yes just a couple of slides back i think

on your results for an anti-ferromagnetic chain uh yes this one i'm wondering about the the blue versus the green data uh did did you put a bias on one of the spins

or did you post select there is no bias uh this is uh our the purely eyesighting hamiltonian with nodes are

n equal to 16 antiferromagnetic spindling are but we post selected okay we are one up down up down one of the two ground state

uh when it is reported as a final state then we select it and if the other one is selected then we discard it that's why

other questions questions from the audience maybe the audience online also thank you for the nice talk um so i was

just wondering where do you see the first application area for this particular compute technologies there are specific you know time scales or you

know variable number that would be well matched i think compressed sensing are drug discovery and communication network

they are present cim uh cyber cim particularly on gpu is actually i think

ready for practical use but again i think we are not really expert on the application area so the real market exists or not i don't

know here but technically cyber cim is ready i think but the physical cim in particular or

optical cim is actually only sort of idea exists and hardware development actually takes

obviously more than 10 years okay i think it's time to move to the next speaker so let's thank professor yamamoto again