  Conventional computing architectures have no known efficient algorithms for
combinatorial optimization tasks, which are encountered in fundamental areas
and real-world practical problems including logistics, social networks, and
cryptography. Physical machines have recently been proposed and implemented as
an alternative to conventional exact and heuristic solvers for the Ising
problem, one such optimization task that requires finding the ground state spin
configuration of an arbitrary Ising graph. However, these physical approaches
usually suffer from decreased ground state convergence probability or
universality for high edge-density graphs or arbitrary graph weights,
respectively. We experimentally demonstrate a proof-of-principle integrated
nanophotonic recurrent Ising sampler (INPRIS) capable of converging to the
ground state of various 4-spin graphs with high probability. The INPRIS
exploits experimental physical noise as a resource to speed up the ground state
search. By injecting additional extrinsic noise during the algorithm
iterations, the INPRIS explores larger regions of the phase space, thus
allowing one to probe noise-dependent physical observables. Since the recurrent
photonic transformation that our machine imparts is a fixed function of the
graph problem, and could thus be implemented with optoelectronic architectures
that enable GHz clock rates (such as passive or non-volatile photonic circuits
that do not require reprogramming at each iteration), our work paves a way for
orders-of-magnitude speedups in exploring the solution space of combinatorially
hard problems.
