Memcomputing NP-complete problems in polynomial time using polynomial
resources and collective states
Fabio L. Traversa,1, 2, ∗ Chiara Ramella,2, † Fabrizio Bonani,2, ‡ and Massimiliano Di Ventra1, §

arXiv:1411.4798v3 [cs.ET] 7 Jul 2015

1

Department of Physics, University of California, San Diego, La Jolla, California 92093, USA
2
Department of Electronics and Telecommunications, Politecnico di Torino, Turin, Italy
(Dated: July 9, 2015)

Memcomputing is a novel non-Turing paradigm of computation that uses interacting memory
cells (memprocessors for short) to store and process information on the same physical platform[1].
It was recently proved mathematically that memcomputing machines have the same computational
power of non-deterministic Turing machines[2]. Therefore, they can solve NP -complete problems in
polynomial time and, using the appropriate architecture, with resources that only grow polynomially
with the input size. The reason for this computational power stems from properties inspired by
the brain and shared by any universal memcomputing machine, in particular intrinsic parallelism
and information overhead[2], namely the capability of compressing information in the collective
state of the memprocessor network. Here, we show an experimental demonstration of an actual
memcomputing architecture that solves the NP -complete version of the subset-sum problem in only
one step and is composed of a number of memprocessors that scales linearly with the size of the
problem. We have fabricated this architecture using standard microelectronic technology so that it
can be easily realized in any laboratory setting. Even though the particular machine presented here
is eventually limited by noise–and will thus require error-correcting codes to scale to an arbitrary
number of memprocessors–it represents the first proof-of-concept of a machine capable of working
with the collective state of interacting memory cells, unlike the present-day single-state machines
built using the von Neumann architecture.

INTRODUCTION

There are several classes of computational problems
that require time and resources that grow exponentially
with the input size when solved. This is true when
these problems are solved with deterministic Turing machines, namely machines based on the well-known Turing paradigm of computation which is at the heart of
any computer we use nowadays [3, 4]. Prototypical examples of these difficult problems are those belonging to
the class that can be solved in polynomial (P ) time if
a hypothetical Turing machine–named non-deterministic
Turing machine–could be built. They are classified as
non-deterministic polynomial (NP ) problems, and the
machine is hypothetical because, unlike a deterministic Turing machine, it requires a fictitious “oracle” that
chooses which path the machine needs to follow to get to
an appropriate state [3, 5, 6]. As of today, no one knows
whether NP problems can be solved in polynomial time
by a deterministic Turing machine [7, 8]. If that were the
case we could finally provide an answer to the most outstanding question in computer science, namely whether
NP=P or not[3].
Very recently a new paradigm, named memcomputing
[1] has been advanced. It is based on the brain-like notion
that one can process and store information within the
same units (memprocessors) by means of their mutual interactions. This paradigm has its mathematical foundations on an ideal machine, alternative to the Turing one,
that was formally introduced by two of us (FT and MD)
and dubbed universal memcomputing machine (UMM)

[2]. Most importantly, it has been proved mathematically that UMMs have the same computational power of
a non-deterministic Turing machine [2], but unlike the
latter, UMMs are fully deterministic machines and, as
such, they can actually be fabricated. A UMM owes
its computational power to three main properties: intrinsic parallelism–interacting memory cells simultaneously and collectively change their states when performing computation; functional polymorphism–depending on
the applied signals, the same interacting memory cells
can calculate different functions; and finally information
overhead–a group of interacting memory cells can store a
quantity of information which is not simply proportional
to the number of memory cells itself.
These properties ultimately derive from a different
type of architecture: the topology of memcomputing machines is defined by a network of interacting memory
cells (memprocessors), and the dynamics of this network
are described by a collective state that can be used to
store and process information simultaneously. This collective state is reminiscent of the collective (entangled)
state of many qubits in quantum computation, where the
entangled state is used to solve efficiently certain types
of problems such as factorization [9]. Here, we prove
experimentally that such collective states can also be implemented in classical systems by fabricating appropriate networks of memprocessors, thus creating either linear or non-linear combinations out of the states of each
memprocessor. The result is the first proof-of-concept
machine able to solve an NP -complete problem in polynomial time using collective states.
The experimental realization of the memcomputing

