Non-Markovian momentum computing: Thermodynamically efficient and computation universal

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 continuous-time 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 two bits, and swapping bits are inaccessible. We show that expanding the toolset to continuous-time 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 thermodynamically costless bit flip, providing a counterexample to rate-equation modeling. We generalize this to a costless Fredkin gate—a key operation in reversible computing that is Turing complete (computation universal). Going beyond rate-equation dynamics is not only possible but also necessary if stochastic thermodynamics is to become part of the paradigm for physical information processing.

Figure 1

Particle ensemble undergoing the Fredkin gate protocol with zero coupling to the thermal reservoir. Snapshots of the state evolution are given at times $0,\tau /4,\tau /2,\text{and}\tau$, with the black arrows indicating forward time. Color encodes in which informational state each trial begins: gray: 000, 001, 010, 011; orange: 100; red: 101; blue: 110; green: 111. Additional details are available in the Appendix. Animations are available online [37].

Figure 2

Logical fidelity ($\text{successful}\text{trials}/\text{total}\text{trials}$) in the low-coupling Fredkin gate and the average net work required to implement it for different values of the thermal coupling constant $\lambda$, measured in units of $\pi \mu /\tau$. Computational bits refers to states that fall in the region $x>0$, where the computational potential is in effect.

Figure 3

Slice of the potential energy landscape $V(x,y,z)$ in the $y-z$ plane: (a) information-storing domain ($x=-x_0$) and (b) controlled-swap domain ($x=x_0$).

Figure 4

Particle ensemble initialized in equilibrium with $V^{\mathrm{store}}(x,y,z)$ undergoing the Fredkin gate protocol with zero coupling to the thermal reservoir. Each snapshot of the state evolution is separated by a time interval of $\tau /8$, with the black arrows indicating forward time. Color encodes in which informational state each trial begins. The 101 (red) and 110 (blue) states only oscillate by a quarter period in the time ($\tau /2$) it takes the 100 (yellow) and 111 (green) states to oscillate by a half cycle. As the 100 and 111 trials return to their initial positions, the 110 and 101 states approach their final positions: a half cycle from where they started (right). The states have been swapped. Animations available online [37].