Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA coherent Ising machine for MAX-CUT problems : Performance evaluation against semidefinite programming relaxation and simulated annealing
240
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Combinatorial optimization problems are computationally hard in general, but they are ubiquitous in our modern life. A coherent Ising machine (CIM) based on a multiple-pulse degenerate optical parametric oscillator (DOPO) is an alternative approach to solve these problems by a specialized physical computing system. To evaluate its potential performance, computational experiments are performed on maximum cut (MAX-CUT) problems against traditional algorithms such as semidefinite programming relaxation of Goemans-Williamson and simulated annealing by Kirkpatrick, et al. The numerical results empirically suggest that the almost constant computation time is required to obtain the reasonably accurate solutions of MAX-CUT problems on a CIM with the number of vertices up to $2 times 10^4$ and the number of edges up to $10^8$.
rate research
Read More
The coherent Ising machine is expected to find a near-optimal solution in various combinatorial optimization problems, which has been experimentally confirmed with optical parametric oscillators (OPOs) and a field programmable gate array (FPGA) circuit. The similar mathematical models were proposed three decades ago by J. J. Hopfield, et al. in the context of classical neural networks. In this article, we compare the computational performance of both models.
Many tasks in our modern life, such as planning an efficient travel, image processing and optimizing integrated circuit design, are modeled as complex combinatorial optimization problems with binary variables. Such problems can be mapped to finding a ground state of the Ising Hamiltonian, thus various physical systems have been studied to emulate and solve this Ising problem. Recently, networks of mutually injected optical oscillators, called coherent Ising machines, have been developed as promising solvers for the problem, benefiting from programmability, scalability and room temperature operation. Here, we report a 16-bit coherent Ising machine based on a network of time-division-multiplexed femtosecond degenerate optical parametric oscillators. The system experimentally gives more than 99.6 % of success rates for one-dimensional Ising ring and nondeterministic polynomial-time (NP) hard instances. The experimental and numerical results indicate that gradual pumping of the network combined with multiple spectral and temporal modes of the femtosecond pulses can improve the computational performance of the Ising machine, offering a new path for tackling larger and more complex instances.
Semidefinite Programming (SDP) is a class of convex optimization programs with vast applications in control theory, quantum information, combinatorial optimization and operational research. Noisy intermediate-scale quantum (NISQ) algorithms aim to make an efficient use of the current generation of quantum hardware. However, optimizing variational quantum algorithms is a challenge as it is an NP-hard problem that in general requires an exponential time to solve and can contain many far from optimal local minima. Here, we present a current term NISQ algorithm for SDP. The classical optimization program of our NISQ solver is another SDP over a smaller dimensional ansatz space. We harness the SDP based formulation of the Hamiltonian ground state problem to design a NISQ eigensolver. Unlike variational quantum eigensolvers, the classical optimization program of our eigensolver is convex, can be solved in polynomial time with the number of ansatz parameters and every local minimum is a global minimum. Further, we demonstrate the potential of our NISQ SDP solver by finding the largest eigenvalue of up to $2^{1000}$ dimensional matrices and solving graph problems related to quantum contextuality. We also discuss NISQ algorithms for rank-constrained SDPs. Our work extends the application of NISQ computers onto one of the most successful algorithmic frameworks of the past few decades.
In this paper we give an algorithm to round the floating point output of a semidefinite programming solver to a solution over the rationals or a quadratic extension of the rationals. We apply this to get sharp bounds for packing problems, and we use these sharp bounds to prove that certain optimal packing configurations are unique up to rotations. In particular, we show that the configuration coming from the $mathsf{E}_8$ root lattice is the unique optimal code with minimal angular distance $pi/3$ on the hemisphere in $mathbb R^8$, and we prove that the three-point bound for the $(3, 8, vartheta)$-spherical code, where $vartheta$ is such that $cos vartheta = (2sqrt{2}-1)/7$, is sharp by rounding to $mathbb Q[sqrt{2}]$. We also use our machinery to compute sharp upper bounds on the number of spheres that can be packed into a larger sphere.
We show that the nonlinear stochastic dynamics of a measurement-feedback-based coherent Ising machine (MFB-CIM) in the presence of quantum noise can be exploited to sample degenerate ground and low-energy spin configurations of the Ising model. We formulate a general discrete-time Gaussian-state model of the MFB-CIM which faithfully captures the nonlinear dynamics present at and above system threshold. This model overcomes the limitations of both mean-field models, which neglect quantum noise, and continuous-time models, which assume long photon lifetimes. Numerical simulations of our model show that when the MFB-CIM is operated in a quantum-noise-dominated regime with short photon lifetimes (i.e., low cavity finesse), homodyne monitoring of the system can efficiently produce samples of low-energy Ising spin configurations, requiring many fewer roundtrips to sample than suggested by established high-finesse, continuous-time models. We find that sampling performance is robust to, or even improved by, turning off or altogether reversing the sign of the parametric drive, but performance is critically reduced in the absence of optical nonlinearity. For the class of MAX-CUT problems with binary-signed edge weights, the number of roundtrips sufficient to fully sample all spin configurations up to the first-excited Ising energy, including all degeneracies, scales as $1.08^N$. At a problem size of $N = 100$ with a few dozen (median of 20) such desired configurations per instance, we have found median sufficient sampling times of $6times10^6$ roundtrips; in an experimental implementation of an MFB-CIM with a 10 GHz repetition rate, this corresponds to a wall-clock sampling time of 0.6 ms.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
