NonMarkovian Thermodynamic Computing: Thermodynamically
Efficient and Computation Universal
Kyle J. Ray, Gregory W. Wimsatt, Alexander B. Boyd, and James P. Crutchfield
Complexity Sciences Center
Physics Department
University of California at Davis
Davis, CA 95616

ABSTRACT:
Practical, useful computations are instantiated via physical
processes. Information must be stored and updated within a
system's configurations, whose energetics determine a
computation's cost. To describe thermodynamic and biological
information processing, a growing body of results embraces rate
equations as the underlying mechanics of computation. Strictly
applying these continuoustime stochastic Markov dynamics,
however, precludes a universe of natural computing. Within this
framework, operations as simple as a NOT gate, flipping a bit, and
swapping bits are inaccessible. We show that expanding the toolset
to continuoustime hidden Markov dynamics substantially removes
the constraints, by allowing information to be stored in a
system's latent states. We demonstrate this by simulating
computations that are impossible to implement without hidden
states. We design and analyze a thermodynamicallycostless bit
flip, providing a counterexample to rateequation modeling. We
generalize this to a costless Fredkin gate—a key operation in
reversible computing that is Turing complete (computational
universal). Going beyond rateequation dynamics is not only
possible, but necessary if stochastic thermodynamics is to become
part of the paradigm for physical information processing. The
increased analytical challenges are readily addressed with
recentlyintroduced spectral decomposition methods for
nondiagnonalizable dynamics.
Alexander B. Boyd, Kyle J. Ray, Gregory W. Wimsatt, and James P. Crutchfield,
“NonMarkovian Thermodynamic Computing: Thermodynamically
Efficient and Computation Universal”, Physical Review
Research 3:2 (2021) 023164.
doi:10.1103/PhysRevResearch.3.023164.
[pdf]
arxiv.org:2010.01152 [condmat.statmech].
Selected animations of continuoustime thermodynamicallyfree Fredkin gate:
See Supplemental Material at [URL will be inserted by publisher]
for a suite of animations that showcase the action of the proposed
Fredkin gate on the underlying state space.

Animation 1 (MPEG 4)
Particle ensemble undergoing the Fredkingate protocol, with
initial conditions drawn from the equilibrium distribution of the
storage potential. We see that the momentum the particles pick up
while traveling to the point acts as a memory, allowing us to
continue to control the disparate initial conditions
independently. Here, we easily see how the action of two
parabolic wells with differing characteristic frequencies allows
for 110 and 101 to swap places, while 100 and 111 complete a full
cycle, returning to their initial coordinates.

Animation 2 (MPEG 4)
(Left) Particle ensemble undergoing the Fredkingate protocol,
with initial conditions drawn from the equilibrium distribution of
the storage potential. Looking at the dynamics projected onto the
yz plane allows for a clear view of how the controlledswap
operation takes place in the computational subspace. The grey
points represent storage bits that are not exposed to the
computational potential. Note especially that the particles not
only end in the appropriate informational quadrant, but also their
initial distribution over that quadrant—which is a necessary
condition for the net thermodynamic work to vanish. (Right) An illustrative
animation of how a uniform distribution over y and z changes over
the protocol duration. Each colored square represents a uniform
distribution in the corresponding y,z quadrant, with z = 2 and
v_{x} = v_{y} = v_{z} = 0.

Animation 3 (MPEG 4)
Particle ensemble undergoing the Fredkingate protocol, with
initial conditions drawn from the equilibrium distribution of the
storage potential. The y' and z' phase spaces allows us to see the
most relevant projection of the rotation that takes place in the
full phase space. When the computational protocol turns on, the
particles associated with x > 0 stop rotating about local
storage well minima, and start rotation about the minima of
V^{comp}. Side by side, we clearly see a full period in
the z' subspace and only half a period in the y' subspace—as
required to perform the Fredkin gate.