# Integer Factorization by Quantum Measurements

G. Mussardo  SISSA, Via Bonomea 265, I-34136 Trieste, Italy.  INFN, Sezione di
Trieste, Via Valerio 2, I-34127 Trieste, Italy  A. Trombettoni  Dipartimento
di Fisica, Universitá di Trieste, Strada Costiera 11, I-34151 Trieste, Italy
INFN, Sezione di Trieste, Via Valerio 2, I-34127 Trieste, Italy

Quantum algorithms are at the heart of the ongoing efforts to use quantum
mechanics to solve computational problems unsolvable on ordinary classical
computers Nielsen2010 ; Preskill ; Pittenger . Their common feature is the use
of genuine quantum properties such as entanglement and superposition of states
HorodeckiRMP2009 . Among the known quantum algorithms, a special role is
played by the Shor algorithm Shor1994 ; Shor1995 , i.e. a polynomial-time
quantum algorithm for integer factorization, with far reaching potential
applications in several fields, such as cryptography Ekert . For an integer
$N$ of the order of $2^{n}$, i.e. with $n$ digits, the Shor algorithm permits
its factorization in (order of) $n$ steps. This results in an exponential gain
in computational efficiency with respect to the best known classical
algorithms. Here we present a different algorithm for integer factorization
based on another genuine quantum property: quantum measurement Peres1993 ;
Shankar1994 ; Sakurai2020 . In this new scheme, the factorization of the
integer $N$ is achieved in a number of steps equal to the number of its prime
factors, referred to as $k$– e.g., if $N$ is the product of two primes, two
quantum measurements are enough, regardless of the number of digits $n$ of the
number $N$. Since $k$ is the lower bound to the number of operations one can
do to factorize a general integer, then one sees that a quantum mechanical
setup can saturate such a bound. Once established this, we discuss how the
algorithm can physically be ran. We argue that one needs a single-purpose
device where quantum measurements of an observable with assigned spectrum can
be performed. The preparation from scratch of this device requires the
solution, once for all and not for each factorization operation, of $\sim
2^{n}$ differential equations, a task that with a quantum computer can be
accomplished in $n$ steps.

Introduction.  Recent progress in the implementation of quantum devices has
led to the experimental demonstration of some instances of quantum advantage.
This happens when a specific computational problem may be solved faster and
more efficiently on quantum processors rather than a classical computer Wu2021
. To achieve this goal the quantum processor must have an architecture made at
least of several tens of qubits and long enough decoherence times.

A notable example, from a historical and conceptual point of view, of a clear
quantum advantage is provided by the Shor algorithm Shor1994 ; Shor1995 . This
algorithm indicates how to solve efficiently on a quantum computer the long-
standing problem of finding the prime factors of an integer number $N$.
Assuming that such a number $N$ is of order $2^{n}$, the Shor algorithm
exploits in an ingenious way the implementation of the discrete Fourier
transform on $n$ qubits. To date, its validity has been shown with the
factorization of a small numbers (the present computational bottleneck being
the quantum modular exponentiation). The factorization of the number,
$15=3\times 5$, was done using $7$ qubits with an NMR implementation of a
quantum computer Vandersypen2001 . Similar demonstrations were performed using
photonic Lu2007 ; Lanyon2007  and solid-state qubits Lucero2007 , while in
2012, with the $n$ qubits control register replaced by a single qubit recycled
$n$ times, it was achieved the factorization of the integer $21=3\times 7$
Martin2012 . Despite their simplicity, these examples nevertheless provide a
proof of principle realization of the algorithm.

In this paper we present a different route for integer factorization, based on
an algorithm which exploits another genuine quantum property: projective
quantum measurement Peres1993 ; Shankar1994 ; Sakurai2020 . As it is well
known from quantum mechanics axioms, if a physical system is in a normalised
state $|\psi\,\rangle$, a measurement of an observable $\hat{O}$ will yield
one eigenvalue $\alpha$ of its spectrum with probability
$\mid\langle\psi\mid\alpha\rangle\mid^{2}$, where $|\alpha\,\rangle$ is the
normalised eigenfunction corresponding to the eigenvalue $\alpha$

$\hat{O}\,|\alpha\,\rangle\,=\,\alpha\,|\alpha\,\rangle\,.$ (1)

As a result of the measurement, the system state will change from
$|\psi\,\rangle$ to $|\alpha\,\rangle$. For problems related to number theory,
interesting spectra to consider are: (a) the natural numbers, corresponding to
the Hamiltonian of an harmonic oscillator Shankar1994 ; Sakurai2020 ; (b) the
primes GMscattering ; holographic ; and (c) the logarithm of the primes mack10
; Weiss ; Schleich1 ; Schleich2 ; Schleich ; MTZ . Employing such spectra, one
may translate number theory problems in quantum physical settings. As an
example of this general philosophy, in this paper we show that with a suitable
choice of the operator $\hat{O}$ is possible to determine the prime factors of
an integer number $N$ by making a finite set of quantum measurements.

The layout of this article is as follows: after a brief reminder on classical
algorithms on primality and factorization of integers, we present our quantum
algorithm for the factorization problem. This algorithm is discussed in terms
of the familiar setting of Schrödinger Hamiltonian although, as shown in the
Supplementary Materials, it also admits a digital implementation. The
computational costs of Shor’s and our algorithm are thoroughly discussed in
the last part of the paper. In the Supplementary Materials we discuss the
digital implementation of our algorithm and a gedanken experiment able to
achieve, in principle, a projective measurement of quantum system
eigenenergies.

Classical primality tests and factorization algorithms.  The fundamental
theorem of arithmetic states that every natural number $N$ greater than $1$ is
either a prime number $p_{k}$ or can be represented as a product of prime
numbers

$N=p_{a_{1}}^{\alpha_{1}}p_{a_{2}}^{\alpha_{2}}\ldots
p_{a_{k}}^{\alpha_{k}}\,\,\,,$ (2)

where $p_{a_{1}}<p_{a_{2}}\cdots<p_{a_{k}}$ are $k$ ordered primes and
$\alpha_{i}\geq 1$ their multiplicity. Hence, prime numbers may be regarded as
the atoms of arithmetic but, in contrast with the finitely many chemical
elements, the number of primes is instead infinite, as shown by a classic
argument by Euclid dated more than 2000 years ago. The appearance of prime
numbers along the integer sequence is completely unpredictable. However, their
coarse graining properties, and in particular how many prime numbers there are
below any real number $x$, are aspects which can be controlled with remarkable
precision. In other words, while there is no known simple function $f(n)$
which gives the $n$-th prime number $p_{n}$ (and the actual determination of
prime numbers can only be done by means of the familiar Eratosthenes’s sieve
Ribenboim ; Schroeder ; Zagier ; Granville ; Rose ), we have instead perfect
knowledge of the inverse function $\pi(x)$ which counts the number of primes
below the real number $x$ Hardy ; Apostol ; Tao ; Ore ; Ribenboim ; Schroeder
; Zagier ; Granville ; Rose ; theorem1 ; theorem2 ; theorem3 ; theorem4 ;
Riemannorig ; Edwards ; Borwein . Such a function was exactly determined by
Riemann (see, for instance Edwards ): it has a staircase behaviour (since it
jumps by $1$ each time $x$ crosses a prime), but becomes smoother and smoother
for increasing values of $x$, and its asymptotic behaviour is constrained by
the “Prime Number Theorem” theorem1 ; theorem2 ; theorem3 ; theorem4 stating
that $\lim_{x\to\infty}\frac{\pi(x)\ln x}{x}\,=\,1$. Notice that
$p_{n}\,=\,\pi^{-1}(n)$. Hence, inverting at the lowest order the function
$\pi(x)$, one gets the following scaling law for the $n$-th prime number:
$p_{n}\simeq n\,\log n$.

Let’s first discuss the primality test. How can one tell whether an integer
$N$ is prime? What if the number has hundreds or thousands of digits? This
question may seem abstract or irrelevant, but primality tests are performed
every time to make online transactions secure. Given an integer $N$, determine
whether or not $N$ is a prime number constitutes a primality test. The naive
way to check the primality of an integer $N$ is to divide it by any prime
number between $2$ and $\sqrt{N}$. Assuming we express the number $N$ in
binary basis, if $N$ is of order $2^{d}$, the number of operations
${\mathscr{D}}$ of this naive primality algorithm scales exponentially with
the number of digits, i.e. ${\mathscr{D}}\sim 2^{d/2}$. Many different
algorithms have been proposed, both deterministic or probabilistic nature
(see, for instance Gillen ), to reduce the complexity of the primality test.
The final answer was given in 2002 Agrawal  in terms of a deterministic
protocol (the AKS test) whose complexity scales as Agrawal
${\mathscr{D}}_{AKS}\sim(\log N)^{7.5}$.

Let’s now imagine that the primality test outputs that $N$ is not a prime.
Then, looking at (2), how to determine the prime factors $p_{a_{1}}\ldots
p_{a_{k}}$ of the integer $N$? This is the question addressed by any
factorisation algorithm. Let $N$ be a number of $n$-bit digits: currently
there is no classical factorization algorithm whose complexity scales
${\mathscr{D}}\sim{\cal O}(n^{\alpha})$ for some constant $\alpha$. Although
neither the existence nor non-existence of such algorithms has been proved, it
is generally believed that they do not exist and hence that the problem is not
in the class of Polynomial Time Algorithms. If so, then the problem is clearly
in class NP, although it is not certain whether it is or is not in the class
of NP-complete problems fact1 ; fact2 ; fact3 . The best classical algorithm
known is the so-called general number field sieve (GNFS) fact2  whose
complexity for a number $N$ scales as $\exp(\ln N)^{1/3}$.

The factorization algorithm by quantum measurements.  In the following we
discuss how to devise a very efficient factorisation algorithm using quantum
mechanical measurements in a way that the number of steps is finite and does
not scale with the $n$ digits of $N$. In our presentation the operator
$\hat{O}$ is the guise of the familiar Hamiltonian $\hat{H}$, but the reader
is of course free to substitute the operator $\hat{H}$ with any other
hermitian operator with the appropriate spectra. Let assume that the
Hamiltonian $\hat{H}$ is made up of two Hamiltonians $\hat{H}_{1}$ and
$\hat{H}_{2}$ which commute to each other:

$\hat{H}\,=\,\hat{H}_{1}+\hat{H}_{2}\,,\,\,\,\,\,\,\,\,\,\,[\hat{H}_{1},\hat{H}_{2}]=0\,\,\,.$
(3)

We choose $\hat{H}_{1}$ to have $M$ eigenvalues given by the logarithms of the
primes, where $M=2^{d}$ is a fixed cut-off (which however can be increased as
desired)

$E_{n}^{(1)}\,=\,\log p_{n}\,;\hskip 5.69054ptn=1,2,3,\cdots 2^{d}\,.$ (4)

The corresponding eigenfunctions will be denoted as $|\log p_{n}\rangle$.

On the other hand, the second term $\hat{H}_{2}$ in the Hamiltonian $\hat{H}$
is chosen to have the eigenvalues given by the logarithms of the integers, up
to the same cut-off $M$, i.e.

$E_{m}^{(2)}=\log m\,;\hskip 5.69054ptm=2,3,\ldots 2^{d}\,.$ (5)