2
machine presented here, and theoretically proposed in
Ref. [2], can solve the NP -complete [10] version of the
subset-sum problem (SSP) in polynomial time with polynomial resources. This problem is as follows: if we consider a finite set G ⊂ Z of cardinality n, is there a nonempty subset K ⊆ G whose sum is a given integer number s? As we discuss in the following paragraphs, the
machine we built is analog and hence would be scalable
to very large numbers of memprocessors only in the absence of noise or using some error-correcting codes. This
problem derives from the fact that in the present realization we use the frequencies of the collective state to
encode information and, to maintain the energy of the
system bounded, the amplitudes of the frequencies are
dampened exponentially with the number of memprocessors involved. However, this latter limitation is due
to the particular choice of encoding the information in
the collective state, and could be overcome by employing
other realizations of memcomputing machines that are
digital and using error-correcting codes. For example in
Ref. [2] two of us (FT and MD) proposed a different way
to encode a quadratic information overhead in a network
of memristors that is not subject to this energy bound.
Another example in which information overhead does
not need exponential growth of energy is again quantum computing. For instance, a close analysis of the
Shor’s algorithm [11] shows that the collective state of
the machine implements all at once (through the superposition of quantum states) an exponential number of
states, each one with the same probability that decreases
exponentially with the number of qubits involved. Successively, the quantum Fourier transform reorganizes the
probabilities encoded in the collective state and “selects”
those that actually solve the implemented problem (the
prime factorization in the case of the Shor’s algorithm).
It is worth noticing, however, that also quantum computing algorithms necessarily require error-correcting codes
for their practical implementation due to the several unavoidable sources of noise [9].
Here, it is also worth stressing that our results do not
answer the NP=P question, since the latter has its solution only within the Turing-machine paradigm: although
a UMM is Turing-complete [2], it is not a Turing machine.
In fact, (classical) Turing machines employ states of single memory cells and do not use collective states. Finally,
we mention that other unconventional approaches to the
solution of NP-complete problems have been proposed
[8, 12–16], however none of them reduces the computational complexity or requires physical resources not exponentially growing with the size of the problem. On the
contrary, our machine can solve an NP -complete problem with only polynomial resources. As anticipated, this
last claim is strictly valid for an arbitrary large input size
only in the absence of noise.

RESULTS
Implementing the SSP.

The machine we built to solve the SSP is a particular
realization of a UMM based on the memcomputing architecture described in Ref. [2], namely it is composed of a
control unit, a network of memprocessors (computational
memory) and a read-out unit as schematically depicted
in Figure 1. The control unit is composed of generators
applied to each memprocessor. The memprocessor itself
is an electronic module fabricated from standard electronic devices, as sketched in Figure 2 and detailed in
the Materials and Methods section. Finally, the read-out
unit is composed of a frequency shift module and two
multimeters. All the components we have used employ
commercial electronic devices.
The control unit feeds the memprocessor network with
sinusoidal signals (that represent the input signal of the
network) as in Figure 1. It is simple to show that the collective state of the memprocessor network of this machine
(that can be read at the final terminals of the network)
is given by the real (up terminal) and imaginary (down
terminal) part of the function
g(t) = 2−n

n
Y

(1 + exp[iωj t])

(1)

j=1

where n is the number of memprocessors in the network
and i the imaginary unit (see Materials and Methods or
Ref. [2]). If we indicate with aj ∈ G the j-th element
(integer with sign) of G, and we set the frequencies as
ωj = 2πaj f0 with f0 the fundamental frequency equal for
any memprocessor, we are actually encoding the elements
of G into the memprocessors through the control-unit
feeding frequencies. Therefore, the frequency spectrum
of the collective state (1) (or more precisely the spectrum of g(t) − 2−n ) will have the harmonic amplitude,
associated with the normalized frequency f = ω/(2πf0 ),
proportional to the number of subsets K ⊆ G whose sum
s is equal to f . In other words, if we read the spectrum of
the collective state (1), the harmonic amplitudes are the
solution of the subset sum problem for any s. From this
first analysis we can make the following considerations.
Information overhead: the memprocessor network is
fed by n frequencies encoding the n elements of G, but the
collective state (1) encodes all possible sums of subsets of
G into its spectrum. It is well known [7] that the number
of possible sums s (or equivalently the scaled frequencies
f of the spectrum) can bePestimated P
in the worst case
as O(A) where A = max[ aj >0 aj , − aj <0 aj ]. Obviously A (sometimes called the capacity of the problem)
has exponential growth [17] on the minimum number p
of bits used to represent the elements of G (p is called
precision of the problem and we have A = O(2p ), if we
take the precision in bits). Thus the spectrum of the

3
Control Unit

