A Physical Computing Approach based on Coupled Oscillators
for Nondeterministic Polynomial-time Hard Problems
Corentin Delacour1 , Thierry Gil1 , Nadine Azemard-Crestani1 , Aida Todri-Sanial1,2
1. LIRMM, University of Montpellier, CNRS, France
2. Eindhoven Technical University, The Netherlands

Summary. This paper introduces a novel physical computing hardware based on mixed-signal
coupled oscillators to solve Nondeterministic Polynomial-time Hard problems (NP-hard) in continuoustime. Notably, the proposed architecture allows the mapping of any Ising problem and naturallysearches for ground states by performing gradient descent of a relaxed cost function. We highlightthe hardware potential by solving Max-cut and Max-3-SAT problems with a 16-oscillator chip.

1Introduction

As an alternative to von Neumann’s digital computing, physics-based computing proposes to encode
variables in physical quantities and harness natural laws to operate a system where memory and processors
are interlinked. Such as, neuromorphic computing takes inspiration from the brain to operate artificial
neural networks as dynamical systems rather than algorithms to gain efficiency.
In this paper, we propose an alternative physical computing architecture based on mixed-signal coupled oscillators to solve Combinatorial Optimization Problems (COPs) in continuous time. COPs are
essential for many applications involving logistics, scheduling, resource allocation, risk minimization,etc., but are often intractable for large instances as many relevant COPs belong to the Nondeterministic
Polynomial-time hard class (NP-hard), i.e. there is no known method to find the optimal solution inpolynomial-time [1].

2

Coupled oscillators and Combinatorial Optimization

A coupled-oscillator system can be thought of as an Oscillatory Neural Network (ONN) where neurons
are oscillators and synapses are coupling elements. When neurons oscillate with uniform frequency f0 ,ONNs can solve COPs in phase domain using their intrinsic gradient descent of an energy function [2].
Here, we propose an electrical ONN hardware architecture (Fig.1a) allowing precise mapping of COP
cost functions to the ONN energy that is minimized in continuous-time [3]. A neuron i is a relaxation
oscillator producing both analog and digital oscillations at its input and output, respectively. A synapse
consists of a capacitor Cij that transforms the digital waveform of neuron j into current spikes sent tothe analog input of neuron i. Each synaptic spike provokes a phase shift whose dynamics induce theminimization of a bounded energy function E defined as:(PN PNPN
E = i=1 j=1 Cij triangle(ϕi − ϕj ) + i=1 Ci−0 triangle(ϕi )(1)dϕi /dt = −∂E/∂ϕi
Where phases are measured with respect to a reference oscillator ϕ0 =0 and triangle(θ) is a 2π-periodic
interaction function defined as triangle(θ) = θ − π/2, if 0 ≤ θ ≤ π or triangle(θ) = 3π/2 − θ, if π ≤ θ ≤ 2π.
When phases are binary
P Psuch as ϕi =Pkπ, k ∈ Z, the ONN energy (1) is proportional to the Ising
Hamiltonian H = − i j Jij Si Sj − i hi Si with Si ± 1 that describes spin glasses in physics [4]. In
fact, it has been shown that all of Karp’s 21 NP-complete problems can be reduced to the problem offinding the ground states of the Ising Hamiltonian [4]. Thus, our ONN energy (1) can be thought of asa relaxation of Ising problems where variables are analog phases ϕi corresponding to Ising spins Si .
First, a COP is described by an Ising Hamiltonian and then mapped to the ONN hardware byprogramming synaptic capacitors Cij (pairwise interactions) and Ci−0 (external field). Next, the ONN isturned on with some initial phase state and the oscillator phases evolve according to nonlinear dynamics(1). Finally, phases are measured, and their positions on the unit circle provide a COP solution ascos ϕi > 0 −→ Si = +1 and cos ϕi ≤ 0 −→ Si = −1.

3Experiments on NP-hard Max-Cut and Max-3-SAT problems

We first investigate solving the Max-cut problem with our ONN which is a widely studied NP-hard COP.
Given a graph composed of N vertices connected by edges, finding the maximum graph cut (Max-cut)
consists in finding two complementary subsets of vertices that maximize the number of edges between
them. Fig.1b shows the Max-cut mapping to the ONN and experimental results up to N=16 vertices

(oscillators) using a CMOS proof-of-concept implemented with a 65nm technology (Fig.1a). Comparedto the best-in-class approximation algorithm found by Goemans and Williamson (GW) [5], our ONN
finds cut values cut > 0.9 cutGW after 15 oscillation cycles only. With oscillators running at 1 MHz, theruntime is improved by more than 4 orders of magnitude compared to GW executed on MATLAB witha standard laptop.
To showcase the implementation of Ising external fields hi (with capacitors Ci−0 ), we consider
solving the Max-3-SAT problem which consists in finding the Boolean assignment
W r Wofr variable x thatrl2 l3 in the formulamaximizes
thenumberofTRUEclauses
composedofthreeliterals
C=lr
1V V VVf = C1 C2 ... CM −1 CM with ljr ∈ {x1 , ..., xN , x1 , ..., xN }. f can be expressed as a graph where
the NP-complete decision problem ”Are there K satisfiable clauses in f ?” is reduced to ”Is there an
Independent Set (IS) of size K ?” where IS is a set of nodes that are independent (disconnected). Theequivalent graph is constructed as follows [4]. Each literal ljr is mapped to a vertex and the three vertices
forming a clause are interconnected (triangle sub-graph), so at most one vertex per clause is in the IS.
Moreover, all the pairs of complementary literals are connected as they cannot simultaneously satisfy
the two corresponding clauses. Overall, the IS size gives the number of satisfied clauses, and finding theMax-3-SAT is equivalent to finding a maximum IS (MIS) in the corresponding graph. MIS is NP-hardand can be reduced to an Ising ground state problem compatible with the ONN [4].
Fig.1c presents the ONN mapping and preliminary results with 4 variables and various numbers ofclauses up to M=32. Solving (1) in simulations provides near-optimum Boolean assignments in lessthan 100 oscillation cycles, and were confirmed by experiments although limited to 5 clauses (the chip
contains 16 oscillators only). Nevertheless, the results confirm the architecture’s ability to implement
Ising problems having both interaction terms Jij and field hi . As the hardware is modular, we envisionconnecting several chips together to address larger instances of various NP-hard problems such as 0-1Integer Programming or Knapsack problems.
a) ONN architecture210b) Max-cut solver

