Landauer machine
Pub. 2026 Aug 9In 1961 Roger Landauer argued that any logically irreversible computation must produce a minimum amount of heat. The argument at its most basic: consider a particle in one of two equivalent but distinct states called "0" and "1". If that particle is then forced to be in just the "0" state, effectively "erasing" or "zeroing" the particle, that operation reduces the particle's number of states by half, decreasing its entropy by $k \ln(2)$. The entropy of the universe must have increased by at least $k \ln(2)$ in kind. This transfer of entropy is envisioned by Landauer as a transfer of at least $k T \ln(2)$ joules of heat into the universe.
Let's put aside whether this is true or not in the general case. I want to make a model of a machine that does operate at this limit, what I'm calling a "Landauer machine".
There are many models out there of reversible computers: ones that generate no heat at all. There are fewer models of Landauer machines, but they do exist: bi-stable wells, brownian computers, atom-in-box models, etc. I like the atom-in-box models, because of its simplicity and obvious correctness. But I've never seen this model taken all the way to usable computation. So that's what I want to do here.
The model
The model described here is very simple, thermodynamics 101 stuff. It does computation on gas particles in containers by compressing and expanding them in various ways.
Some papers I've read hand-wave away some details of how a computer like this would work. You have to be careful though. For example, you can't just attach a random sensor to a gas container and use it to control what operations to perform, because that implies a form of computation, and you'd have to argue that that process is itself reversible.
So I'm deliberate in my choice of primitives:
- Bits are pairs of boxes, one that contains a single particle at high pressure and temperature, and one that contains a vacuum. Whether a bit denotes 0 or 1 depends on their orientation.
Red means high temperature, high pressure. Blue means vacuum.
I'm assuming the particle to be monoatomic, so there are no extra degrees of freedom to hide entropy in.
- Boxes can be separated and rejoined.
- The walls of the boxes can be rigid or movable as need be.
- Different parts of the computation can take place in different heat baths at different pressures as the situation demands. Boxes are transferred between computations with different heat bath requirements by physically moving them out of one and into another, which takes zero work.
- We can perform isothermal compression/expansion to a box in finite time. Or close enough to finite.
- Boxes can be connected by tubes. These tubes are assumed to have essentially zero volume, and so gas moves through them essentially instantly.
- We can use pistons that travel a pre-specified distance at a pre-specified schedule.
- If those pistons have to do work on its load to travel its distance, it can. If the load does work on the piston instead, that's also allowed, and that energy is stored. They're allowed to dynamically supply or receive however much is necessary to move its distance. However, they aren't able to dynamically choose whether to give or receive work, or to receive work in two different directions.
This last point is to prevent designs that are too carefree about how energy is absorbed from a thermodynamic process. For example, a design that relies on being able to extract energy from an adiabatic process between two boxes of unknown pressures. I'm not aware of any design that doesn't use some sort of ratcheting mechanism, which has thermodynamic implications. Etc.
Building blocks
NOT
The simplest example of a reversible operation is the identity operation, which is when you do nothing to a bit.
The second simplest example of a reversible operation is NOT:
This hopefully explains why we're representing bits this way. Dual-rail-like representations work better when conservation of matter is a concern.
SET / RST
The simplest example of an irreversible operation is RST:
This is a classic thermodynamics example. The dividing wall is removed between the two halves, doing a free expansion on the gas. Pressure halves, volume doubles, temperature remains the same. Then a piston isothermally compresses into the correct half, leaving behind a vacuum in the other. This compression performs $k T \ln(2)$ joules of work on the gas. But since we're keeping a constant temperature, the energy of our monoatomic gas is also constant, and so that $k T \ln(2)$ joules radiates off as heat, exactly as the Landauer limit predicts. The movements of these pistons are meant to be done very slowly to enable this.
Alternatively, the entropy of a particle in a box is
$$S = k \ln \left( V \left( \frac{4 \pi m U}{3 h^2} \right)^{3/2} \right) + \frac{5}{2}.$$
When the wall is removed, $V$ doubles, $U$ stays the same, so $\Delta S = k \ln(2)$. After the compression phase, $V$ halves again, $U$ stays the same because the compression is isothermal, so $\Delta S = -k \ln(2)$ again. The first entropy increase comes free, but then the second can't happen without transferring it somewhere else, here to the environment in the form of $T \Delta S$ units of heat.
This should look very familiar to anyone who's opened a thermodynamics textbook. But for our purposes we're going to depart from this a bit and use a slightly different construction. This alternate RST consumes the same amount of energy and generates the same amount of heat:
The inverted operation is SET, which sets the bit to 1:
The circuit symbols for SET and RST are arrows pointing right, which represents how these gates can only run in the left-to-right direction, because they're irreversible. In contrast to the NOT symbol X, which is horizontally symmetric and can be run in reverse.
An interesting direction not explored here is that theoretically, if you have bits from a known probaility distribution, you can RST them for less energy and heat. If your bits have value 1 with probability $p$ and 0 with probability $1-p$, a RST burns $-k T (p \ln(p) + (1-p) \ln(1-p))$. Maroney (2018) has some diagrams for this.
These 4 operations, identity NOT SET RST, fills out all $\mathbb{B}^\mathbb{B}$.
CNOT
$\mathbb{B}^2 \rightarrow \mathbb{B}$ operations aren't that interesting by themselves, since they always require unconditional erasure and heat. We're looking instead at operations where the output replaces one of the inputs.
The simplest nontrivial reversible operation of this kind is the CNOT, or Toffoli gate:
The output on the bottom tube is A XOR B. CNOT is reversible, since you can apply it again and get back the inputs: A XOR (A XOR B) = B.
The white fill on the control bit means that the NOT occur when A=1. Keeping with the SET/RST color scheme above, having a black fill would mean the NOT would occur when A=0.
The mechanism for this a bit fiddly. The idea is that a piston could push one of the boxes; if it's pressurized the box would move, and collapse if not. This can be used to select which routing tubes connect the input and output boxes. In order for the vacuum box to collapse correctly, this must be done in a vacuum environment, which is what that middle blue square is about. Don't worry about the red area for right now.
I'm a little worried about this setup. In any Landauer machine, you need to make sure you can't do A CNOT A, where the same bit is used for both input and control. Being able to do this would have implications. For example, you could use this technique to potentially RST a bit with 0 heat, using the property that A XOR A = 0. Luckily I think I'm okay. If this construction works how I think it should, the collapsing vaccum box in the A=1 case wouldn't get undone, which would cause problems down the line. But that reasoning seems shakey, so I'm not sure.
We're going to elide any more discussion of this subject, and we're not going to be using any self-controlling operations in the rest of this piece. Honestly, I'm not too worried about it. I'm mostly interested in the idea of a Landauer machine and what can be done with them. I'm confident that any problems can be worked out.
CSET / CRST
The corresponding 2-input irreversible operation is the controlled reset, CRST:
This is where the red area comes in. CRST does an isothermal compression, so needs a heat bath. The parallel tubes are insulated, but the merging tubes are not, allowing heat to flow freely.
The construction of this gates has the property that work is done, and therefore heat produced, only when A=1. When A=0, the output matches the input, so is reversible and no heat should be produced. In addition, heat is always produced when A=1, even if B=0 already.
Like with RST, there is an inverted version called CSET:
With these you can implement all $\mathbb{B}^2 \rightarrow \mathbb{B}$ logic gates. For completeness, here's half of the 16 binary logic gates (the rest can be made by adding a NOT to the end of the B line):
Fanout
Just because we have XOR and AND, doesn't mean we're in the clear. In classical logic NAND is universal, but not necessarily here. One of the reasons NAND is universal is due to wire fanout. Here's what fanout looks like in a Landauer computer:
In most discussions of reversible computers, there's an assumption that we have access to a large amount of known 0 bits that we can pull from at any time. Maybe these can be thought of as being generated in a reversible way, like boxes that package up naturally occurring vacuum and hi-temp gasses and transported to the computer with 0 work.
However, this is probably not actually the case. Almost certainly, in a truly realized Landauer machine, the most common practical way of generating a 0 would be to RST an unknown bit.
So fanout results in either memory usage or heat. Also, we can't just convert traditional logic circuit diagrams to their Landauer machine equivalents and expect them to operate at the Landauer limit.
3 input gates
The construction we're using, where the control bits connect tubes that route to the correct destination boxes, can extend to multiple control bits. It can even extend to mix-matched control bits!
At last, this is the reason for the strange control bit mechanism. It's to allow for multiple control bits. Each piston below pushes up, and the routing tubes raise when any of the boxes is pushing them. This uses $AB = 1 - ((1 - A) \, \text{OR} \, (1 - B))$.
If you don't like the movement of the boxes around the circuit, note that the box movement is set in stone for each circuit, so no decisions are being made. If you want, you can imagine more tubes and pistons that deterministically push the gas around in the correct order.
Full adder
Let's make a full adder!
There are reversible full adders out there:
Pretty cool, but not quite what I want.
In the left circuit an extra 0 bit is introduced, and a 3-bit input results in a 4-bit output. This means that every pair of bits we add together will result in another bit of memory getting trashed.
The right circuit is closer to what I want. The sum replaces B, evocative of how the intel 8080's ADD instruction always adds into an accumulator. And one of the workings bits was erased at the end, allowing this circuitry can be reused.
However, that RST is unconditional, which isn't ideal.
For the rest of this post I'm going to be counting SETs and RSTs. Each one consumes $k T \ln(2)$ energy and generates the same amount of heat. I'm going to define 1 unit of "waste heat" (1 WH) to be equal to $k T \ln(2)$ for brevity.
Take a look at the truth table for a full adder:
A B C | A' S' C'
--------------------
0 0 0 | 0 0 0
0 0 1 | 0 1 0 <--
0 1 0 | 0 1 0 <--
0 1 1 | 0 0 1
1 0 0 | 1 1 0
1 0 1 | 1 0 1 <--
1 1 0 | 1 0 1 <--
1 1 1 | 1 1 1
Pointers are towards the noninvertible lines. There are two pairs of inputs that result in the same output. Therefore, a good adder circuit for a Landauer machine would be generate 1WH for those noninvertable outputs, and 0 WH for the invertable ones.
This circuit fits the bill:
Despite having both a CSET and a CRST, only one can trigger on any addition. Also, if you supply random bits to A,B,C the SET/RST will will trigger 50% of the time, like suggested in the logic table above!
Okay, enough stalling, here's a full ripple carry adder:
This 4-bit adder is made up of 4 1-bit full adders chained together. The statistics from above continue to apply: this circuit can generate a max of 4 WH, and will do 7/16 = 0.44 WH per addition on average for random inputs.
This can be made better. Chaining 1-bit adders together is less heat-efficient than constructing larger adders from scratch. For example, here's a 2x2 bit adder:
This circuit will, at max, generate 1 WH per addition, with an average rate of 0.75 WH per two random inputs. This is better than the equivalent chained 1-bit adders, which will generate a max of 2 WH and an average of 1 WH per two random inputs.
This pattern keeps going. For a n-bit adder, you can construct the circuit to make at max 1 WH per addition, but the probability of one happening gets closer to 100% for two random inputs as n gets large.
In an actual Landauer machine, where the addition circuitry would be reused for each addition, there would have to be an extra RST at the start to zero out the carry bit, so for practical purposes 1 should be added to the above numbers.
If you make one giant n-bit adder all at once, without chaining smaller adders together, and have no need for carry bits, you can do this reversibly! This is breaks the pattern, because $(A, B) \rightarrow (A, A + B)$, without the carry bits, is reversible. So such a circuit should generate no heat.
Adder circuit depths get long, though. The traditional solution for reducing adder circuit latency is parallelism. You break up your adder circuit into full adder blocks that compute results for both C=0 and C=1 in parallel, which throw away the incorrect result when it gets the correct C. Needless to say this generates lots of heat. There's a tradeoff between parallelism of this kind and heat-efficiency.
Endothermic computation
There's an old response to Landauer's limit, I believe first stated by Bennett (1982). It goes something like this:
It may be true that logically and physically irreversible operations both increase entropy, and logically irreversible operations generate heat. But if you expand your idea of logic reversibility a little, you can relax the relationship between logical and physical reversibility.
An example given is erasing a random bit. You can't unerase a bit, because you can no longer know what the input was. But you can re-randomize it: just remove and re-insert the divider between the boxes! The boxes contain a single particle, which can only be in one of the two boxes when the divider comes back down.
The "relaxed" view of reversibility here is that erasing a random bit just moves $k \ln(2)$ entropy from the bit to the environment, which can be reversibly moved back.
Going further, you can run the RST gate backwards. Not only does the bit re-randomize, but also the energy and heat flow in the opposite direction.
Equivalently a RCRST would generate random bit if A=0 and the controls are all satisfied, and preserve the input if the controls aren't.
You can take any circuit, like the ones we've been talking about so far, and run them backwards. For example, if you run the addition circuit backwards with a given output, you will get back a random set of inputs that sum to the output.
You do have to be careful not to feed invalid inputs to the reverse addition circuit. If you feed A=0 S=1 D=1 into it (which is not one of the possible outputs of a full adder), a 1 will be fed into the RCRST and puts the computer into an illegal state.
Running computations in reverse has been studied to death, so I don't think I can contribute anything here.
What's most interesting for me is that a RRST absorbs heat! The general vibe around reversible computing is that it's the most efficient kind of computation, since it generates no heat. But the addition example above generates negative heat, so is even more efficient than a reversible addition!
There specific example above isn't that interesting by itself. More research should be done to find more interesting examples of this reverse, endothermic computing.
Monte carlo
I'm interested in what we can do with the energy gained from RRST. My intuition says that there's a limit to the amount of computation that can be done "for free" if you have a free 0 bit. If you commit to reversible computing, then there's no limit to the amount of computation that can be done. But if you're playing by the rules I've laid out above, where fanout isn't free, is the situation different? If we're given $n$ "free" 0-bits, what sort of things can we compute with them?
I have a very special place in my heart for monte carlo algorithms. So instead of running computations backwards, another option I want to try is to generate random bits and directly compute something.
For this post's finale, we're going to calculate $\pi$ endothermally, using the old circle-in-square rejection sampling trick. It's a simple algorithm that doesn't require many operations: generate two real numbers between 0 and 1 uniformly, square them, and add them. Then take the carry bit from the last addition, and add it to an accumulator. Repeat this $m$ times, and the expected value of the accumulator is $m(1 - \pi / 4)$.
To make things simple, say we have 24 "free" 0-bits: 8 for both random real numbers, and 8 for the accumulator.
Generating two random 8-bit numbers $x$ and $y$ using RRST absorbs 16 WH from the environment. This is going to be the fuel we'll use for the rest of the calculations. We'll interpret $x$ and $y$ as fixed point representations of $2^{-8} x$ and $2^{-8} y$.
Squaring would act like mulh, multiplying the 8-bit number by itself to produce a 16-bit number, and then returning the high 8-bits, only without the intermediate. By my calculations, such a circuit should burn 4 WH at worse, and ~0.71 WH on average.
We've gone over additions: the most optimal 8-bit adder with an output carry bit will generate 1 WH to clear the output carry bit. However, without any carry bits it would generate 0 WH! So here we'd make some custom circuitry that adds an 8-bit number to a 16-bit number for 0 WH, and use it on $x + (2^8 accumulator + y)$. This takes care of both additions!
To repeat the process, you can't zero out x and y, because that would burn all of our 16 WH. But we don't need to do that. RST followed by RRST burns 0 WH and re-randomizes the bits. And you're ready to go again!
I'm not taking into account a loop counter, since I don't know what to do when the counter reaches 0.
All in all, each loop burns ~$2 \cdot 0.71$ WH = 1.42 WH on average, so you can do ~11 iterations on average before you're no longer endothermic. With 11 iterations you will calculate a value of pi between [2.5, 4] 90% of the time, and between [2.9, 3.3] only 50% of the time, lol.
Increasing the bitcount helps. The WH for squaring n-bit numbers seems have a worst case of $\log_2(\sqrt{n})$ WH, and converges to an average of ~0.73 WH as n gets large. So expanding these circuits to, say, 32 bits would give you 45 iterations on average! But at the expense of massively increased circuitry complexity, because the adders and multipliers I'm assuming here have sizes that scale exponentially in n, I believe.
I really wanted to draw the circuit for these, but unfortunately the circuit diagram for one loop is far too large to see.
To answer the question at the top of this section, for branchless programs and large $n$ there seems to be no real limit to how much computation a Landauer machine could do. Most of the basic operations (addition, multiplication, etc) seem to burn O(1) WH. For small $n$ this is still an interesting question. For branchful programs, more investigation still needs to be done.