0.5[(1+cos(1t)] 0.5[1+cos(2t)] 0.5[1+cos(3t)]

~

~

0.5[1+cos(5t)]

0.5[1+cos(6t)]

~

~

~

1V

~

0.5[1+cos(4t)]

Memprocessor

Internal collective state

- s/2

s/2
cos(st) sin(st)

~ ~

Vs=VDCup+VDCdown

Frequency
Shift
Module

Multimeters
V-s=VDCup-VDCdown

Read-out Unit

FIG. 1. Scheme of the memcomputing architecture used in this work to solve the subset-sum problem. The central spectrum
has been obtained by the discrete Fourier transform of the experimental output of a network of 6 memprocessors encoding the
set G = {130, −130, −146, −166, −44, 118} with fundamental frequency f0 = 100 Hz.

collective state (1) encodes an information overhead that
grows exponentially with the precision of the problem.
Computation time: the collective state (1) is a periodic
function of t with minimum period T = 1/f0 because all
frequencies involved in (1) are multiples of the fundamental frequency f0 . Therefore, T is the minimum time
required for computing the solution of the SSP within
the memprocessor network and so it can be interpreted
as the computation time of the machine. However, this
computation time is independent of both n and p.
Energy expenditure: the energy required to compute
the SSP can be estimated as that quantity proportional
to the energy of the collective state in one period E =
RT
RT
|g(t)|2 dt. By using (1) we have E ≤ 0 dt ≤ 1/f0 ,
0
so also the energy needed for the computation is independent of both n and p. It is worth remarking here
that, in order to keep the energy bounded, all generators
have the coefficient 0.5 (see Figure 1) then introducing
(see Materials and Methods) the factor 2−n in Eq. (1).
This means that all frequencies involved in the collective state (1) are dampened by the factor 2−n . In the
case of the ideal machine, i.e., a noiseless machine, this

would not represent an issue because no information is
lost. On the contrary, when noise is accounted for, the exponential factor represents the hardest limitation of the
experimentally fabricated machine, which we reiterate is
a technological limit for this particular realization of a
memcomputing machine but not for all of them.

Reading the SSP solution

With this analysis we have proven that the UMM represented in Figure 1 can solve the SSP with n memprocessors, a control unit formed by n + 1 generators and
taking a time T and an energy E independent of both
n and p. Therefore, at first glance, it seems that this
machine (without the read-out unit) can solve the SSP
using only resources polynomial (specifically, linear) in
n. However, we need one more step: we have to read
the result of the computation. Unfortunately, we cannot simply read the collective state (1) using, e.g., an
oscilloscope and performing the Fourier conversion. This
is because the most optimized algorithm to do this (see
Materials and Methods and Ref. [2]) is exponential in

4
(a) MEMPROCESSOR
Controlled
Inverting Differentiator
1

v
Voltage Multiplier

_d

Summing
Amplifier

dt

.

v1

vv1+ 1vv2

v2

vv2  1vv1

.

Difference
Amplifier
(b) FREQENCY SHIFT MODULE
cos(st)

|s| ωs /(2π)
[KHz]
0
0
74
7.4
130 13.0
146 14.6
248 24.8
485 48.5
486 48.6

VDCup VDCdown
[mV]
[mV]
31.7
0
15.3
15.0
-0.2
14.9
14.8
15.8
7.6
7.2
-0.4
-0.7
-8.9
6.6

Vs
[V]
1.02
1.94
0.94
-0.06
0.95
-0.07
-0.14

V−s #subs. #subs.
[V] sum s sum −s
1.02
1
1
0.02
2
0
-0.97
1
1
1.96
0
2
0.02
1
0
0.02
0
0
0.99
0
1

TABLE I. Measurements from the read-out unit of Figure 1
for a 6–memprocessor network with fundamental frequency
f0 = 100 Hz encoding the set G = {130, −130, −146, −166,
−44, 118}. In the fifth and sixth columns the voltages are
respectively given by Vs = 26 (VDCup + VDCdown ) and V−s =
26 (VDCup −VDCdown ). The last two columns are the analytical
results.

sin(st)

Re[v] cos(st)

Re[v]

Im[v] sin(st)

Im[v]

Voltage Multiplier

FIG. 2. (a) Simplified schematic of the memprocessor architecture used in this work to solve the subset-sum problem
(more details can be found in the Supplementary Information). (b) Schematic of the frequency shift module.

p, i.e., it has the same complexity of standard dynamic
programming [17].
However, a solution to this problem can be found by
just using standard electronics to implement a read-out
unit capable of extracting the desired frequency amplitude without adding any computational burden. In Figure 1 we sketch the read-out unit we have used. It is
composed of a frequency-shift module and two multimeters. The frequency shift module is in turn composed
of two voltage multipliers and two sinusoidal generators
as depicted in Figure 2 and it works as follows. If we
connect to one multiplier the real part of a complex signal v(t) and to the other multiplier the imaginary part,
we obtain at the outputs vup (t) = Re[v(t)](exp[iωs t] +
exp[−iωs t])/2 and vdown (t) = −iIm[v(t)](exp[iωs t] −
exp[−iωs t])/2. The sum and difference of the two outputs are vup + vdown = Re[v(t) exp[−iωs t]] and vup −
vdown = Re[v(t) exp[iωs t]]. From basic Fourier calculus,
v(t) exp[−iωs t] and v(t) exp[iωs t] are the frequency spectrum shifts of ωs /(2π) and −ωs /(2π) for the function
v(t), respectively. Consequently, if we read the DC voltages VDCup and VDCdown of vup (t) and vdown (t) using two

multimeters and perform the sum VDCup + VDCdown and
difference VDCup − VDCdown we obtain the amplitudes Vs
and V−s of the harmonics at the frequencies ωs /(2π) and
−ωs /(2π), respectively (see Figure 1).
Hence, by feeding the frequency shift module with the
Re[g(t)] and Im[g(t)] from (1), reading the output with
the two multimeters, and performing sum and difference of the final outputs we obtain the harmonic amplitude for a particular normalized frequency f according to
the external frequency ωs of the frequency-shift module.
In other words, without adding any additional computational burden and time, we can solve the SSP for a
given s by properly setting the external frequency of the
frequency-shift module.
It is worth noticing that, if we wanted to simulate
our machine by including the read-out unit the computational complexity would be O(2p ) (close to the standard
dynamic programming that is O(n2p ) [17]). In fact, from
the Nyquist-Shannon sampling theorem[18], the minimum number of samples of the shifted collective state
(i.e,. the outputs of the frequency-shift module) must be
equal to the number of frequencies of the signal (in our
case of O(2p )) in order to accurately evaluate even one
of the harmonic amplitudes [19]. The last claim can be
intuitively seen from this consideration: the DC voltage
VDCup must be calculated in the simulation by evaluating
RT
the integral VDCup = T −1 0 vup (t)dt and this requires
at least O(2p ) samples for an accurate evaluation [18].
On the other hand, the multimeter of the hardware implementation, being essentially a narrow low-pass filter,
performs an analog implementation of the integral over
a continuous time interval T (independent of n and p),
directly providing the result, thus avoiding the need of
sampling the waveform and computing the integral.
In Figure 3 the absolute value of the spectrum of the
collective state for networks of 4, 5 and 6 memprocessors is compared with the theoretical results given by the

5
2

4 memprocessors

Number of subsets

1
0
2

0
5 memprocessors

1
0
2

0
6 memprocessors

1
0
−50

−40

−30

−20

−10

0
10
Frequency (KHz)

20

30

40

50

FIG. 3. Spectra of internal collective state of three different networks with fundamental frequency f0 = 100 Hz. 4–memprocessor
network encodes the set G = {130, −130, −146, −166}. 5–memprocessor network encodes G = {130, −130, −146, −166, −44}.
6–memprocessor network encodes G = {130, −130, −146, −166, −44, 118}.

spectrum of (1) (see Materials and Methods for more details on the hardware and measurement process). Nonidealities of the circuit and electronic noise in general
are the sources of the small discrepancies with respect
to the theoretical results. Nevertheless, the machine we
fabricated demonstrates that using the collective state
of all memprocessors, instead of the uncoupled states of
the individual memory units, we can carry out difficult
computing tasks (NP-complete problems) with polynomial resources. Finally, in Table I, the measurements
at the read-out circuit are listed for different harmonics
for a 6-memprocessor network. The precision is up the
third digit as can be seen from the comparison with the
theoretical results.

terminals of the second memprocessor is given by
v2out =v1in v2in = 2−2 (1 + eiω1 t )(1 + eiω2 t )+
+2−1 (1 + eiω1 t )ε2 (t) + 2−1 (1 + eiω2 t )ε1 (t)+
+ε1 (t)ε2 (t).

(2)

If the noise term is small enough (low noise components) the quantity ε1 (t)ε2 (t) is negligible compared to
the other terms and can be neglected. Following the same
steps, the network composed of n memprocessors has collective state (under low noise condition) of the form
g(t) =vnout = 2−n

n
Y

(1 + eiωj t )+

j=1

+2−n+1

n
X
k=1

DISCUSSION

εk (t)

n
Y

(1 + eiωj t ) = gS (t) + gN (t)

j=1
j6=k

(3)
Scalability and Error Correction

As anticipated, the machine we have built would ultimately be limited by unavoidable noise sources, thus
requiring error-correcting codes. However we prove here
that under the assumption of low noise, additive white
noise does not affect the machine output. Therefore, only
non-idealities of the devices and colored noise represent
a limit for this particular machine. To analyze this issue
we consider first the simplest case of independent white
Gaussian additive noise sources for each memprocessor.
Under this hypothesis each memprocessor has complex
noisy input of the form vjin = 2−1 (1 + exp[iωj t]) + εj (t).
When we connect two memprocessors, the output at the

Using the expression (3) we can calculate the signal-tonoise-ratio as the ratio between the power of the signal
and the power of the noise. The signal power (neglecting
RT
noise) is simply given by S = E = 0 |gS (t)|2 dt ≈ T
RT
and the noise power is given by N = 0 E[|gN (t)|2 ]dt,
where E[·] is the expectation value operator. Since the
noise
independent we have E[|gN (t)|2 ] ≈
Pn sources are
2
2
k=1 E[|εk (t)| ], and being the sources white E[|gN (t)| ]
2
is independent of time. Finally, assuming E[|εk (t)| ] =
E[|εj (t)|2 ] for any j and k we have E[|gN (t)|2 ] ≈
T nE[|ε|2 ] and the signal-to-noise ratio reads
S
1
≈
.
N
nE[|ε|2 ]

(4)

6
However, being the noise withe, the noise power spectrum, according to (3), is distributed among the different harmonics with weights given by the coefficients in
(3) that are exponentially decreasing with n. Therefore,
the signal to noise ratio for each harmonic has the same
order of magnitude of (4) and hence the withe noise (under conditions of low noise) does not affect the machine
when we scale it up.
On the other hand, non-idealities, colored and 1\f
noise and other non-Gaussian noise sources, have spectra
that are not distributed on the harmonics as withe noise.
For example, the 1\f noise accumulates on the output
harmonic during the process of measurement. Nevertheless, if the total noise can be considered low, the equation
(3) is still valid but the ratio (4) should be taken frequency dependent. In this case we can apply the Shannon’s noisy-channel coding theorem [20] with our machine interpreted as a noisy channel with capacity C.
The input is given by the control unit and the output
is the collective state g(t). The Shannon theorem then
states that for any ε > 0 and R < C, there exists a code
of length N and rate ≥ R and a decoding algorithm, such
that the maximal probability of block error is ≤ ε.
In addition, using the Shannon–Hartley theorem [21]
we have that for frequency dependent noise the capacity
C can be calculated as


Z B
S(f )
df,
(5)
C=
log2 1 +
N (f )
0
where B is the bandwidth of the channel. In our case, the
lower bound of B can be taken as linear in the number of
memprocessors, i.e., B = B0 n with B0 a constant, and
S/N is given by (4). We finally have (for large n)


Z B
1
B0
. (6)
C≈
log2 1 +
df ≈
2
nE[ε (f )]
E[ε2 ] ln 2
0
R nB
−1
where E[ε2 ] = limn→∞ 0 0 E[ε2 (f )]−1 df .
We therefore conclude that our machine compresses
data in an exponential way with constant capacity. At
the output we have the exponential decreasing probability of finding one solution of the subset sum problem
when we implement brute force the algorithm, i.e., without any error-correcting coding. However, from Shannon
theorem, there exists a code that allows us to send the
required information with bounded error. The question
is then whether there is a polynomial code that accomplishes this task. We briefly discuss here the question
heuristically. If our machine were Turing-like, the polynomial code could exist only if N P = P . Instead, our
machine is not Turing-like, and the channel can perform
an exponential number of operations at the same time.
Since this is similar to what quantum computing does
when solving difficult problems such as factorization, and
we know that for quantum computing polynomial correcting codes do exist [9], we expect similar coding can
be applied to our specific machine as well.

CONCLUSIONS

In summary, we have demonstrated experimentally
a deterministic memcomputing machine that is able to
solve an N P -complete problem in polynomial time (actually in one step) using only polynomial resources. The
actual machine we built clearly suffers from technological limitations due to unavoidable noise that impair its
scalability. These limitations derive from the fact that
we encode the information directly into frequencies, and
so ultimately into energy. This issue could, however, be
overcome either using error correcting codes or with other
UMMs that use other ways to encode such information
and are digital at least in their input and output. Irrespective, this machine represents the first experimental
realization of a UMM that uses the collective state of the
whole memprocessor network to exploit the information
overhead theoretically introduced in Ref. [2]. Finally, it
is worth mentioning that the machine we have fabricated
is not a general purpose one. However, other realizations
of UMMs are general purpose and can be easily built
with available technology[22–26]. Their practical realization would thus be a powerful alternative to current
Turing-like machines.

MATERIALS AND METHODS
Experimental Design

The operating frequency range of the experimental
setup needs to be discussed with the measurement target
in mind. For the measurement of the entire collective
state, the limiting frequency is due to the oscilloscope
we use to sample the full signal at the output of the
memprocessor network. On the other hand, the measurement of some isolated harmonic amplitudes using the
read-out unit, transfers this bottleneck to the voltage
generators and internal memprocessor components. It
is worth stressing that measuring the collective state is
not the actual target of our work because it has the same
complexity of the standard algorithms for the SSP as discussed in the Results section and in Ref. [2]. Here, for
completeness, we provide measurements of the collective
state only to prove that the setup works properly. The
actual frequency range of the setup is discussed in the
next section.

Setup frequency range

Let us consider aj ∈ G, and the integer


 X
X 
A = max −
aj ,
aj .


aj <0

aj >0

(7)

7
We also consider f0 ∈ R and we encode the aj in the
frequencies by setting the generators at frequencies fj =
|aj |f0 , so the maximum frequency of the collective state
is fmax = Af0 . From these considerations, we can first
determine the range of the voltage generators: it must
allow for the minimum frequency (resolution)
fgmin ≤ f0

(8)

and maximum frequency (bandwidth)
fgmax ≥ f0 max{|aj |}.
G

(9)

We employed the Agilent 33220A Waveform Generator[?
], which has 1 µHz resolution and 20 MHz bandwidth.
This means that, in principle, we can accurately encode
G when composed of integers with a precision up to 13
digits (which is quite the same precision of the standard double-precision integers) provided that a stable
and accurate external clock reference, such as a rubidium frequency standard is used. This is because the internal reference of such generators introduces a relative
uncertainty on the synthesized frequency in the range
of some parts-per-billion (10−9 ) thus limiting the resolution at high frequency, down to few mHz at the maximum frequency. However, as anticipated, this issue can
be resolved by employing an external reference providing higher accuracies. On the other hand, note that the
frequency range can be, in principle, increased by using
wider bandwidth generators, up to the GHz range.
Another frequency limitation concerning the maximum
operating frequency is given by the electronic components of the memprocessors. In fact, the active elements
necessary to implement in hardware the memprocessor
modules have specific operating frequencies that cannot be exceeded. Discrete operational amplifiers (OPAMPs) are the best candidates for this implementation
due to their flexibility in realizing different types of operations (amplification, sum, difference, multiplication,
derivative, etc.). Their maximum operating frequency
is related to the gain-bandwidth product (GBWP). We
used standard high frequency OP-AMP that can reach
GBWP up to few GHz. However, such amplifiers usually show high sensitivity to parasitic capacitances and
stability issues (e.g., a limited stable gain range). Typical maximum bandwidth of such OP-AMPs that ensures
unity gain stability and acceptable insensitivity to parasitics are of the order of few tens of MHz, thus compatible with the bandwidth of the Agilent 33220A Waveform
Generator. Therefore, we can set quantitatively the last
frequency limit related to the hardware as
fOP AM Pmax > Af0 ,

(10)

and ensure optimal OP-AMP functionality. Finally using (8)-(10) we can find a reasonable f0 satisfying the
frequency constraints.

Memprocessor

The memprocessor, synthetically discussed in the Results section and sketched in Figure 2, is shown in
the pictures of Figure S1-(a) and a more detailed circuit schematics is given in Figure S1-(b). Each module has been realized as a single Printed Circuit Board
(PCB) and connections are performed through coaxial
cables with BNC terminations. According to Figure 2,
d
,
each memprocessor must perform one derivative −ωj−1 dt
four multiplications, one sum and one difference. Since
v(t) = 0.5[1 + cos(2πf0 aj t)] and ωj = 2πf0 aj , then
−ωj−1 v̇(t) = 0.5 sin(2πf0 aj t), i.e. the quadrature signal with respect to the input v(t). This can be easily
obtained with the simple OP-AMP-based inverting differentiator depicted in Figure S1-(b), designed to have
unitary gain at frequency ωj . Similarly, an inverting
summing amplifier and a difference amplifier can be realized as sketched in Figure S1-(b) to perform sum and
difference of voltage signals, respectively. The OP-AMP
selected is the Texas Instruments LM7171 Voltage Feedback Amplifier.
Implementing multiplication is slighly more challenging. OP-AMP based analog multipliers are very sensitive circuits. Therefore, they need to be carefully calibrated. This makes a discrete OP-AMP based realization quite challenging and the integration expensive.
We thus adopted a pre-assembled analog multiplier: the
Texas Instrument (Burr-Brown) MPY634 Analog Multiplier, which ensures four-quadrant operation, good accuracy and wide enough bandwidth (10MHz). The only
drawback of this multiplier is that the maximum precision is achieved with a gain of 0.1. Therefore, being the
input signals in general quite small, this further lowering
of the precision can make the output signal comparable
to the offset voltages of the subsequent OP-AMP stages.
For this reason, we have included in the PCB a gain stage
(inverting amplifier) before each output to compensate
for the previous signal inversion and lowering. These
stages permit also manual offset adjustment by means of
a tunable network added to the non-inverting input, as
shown in the schematic. Finally a low-pass filter with
corner frequency fc  Af0 has been added to the outputs to limit noise. Figure S1-(a) shows a picture of one
of the modules, which have been realized on a 100 mm
× 80 mm PCB. The power consumption of each module
is quite high since all of the 10 active components work
with ±15 V supply. OP-AMPs have a quiescent current
of 6.5 mA, while the multipliers a quiescent current of 4
mA, yielding a total DC current of around 50 mA per
module.
Finally, we briefly discuss how connected memprocessors work. From Figure 2, if we have v(t) = 0.5[1 +
cos(ωt)], v1 = Re[f (t)] and v2 = Im[f (t)] for an arbitrary
complex function f (t), at the output of the memproces-

8
sor we will find
v1out = 0.5[1 + cos(ωt)]Re[f (t)] − 0.5 sin(ωt)Im[f (t)] =

= Re[0.5 1 + eiωt f (t)]
(11)
v2out = 0.5[1 + cos(ωt)]Im[f (t)] + 0.5 sin(ωt)Re[f (t)] =

= Im[0.5 1 + eiωt f (t)]
(12)
Since we can only set positive frequencies for the generators, in order to encode negative frequencies (i.e., a
negative aj ) we can simply invert the input and output
terminals as depicted in Figure S1-(c). Therefore, if we
set f (t) = 1 for the first memprocessor, i.e., v1 = 1 and
v2 = 0, at the output of the first memprocessor we will
find the real and imaginary parts of 0.5(1 + exp[iω1 t])
that will be the new f (t) for the second memprocessor.
Proceeding in this way we find the collective state (1) at
the end of the last memprocessor.

Analysis of the Collective State

In order to test if the memprocessor network correctly
works, we have carried out the measurement of the full
collective state g(t) at the end of the last memprocessor.
This task requires an extra discussion on the operating
frequency range. Indeed, the instrument we used to acquire the output waveform is the LeCroy WaveRunner
6030 Oscilloscope. The measurement process consists in
acquiring the output waveforms and apply the FFT in
software. Being the collective state a purely periodic signal, i.e., a signal containing only frequencies multiples
of f0 and with known maximum frequency fmax = Af0 ,
from the discrete Fourier transform theory and NyquistShannon sampling theorem[2, 18], we need to sample the
interval [0, 1/f0 ] into N = 2fmax /f0 + 1 subintervals of
width ∆t = (N f0 )−1 to compute the exact spectrum of
g(t). In other words we need samples g(tj ) with tj = k∆t
and k = 0, ..., N − 1 to compute the exact spectrum of
g(t). Therefore, with the oscilloscope we must be able
to acquire at least N + 1 samples of g(t) into the time
interval [0, 1/f0 ].
This relationship turns out to be a constraint on the
usable frequency range since we must perform the measurement in a reasonable time, and we cannot exceed
the maximum sampling frequency of the instrument that
we use for acquisition, nor its maximum memory capability. In our experimental proof, the LeCroy WaveRunner 6030 Oscilloscope is characterized by 350 MHz
bandwidth, 2.5 GSa/s sampling rate and 105 discretization points when saving waveforms in ascii format (i.e.,
NOmax = 105 ). The bandwidth of the oscilloscope is very
large thus it is not really a constraint, while the limit
NOmax is, in fact we have the constraint
fmax ≤

f0
(NOmax − 1) .
2

(13)

With this value, choosing f0 = 1 Hz allows to have A ≤
(105 −1)/2, fmax <
∼ 50 KHz and requires 1 s measurement
time which is a quite long time in electronics. Therefore,
without varying A, we can choose larger f0 that allows
for a smaller measurement time. We choose f0 = 100 Hz
which means a measurement time of only few tens of ms,
and fmax <
∼ 5 MHz.
Experimental set-up

The laboratory set-up we have employed is sketched in
Fig. S2-(a), while Fig. S3 reports a picture of the same.
The order of cascade connection of the memprocessors is
arbitrary. For this test, we ordered the module such that
G = {130, −130, −146, −166, −44, 118} (see Figure S2(a)) in order to have the two memprocessors related to
the two positive numbers (130 and 118) at the beginning
and at the end of the chain, respectively, thus minimizing the number of the “swapped” connections (see Figure S1-(c)). A two-output power supply (model Agilent
E3631A) is used to generate both the 0 and 1 V at the inputs of the first memprocessor and the ±15 V supply for
all the modules (parallel connection). The input v(t) of
each module is generated by a Agilent 33220A waveform
generator, while the output is observed through both an
oscilloscope (model LeCroy Waverunner 6030, see Figure S2-(c)) and a multimeter (model Agilent 34401A). In
particular, the oscilloscope is used for the AC waveform,
while the multimeter mesured the DC component in order to avoid errors due to the oscilloscope probes which
are very inaccurate at DC and may show DC offsets up
to tens of mV.
Another issue concerns the synchronization of the generators. The six generators we use must share the same
time base and they must have the same starting instant
(the t = 0 instant) when all the cosine waveforms must
have amplitude 0.5 V. To have a common time base we
used the 10 MHz time base signal of one of the generators (master) and we connected the master output signal
to all the other (slave) generators at the 10 MHz input.
In this way they ignore their own internal time base and
lock to the external one. In order to have a common
t = 0 instant we must run the generators in the infinite
burst mode. In this mode the generators produce no output signal until a trigger input is given, and then they
run indefinitely until they are manually stopped. The
trigger input can be external or manual (soft key): the
master device is set up to expect a manual input while
the slave devices are controlled by an external trigger
coming from the master. Finally, in order to correctly
visualize the output waveforms we must “synchronize”
also the oscilloscope. The trigger signal of the oscilloscope must have the same frequency of the signal to be
plotted, or at least one of its subharmonics. Otherwise,
we see the waveform moving on the display and, in case

9
two or more signals are acquired, we lose the information
concerning their phase relation. To solve this problem we
connect the external trigger input of the oscilloscope to a
dedicated signal generator, producing a square waveform
at frequency f0 , which is the greatest common divisor of
all the possible frequency components of the output signals. This dedicated generator is also used as the master
for synchronization. Fig. S2-(b) shows how the generators must be connected in order to obtain the required
synchronization.
Acknowledgements The hardware realization of the
machine presented here was supported by Politecnico di
Torino through the Neural Engineering and Computation Lab initiative. MD acknowledges partial support
from CMRR.

∗
†
‡
§

[1]
[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

fabio.traversa@polito.it
chiara.ramella@polito.it
fabrizio.bonani@polito.it
diventra@physics.ucsd.edu
Massimiliano Di Ventra and Yuriy V. Pershin. The parallel approach. Nature Physics, 9:200–202, 2013.
F. L. Traversa and M. Di Ventra.
Universal Memcomputing Machines.
(preprint on
arXiv:1405.0931)
IEEE
Transaction
on
Neural
Networks
and
Learning
Systems,
DOI:
10.1109/TNNLS.2015.2391182, 2015.
Michael R. Garey and David S. Johnson. Computers and Intractability; A Guide to the Theory of NPCompleteness. W. H. Freeman & Co., New York, NY,
USA, 1990.
John L. Hennessy and David A. Patterson. Computer
Architecture, Fourth Edition: A Quantitative Approach.
Morgan Kaufmann Publishers Inc., San Francisco, CA,
USA, 2006.
Alan M. Turing. On computational numbers, with an
application to the entscheidungsproblem. Proc. of the
London Math. Soc., 42:230–265, 1936.
Alan M. Turing. The Essential Turing: Seminal Writings
in Computing, Logic, Philosophy, Artificial Intelligence,
and Artificial Life, Plus The Secrets of Enigma. Oxford
University Press, 2004.
Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press,
2009.
Kan Wu, Javier Garcı́a de Abajo, Cesare Soci, Perry Ping
Shum, and Nikolay I Zheludev. An optical fiber network
oracle for np-complete problems. Light: Science & Applications, 3(2):e147, 2014.
Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge Series on
information and the Natural Sciences. Cambridge University Press, 10th Aniversary edition, 2010.
Richard M Karp. 50 Years of Integer Programming 19582008, chapter Reducibility among combinatorial prob-

lems, pages 219–241. Springer Berlin/Heidelberg, 2010.
[11] P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.
SIAM Journal on Computing, 26(5):1484–1509, 1997.
[12] Damien Woods and Thomas J Naughton. Optical computing: photonic neural networks. Nature Physics,
8(4):257–259, 2012.
[13] Tien D Kieu. Quantum algorithm for Hilbert’s tenth
problem. International Journal of Theoretical Physics,
42(7):1461–1478, 2003.
[14] Leonard M Adleman. Molecular computation of solutions
to combinatorial problems. Science, 266(5187):1021–
1024, 1994.
[15] Z Ezziane. Dna computing: applications and challenges.
Nanotechnology, 17(2):R27, 2006.
[16] Mihai Oltean. Solving the hamiltonian path problem with a light-based computer. Natural Computing,
7(1):57–70, 2008.
[17] Sanjoy Dasgupta, Christos Papadimitriou, and Umesh
Vazirani. Algorithms. McGraw-Hill, New York, NY,
2008.
[18] F. Bonani, F. Cappelluti, S. D Guerrieri, and F. L.
Traversa. Wiley Encyclopedia of Electrical and Electronics Engineering, chapter Harmonic Balance Simulation
and Analysis. John Wiley and Sons, Inc., 2014.
[19] Gerald Goertzel. An algorithm for the evaluation of finite trigonometric series. The American Mathematical
Monthly, 65(1):34–35, 1958.
[20] C. E. Shannon. A mathematical theory of communication. The Bell System Technical Journal,, 27:379–423,
623–656, 1948.
[21] Herbert Taub and Donald L. Schilling. Principles of
Communication Systems. McGraw-Hill Higher Education, 2nd edition, 1986.
[22] Fabio L. Traversa, Fabrizio Bonani, Yuriy V. Pershin,
and Massimiliano Di Ventra.
Dynamic Computing
Random Access Memory. Nanotechnology, 25:285201,
2014.
[23] Rainer Waser and Masakazu Aono. Nanoionics-based
resistive switching memories. Nature materials, 6:833,
2007.
[24] Dmitri B. Strukov, Gregory S. Snider, Duncan R. Stewart, and R. Stanley Williams. The missing memristor
found. Nature, 453(7191):80–83, May 2008.
[25] T. Driscoll, Hyun-Tak Kim, Byung-Gyu Chae, Bong-Jun
Kim, Yong-Wook Lee, N. Marie Jokerst, S. Palit, D. R.
Smith, M. Di Ventra, and D. N. Basov. Memory metamaterials. Science, 325(5947):1518–1521, 2009.
[26] A. Chanthbouala, V Garcia, R. O. Cherifi, K. Bouzehouane, S Fusil, X. Moya, S. Xavier, H. Yamada, C. Deranlot, N. D. Mathur, M. Bibes, A Barthlmy, and J. Grollier. A ferroelectric memristor. Nature materials, 11:860–
864, 2012.

SUPPLEMENTARY INFORMATION

10
(a) MEMPROCESSOR CIRCUIT

Multiplier

Multiplier

Multiplier

(b) MEMPROCESSOR SCHEMATIC

vin1

Multiplier

vin2
v

+15

15
+15

vout1

+15

Summing
Amplifier

15

15 Inverting

+15

Amplifier

15
+15

Filter

vout2

+15

Difference
Amplifier
15

Controlled
Inverting Differentiator

15

(c) MEMPROCESSOR CONNECTIONS
aj>0

aj<0

v

v

vin1

vout1

vin2

vout2

vin1

vout1

vin2

vout2

FIG. 4. Memprocessor module. (a) Pictures, (b) schematic, (c) connection rule of the memprocessor module.

11
(a) BENCH DESCRIPTION
Waveform generators

1
2

1

Optional
processing

Oscilloscope

3

2
4

Memprocessors

6

3
5
4

5

DC supply / 1V
generator

Master

Multimeter

6

Frequency shift
module
(b) MEMPROCESSOR NETWORK

Connection of the
second module

FIG. 5. (a) Sketch of the laboratory test bench. (b) Synchronization of the waveform generators. (c) Collective state of 6
memprocessors network read by the oscilloscope.

12
(a) LAB BENCH SKETCH
Agilent 33220A
Waveform Generators
13 kHz

Agilent E3631A
Power Supply

13 kHz

OUT

1V

±15V

Agilent 34401A
Digital Multimeters

4.4 kHz
OUT

OUT

Master sync.
(Agilent 33220A)

0-6 V / ± 25 V
- +

Le Croy WaveRunner 6030
Digital Oscilloscope

11.8 kHz
OUT

14.6 kHz

- GND +

16.6 kHz

100 Hz

OUT

OUT

OUT
Ext. Trig.

Vre

M1

M2

M3

M4

M5

M6

130

-130

-146

-166

-44

118

Freq. shift
module

Vim

V’re

(b) SYNCHRONIZATION OF THE WAVEFORM GENERATORS
REAR

10MHz
IN

REAR

10MHz
OUT
REAR

REAR

Ext. Trig. I/O

(c) OSCILLOSCOPE

FIG. 6. Pictures of the laboratory test bench.

REAR

GND

V’im