The corresponding eigenvectors will be denoted as $|\log m\rangle$. We will
discuss below how such Hamiltonians $H_{1}$ and $H_{2}$ can be explicitly
realised in a laboratory by means of spatial light laser modulators, as it was
recently done for an Hamiltonian having the prime numbers as quantum spectrum
holographic .

The generic eigenfunctions of $\hat{H}$ are then given by

$|\log p_{n}\rangle\,|\log m\rangle\,,$ (6)

which correspond to the eigenvalues $E_{n,m}\,\equiv\,\log p_{n}+\log m$.

The factorization problem of a natural number $N$ consists of finding the
primes entering its decomposition (2). In order to do so, our protocol
consists of the following steps.

  1. 1.

Take initially the logarithm of the number $N$ to be factorized, promote it to
be an eigenvalue of the Hamiltonian $\hat{H}$ and prepare the initial state
$|\log N\rangle$.

  2. 2.

For an integer $N$ – as the one given in Eq.(2) – made of $k$ distinct primes,
the corresponding energy level of $\hat{H}$ is $k$-fold degenerate, i.e. the
degeneracy of the level depends only on the number of distinct primes present
in $N$ and not on their multiplicities. Indeed, $\log N$ can be written in the
following $k$ different ways

$\displaystyle\log N$ $\displaystyle\,=\,$ $\displaystyle\log
p_{1}+\log\left(p_{1}^{a_{1}-1}p_{2}^{a_{2}}...p_{k-1}^{a_{k-1}}p_{k}^{a_{k}}\right)\,\equiv\,\log
p_{1}+\log\tilde{N}_{1}$ $\displaystyle\log N$ $\displaystyle\,=\,$
$\displaystyle\log
p_{2}+\log\left(p_{1}^{a_{1}}p_{2}^{a_{2}-1}..p_{k-1}^{a_{k-1}}p_{k}^{a_{k}}\right)\,\equiv\,\log
p_{2}+\log\tilde{N}_{2}$ $\displaystyle\cdots$ (7) $\displaystyle\log N$
$\displaystyle\,=\,$ $\displaystyle\log
p_{k}+\log\left(p_{1}^{a_{1}}p_{2}^{a_{2}}...p_{k-1}^{a_{k-1}}p_{k}^{a_{k}-1}\right)\,\equiv\,\log
p_{k}+\log\tilde{N}_{k}$

where $\tilde{N}_{a}\,\equiv\,N/p_{a}$ is the integer obtained dividing the
original number $N$ by one of its prime factor $p_{a}$.

  3. 3.

Hence, the generic state of the $k$-th degenerate manifold with energy $\log
N$ (here simply denoted as $|\log N\rangle$) admits the expansion

$|\log N\rangle\,=\,\sum_{a=1}^{k}c_{a}|\log p_{a}\rangle|\log
N_{a}\rangle\hskip 14.22636pt,\hskip
14.22636pt\sum_{a=1}^{k}|c_{a}|^{2}\,=\,1$ (8)

For a generic state, we can assume that all coefficients of this expansion are
different from zero. Their values are actually not essential for the running
of the algorithm, so one may assume to be randomly distributed, as would occur
in the case of a random initial state preparation.

  4. 4.

After the state (8) is prepared, measure $\hat{H}_{1}$. With all coefficients
$c_{a}$ different from zero, the output will be the logarithm of one of the
primes present in $N$, say $\log p_{b}$, with probability $|c_{b}|^{2}$.

  5. 5.

Once the result of this measurement is known, divide the original number $N$
by the prime $p_{b}$ identified by the output of the $\hat{H}_{1}$
measurement. In this way one obtains the lower integer
$\tilde{N}_{b}=N/p_{b}$. Then, start over, taking $\tilde{N}_{b}$ as the
integer to be factorized. The procedure will halt after a number of iterations
$l$ equal to the total number of primes present in $N$, i.e.

$I\,=\,\sum_{l=1}^{k}\alpha_{l}\,\,\,.$ (9)

Notice that the number of quantum measurements can be made equal to the number
of distinct factors substituting the previous point $5.$ with this new one

  1. 5.’

Once the result of this measurement is known, divide the original number $N$
by the prime $p_{b}$ identified by the output of the $\hat{H}_{1}$
measurement. In this way one obtains the lower integer $N/p_{b}$. Use a
classical computer to continue to divide for $p_{b}$ till the obtained number
is not longer divisible for $p_{b}$. In this way one obtains the multiplicity
$\alpha_{b}$ associated to the factor $p_{b}$. Then, start again the
procedure, taking $\tilde{N}_{b}=N/p_{b}^{\alpha_{b}}$ as the integer to be
factorized.

Figure 1: The graph associated to the various quantum measurements of
$\hat{H}_{1}$ which pin down the different prime factors of $N$. In the
example shown in the figure, the number to factorize is $N=231=3\times 7\times
11$. For simplicity, along the links of the graph, we indicate the primes
(rather than their logarithm) which are the outputs of the three stages
$A,B,C$ measurements of $\hat{H}_{1}$. One gets a complete factorisation
independently of the path associated to the chain of $\hat{H}_{1}$
measurements.

Four significant remarks are in order:

  * •

A primality test can be immediately implemented by performing a single quantum
measurement of $\hat{H_{1}}$ on the initial state $|\log N\rangle$. If the
system collapses (remains) in itself, $N$ is a prime.

  * •

A discussion on the preparation of the intial state is in the Supplementary
Materials.

  * •

If the multiplicity of the last factor, say $p_{k}$, to be factorized is $1$,
then the last operation with the measurement of $\hat{H}_{1}$ actually amounts
to apply the identity operator. If the multiplicity of different from $1$,
i.e. $\alpha_{k}>1$, then $\alpha_{k}$ subsequent quantum measurements of
$\hat{H}_{1}$ will produce each time with probability $1$ the same eigenstate
$|\log p_{k}\rangle$.

  * •

The successful implementation of the algorithm is guaranteed independently of
the $\hat{H}_{1}$ outputs obtained at the various stages of the algorithm. It
is a all roads lead to Rome procedure. As shown in Figure 1, there are
possible branches resulting from successive measurements of $\hat{H}_{1}$.
Imagine, for instance, that we want to factorize the number $N=231$, whose
prime decomposition is given by $N=3\times 7\times 11$. As a result of the
first measurement, we could have one of three possibie outputs: $\log 3$,
$\log 7$ or $\log 11$.

    1. 1.

If the first output is $\log 3$, the next integer to be factorized is
$\tilde{N}_{3}=77$ and the next measurement of $H_{1}$ starting from the (log)
of this number, can give, as output, either $\log 7$ or $\log 11$. Once this
last measurement is made, the next number is uniquely determined, thus
arriving to the complete factorization of the number $N=231$. It is easy to
see that the same conclusion will be reached if there is a different initial
output.

    2. 2.

If the first output is $\log 7$, the next integer to be factorized is
$\tilde{N}_{7}=33$ and the next measurement of $H_{1}$ starting from the (log)
of this number, can give, as output, either $\log 3$ or $\log 11$. Once this
last measurement is made, the next number is uniquely determined, thus
arriving to the complete factorization of the number $N=231$.

    3. 3.

If the first output is $\log 11$, the next integer to be factorized is
$\tilde{N}_{11}=21$ and the next measurement of $H_{1}$ starting from the
(log) of this number, can give, as output, either $\log 3$ or $\log 7$. Once
this last measurement is made, the next number is uniquely determined, thus
arriving at the complete factorization of the number $N=231$.

The key feature of this algorithm is the projective quantum measurements of
hermitian operators, such as the Hamiltonians we have employed. This leads to
an algorithm with the least possible number of operations, equal to $k$,
relative to the factorization of an integer made of $k$ primes, see below for
a discussion of this point.

Given that quantum mechanics is based on linear algebra while the mathematical
problem relative to factorization involves products, Hamiltonians with
logarithm of the primes as spectrum are very natural to study and have been
also used before Weiss ; Schleich1 ; Schleich2 ; Schleich . In more detail, a
thermally isolated non-interacting Bose gas loaded in a one-dimensional
potential with logarithmic energy eigenvalues was discussed in Weiss , where
asymptotic formulas for factorising products of different primes were
provided. Time-dependent perturbation in (possibly multiple copies of) a
potential having logarithms of the primes as eigenvalues was instead proposed
in Schleich1 ; Schleich2 ; Schleich , where the number $N$ to be factorized is
encoded in the frequency of a sinusoidally modulated interaction acting on the
ground-state of the potential. In this approach, if the integer is a product
of $k$ primes, one needs to prepare an ensemble of $k$ identical systems each
with an energy spectrum given by the logarithm of the primes Schleich .
Recently, a paper discussed the possible use of an Hamiltonian having as
eigenvalues the logarithm of the primes for search algorithm arm .

Our approach differs from the one discussed in Schleich  for two key features:
first, the presence of $\hat{H}_{2}$ in our Hamiltonian and, secondly, the use
of quantum measurements. Employing our Hamiltonian, made of a piece relative
to the logarithm and another one relative to the logarithm of the integers, it
is possible to factorize an integer $N$ without knowing a-priori the number
$k$ of distinct primes (and their multicplicities) this number $N$ is made of.

Concerning the quantum measurement of $\hat{H}_{1}$, one could use the von
Neumann scheme vonN , which consists of setting up a coupling with a test
particle of the form $\hat{p}\,\hat{O}$, where $\hat{p}$ is the momentum
operator of the test particle and $\hat{O}$ the operator to be measured. In
our case, those quantum measurements can be performed in a slightly different
way following the gedanken experiment discussed in the Supplementary
Materials.

Quantum Potentials.  Let’s now discuss how to implement in a laboratory the
algorithm described in the previous section. One possibility is to adopt a
digital route: this consists of implementing a discrete quantum register of
two-level systems, such spin-$1/2$. This can be done with a quantum ladder,
where in the first leg one constructs the Hamiltonian $\hat{H}_{1}$ whose
eigenvalues are the logarithms of the primes, while in the second leg the
Hamiltonian $\hat{H}_{2}$ whose eigenvalues are the logarithms of the
integers. Both legs should have $d$ spins. The eigenvalues should be
respectively the logarithms of the first $2^{d}$ primes and the logarithms of
the first $2^{d}$ integers. Given the current trend of quantum computing
technology, this seems the simplest thing to do. However, as discussed in more
detail in the Supplementary Materials, this digital implementation of our
algorithm has the following bottleneck: while realising $\hat{H}_{2}$ is an
easy task (since it consists of fixing a number of couplings which is linear
in $d$), realizing $\hat{H}_{1}$ needs instead to tune an exponential number
of long-range, many-body couplings between the qubits, and it is fair to say
that this obstacle seems unlikely to be overcome soon, at least with the
present technology. Even more, the tuning of this exponential number of long-
range, multi-body couplings is not a scalable protocol: if they are known for
a certain number $d$ of qubits, due to the peculiar behaviour of the primes
one cannot expect to use this knowledge to fix the couplings for the $(d+1)$
qubit system.

Let’s now look at the implementation of our algorithm adopting the analog
route in terms of Schrödinger Hamiltonians. This is similar to what has been
done recently holographic  for a quantum potential of the primes. Hence, we
will deal with Hamiltonians of a particle of mass $m$ of the form
$\hat{H}\,=p^{2}/2m+V(x)$ with their eigenvalues determined by the Schrödinger
equation $\hat{H}\psi_{n}=e_{n}\psi_{n}$.

