  We propose an algorithm inspired by optical coherent Ising machines to solve
the problem of polynomial unconstrained binary optimization (PUBO). We
benchmark the proposed algorithm against existing PUBO algorithms on the
extended Sherrington-Kirkpatrick model and random third-degree polynomial
pseudo-Boolean functions, and observe its superior performance. We also address
instances of practically relevant computational problems such as protein
folding and electronic structure calculations with problem sizes not accessible
to existing quantum annealing devices. The application of our algorithm to
protein folding and quantum chemistry problems sheds light on the shortcomings
of approximating the electronic structure problem by a PUBO problem, which, in
turn, puts into question the applicability of the unconstrained binary
optimization formulation, such as that of quantum annealers and coherent Ising
machines, in this context.
