The computational complexity of optical quantum annealers and Ising machines

Quantum annealers hold promise as optimization platforms for quantum machine learning applications and as layered neural networks. Recently, Optical Ising Machines (OIM) have been presented as a straight forward method to achieve this computational model. Relying on optical nonlinearities inside resonators, these devces are a network of coupled optical parametric oscillators (OPOs), a mature and practical technology in the field of continuous-variable quantum computing (CVQC). Despite the use of a key ingredient of CVQC (the second order nonlinearity which facilitates entanglement), the computational model of OIMs remains an open question. Here, we present a study of three different computational models based on physics of increasing complexity. We outline a fully classical nonlinear system of coupled oscillators, a semiclassical model of OPOs in the truncated Wigner representation, and a fully quantum treatment in the positive P representation. We present benchmarks of each model and outline their relative capability to capture the relevant physics responsible for practical computation in OIMs. Using these benchmarks, based on known quadratic optimization problems, we determine the computational complexity of these devices.