A potential ${\cal V}_{N}(x)$ entering a Schrödinger Hamiltonian with a finite
and assigned number of eigenvalues $\\{e_{0},e_{1},...,e_{M}\\}$ can be
constructed using methods of Supersymmetric Quantum Mechanics (SQM) SUSYKhare
; QMprime1 ; QMprime2 . The procedure consists of solving iteratively the non-
linear differential equations for the sequence of superpotentials $W_{k}(x)$

$W_{k}^{\prime}(x)-W^{2}_{k}(x)+{\mathscr{V}}_{k-1}(x)=\tilde{E}_{k}\quad\quad,\quad\quad
k=1,...,M\,\,\,,$ (10)

where $\tilde{E}_{k}=e_{M-k}-e_{M}$ are the negative spacings computed from
the highest eigenvalue $e_{M}$, where the potential ${\cal V}_{k}(x)$ is
obtained iteratively from

${\cal V}_{k}(x)=2\tilde{E}_{k}+2W^{2}_{k}(x)-{\cal V}_{k-1}(x)\,\,\,.$ (11)

The initial condition is set to be $W_{k}(0)=0$ as well as ${\cal V}_{0}(x)=0$
so that $e_{0}=0$. Substituting iteratively the ${\cal V}_{k}(x)$ of (11) in
(10), one gets a system of nonlinear differential equations for the $W_{k}$.
The potentials ${\cal V}_{k}(x)$ for $k=1,...,N-1$ are just intermediate steps
of the computation since the final potential ${\cal V}_{M}(x)$, to be
determined iteratively in $M$ steps. which accommodates all energy eigenvalues
can be constructed using only $W_{k}(x)$. This procedure can be easily
implemented to compute the potential $V(x)={\cal V}_{M}$ such that
$\hat{H}=p^{2}/2m+V(x)$ has as eigenvalues the set of assigned values
$\\{e_{0},e_{1},...,e_{M}\\}$. For instance, such a set can be of the first
$M$ primes holographic ; QMprime2  or the logarithm of the first $M$ primes
mack10 .

To conclude the implementation of our algorithm, let’s then define the
potentials $V_{1}(x)$ and $V_{2}(y)$ entering the two Schrödinger Hamiltonians
$\hat{H}_{1}$ and $\hat{H}_{2}$ of the previous section111It is worth to
recall that the both potentials $V_{1}(x)$ and $V_{2}(y)$ can be also
constructed in a semi-classical approximationGMscattering  for all primes and
integers.

$\hat{H}_{1}(x)\,=\,\frac{p_{x}^{2}}{2m}+V_{1}(x)\,\,\,\,\,\,\,,\,\,\,\,\,\,\,\hat{H}_{2}(y)\,=\,\frac{p_{y}^{2}}{2m}+V_{2}(y)\,\,\,,$
(12)

where $p_{x}$ and $p_{y}$ are the $x$ and $y$ components of its momentum, and
such $\hat{H}_{1}$ ($\hat{H}_{2}$) has as eigenvalues the logarithm of the
first $2^{d}$ primes (respectively, the logarithm of the first $2^{d}$
integers). The plot of $V_{1}(x)$ and $V_{2}(y)$ in a specific case is
reported in SM 4. Incidentally, if the Goldbach conjecture were true, taking
the same Hamiltonian $\hat{H}_{1}$ in both the $x$ and $y$ direction, i.e.
${\cal H}=\hat{H}_{1}(x)+\hat{H}_{1}(y)$, the spectrum of ${\cal H}$ would be
given by the logarithms of all even numbers.

Discussion on computational complexity.  Once the potentials described above
are experimentally realised, one can use the two Hamiltonians $\hat{H}_{1}$
and $\hat{H}_{2}$ to build up the Hamiltonian
$\hat{H}=\hat{H}_{1}+\hat{H}_{2}$ and proceed to factorize the integers $N$
below the cut-off $M$ through a sequence of $\hat{H}_{1}$ measurements. So,
for example, if $N$ is a product of $3$ primes, only three quantum
measurements are needed. One can show that $k$ is clearly the lower bound of
operations to factorize an integer, independently from quantum mechanics.
Indeed, suppose that the integer $N$ has the form (2) and that one is given
the information that $p_{1},\cdots,p_{k}$ are its factors. To verify it, one
divide by one of them, say $p_{1}$, and continue by it till it is possible
($\alpha_{1}+1$ divisions), and so on, for a total of
$\sum_{i=1}^{k}\alpha_{i}+k$ divisions. If one is also provided the
information about the multiplicities, then only $k$ divisions are needed. In
the latter case, the last division is trivial.

The procedure proposed here saturates such lower bound. Indeed, from the first
quantum measurement one gets one of the factors, and then divide $N$ (e.g.
using a classical computer) by the latter till the obtained number is not
longer divisible. Iterating this way one needs $k$ quantum measurements (the
last, $k$-th, being equal to the identity) and $\sum_{i=1}^{k}\alpha_{i}$
divisions on the classical computer. One sees that the factorization based on
quantum measurements saturates the lower bound, whether the multiplicities are
given or they are not.

There is however a question to face: if the Shor algorithm has a complexity
scaling with $O(\log N)$, i.e. of the number of digits, how how reconciled or
put in relation with the fact that our scheme has a complexity of order
$O(k)$, i.e. of the number of factors of $N$? As shown in the following, the
answer is interesting and related to how the algorithm can be run. The
difference $O(\log N)$ vs. $O(k)$ is emerging if one has a device in which the
quantum measurement of an operator with assigned spectrum is physically
possible. But, if such device is not at hand, and since one needs an operator
having as eigenvalues the logarithms of the primes and another with the
logarithms of the integers, one physically needs a device in which such
operators with assigned spectra are implemented. The following discussion will
show that – if this device is not given and has to be implemented from scratch
– one is subjected again to a complexity which is essentially $O(\log N)$,
with some extra features discussed below.

One has to realise that the determination of a final potential such as
$V_{M}(x)$ with $M$ energy eigenvalues $e_{k}$ ($k=1,2,\ldots M$) has an
algorithm complexity equal to $M$, because this is the number of differential
equations to solve. Hence, in the presence of an exponential number of energy
levels, there will be an exponential number of differential equations to solve
to accommodate these levels. If this would be true, even though at a software
level our algorithm has a finite degree of complexity, at its hardware level
(i.e. to physically build the device) its complexity would grow exponentially.
However, there is a very interesting way to cure the rapid exponential growth
of complexity at the hardware level. The remedy comes from a result by Lloyd
et al. lloyd  who showed that a system of $M$, possibly non-linear,
differential equations of the form

$\frac{d\vec{W}}{dx}+\mathbf{f}(W)\cdot\vec{W}=\vec{b}$ (13)

where $\mathbf{f}$ is a $M\times M$ matrix and $\vec{b}$ is a constant vector,
can be solved on a quantum computer in $\log M$ number of steps! Namely, there
is an exponential speed up which turns our problem to adjust an exponential
number $2^{d}$ of eigenvalues in each of the Hamiltonians $H_{1}$ and $H_{2}$
in terms of only $d$ computational steps.

Remarkably enough, the system of differential equations from supersymmetric
quantum mechanics can be recast exactly as in eq. (13) by taking
$\vec{W}=(W_{1},...,W_{M})^{T}\in\mathbb{R}^{M}$, and the entries of the
(triangular) matrix $\mathbf{f}$ and the vector $\vec{b}$ given by

$f_{ab}\,=\,\left\\{\begin{array}[]{llll}0&,&&a>b\\\ -W_{a}&,&&a=b\\\
(-1)^{a}2W_{b}&,&&a<b\end{array}\right.\,\,\,\,\,\,\,\,\,,\,\,\,\,\,\,\,\,\,b_{k}=\tilde{E}_{k}+\sum^{k-1}_{i=1}(-1)^{i}2\tilde{E}_{k-i}\,\,\,.$
(14)

Notice that, in the digital implementation of our algorithm, where
$\hat{H}_{1}$ is a spin Hamiltonian of $d$ quantum spins, one has to solve an
exponential number of linear algebraic equations. This ensures that the
eigenvalues are the first $2^{d}$ primes, or their logarithms. So, one could
use the quantum computer matrix inversion algorithm to solve them in order of
$d$ steps. The point is that one has to physically implement an exponential
number of multi-body, arbitrarily long-range couplings among the spins – which
must be contrasted with the analog implementation of the potentials $V_{1}$
and $V_{2}$, where the only limitation is provided by the resolution we can
reach to realize them.

We conclude that the exponential growth of complexity at the hardware level
for our procedure can be cured in digital form by using a (true) quantum
computer, when available. This argument shows that the factorization protocol
in terms of quantum measurements presented here and the Shor algorithm have
similar complexity of $O(\log N)$. However, comparing in more detail the two
algorithms, their pros and cons are the following: the Shor algorithm could
run on a multi-purpose quantum computer and will take each time $O(\log N)$
steps to factorize a number $N$. On the contrary, our algorithm could run on a
dedicated (not multi-purpose) device, which can be set up by solving, once for
all, on a quantum computer a system of differential equations in $O(\log N)$
steps. Once this dedicated device has been set up, it perform factorization an
integer $N$ in $k$ steps, $k$ being the number of prime factors, which is the
least possible number of steps. It would be interesting to see if such devices
can be used to solve other cryptographic and number theory problems in the
future.

Acknowledgments – The authors thank D. Bernard, M. Berry, J. L. Cardy, D.
Cassettari, A. Schwimmer and A. Smerzi for useful discussions and
correspondence. GM acknowledges the grants PNRR MUR Project PE0000023-NQSTI
and PRO3 Quantum Pathfinder. AT acknowledges MIT for kind hospitality during
the writing of the final part of the manuscript. He also acknowledges the MIT-
FVG Seed Fund Collaboration Grant ”Non-Equilibrium Thermodynamics of
Dissipative Quantum Systems”.

Supplementary Material 1 - Preparation of the initial state

To prepare the state $|\log N\rangle$ one can also employ the quantum
measurements’ projective nature. Namely, one can start with a state
$|\Psi\rangle$ belonging to an ensemble with the expectation value of the
energy equal to $\log N$: $\langle\Psi|\hat{H}|\Psi\rangle=\log N$ and
variance $\Delta$. If $\Delta$ is quite narrow, the expansion of this state in
eigenstates of $H$ will involve only a few terms nearby the eigenvalues $\log
N$, i.e.

$\mid\Psi\rangle\,=\,\sum_{\tilde{N}\in\\{N-\Delta,N+\Delta\\}}\gamma_{n}\,\mid\log\tilde{N}\rangle\,\,\,.$
(15)

If we measure $\hat{H}$ on this state, the measurement causes the system
collapse on one of the eigenstates of $\hat{H}$ entering (15). If the
measurement output is $\log N$, we can start the procedure described above. If
not, we re-prepare the state and re-measure $\hat{H}$ since, sooner or later
the expected value will appear. Clearly, the number of iterations depends on
the variance of $\hat{H}$ on $\Psi$. Another strategy could be to measure
$\hat{H}_{1}$ on $\Psi$ and verify whether the state collapses on a factor of
the integer $N$.

Supplementary Material 2 - Examples of $\hat{H}_{1}$

In both digital and analog versions of the algorithm presented in the main
text, the requirements are: a) the implementation of an operator $\hat{O}$ sum
of two operators $\hat{O_{1}}$ and $\hat{O}_{2}$ having as eigenvalues,
respectively, the logarithms of the prime numbers and of the integer numbers;
and b) the possibility to perform quantum measurements of $\hat{O}_{1}$.

