Mechanisms And Methods On Enhancing Convergence To Ground State Of Coherent Ising Machine

There are various combinatorial optimization problems in many areas of realworld applications and scientific research,such as finance,machine learning,logistics scheduling,circuit design and drug discovery.Finding the optimal solutions to these problems can greatly reduce costs and waste of resources.The computation time of such problems scales exponentially with the problem size,and solving them in a polynomial time is beyond the reach of conventional digital computer.Laws of physics have proved useful for solving combinatorial optimization problems.Simulated annealing and quantum adiabatic algorithm are designed according to fundamentals of statistical and quantum mechanics,respectively.Recently,the coherent Ising machine(CIM)based on time-multiplexed degenerate optical parametric oscillators(DOPOs)taking advantage of principles in quantum optics has been proposed.This system can solve large-scale combinatorial optimization problems within 10-3 s and has the advantages of room-temperature operation and all-to-all spin-spin couplings.However,the machine can be trapped by local minima which increases exponentially with problem size.This leads to a decrease in the probability of obtaining the optimal solutions.The main work of this thesis is proposing two methods to overcome this problem and increase the success probability of the CIM.The specific research work is as follows:1.Quantum adiabatic theorem is introduced into the ground-state-search process of the CIM and a scheme to achieve adiabatic evolution on the CIM is designed.The initial state is set to the ground state of an all-to-all connected and homogeneous couplings(Jij = 1)MAX-CUT problem.Then the continuous Hamiltonian is discretized,that is,the adiabatic evolution process is divided into M equal intervals.The instantaneous Hamiltonian H(t)is slowly enough changed,and the final state is the Hamiltonian of the MAX-CUT problem to be solved.It is found that the computing performance of the A-CIM is affected by the "freezing" effects in the simulation.Once the system reaches the freezing point,the amplitude of each DOPO pulse will remain unchanged for the rest of the computation,so that the system cannot finally reach the ground state of the Ising problem.A method of randomly flipping several spins at the end of each adiabatic evolution interval is proposed to solve this problem so that the system can continue to evolve to a lower energy state.2.To test the performance of the A-CIM,the MAX-CUT problems with the number of vertices N = 10 ~ 100 are first solved.The probability of obtaining the optimal solution by A-CIM is increased by up to 23.61% compared with the traditional CIM.Then the sparsely connected G-set instances and fully connected complete graphs with the number of vertices ranging from 800 to 2000 are solved.The optimal cut value and average cut value obtained by A-CIM in 100 trials are both higher than those of traditional CIM.The simulation results show that the performance advantages of A-CIM can be extended to large-scale problems,and the required computation time is independent of the problem size.3.Taking a N = 8 MAX-CUT problem as an example,the bifurcation structure of the DOPO network with common pump rates is analyzed.For p < 0.909,only local minima occurs.For 0.909 < p <1,local minima and optimal solutions coexist.Then the bifurcation structure of the DOPO network when one of the pump rates is varied and others remain constant is analyzed.There are parameter sets pj that give only optimal solutions,which indicates that adjusting the pump rate of an appropriate node individually can prevent the system from falling into local minima.A pump rate control scheme is proposed based on the above analysis and the MAX-CUT problem with N = 8,10,16,20 is solved based on this scheme.The simulation results show that the probability of obtaining the optimal solution by the non-uniform pumping CIM is increased by 3.4% ~ 25.3% compared with the traditional CIM.