C21C31C41

V2out (t)C12C22C32C42V0out (t)C20C30C40S6C13C14C23C24C33C34IN 3V1in (t)

J25
S5C44

S4S3+hi,jONN mapping
Edges

TRUE x2

N Neurons
Reference: 1

Jij → Cij = Cji+h

𝐒𝐢 = +𝟏Hysteresis

Signsign(Cij )Programmation

ANALOGDIGITAL-Jx3x3+h +hmin

Si ∈{−1;1}-J+hTRUEx1-Jx2x2-J+h +hx3 TRUE+hH=J෍Si Sj − ෍ hi Siij∈{edge}iJ>hONN Mapping

Amplitude

𝐒𝐢 = −𝟏jCL-Jxഥ1NSynapse
Viout V out+hx1

N Vertices

ONN operation

4Ising problem (MIS)min H = − ෍ Jij Si Sj

Si ∈{−1;1}

J34

Input formulaf = (x1 ⋁x2 ⋁x3 )⋀(xഥ1 ⋁x2 ⋁x3 )⋀(x1 ⋁x2 ⋁x3 )V2in (t)NeuronShaper

C43

N

S2S1c) Max 3-SAT solver

Ising problem

Input graph

V1out (t)Max-cut

V4out (t)Viin

V4in (t)C11C10V3out (t)V3in (t)C0 C1 C2 C3ONN accuracy (exp.)

M clauses

Edges

3M Neurons
Reference: 0

Jij → Cij = Cji
hi → Ci0

ONN accuracy for 4 variables

IijONN chip
1.7 mmViin

16 Neurons @1MHz
256x 5-bit synapses
P=167μW

2.2 mmFigure 1: a) ONN architecture and chip implementation. b) Solving Max-cut with ONN for N(N-3)/2graphs with various densities per size N and running 10 trials per graph with the chip. The obtained cut
is normalized by GW’s best cut. c) Solving Max-3-SAT with ONN. Simulations numerically solve (1)with Python’s SciPy package. For each number of clauses M, we generate 10 random formulas and run
the ONN 10 times (J=6 and h=4). The mean value is plotted.

References[1] R.M. Karp, doi.org/10.1007/978-1-4684-2001-2-9, 1972.
[2] T. Wang et. al., doi.org/10.1007/s11047-021-09845-3, 2021.
[3] C. Delacour et al., preprint, https://hal.science/hal- 03961010, 2023.
[4] A. Lucas, doi.org/10.3389/fphy.2014.00005, 2014.
[5] M. Goemans and D. Williamson, doi.org/10.1145/227683.227684, 1995