Let’s discuss the digital setting, referring to the main text for the analog
case. We assume then that we have two registers, denoted by $1$ and $2$, of
$d$ qubits each, labeled by the index $j=1,\cdots,d$. The observable
$\hat{O}_{1}$ acts only on register $1$, and similarly $\hat{O}_{2}$ acts only
on register $2$, where the first operator has, as eigenvalues, the (natural)
logarithms of the first $2^{d}$ primes starting from prime $2$, while the
second operator has, as eigenvalues, the (natural) logarithms of the first
$2^{d}$ natural numbers.

To fix the notation, let discuss the operators $\hat{\cal O}_{1}$ and
$\hat{\cal O}_{2}$ having as eigenvalues respectively the first $2^{d}$ prime
number and the first $2^{d}$ integers. Formally one can then implement the
desired operators $\hat{O}_{1}$ and $\hat{O}_{2}$, since the former (latter)
has the same eigenvalues of $\hat{\cal O}_{1}$ and $\hat{\cal O}_{2}$.

To build $\hat{\cal O}_{2}$ is considerably easier – actually, exponentially
easier than to construct $\hat{\cal O}_{1}$. First of all, let’s consider in
the second register the operator Nielsen2010

$\hat{Z}_{j}=\mathbb{1}\otimes\mathbb{1}\otimes\cdots\otimes\stackrel{{\scriptstyle\stackrel{{\scriptstyle
j}}{{\downarrow}}}}{{Z}}\otimes\cdots\mathbb{1}$

where

$\mathbb{1}=\begin{pmatrix}1&0\\\
0&1\end{pmatrix}\,\,\,\,\,\,\,\,\,,\,\,\,\,\,\,\,\,\,Z=\begin{pmatrix}1&0\\\
0&-1\end{pmatrix}$

and the symbol $\otimes$ denotes the tensor product between matrices 222We
remind for convenience that if one has two matrices $A_{ij}$ and
$B_{i^{\prime}j^{\prime}}$, then the matrix $A\otimes B$ has as matrix
elements $(A\otimes B)_{ii^{\prime},jj^{\prime}}=A_{ij}\cdot
B_{i^{\prime}j^{\prime}}$, so that, e.g., $Z\otimes\mathbb{1}$ is the $4\times
4$ matrix $\begin{pmatrix}\mathbb{1}&\mathbb{0}\\\
\mathbb{0}&-\mathbb{1}\end{pmatrix}$ written as a block matrix, where
$\mathbb{0}$ is the $2\times 2$ matrix $\mathbb{0}=\begin{pmatrix}0&0\\\
0&0\end{pmatrix}$.. It is then clear that the $\hat{Z}_{j}$ are $2^{d}\times
2^{d}$ matrices and correspond to the observable $z$-component of the $j$-th
spin Sakurai2020 . Let’s now define the $2\times 2$ matrix ${\cal
N}=(\mathbb{1}+Z)/2=\begin{pmatrix}1&0\\\ 0&0\end{pmatrix}$, having evidently
$0$ and $1$ as eigenvalues, and the corresponding matrices

$\hat{{\cal
N}}_{j}=\mathbb{1}\otimes\mathbb{1}\otimes\cdots\otimes\stackrel{{\scriptstyle\stackrel{{\scriptstyle
j}}{{\downarrow}}}}{{\cal{N}}}\otimes\cdots\mathbb{1}\,\,\,.$

One can immediately show that the operator

$\hat{\cal O}_{2}=2\,\hat{\mathbb{1}}_{d}+\sum_{j=1}^{d}2^{j-1}\hat{{\cal
N}}_{j}$ (16)

has as eigenvalues the first $2^{d}$ integers starting from $2$, with
$\hat{\mathbb{1}}_{d}=\mathbb{1}\otimes\mathbb{1}\otimes\cdots\otimes\mathbb{1}$
being the $2^{d}\times 2^{d}$ identity matrix. The rationale is that the sum
$\sum_{j}2^{j-1}\hat{{\cal N}}_{j}$ in (16) gives the binary representation of
the numbers from $0$ to $2^{d}-1$. For example, for $d=3$, the operator
$2^{0}\hat{N}_{1}+2^{1}\hat{N}_{2}+2^{2}\hat{N}_{3}$ has the eigenvalues
$0,1,2,3,\cdots,7$, as one can immediately verify. So it remains to sum to
(16) only the constant $2$.

Let now come to $\hat{{\cal O}}_{1}$. A strategy to give $\hat{{\cal O}}_{1}$
in terms of the operators $\hat{{\cal N}}_{i}$’s is to write all possible
multi-spin operators in which the $\hat{{\cal N}}_{i}$ enter $0$ times, $1$
times, $2$ times, $3$ times and so on. Borrowing the notation from treatments
of one-dimensional spin chains with multi-spin interactions, see e.g. Gori2011
, one can write

$\hat{\cal
O}_{1}=j_{\emptyset}\,\hat{\mathbb{1}}_{d}+\sum_{i_{1}}j_{i_{1}}\hat{N}_{i_{1}}+\sum_{i_{1},i_{2}}j_{i_{1},i_{2}}\hat{N}_{i_{1}}\hat{N}_{i_{2}}+$
$+\sum_{i_{1},i_{2},i_{3}}j_{i_{1},i_{2},i_{3}}\hat{N}_{i_{1}}\hat{N}_{i_{2}}\hat{N}_{i_{3}}+\cdots+j_{i_{1},i_{2},i_{3},\cdots,i_{m}}\hat{N}_{i_{1}}\hat{N}_{i_{2}}\cdots\hat{N}_{i_{m}}\,,$
(17)

with all sums run from $1$ to $d$. Now the statement is that one can choose
the coefficients $\left\\{j_{\mu}\right\\}$ such that the the eigenvalues of
$\hat{\cal O}_{1}$ are exactly the first $2^{d}$ primes, since the total
number of the coefficients $\left\\{j_{\mu}\right\\}$ is exactly $2^{d}$: to
do so, one has to solve a linear system of $2^{d}$ equations in the unknowns
$\left\\{j_{\mu}\right\\}$ using the first $2^{d}$ primes are the input.

For instance, in the case $d=3$, with the values of the coefficients given by

$j_{\emptyset}=2\,\,,\,\,j_{1}=1\,\,,\,\,j_{2}=3\,\,,\,\,j_{3}=5\,\,,\\\
j_{12}=5\,\,,\,\,j_{23}=3\,\,,\,\,j_{13}=9\,\,,\,\,j_{123}=-9$

one gets the first $2^{3}=8$ primes $2,3,5,7,11,13,17,19$.

Up to $d=5$, the explicit expressions of $\hat{\cal O}_{1}^{(d)}$ having the
first $2^{d}$ primes starting from $p=2$ and defined on $d$ qubits are given
by

$\displaystyle\hat{\cal O}_{1}^{(2)}$ $\displaystyle=$ $\displaystyle
2\hat{\mathbb{1}}+1\hat{N}_{1}+3\hat{N}_{2}+1\hat{N}_{1}\hat{N}_{2}$
$\displaystyle\hat{\cal O}_{1}^{(3)}$ $\displaystyle=$ $\displaystyle
2\mathbb{1}_{3}+1\hat{N}_{1}+3\hat{N}_{2}+5\hat{N}_{3}+5\hat{N}_{1}\hat{N}_{2}+3\hat{N}_{2}\hat{N}_{3}+9\hat{N}_{1}\hat{N}_{3}-9\hat{N}_{1}\hat{N}_{2}\hat{N}_{3}$
$\displaystyle\hat{\cal O}_{1}^{(4)}$ $\displaystyle=$ $\displaystyle
2\hat{\mathbb{1}}_{4}+1\hat{N}_{1}+3\hat{N}_{2}+5\hat{N}_{3}+9\hat{N}_{4}+7\hat{N}_{1}\hat{N}_{2}+9\hat{N}_{1}\hat{N}_{3}+7\hat{N}_{1}\hat{N}_{4}+13\hat{N}_{2}\hat{N}_{3}+$
$\displaystyle+$ $\displaystyle
15\hat{N}_{2}\hat{N}_{4}+15\hat{N}_{3}\hat{N}_{4}-3\hat{N}_{1}\hat{N}_{2}\hat{N}_{3}-3\hat{N}_{1}\hat{N}_{2}\hat{N}_{4}-5\hat{N}_{1}\hat{N}_{3}\hat{N}_{4}-15\hat{N}_{2}\hat{N}_{3}\hat{N}_{4}-7\hat{N}_{1}\hat{N}_{2}\hat{N}_{3}\hat{N}_{4}$
$\displaystyle\hat{\cal O}_{1}^{(5)}$ $\displaystyle=$ $\displaystyle
2\mathbb{1}_{5}+1\hat{N}_{1}+3\hat{N}_{2}+5\hat{N}_{3}+9\hat{N}_{4}+11\hat{N}_{5}+11\hat{N}_{1}\hat{N}_{2}+11\hat{N}_{1}\hat{N}_{3}+11\hat{N}_{1}\hat{N}_{4}+15\hat{N}_{1}\hat{N}_{5}+$
$\displaystyle+$ $\displaystyle
21\hat{N}_{2}\hat{N}_{3}+23\hat{N}_{2}\hat{N}_{4}+25\hat{N}_{2}\hat{N}_{5}+27\hat{N}_{3}\hat{N}_{4}+29\hat{N}_{3}\hat{N}_{5}+31\hat{N}_{4}\hat{N}_{5}+5\hat{N}_{1}\hat{N}_{2}\hat{N}_{3}+\hat{N}_{1}\hat{N}_{2}\hat{N}_{4}-\hat{N}_{1}\hat{N}_{2}\hat{N}_{5}+$
$\displaystyle+$ $\displaystyle
5\hat{N}_{1}\hat{N}_{3}\hat{N}_{4}-\hat{N}_{1}\hat{N}_{3}\hat{N}_{5}-1\hat{N}_{1}\hat{N}_{4}\hat{N}_{5}-7\hat{N}_{2}\hat{N}_{3}\hat{N}_{4}-7\hat{N}_{2}\hat{N}_{3}\hat{N}_{5}-7\hat{N}_{2}\hat{N}_{4}\hat{N}_{5}-13\hat{N}_{3}\hat{N}_{4}\hat{N}_{5}+$
$\displaystyle-$ $\displaystyle
25\hat{N}_{1}\hat{N}_{2}\hat{N}_{3}\hat{N}_{4}-23\hat{N}_{1}\hat{N}_{2}\hat{N}_{3}\hat{N}_{5}-25\hat{N}_{1}\hat{N}_{2}\hat{N}_{4}\hat{N}_{5}-29\hat{N}_{1}\hat{N}_{3}\hat{N}_{4}\hat{N}_{5}-25\hat{N}_{2}\hat{N}_{3}\hat{N}_{4}\hat{N}_{5}+49\hat{N}_{1}\hat{N}_{2}\hat{N}_{3}\hat{N}_{4}\hat{N}_{5}$

E.g., one can directly verify that the eigenvalues of $\hat{\cal O}_{1}^{(5)}$
are the first $2^{5}=32$ primes

$p=2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,71,73,79,83,89,97,101,103,107,109,113,127,131$

In the course of our analysis we observe the emergence of some regularity:
first of all that the coefficients are relative integers moreover taht
$j_{\emptyset}=2$, $j_{i}=p_{i}-2$, where $p_{i}$ is the $i$th prime and,
finally, that increasing the number of qubits implies that the $j_{\mu}$ pass
form positive to negative values. But, at the same time, we notice that there
is no simple pattern of the remaining coefficients $\left\\{j_{\mu}\right\\}$:
if one has the coefficients $\left\\{j_{\mu}\right\\}$ for a certain value of
$d$, it seems that there is no a simple procedure to get the
$\left\\{j_{\mu}\right\\}$ relative to $d+1$. After all this is not
surprising, since we know that even very effective ways to plot the primes can
display striking regularities (see, for instance, the pattern emerging from
Ulam spiralsUlam ), but they cannot predict the $d$-prime simply by knowing
the first $d-1$ primes. In other words, to determine for each $d$ the
coefficients $\left(j_{\mu}\right\\}$ one has to solve a system with $2^{d}$
unknowns assuming that we know the first $2^{d}$ primes.

A way to visualize the coefficients $\left\\{j_{\mu}\right\\}$ is to put in a
table like the following, where the coefficients are written in the form
$j_{i_{1},\cdots,i_{k}}$ with $i_{1}<i_{2}<\cdots<i_{k}$, ordering them in a
way that among two $k$ tuples $(i_{1},\cdots,i_{k})$ and
$(j_{1},\cdots,j_{k})$, the one with the smallest among $i_{1}$ and $j_{1}$ is
listed before, and if $i_{1}=j_{1}$ then the one with the smallest among
$i_{2}$ and $j_{2}$ is listed before, and so one. Therefore, for $k=3$ and
$m=5$, we report in the table the values of $j_{123}$, $j_{124}$, $j_{125}$,
$j_{134}$, $j_{135}$, $j_{145}$, $j_{234}$, $j_{235}$, $j_{245}$, $j_{345}$.

m $\to$ | 2 | 3 | 4 | 5
---|---|---|---|---
$j_{\emptyset}$ | 2 | 2 | 2 | 2
$j_{i}$ | 1, 3 | 1,3,5 | 1,3,5,9 | 1,3,5,9,11
$j_{ij}$ | 1 | 5, 3, 9 | 7, 9, 7, 13, 15, 15 | 11, 11, 11, 15, 21, 23, 25, 27, 29, 31
$j_{ijk}$ | 0 | -9 | -3,-3,-5,-15 | 5,1,-1,5,-1,-1,-7,-7,-7,-13
$j_{ijkl}$ | 0 | 0 | -7 | -25,-23,-25,- 29,-25
$j_{ijklm}$ | 0 | 0 | 0 | 49

Similarly to what we described above, one could determine the couplings $j$’s
in such a way that $\cal{O}_{1}$ has as eigenvalues the logartithm of the
first $2^{d}$ primes: in the few attempts we have done, their values appear
erratic as well.

Supplementary Material 3 - Gedankenexperiment

In this section we discuss a Gedankenexperiment for implementing the
measurement procedure discussed in Section 2. First of all, let’s imagine that
the Hamiltonians $H_{1}$ and $H_{2}$ are realised, as in holographic , in
terms of some laser optical device. We put together this optical device inside
a metallic box $S$ and transfer an electric charge $Q$ on it so that this
metallic box acts as a Faraday cage which isolates the quantum system inside
the box from external perturbations. From an outside, such a metallic box $S$
can simply be characterised in terms of its electric charge $Q$ and its mass
$M$. The mass $M$ is made by the mass $m_{b}$ of the metallic box and the
quantum energy levels occupied by the particle, assuming the equivalence
between masses and energies (in the following we take the units such that the
speed of light is equal to 1, $c=1$). Being the Hamiltonian $H$ made of two
commuting Hamiltonians $H_{1}(x)$ and $H_{2}(y)$ along the axes $x$ and $y$,
the system the have two different inertias regarding the two axes: if
$e^{(1)}_{i}$ and $e^{(2)}_{j}$ denote the $i$-th and the $j$-th energies
along the $x$ and the $y$ axis, there will be an horizontal mass
$M_{x}=m_{b}+e^{(1)}_{i}$ and a vertical mass $M_{y}=m_{b}+m^{(2)}_{k}$.

Figure 2: Mass spectrometer which permits to measure the horizontal mass
$M_{x}$ of the system $S$ and therefore to project on one of the horizontal
energy eigenstate $|e^{(1)}_{a}\,\rangle$.

We can send our system $S$ to a mass spectrometer, such as the one shown in
Figure 2. Such a classical apparatus will set up a Stern-Gerlach experiment
and we can measure the energy projectively. Indeed, skipping the details of
the motion, the system $S$ trajectory is determined by the ratio $Q/M_{x}$.
Hence, if the system $S$ is in a linear superposition of $k$ energy
eigenstates of $H_{1}(x)$ (as it is indeed the case for our vector (8))

$|\psi\,\rangle\,=\,\sum_{i=1}^{k}a_{i}|e^{(1)}_{i}\,\rangle\,\,\,,$ (18)

then, when the system $S$ passes through the mass spectrometer, it will end up
in one of the $k$ different trajectories $\\{T_{1},T_{2},\ldots T_{k}\\}$, as
shown in Figure 2. Imagine that the system ends following the $a$-th
trajectory, then after the passage through the mass spectrometer, the system
is projected on the energy eigenstate $|e^{(1)}_{a}\,\rangle$.

Supplementary Material 4 - Potentials $V_{1}$ and $V_{2}$

In Figure 3 we show the plots of $V_{1}(x)$ and $V_{2}(y)$ with a spectrum
given respectively by $\log p_{k}$ and $\log m$ for the first $M=64=2^{6}$
energy levels of each potential.

Figure 3: Plots of the potentials $V_{1}(x)$ (a) and $V_{2}(y)$ (b) relative
to $N=64=2^{5}$ energy levels given respectively by the logarithm of the
primes, $\log p_{k}$, and the logarithm of the integers, $\log m$.

## References

  * (1) M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th anniversary edition (Cambridge University Press, Cambridge, 2010).
  * (2) J. Preskill, Lecture Notes for Physics 229:Quantum Information and Computation.
  * (3) A. O. Pittenger, An Introduction to Quantum Computing Algorithms (Birkhäuser, Boston, 2000).
  * (4) R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki, Rev. Mod. Phys. 81, 865 (2009).
  * (5) P. W. Shor, in Proceedings of the 35th Annual Symposium on the Foundations of Computer Science, ed. S.Goldwasser (IEEE Computer Society, Los Alamitos, 1994), p. 124.
  * (6) P. W. Shor, Phys. Rev. A 52, R2493 (1995).
  * (7) A. Ekert and R. Jozsa, Rev. Mod. Phys. 68, 733 (1996).
  * (8) A. Peres, Quantum theory: concepts and methods (Kluwer, Dordrecht, 1993).
  * (9) R. Shankar, Principles of quantum mechanics, 2nd edition (Plenum, New York, 1994).
  * (10) J. J. Sakurai, Modern quantum mechanics, 3rd edition revised by J. Napolitano (Cambridge University Press, Cambrdige, 2020).
  * (11) G. Mussardo, The Quantum Mechanical Potential for the Prime Numbers, `arXiv:cond-mat/9712010`.
  * (12) D. Cassettari, G. Mussardo, A. Trombettoni Holographic Realization of the Prime Number Quantum Potential, https://arxiv.org/abs/2202.03446.
  * (13) Y. Wu et al., Phys. Rev. Lett. 127, 180501 (2021).
  * (14) L. M. Vandersypen, M. Steffen, G. Breyta, C. S. Yannoni, M. H. Sherwood, and I. L. Chuang, (2001), Nature 414, 883 (2001).
  * (15) C.-Y. Lu, D. E. Browne, T. Yang, and J.-W. Pan, Phys. Rev. Lett. 99, 250504 (2007).
  * (16) B. P. Lanyon, T. J. Weinhold, N. K. Langford, M. Barbieri, D. F. V. James, A. Gilchrist, and A. G. White, Phys. Rev. Lett. 99, 250505 (2007).
  * (17) E. Lucero, R. Barends, Y. Chen, J. Kelly, M. Mariantoni, A. Megrant, P. O’Malley, D. Sank, A. Vainsencher, J. Wenner, T. White, Y. Yin, A. N. Cleland, and J. M. Martinis, Nat. Phys. 8, 719 (2012).
  * (18) E. Martín-López, A. Laing, T. Lawson, R. Alvarez, X.-Q. Zhou, and J. L. O’Brien, Nat. Photonics 6, 773 (2012).
  * (19) P. Ribenboim, The New Book of Prime Number Records, Springer-Verlag, Berlin-New York (1996).
  * (20) M.R. Schroeder, Number Theory in Science and Communication, Springer–Verlag, Berlin (1990).
  * (21) D. Zagier, Math. Intelligencer 0, 7 (1977).
  * (22) A. Granville and G. Martin, Prime Number Races, American Mathematical Monthly. 113 (1), 1–33 (2006).
  * (23) H.E. Rose, A Course in Number Theory, Oxford Science Publications (1994).
  * (24) G.H. Hardy and E.M. Wright, An Introduction to Theory of Numbers, Oxford University Press (1979).
  * (25) T.M. Apostol, Introduction to Analytic Number Theory, 5th ed., Springer, New York (1998).
  * (26) T. Tao, Structure and Randomness in the Prime Numbers in An Invitation to Mathematics, eds. D. Schleicher and M. Lackmann, Springer (2011).
  * (27) O. Ore, Number Theory and its History, McGraw–Hill, New York (1948).
  * (28) G.F. B. Riemann, Über die Anzahl der Primzahlen unter einer gegebenen Grösse, Monatsber. Königl. Preuss. Akad. Wiss. Berlin, 671-680 (Nov. 1859).
  * (29) H.M. Edwards, Riemann Zeta Function, Academic Press, New York (1974).
  * (30) P. Borwein, S. Choi, B. Rooney, A. Weirathmueller, The Riemann Hypothesis: A Resource for the Afficionado and Virtuoso Alike, Springer (2007).
  * (31) J. Hadamard, Sur la distribution des zéros de la fonction zeta(s) et ses conséquences arithmétiques, Bull. Soc. Math. France 24, 199-220 (1896).
  * (32) C.J. de la Vallée Poussin, Recherches analytiques la théorie des nombres premiers, Ann. Soc. Scient. Bruxelles 29, 183-256 (1896).
  * (33) A. Selberg, An Elementary Proof of the Prime Number Theorem, Ann. Math. 50, 305-313 (1949).
  * (34) P. Erdős, Démonstration élémentaire du théorème sur la distribution des nombres premiers, Scriptum 1, Centre Mathématique, Amsterdam (1949).
  * (35) Lasse Rempe-Gillen, Rebecca Waldecker, Primality testing for beginners, American Mathematical Society, 2014
  * (36) M. Agrawal, N. Kayal, and N. Saxena, Primes is in P, Annals of Mathematics, 160 (2004), 781–79;
  * (37) Lenstra, Arjen K. (2011), Integer Factoring, in van Tilborg, Henk C. A.; Jajodia, Sushil (eds.), Encyclopedia of Cryptography and Security, Boston, MA: Springer US, pp. 611–618.
  * (38) Richard Crandall and Carl Pomerance (2001). Prime Numbers. A Computational Perspective. Springer.
  * (39) Samuel S. Wagstaff Jr. (2013). The Joy of Factoring. Providence, RI: American Mathematical Society.
  * (40) G.Mussardo, A. Trombettoni and Z. Zhang, Prime Suspects in a Quantum Ladder, Phys.Rev.Lett. 125 (2020) 240603.
  * (41) R. Mack, J. P. Dahl, H. Moya-Cessa, W. Strunz, R. Walser, and W. P. Schleich, Phys. Rev. A 82, 032119 (2010).
  * (42) C. Weiss, S. Page, and M. Holthaus, Physica A 341, 586 (2004).
  * (43) F. Gleisberg, R. Mack, K. Vogel, and W. P. and Schleich, New J. Phys. 15, 023037 (2013).
  * (44) F. Gleisberg, M. Volpp, and W. P. Schleich, Phys. Lett. A 379, 2556 (2015).
  * (45) F. Gleisberg, F. Di Pumpo, G. Wolff, and W. P. Schleich, J. Phys. B: At. Mol. Opt. Phys. 51, 035009 (2018).
  * (46) A. E. Allahverdyan and D. Petrosyan, Dissipative search of an unstructured database, Phys. Rev. A 105, 032447 (2022).
  * (47) J. von Neumann, Mathematical Foundations of Quantum Mechanics, Princeton Univ. Press, Prince- ton, N.J., 1955.
  * (48) F. Cooper, A. Khare, U. Sukhatme, Supersymmetry and Quantum Mechanics, Phys. Rep. 251, 267-385 (1995).
  * (49) A. Ramani, B. Grammaticos and E. Caurier, Fractal potentials from energy levels, Phys. Rev. E 51, 6323 (1995).
  * (50) B.P. van Zyl and D.A. Hutchinson, Riemann zeros, prime numbers, and fractal potentials, Phys. Rev. E 67, 066211 (2003).
  * (51) S. Lloyd, G. De Palma, C. Gokler, B. Kiani, Z. Liu, M. Marvian, F. Tennie, T. Palmer Quantum algorithm for nonlinear differential equations, https://arxiv.org/abs/2011.06571.
  * (52) G. Gori and A. Trombettoni, J. Stat. Mech. P10021 (2011).
  * (53) M.L. Stein, S.M. Ulam, M.B. Wells, A Visual Display of Some Properties of the Distribution of Primes, American Mathematical Monthly, Mathematical Association of America, 71 (5): 516–520, (1964); M.L. Stein, S.M. Ulam, An Observation on the Distribution of Primes, American Mathematical Monthly, Mathematical Association of America, 74 (1) (1967).


L PREPRINT - To appear at VLSI-SoC 20244.5cm,1cm1.001.8

# In-Memory Mirroring: Cloning Without Reading

Simranjeet Singh1, Ankit Bende3, Chandan Kumar Jha4, Vikas Rana3,
Rolf Drechsler45, Sachin Patkar1, Farhad Merchant2
1IIT Bombay, India, 3Forschungszentrum Jülich GmbH, Germany,
4University of Bremen, Germany, 5DFKI GmbH, Germany, 2Newcastle University, UK
{simranjeet<EMAIL_ADDRESS>{a.bende<EMAIL_ADDRESS>
{chajha<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In-memory computing (IMC) has gained significant attention recently as it
attempts to reduce the impact of memory bottlenecks. Numerous schemes for
digital IMC are presented in the literature, focusing on logic operations.
Often, an application’s description has data dependencies that must be
resolved. Contemporary IMC architectures perform read followed by write
operations for this purpose, which results in performance and energy
penalties. To solve this fundamental problem, this paper presents in-memory
mirroring (IMM). IMM eliminates the need for read and write-back steps, thus
avoiding energy and performance penalties. Instead, we perform data movement
within memory, involving row-wise and column-wise data transfers.
Additionally, the IMM scheme enables parallel cloning of entire row (word)
with a complexity of $\mathcal{O}(1)$. Moreover, we analyzed the energy
consumption of the proposed technique on an RRAM crossbar with an
experimentally validated JART VCM v1b model. The IMM increases energy
efficiency and shows 2$\times$ performance improvement compared to
conventional data movement methods.

###### Index Terms:

RRAM, cloning, data dependency, energy efficiency, performance

##  I Introduction

The gap between the processing unit and memory leads to speed limitations
known as the memory wall. This challenge is addressed by processing data
within the memory and has emerged as a solution to alleviate memory bottleneck
issues [1]. One solution is to design the logic-in-memory (LiM). The
fundamental approach in LiM involves storing input logical states in memory
cells, with the computed output remaining in memory as a logical state.
Various memory technologies, including resistive random access memory (RRAM),
phase change memory (PCM), and spin-transfer torque magnetic random access
memory (STT-RAM), have been utilized to implement LiM.

Among these technologies, RRAM stands out as a contender for LiM, where
logical states are represented by the resistive state of the device, enabling
computation within the memory [2]. Several schemes of LiM using RRAM devices
have been demonstrated, such as MAGIC [3], IMPLY [4], FELIX [5], and Majority
[6], and so on [7]. Fig. 1(a) shows the schematic to implement the MAGIC OR
gate in the crossbar given in Fig. 1(b). Furthermore, experimental
demonstrations of some schemes have been conducted, validating the schemes [8,
9, 10].

Figure 1: (a) schematic for implementing the OR operation within the crossbar
architecture, utilizing three memristors. Two memristors are designated as
inputs, while the third is output storage. (b) The crossbar architecture
demonstrates the parallel execution of the same operation. (c) The challenge
of data dependency and proposes a solution by transferring data between
devices within rows and/or columns.

Various architectures have been proposed to map the logic on the crossbar to
compute serially and in parallel. Considering the area and latency constraint,
parallel mapping has been proposed, such as CONTRA [11] and SIMPLE [12]. These
schemes allow the mapping of the logic function in parallel, where both the
rows are columns considered. However, data dependencies arise in many cases,
particularly when the operations are performed in multiple columns. Fig. 1(c)
presents a scenario where three operations need to be performed, with
operation T dependent on data from P and Q (left code snippet). Currently,
these dependencies are handled by copying the data from the current cell to
the required cell, which either requires a read and write-back cycle [12] or
two complement operations [13], thereby resulting in increasing the overall
energy and latency of the computation.

This paper proposes an in-memory mirroring (IMM) technique to mitigate data
dependency by facilitating data cloning within the memory, thereby eliminating
the need for energy-intensive read and write-back operations. Unlike previous
approaches, inspired by the RowClone methods for DRAM [14], IMM operates
directly within the crossbar memory and does not require a read cycle,
improving the overall computation latency. Furthermore, IMM introduces the
capability for parallel cloning of entire rows with a one-cycle latency,
further enhancing its efficiency and scalability. To the best of our
knowledge, our paper represents the first pioneering demonstration of IMM
using an experimentally validated device model. The following are the
contributions of this paper:

  * •

Concept of cloning: bit cloning and word cloning.

  * •

Simulation analysis and validation using JART VCM v1b [15] SPICE model aims to
demonstrate the cloning data in rows, columns, and in parallel.

  * •

Finally, energy and latency calculations during the cloning operation are
conducted, and the results are compared with those found in the literature.

##  II Background and Related Work

###  II-A Memristive Devices

Memristive devices have emerged as a significant advancement in non-volatile
memory technology. Initially proposed as a concept by Leon Chua in 1971 [16],
memristive devices have gained prominence due to their unique ability to store
data by modulating resistance states [17]. One such device is RRAM, where
resistance modulation is achieved by applying a voltage across these device
terminals. In response, the resistance of the devices changes based on the
magnitude and direction of the current flow. Typically, these memristive
devices can be interconnected to form a crossbar structure. However, issues
related to forming and sneak-path currents can arise when individual
memristive devices are connected without a CMOS transistor in series. To
mitigate these concerns, memristive devices are fabricated with a CMOS
transistor in series, resulting in what is known as a 1T1R cell.

A memristive 1T1R cell possesses at least two distinct states: high resistive
state (HRS) and low resistive state (LRS) that are mapped to Boolean logic ‘0’
and ‘1’ for LiM implementation. To simulate the characteristics of RRAM cells,
several models have been introduced in the literature for characterization at
the SPICE level [18]. Among all the models, JART VCM v1b is particularly
noteworthy as an open-source model that is based on experimental data from
devices fabricated at Forschungszentrum Jülich GmbH, Germany [15]. Moreover,
the logic gate using the MAGIC design style has been experimentally validated,
resembling the device from the JART VCM 1b model [9]. So, in this study, JART
VCM v1b has been used to conceptualize and conduct simulation analyses.

###  II-B Related Work

Previous attempts to handle the energy and latency during data dependency for
LiM have been focused on synthesizing the logic function to reduce the number
of copy operations [12]. However, the problem remains the same: computation
still requires some copy operations that are expensive in energy and latency.
Another approach that has been recently used is performing the two-time
complement operation to copy within the memory [13]. Even though this scheme
still does not require a read cycle, the copy operation needs two cycles,
leading to latency and energy inefficiency. Another approach for copying using
the IMPLY logic style has been demonstrated with passive devices, requiring an
extra $R_{s}$ resistor and an additional isolation voltage. Adding $R_{s}$ and
addressing the sneak path problem in the passive crossbar makes this method
impractical in real crossbar implementations [19].

Although previous literature provides limited evidence of copy operations,
typically performed using four devices in series [20] or a passive devices, a
comprehensive analysis of this approach is lacking. To the best of our
knowledge, our paper represents the first pioneering demonstration of IMM
using an experimentally validated device model.

##  III Operating Principle of Cloning

Figure 2: (a) RRAM schematic for cloning. (b) the approximate equivalent
circuit.

TABLE I: Parameters (JART)

Params | Value
---|---
LRS ($R_{On}$) | $\approx 3.5-4.5K$\mathrm{\SIUnitSymbolOhm}$$
HRS ($R_{Off}$) | $\approx 65-70K$\mathrm{\SIUnitSymbolOhm}$$
$V_{Set}$ | 1V
$V_{Reset}$ |  $>$2.0V
$V_{Read}$ | 0.5V
$V_{C}$ | 1.5V
$V_{g}$ | 2.5V

Figure 3: Different configurations of crossbar architectures. In (a), the
vertical crossbar layout is presented, wherein the gates of transistors are
connected vertically. (b) Bit-cloning in the vertical crossbar. (c) Horizontal
crossbar, characterized by horizontally connected transistor gates. (d) Bit-
cloning in horizontal crossbar

The IMM process utilizes just two memristors for cloning; one holds the data
to be cloned, while the second is the target for cloning. Initially, all
devices are considered to be in the HRS state. Fig. 2(a) shows the schematic
for one-bit cloning, where two cells named Cell A and Cell B have been used.
Cell A contains the data to be cloned into Cell B, which begins in the HRS
state. An equivalent representation of Fig. 2(a) is shown in Fig 2(b) using
the simple resistors. The resistance of Cell A is marked as $R_{A}$;
similarly, the resistance of Cell B is marked as $R_{B}$. Two possible values
of $R_{A}$ and $R_{B}$ could be either HRS or LRS.

In the cloning operation, a positive voltage $V_{C}$ is applied across Cell B,
while Cell A is connected to the ground. Throughout this process, the gates of
both transistors are fully open, and devices sharing the common line are kept
open ($r_{0}$). This establishes a pathway between Cells A and B, where
$R_{A}$ and $R_{B}$ are connected in series. The parameters list used for the
analysis is shown in Table I. This creates a potential drop at $r_{0}$, which
can be calculated according to the Equation 1. The cloning voltage ($V_{C}$)
is chosen to be slightly greater than the Set threshold voltage ($V_{Set}$) of
the memristive cell. In this case, 1.5V as $V_{C}$ has been chosen for a
successful cloning operation.

$V_{r0}=\frac{R_{A}}{(R_{A}+R_{B})}\times V_{C}$ (1)

Based on the values of $R_{A}$ and $R_{B}$, there are two scenarios to
consider: (1) when the input data ($R_{A}$) is logic ‘0’ (HRS), and (2) when
the input data ($R_{A}$) is in LRS or logic ‘1’. The IMM technique allows for
a change of the state of $R_{B}$ according to the state of $R_{A}$.

###  III-A Case 1: Cloning Logic ‘1’

In this case, Cell A contains logic ‘1’, which needs to be cloned in Cell B
and is initialized to logic ‘0’ (HRS). When the $V_{C}$ is applied, the
$V_{r0}$, according to Equation 1, becomes very less because the
$R_{A}<<R_{B}$. As the $(V_{C}-V_{r0})\approx V_{C}$ is greater than the Set
voltage ($>V_{Set}$), it generates a sufficient voltage across Cell B,
enabling it to transition from HRS to LRS. Cell B will switch from HRS to LRS
in accordance with the data in Cell A, eventually cloning the Cell A data into
Cell B. Due to the high reset-to-set ratio ($\approx 2$) in this model, Cell A
will retain its original state.

###  III-B Case 2: Cloning Logic ‘0’

In this scenario, Cell A is in the logic ‘0’, and the target cell (Cell B) is
already in the HRS state. According to Equation 1, the voltage across the row
will be evenly distributed ($R_{A}=R_{B}$), and voltage at $r_{0}$ will be
$\approx V_{C}/2$. The voltage across Cell B, $(V_{C}-V_{r0})\approx V_{C}/2$
is not sufficient to switch the state ($<V_{Set}$). Thus, Cell B will maintain
its original state of HRS, which is the same as the state of Cell A.

##  IV The Proposed Methodology

RRAM often adopts a crossbar structure, which is known for its ability to
facilitate dense memory. In its simplest form, the array consists of
horizontal and vertical lines, where each RRAM cell is connected at each
junction. There are multiple ways to connect the RRAM cell at the junction.
Fig. 3 shows the vertical and horizontal crossbar structure for $m\times n$
(rows $\times$ columns) size. In a vertical crossbar structure, as shown in
3(a), the vertical lines are connected to the electrode of the device, and
horizontal lines are connected to the transistor source. The gate of all the
transistors is connected horizontally. On the other hand, in the horizontal
crossbar, as shown in Fig. 3(d), horizontal lines are connected to the
electrode of the RRAM cell while the vertical lines are connected to a source
of the transistors. Moreover, the gate of transistors is shorted horizontally.
An appropriate voltage at horizontal and vertical lines is applied to write (0
or 1) and read an individual cell in the crossbar. In Fig. 3, $V_{r,x}$ and
$V_{c,y}$ represent the voltage at row and column lines, respectively, where
$\rm|0\leq x<m|$ and $|0\leq y<n|$. $V_{s,z}$ is the gate switch voltage,
which is given as $|0\leq z<n|$ for vertical and $|0\leq z<m|$ for horizontal
crossbar.

In this work, the data is copied from one cell to another without performing
the read operation called cloning or mirroring. Initialization of both input
and output follows a standard memory write operation procedure, and the data
cloning process aligns closely with this write operation method. To integrate
a cloning operation within a crossbar array, two requirements must be
fulfilled: the structure of the crossbar and the connections of the memristive
cells configured within the array as shown in 3. Additionally, the logical
state of the memristive cell should be represented as resistance. Fig. 3 shows
the memristive crossbar structure with the necessary connections. While the
crossbar architecture allows for various other connection configurations, this
study focuses on demonstrating cloning within the structures depicted in both
Fig. 3(a) and Fig. 3(d).

Figure 4: (a) 3x3 crossbar array structure sketch. The gray arrow exemplifies
the voltage source. The colored circle at the junction represents different
memristors’ states. (b) Method of bit cloning in the same row, where the data
is marked as “A,” which will be moved according to the representation of the
green arrow. (c) Row-wise bit operations and the dotted blocks show the
unselected rows and columns. (d) Column-wise bit operation where only one-bit
value will be moved is marked in the green arrow. (e) Selected voltage source
and devices to perform the column-wise bit cloning. (f) Representation of full
column movement where the first complete row word will move to the third row
in parallel. (g) Selection of the required cell to perform word cloning. (h)
final state after performing all operations from (a) to (g) in a sequence

The vertical crossbar structure has a connection that is similar to the
connection depicted in Fig. 2(a) for bit cloning. The $V_{C}$ is applied to
the vertical lines connected to the electrodes of the memristors. For
instance, to execute the clone operation on the first two devices in a row,
$V_{C}$ is applied at $V_{c,1}$ while ground is applied at $V_{c,0}$. Gate
voltages $V_{s,0}$ and $V_{s,1}$ are applied to open both transistors ($>$2V
in this case). The first row ($V_{r,0}$) remains floating, facilitating
cloning as illustrated in Fig. 2(b), effectively transferring data from the
first device to the second. Similarly, voltages can be applied to rows,
columns, and gates of a horizontal crossbar, as depicted in Fig. 3(d), to
execute the cloning operation. Fig. 3(c) illustrates the implementation of the
bit cloning operation in the horizontal crossbar. It is noteworthy that the
operation conducted on the row-wise vertical crossbar resembles the operation
in the horizontal crossbar for the column due to crossbar connections. The
voltage sequence in various configurations enables data to be cloned bit-wise
and column-wise, and even the entire word can be cloned to another word.
Subsequently, we delve into the specifics of each operation. It is important
to note that we exclusively focus on the vertical crossbar as similar
operations can be performed on the horizontal crossbar.

###  IV-A Bit Cloning

In bit cloning, a single bit of data is moved either within the same row or
column, although it can be transferred to any location within the same row or
column. Row-wise and column-wise operations require distinct voltage schemes.
A $3\times 3$ crossbar structure elucidates the cloning methodology shown in
Fig. 4. The device in operation is highlighted using a solid line, while the
dashed line indicates the unselected devices for that specific operation. Fig.
4(a) presents the states of devices in a 3x3 crossbar, where ‘A’ represents
the LRS cell while all other cells are in HRS.

####  IV-A1 Row-Wise

In row-wise bit operation, ‘A’ has to be moved within the same row, as
depicted in Fig. 4(b). The voltage applied to the device follows the
configuration shown in Fig. 3(b), selecting the first two devices connected in
$r,0$. The gates of selected devices are connected to $V_{s,(0,1)}=V_{g}$
while other devices are deselected by applying 0V to their gates. During the
cloning phase, $V_{C}$ is applied at $V_{c,1}$ and $V_{c,0}$ is connected to
GND. The $r,0$ line remains floating, while other row lines are connected to a
voltage, $V_{r,x}=V_{C}/2$, which is due to shared $V_{s,z}$, where $1\leq
x<m$ and $0\leq z<2$. This results in proper device selection, which is shown
in Fig. 4(c), and clone ‘A’ to the desired cell. It’s important to note that
$V_{C}$ is applied across the output device during the row-wise cloning phase.

####  IV-A2 Column-Wise

Similar to row-wise bit cloning, column-wise bit cloning allows data to be
cloned within the column, requiring a distinct voltage configuration in the
opposite direction compared to row-wise bit cloning. Fig. 4(d) displays the
current state of devices after bit-wise cloning and the subsequent operation
with the green arrow. Fig. 4(e) shows the selected and unselected cells for
operation. In column-wise cloning, a single gate line is shared among the
devices in the column, with the commonly shared line being a row line rather
than a column line, as in row-wise bit cloning. The required voltages are
applied to the column side. To select the cell as shown in Fig. 4(d),
$V_{s,0}$ is connected to $V_{g}$, while all other gates are connected to 0V.
During the cloning phase, $V_{r,0}$ is connected to $V_{C}$, and $V_{r,1}$ is
connected to the ground, while all other row voltages are connected to
$V_{C}/2$. The column-wise operation requires $V_{C}$ at the input device,
which creates a positive voltage drop at the device electrode, resulting in
state change for the output device. The applied voltage terminal is opposite
to the operation during row-wise cloning, where the $V_{C}$ is applied at the
output device.

Figure 5: (a) 1T1R cell schematic, (b) material stacks of memristor, (c) I-V
characteristics for 100 cycles Figure 6: (a) Schematic for bit-wise cloning in
the same row. In the schematic, we have four voltage sources, $V_{c,0}$,
$V_{c,1}$, $V_{r,0}$, $V_{r,1}$, and currents in the memristors are marked in
colors. (b) The simulation results’ waveform shows each cycle marked on the
top of the graphs. The last Read cycle shows the state of both devices. (c)
Column-wise bit operation. The voltage sources are at $r_{0}$ and $r_{1}$
along with $c_{0}$ instead of $c_{0}$ and $c_{1}$. (d) Waveform during the
column-wise bit operation.

###  IV-B Word Cloning

As in a vertical crossbar, the gates are shared vertically (refer Fig. 3(a));
it’s possible to do the operation in parallel by opening the gate of all the
lines connected vertically, allowing for the complete row to be cloned to
another row. As depicted in Fig. 4(f), the example involves moving the first
row to the last row (marked by the green arrow). The first Row contains two
‘A’ cells. For word cloning operation, $V_{s,z}$ is connected to $V_{g}$,
where $0\leq z<n$, and $V_{r,0}$ is connected to $V_{C}$, $V_{r,1}$ is
connected to ground, while $V_{c,x}$ remains floating, where $0\leq x<n$. The
unselected rows are connected to $V_{C}/2$. Fig. 4(g) depicts the selected and
unselected devices after applying the specified voltages across the row and
column lines. This allows the complete row to be moved to another row, as each
clone operation can be performed in parallel with a complexity of one cycle
only. The operation is similar to the column-wise operation, where all column
operations happen simultaneously. Fig. 4(h) illustrates the final state after
all operations.

All operations are depicted with respect to the vertical crossbar structure.
Nevertheless, similar operations can also be conducted on the horizontal
crossbar. Additionally, due to the crossbar structure, the operations
interchange between row-wise and column-wise. Furthermore, in the vertical
crossbar, word cloning conducted row-wise will transition to column-wise word
cloning. The voltage required for the basic clone operation will remain the
same.

##  V Results

This section unveils the outcomes derived from SPICE level simulation using
the Cadence spectre. The JART VCM v1b model has been used as an RRAM and the
gpdk 45nm technology node for CMOS integration. This section also provides
insights into the energy consumption associated with cloning operations.

###  V-A 1T1R RRAM Switching Characteristics

The 1T1R cell design comprises a single memristor and one NMOS transistor,
forming the 1T1R structure. Fig. 5(a) illustrates the cell design alongside
the equivalent stack of the memristor depicted in Fig. 5(b). The memristor
model utilized in this investigation is experimentally validated and consists
of a Pt/Ti/TiOx/HfO2/Pt material stack known for its favorable electroforming
voltage and thermal stability. The I-V characteristics of the 1T1R cell are
depicted in Fig. 5(c), which shows Set and Reset voltages marked with the red
lines, with the Set voltage approximately 1V, and the Reset voltage
approximately 2V. Any voltage between the Set and Reset voltages can be
employed for the Read operation, with 0.5V utilized in this study to read the
device state. Throughout the I-V characteristics, the gate of the transistors
is maintained at 2.5V.

###  V-B Cloning Implementation

The schematic depicting row-wise cloning in the vertical crossbar structure is
presented in Fig. 6(a). Initially, all devices are set to HRS by default. To
validate the cloning operation, $d_{0}$ is initialized to LRS/HRS by applying
the necessary voltage at $V_{c,0}$. Fig. 6(b) has the waveform applied to
$V_{c,0}$ and $V_{c,1}$, along with the current flowing through devices
$d_{0}$ and $d_{1}$, denoted as $I_{d0}$ and $I_{d1}$, respectively. A Read
pulse of 0.5V is initially applied across both devices to ascertain their
current state. Subsequently, a Set voltage is applied to $V_{c,0}$ to
transition device $d_{0}$ to LRS, as indicated in the subsequent read cycle.
The ‘Mov’ pulse marked in Fig. 6(b) signifies the clone operation pulse.
During the clone operation, $V_{c,0}=0V/GND$ and $V_{c,1}=V_{C}$ are applied,
while $r_{0}$ remains floating. The final read operation verifies the state of
both devices, confirming that both are in LRS, thus validating the clone
operation.

Fig. 6(c) shows the simulated schematic for column-wise bit cloning. Similar
to row-wise cloning, all devices are initially in HRS. However, the voltage
scheme differs due to the crossbar connection. After Set and Read pulses, the
clone operation is executed by applying $V_{r,0}=V_{C}$ while $V_{r,1}=0V$.
The column line $V_{c,0}$ remains floating during the operation. The final
Read cycle confirms the successful cloning of $d_{0}$ data to $d_{1}$, as
shown in Fig. 6(d).

Finally, word cloning on a 2x2 crossbar structure is depicted in Fig. 7.
Similar to column-wise bit cloning, multiple columns share the same gate and
row lines in the vertical crossbar, enabling parallel data cloning. As shown
in Fig. 7(a), the same $V_{r,0}$ is applied to devices $d_{0}$ and $d_{2}$,
while similarly, $V_{r,1}$ is applied to devices $d_{1}$ and $d_{3}$. Since
$V_{s,0}$ and $V_{s,1}$ are shared for devices connected in $r_{0}$ and
$r_{1}$, respectively, both column lines $c_{0}$ and $c_{1}$ are kept floating
during the ‘Mov’ cycle. Fig. 7(b) shows the waveforms for performing word
cloning. Devices $d_{0}$ and $d_{1}$ are programmed to logic ‘1’ and logic
‘0’, respectively. The state of $d_{0}$ and $d_{1}$ after the clone cycle
(Mov) can be observed in the final Read operation, reflecting the transfer of
$d_{0}$ and $d_{1}$ states to $d_{2}$ and $d_{3}$, respectively.

Figure 7: (a) Schematic for word cloning, showing 2x2 crossbar, where the data in $d_{0}$ and $d_{1}$ will be cloned to $d_{2}$ and $d_{3}$, respectively. The current flowing from each device is marked in colors. (b) Waveform for the cloning “10” TABLE II: Energy consumption for cloning Device operations | Cloning
---|---
Operation |  Voltage V |  Energy (pJ) | Operation |  Voltage V |  Energy (pJ)
Reset | 2.25 | 15.54 | Bit (1) | 1.5 | 9.52
Set | 1.5 | 20.17 | Bit (0) | 1.5 | 0.71
Read (0 & 1) | 0.5 | 3.1 | Word (2-bit) | 1.5 | 11.28

###  V-C Energy and Latency Calculations

Comparing energy consumption and latency of existing methods with the IMM
approach is essential for assessing efficiency. Table II outlines energy usage
during device operations such as Set, Reset, Read, and cloning, classified as
bit and word cloning. The energy is obtained by multiplying the voltage
waveforms with the sensed current and then integrating the product over the
measurement time as per $\int_{0}^{t}v(t)\times i(t)\,dt$, where $t$ is the
pulse time. In existing computing, copying operations typically require two
cycles: read and writeback, consuming approximately 18 pJ and 23 pJ for
copying logic ‘0’ and logic ‘1’, respectively, in the worst case. In terms of
latency, the literature shows the two cycles for copying; in [11], one for
reading and another for writeback, and in [10], two NOT operations to copy. In
contrast, the proposed IMM scheme enables data cloning within the memory in
one cycle, requiring around 10 (9.52 + 0.71) pJ for bit cloning. An average
2-bit word cloning consumes only 11.28 pJ of energy. The proposed scheme
reduces overall energy consumption by the sum of the energy expended during a
read operation and the energy consumed by the peripheral during that
operation. This reduction is particularly significant in large-scale
applications. Additionally, it achieves a 2$\times$ improvement in latency.

##  VI Discussion

This study demonstrates a technique for cloning data within memory without
reading. Table II shows that bit-wise (‘0’ & ‘1’) cloning consumes
approximately 10.2 pJ, as the output cell is in a HRS, limiting switching
current and reducing energy consumption. For 2-bit word cloning, the average
energy is dominated by the “11” combination at around 22 pJ, while “00”
consumes 0.7 pJ, and “01 & 10” consumes 11.11 pJ. These energy values are
based on the operational voltage, which can be adjusted for optimization.
However, it is assumed that all devices are in an HRS, similar to the logic
operation implementation. If the cell has been previously utilized, it must be
switched to HRS before the cloning operation, necessitating an additional
cycle. This procedure is similar to handling a reused cell and initializing
the output cell to HRS. For output devices in use or unknown states,
dependencies can be verified at the compiler level and initialized with the
output device for logic operations, like regular memory write operations.
Since the voltage requirements are compatible with other logic operations, the
area needed for the control circuit for cloning will remain the same.

## Conclusion

This paper introduced the concept of IMM in RRAM memory crossbars, enabling
data cloning without reading the state within a single cycle. IMM facilitates
efficient data cloning within the memory, eliminating the necessity for read
and write-back cycles and resulting in substantial energy savings. Moreover,
the scheme supports bit-wise data movement in both columns and rows while
enabling parallel cloning of entire columns with the complexity of a single
cycle. The effectiveness of the IMM concept has been demonstrated through
SPICE-level simulation analysis with an experimentally validated RRAM model.
Furthermore, we have thoroughly examined the energy consumption and latency
associated with our proposed technique. The IMM scheme exhibits energy
efficiency and is 2$\times$ faster than the existing method of copying data in
the RRAM crossbar. Moving forward, we plan to validate the proposed scheme
experimentally using a fabricated RRAM crossbar.

## Acknowledgments

This work was supported in part by the Federal Ministry of Education and
Research (BMBF, Germany) in the project NEUROTEC II under Project 16ME0398K,
Project 16ME0399, German Research Foundation (DFG) within the Project PLiM (DR
287/35-2) and through Dr. Suhas Pai Donation Fund at IIT Bombay.

## References

  * [1] A. Sebastian _et al._ , “Memory devices and applications for in-memory computing,” _Nature nanotechnology_ , vol. 15, no. 7, pp. 529–544, 2020.
  * [2] R. Waser _et al._ , “Redox‐based resistive switching memories – nanoionic mechanisms, prospects, and challenges,” _Advanced Materials_ , vol. 21, pp. 2632–2663, 07 2009.
  * [3] S. Kvatinsky _et al._ , “MAGIC—Memristor-Aided Logic,” _IEEE TCAS-II_ , vol. 61, no. 11, pp. 895–899, Nov. 2014.
  * [4] S. Kvatinsky _et al._ , “Memristor-based material implication (IMPLY) logic: Design principles and methodologies,” _IEEE TVLSI_ , vol. 22, no. 10, pp. 2054–2066, 2013.
  * [5] S. Gupta _et al._ , “Felix: Fast and energy-efficient logic in memory,” in _2018 IEEE/ACM ICCAD_. IEEE, 2018, pp. 1–7.
  * [6] A. Deb _et al._ , “Automated Equivalence Checking Method for Majority based In-Memory Computing on ReRAM Crossbars,” in _2023 ASP-DAC_ , Jan. 2023, pp. 19–25.
  * [7] S. Singh _et al._ , “Should We Even Optimize for Execution Energy? Rethinking Mapping for MAGIC Design Style,” _IEEE Embedded Systems Letters_ , vol. 15, no. 4, pp. 230–233, 2023.
  * [8] B. Hoffer _et al._ , “Experimental demonstration of memristor-aided logic (MAGIC) using valence change memory (VCM),” _IEEE TED_ , vol. 67, no. 8, pp. 3115–3122, 2020.
  * [9] A. Bende _et al._ , “Experimental Validation of Memristor-Aided Logic Using 1T1R TaOx RRAM Crossbar Array,” in _VLSID_ , 2024, pp. 565–570.
  * [10] H. Padberg _et al._ , “Experimental Demonstration of Non-Stateful In-Memory Logic With 1T1R OxRAM Valence Change Mechanism Memristors,” _IEEE TCAS II_ , vol. 71, no. 1, pp. 395–399, 2024.
  * [11] D. Bhattacharjee _et al._ , “Contra: Area-constrained technology mapping framework for memristive memory processing unit,” in _2020 IEEE/ACM ICCAD_ , 2020, pp. 1–9.
  * [12] R. Ben Hur _et al._ , “Simple magic: Synthesis and in-memory Mapping of logic execution for memristor-aided logic,” in _2017 IEEE/ACM ICCAD_ , 2017, pp. 225–232.
  * [13] B. Perach _et al._ , “Understanding Bulk-Bitwise Processing In-Memory Through Database Analytics,” _IEEE TETC_ , vol. 12, no. 1, p. 7–22, Jan. 2024.
  * [14] V. Seshadri _et al._ , “RowClone: Fast and energy-efficient in-DRAM bulk data copy and initialization,” in _2013 46th Annual IEEE/ACM MICRO_ , 2013, pp. 185–197.
  * [15] C. Bengel _et al._ , “Variability-aware modeling of filamentary oxide-based bipolar resistive switching cells using SPICE level compact models,” _IEEE TSCAS I_ , vol. 67, no. 12, pp. 4618–4630, 2020.
  * [16] L. Chua, “Memristor-The missing circuit elemet,” _IEEE Transactions on Circuit Theory_ , vol. 18, no. 5, pp. 507–519, 1971.
  * [17] D. Strukov _et al._ , “The missing memristor found,” _Nature_ , vol. 453, pp. 80–3, 06 2008.
  * [18] F. Staudigl _et al._ , “A Survey of Neuromorphic Computing-in-Memory: Architectures, Simulators, and Security,” _DATE_ , vol. 39, no. 2, pp. 90–99, 2022.
  * [19] L. Xie _et al._ , “Fast boolean logic mapped on memristor crossbar,” in _2015 33rd IEEE International Conference on Computer Design (ICCD)_ , 2015, pp. 335–342.
  * [20] L. Luo _et al._ , “Reconfigurable stateful logic circuit with cu/cui/pt memristors for in-memory computing,” _IEEE TVLSI_ , vol. PP, pp. 1–13, 05 2024.